Giáo trình Đồ thị và các thuật toán - Chương 3: Các bài toán về đường đi

Định lý 3.1.2 Cho G = (y,E) là đồ thị có hướng, và V E V. Khi đó G liên thông mạnh nếu và chỉ nếu mọi cặp đỉnh a,b E V, tồn tại một đường đi từ a đến V và một đường đi từ V đến b.

Dựa trên thuật toán tìm kiếm theo chiều sâu, ta có thể mô tả cách xác định một đồ thị có hướng có liên thông mạnh hay không thông qua định lý sau:

Định lý 3.1.3 Cho G = (V, E) là đồ thị có hướng, và V G V. Ký hiệu G' := (V, E'} là đồ thị có hướng nhận được từ G bằng cách đảo hướng mỗi cung trong E. Khi đó G là liên thông mạnh nếu và chỉ nếu thuật toán tìm kiếm theo chiêu sâu trên đồ thị có hướng G, khởi đầu từ V, đạt được mọi đỉnh của G và thuật toán tìm kiếm theo chiều sâu trên đồ thị có hướng G', khâi đầu từ V, đạt được mọi đỉnh của G'.