Cách tìm hình tam giác bên trong biểu đồ?

Question

Đây là một bài tập trong Algorithm Design Manual.

Xét bài toán xác định xem một đồ thị vô hướng G được = (V, E) có chứa một hình tam giác hoặc chu kỳ dài 3.

(a) Hãy cho một O (| V |^3) để tìm một hình tam giác nếu có.

(b) Cải thiện thuật toán của bạn để chạy trong thời gian O (| V | · | E |). Bạn có thể giả định | V | ≤ | E |.

Quan sát rằng những giới hạn cho bạn thời gian để chuyển đổi giữa các kề ma trận và danh sách kề đại diện của G.

Đây là suy nghĩ của tôi:

(a) Nếu đồ thị được đưa ra như một danh sách kề, tôi có thể chuyển đổi danh sách thành ma trận bằng O (| V |^2). sau đó tôi làm:

for (int i = 0;i < n;i++) 
    for (int j = i+1;j < n;j++) 
    if (matrix[i][j] == 1) 
     for (int k = j+1;k < n;k++) 
     if (matrix[i][k] == 1 && matrix[j][k] == 1) 
      return true; 

Điều này sẽ cung cấp O (| V |^3) để kiểm tra tam giác.

(b) Trực quan đầu tiên của tôi là nếu biểu đồ được đưa ra dưới dạng danh sách kề, thì tôi sẽ thực hiện bfs. Bất cứ khi nào tìm thấy cạnh chéo, ví dụ: if y-x is a cross edge, thì tôi sẽ check whether parent[y] == parent[x], if true, then a triangle is found.

Bất cứ ai có thể cho tôi biết liệu suy nghĩ của tôi có chính xác hay không?

Cũng cho điều này (b), tôi không chắc chắn sự phức tạp của nó. Nếu nó là O (| V | + | E |), phải không?

Làm cách nào để thực hiện điều đó trong O (| V | * | E |)?

Answer 1

Một giải pháp khả thi O(|V||E|), là ý tưởng cùng của brute-force trong (a):

for each edge (u, v): 
    for each vertex w: 
    if (v, w) is an edge and (w, u) is an edge: 
      return true 
return false 

kiểm tra tất cả các cạnh và không tất cả các cặp đỉnh - với một đỉnh đó tạo thành một tam giác - đó là đủ thông tin để xác định xem cạnh và đỉnh có tạo thành một giải pháp khả thi hay không.

dụ Counter đến giải pháp BFS:

 A 
    /| \ 
    /| \ 
    B C D 
    | | | 
    | | | 
    F---G---H 
    |  | 
    --------- 
    (F, H) is also an edge 

Lưu ý rằng father[F] != father[G] != father[H], do đó thuật toán sẽ trả về false - tuy nhiên, (F, G, H) là một giải pháp khả thi!

Answer 2

Đây là những gì tôi nghĩ:

Giải pháp origianl BFS không đúng như đã nêu ở trên. Nhưng chúng ta có thể sửa đổi DFS. Gán số cho các nút được truy cập khi chúng ta truy cập từng đỉnh trong DFS. Bây giờ, nếu chúng ta đạt đến một đỉnh (trong câu hỏi tôi thấy các cạnh chéo, không có biểu đồ không bị gạch dưới), chúng ta kiểm tra danh sách kề của nó và giả sử một đỉnh được phát hiện (nhưng không được xử lý, không thể xảy ra). . Nếu chênh lệch là 2 thì có chu kỳ dài 3.

Answer 3

Tôi thực sự thích the matrix multiplication solution discussed in this blog post.

Hãy để a = ma trận kề

• Các adjacencies trong một * a (a2) ma trận nhân là số lượng đường dẫn 2-chiều dài
• Các adjacencies trong a2 * một ma trận nhân là số lượng Đường dẫn 3 chiều

Vấn đề là nhân ma trận chậm ... Tuy nhiên, bạn có thể sử dụng GPGPU để thực hiện nhân ma trận và có thể có giải pháp thực hiện trên kiến ​​trúc hiện đại bao gồm GPU.

Answer 4

Nếu bạn có ma trận kề, bạn có thể tìm hình tam giác bằng cách lấy bình phương ma trận và xem ma trận gốc và ma trận vuông có mục nhập khác 0 trong cùng một vị trí hay không.

Phép nhân bản ma trận ngây thơ cần có thời gian O(n^3), nhưng có các thuật toán phép nhân nhanh ma trận hoạt động tốt hơn. Một trong những thuật toán nổi tiếng nhất là thuật toán Coppersmith-Winograd, chạy trong thời gian O(n^2.4). Điều đó có nghĩa là thuật toán diễn ra như sau:

• Sử dụng O(V^2) thời gian để chuyển sang ma trận kề.
• Sử dụng O(V^2.4) thời gian để tính toán bình phương của ma trận kề.
• Sử dụng O(V^2) thời gian để kiểm tra ma trận cho các mục nhập khác không trùng khớp.
• Chỉ mục của hàng và cột nơi bạn tìm thấy trùng khớp các mục khác 0 trong (nếu có) cho bạn biết hai nút liên quan.
• Sử dụng O(V) thời gian để thu hẹp nút thứ ba chung cho cả hai nút đã biết.

Vì vậy, tổng thể mất O(V^2.4) thời gian; chính xác hơn nó mất tuy nhiên nhân ma trận dài mất. Bạn có thể tự động chuyển đổi giữa thuật toán này và thuật toán if-any-edge-end-have-a-common-neighbor that amit explains in their answer để cải thiện điều đó thành O(V min(V^1.4, E)).

Đây là paper that goes more in-depth into the problem.

Đó là loại gọn gàng như thế nào phụ thuộc vào lý thuyết-khám phá vấn đề này là. Nếu giả thuyết về nhân ma trận thực sự là bậc hai lần lượt là đúng, thì bạn sẽ nhận được một thời gian thực sự tốt đẹp ràng buộc của O(V^2) hoặc O(V^2 log(V)) hoặc một cái gì đó như thế. Nhưng nếu máy tính lượng tử hoạt động, chúng tôi sẽ có thể thực hiện even better than that (chẳng hạn như O(V^1.3))!