Thành phần liên thông

Trong lý thuyết đồ thị, một thành phần liên thông của một đồ thị vô hướng là một đồ thị con trong đó giữa bất kì hai đỉnh nào đều có đường đi đến nhau, và không thể nhận thêm bất kì một đỉnh nào mà vẫn duy trì tính chất trên. Một đồ thị liên thông có đúng một thành phần liên thông, chính là toàn bộ đồ thị.

Quan hệ tương đương

Một cách khác để định nghĩa thành phần liên thông là sử dụng các lớp tương đương của một quan hệ tương đương định nghĩa trên tập các đỉnh của đồ thị. Trong một đồ thị vô hướng, đỉnh v tới được từ đỉnh u nếu có đường đi từ u đến v. Trong định nghĩa này, đường đi độ dài 0 từ một đỉnh đến chính nó cũng được tính, và một đỉnh có thể xuất hiện nhiều lần trên đường đi. Quan hệ tới được là một quan hệ tương đương bởi:

Tính chất phản xạ: luôn có đường đi độ dài 0 từ một đỉnh đến chính nó.
Tính chất đối xứng: nếu có đường từ u tới v thì cũng có đường từ v tới u.
Tính chất bắc cầu: nếu có đường từ u tới v và đường từ v tới w thì khi nối hai đường này, ta có đường từ u tới w.

Các thành phần liên thông là các đồ thị con tạo bởi các lớp tương đương của quan hệ này.

Các thuật toán

Có thể tìm các thành phần liên thông trong thời gian tuyến tính bằng thuật toán tìm kiếm theo chiều sâu hoặc tìm kiếm theo chiều rộng.

Các nhà nghiên cứu còn tìm hiểu các thuật toán cho tìm kiếm thành phần liên thông trong những mô hình tính toán giới hạn hơn, chẳng hạn như khi bộ nhớ (không tính phần để lưu trữ dữ liệu vào) là lôgarit của kích thước dữ liệu vào (định nghĩa bởi lớp L). Năm 2008, Reingold đã tìm ra một thuật toán cho việc kiểm tra xem có đường đi giữa hai đỉnh cho trước hay không trong bộ nhớ lôgarit, do đó chứng minh L=SL^[1].

Áp Dụng Bài Toán Thực Tế

BÀI TOÁN "BẢN ĐỒ CÁC VÙNG ĐẢO" Khi tiến hành khảo sát các đảo ở một vùng biển, người ta ghi kết quả khảo sát lại thành một bản đồ nhị phân, trong đó số 0 cho biết biển và số 1 là đất liền và được thể hiện trên 1 bàn cờ ở dạng kẻ lưới Bài toán bản đồ các vùng đảo, là bài toán ứng dụng thực tế của việc tìm thành phần liên thông, là tiền đề cho việc thực hiện một số trò chơi nổi tiếng như: Minesweeper Dò mìn (trò chơi)

1.Ý Tưởng Thuật Toán

Khi làm việc với các dạng lưới kẻ ô như bàn cờ, bản đồ… thì người ta đưa ra khái niệm 2 ô kề nhau. Có nhiều loại kề nhau, như kề nhau theo bước đi con mã, theo đường chéo, theo lận cận 4, lân cận 8. Một đảo chính là một miền liên thông các lân cận 4 trên ma trận lưới.

^[2]

Các ô màu vàng lần lượt là những ô kề nhau theo lân cận 4 và 8 với ô trung tâm (màu đen).
Ô 1 và ô 2 (ô màu xanh) kề nhau theo lân cận 4 (và dĩ nhiên theo lân cận 8 luôn). Tương tự ô 2 và ô 3 cũng kề nhau theo lân cận 4. Ô 3 và ô 4 chỉ kề nhau theo lân cận 8, không theo lân cận 4. Ô 1 và ô 3 cũng kề nhau theo lân cận 8.
Các ô 1, 2 và 3 tạo thành một miền liên thông 4 vì từ 1 đi được đến 2, từ 2 đi được đến 3 theo lân cận 4 (từ 3 không đến 4 được theo lân cận 4). Ô số bốn bản thân nó là một miền liên thông 4.
Nếu xét theo liên thông 8 thì cả bốn ô (1, 2, 3, và 4) tạo thành một miền liên thông 8.