Đồ thị liên thông
Tính liên thông (connectivity) là một trong những tính chất quan trọng nhất của đồ thị nói riêng và lý thuyết đồ thị nói chung.

Một đồ thị được gọi là liên thông (connected) nếu có đường đi giữa mọi cặp đỉnh phân biệt của đồ thị. Ngược lại, đồ thị này được gọi là không liên thông (disconnected).

Cho đồ thị G = (X,U) vô hướng hay có hướng. Ta định nghĩa một quan hệ <=> như hệ sau trên tập đỉnh X:

Với mọi i, j thuộc X, i xấp xỉ j <=> i = j hay có dây chuyền đỉnh đầu là i và đỉnh cuối là j.

Quan hệ này có 3 tính chất: phản xạ, đối xứng và bắc cầu nên nó là một quan hệ tương đương. Do đó tập X được phân hoạch thành các lớp tương đương. Ta định nghĩa:


Một đồ thị không liên thông sẽ bao gồm nhiều đồ thị con liên thông, các đồ thị con này được gọi là các thành phần liên thông (connected component).
Đồ thị liên thông khi và chỉ khi có một thành phần liên thông.

Trong hình trên có 4 thành phần liên thông. (Đỉnh k đứng riêng lẻ theo quy ước cũng tính là 1 thành phần liên thông)


