Làm thế nào để phát hiện nếu phá vỡ một cạnh sẽ làm cho một đồ thị rời rạc?

Question

Tôi có biểu đồ bắt đầu bằng một nút gốc, đơn. Các nút được thêm từng cái một vào biểu đồ. Tại thời điểm tạo nút, chúng phải được liên kết đến nút gốc hoặc đến một nút khác, bằng một cạnh duy nhất. Các cạnh cũng có thể được tạo và xóa (từng cái một, giữa hai nút bất kỳ). Các nút có thể bị xóa từng lần một. Tạo nút và cạnh, thao tác xóa có thể xảy ra theo bất kỳ thứ tự tùy ý nào. OK, vì vậy đây là câu hỏi của tôi: Khi một cạnh bị xóa, có thể xác định, trong thời gian không đổi (tức là với thuật toán O (1)), nếu làm điều này sẽ chia đồ thị thành hai đồ thị rời nhau? Nếu nó sẽ, sau đó mà các cạnh của cạnh sẽ nút gốc thuộc về?

Tôi sẵn sàng duy trì, trong giới hạn hợp lý, bất kỳ cấu trúc dữ liệu bổ sung nào có thể tạo thuận lợi cho việc phát sinh thông tin này.

Có thể không thể thực hiện điều đó trong O (1), nếu có bất kỳ gợi ý nào về văn học sẽ được đánh giá cao.

Chỉnh sửa: Biểu đồ là đồ thị được hướng.

Chỉnh sửa 2: OK, có thể tôi có thể hạn chế trường hợp xóa các cạnh khỏi nút gốc . [Chỉnh sửa 3: không, thực sự] Ngoài ra, không có vùng đất cạnh nào vào nút gốc.

Answer 1

Đây có phải là biểu đồ được chỉ dẫn không? Dưới đây giả định không bị gạch dưới.

Điều bạn đang tìm kiếm là liệu cạnh đã cho có là Bridge trong biểu đồ hay không. Tôi tin rằng điều này có thể được tìm thấy bằng cách sử dụng một traversal tìm kiếm các chu kỳ có chứa cạnh đó và sẽ là O (| V | + | E |).

O (1) quá nhiều để hỏi.

Bạn có thể thấy rằng việc tìm cách duy trì các thành phần được kết nối 2 cạnh trong biểu đồ động có thể hữu ích cho bạn.

Eppstein et al có một bài báo về vấn đề này: http://www.ics.uci.edu/~eppstein/pubs/EppGalIta-TR-93-20.pdf

mà có thể duy trì 2 cạnh các thành phần kết nối, trong một đồ thị của n nút nơi chèn cạnh và xóa bỏ được phép. Nó có thời gian O (sqrt (n)) cho mỗi lần cập nhật và thời gian O (log n) cho mỗi truy vấn.

Vì vậy, bất kỳ lúc nào bạn xóa, bạn có thể truy vấn trong O (logn) để xác định xem số thành phần kết nối 2 cạnh đã thay đổi chưa. Tôi cho rằng nó cũng có thể cho bạn biết thành phần nào là một nút cụ thể.

Bài viết này tổng quát hơn và áp dụng cho các vấn đề về đồ thị khác, không chỉ 2 thành phần được kết nối cạnh.

Tôi khuyên bạn nên tìm cầu và kết nối 2 cạnh năng động để giúp bạn bắt đầu.

Hy vọng điều đó sẽ hữu ích.

Answer 2

Để tăng tốc độ lên một chút so với giải pháp O (| V | + | E |) rõ ràng, bạn có thể giữ một cây bao trùm khá dễ dàng để cập nhật khi biểu đồ thay đổi.

Nếu cạnh không trong cây bao trùm sẽ bị xóa, thì biểu đồ không bị ngắt kết nối và không làm gì cả. Nếu một cạnh trong cây bao trùm bị xóa, thì bạn phải cố gắng tìm một đường đi mới giữa hai đỉnh đó (nếu bạn tìm thấy một, sử dụng nó để cập nhật cây bao trùm, nếu không biểu đồ bị ngắt kết nối).

Vì vậy, tốt nhất trường hợp O (1), trường hợp xấu nhất O (| V | + | E |), nhưng khá đơn giản để thực hiện anyway.

Answer 3

như đã nói bởi Moron ngay trước đây, bạn thực sự đang tìm kiếm Cầu trong biểu đồ của mình.

Bây giờ một cây cầu là một cạnh có thuộc tính được mô tả và cũng có nguồn gốc và kết thúc trong Cắt Vertexes. Cắt đỉnh là chính xác những gì một cây cầu, nhưng trong một phiên bản đỉnh (nút).

Vì vậy, cách duy nhất (mặc dù khá uốn giả thuyết cấu trúc dữ liệu ban đầu) tôi có thể nghĩ, để có được độ phức tạp O (1) cho điều này, nếu bạn kiểm tra đầu tiên mỗi nút trong biểu đồ của bạn nếu nó là một đỉnh cắt và sau đó chỉ đơn giản là trong thời gian liên tục kiểm tra nếu cạnh bạn muốn xóa là một gắn liền với một trong hai.

Tìm xem một nút trong biểu đồ có phải là đỉnh cắt không có O (m + n) trong đó m = # cạnh và n = # nút.

Chúc mừng