3. ĐƯỜNG ĐI. CHU TRÌNH. ĐỒ THỊ LIÊN THÔNG

Định nghĩa 1.

Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị vô hướng G = (V, E) là dãy

x0, x1,…, xn-1, xn

trong đó u = x0 , v = xn , (xi , xi+1)Î E, i = 0, 1, 2,…, n-1.

Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh:

(x0, x1), (x1, x2), …, (xn-1, xn)

Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại.

Thí dụ 1. Trên đồ thị vô hướng cho trong hình 1: a, d, c, f, e là đường đi đơn độ dài 4. Còn d, e, c, a không là đường đi, do (c,e) không phải là cạnh của đồ thị. Dãy b, c, f, e, b là chu trình độ dài 4. Đường đi a, b, e, d, a, b có độ dài là 5 không phải là đường đi đơn, do cạnh (a, b) có mặt trong nó 2 lần.

Hình 1. Đường đi trên đồ thị

Khái niệm đường đi và chu trình trên đồ thị có hướng được định nghĩa hoàn toàn tương tự như trong trường hợp đồ thị vô hướng, chỉ khác là ta có chú ý đến hướng trên các cung.

Định nghĩa 2.

Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó, n là số nguyên dương, trên đồ thị có hướng G = (V, A) là dãy

x0, x1,…, xn-1, xn

trong đó u = x0, v = xn, (xi, xi+1)Î E, i = 0, 1, 2,…, n-1.

Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cung:

(x0, x1), (x1, x2), …, (xn-1, xn)

Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đi hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại.

Thí dụ 2. Trên đồ thị có hướng cho trong hình 1: a, d, c, f, e là đường đi đơn độ dài 4. Còn d, e, c, a không là đường đi, do (c,e) không phải là cạnh của đồ thị. Dãy b, c, f, e, b là chu trình độ dài 4. Đường đi a, b, e, d, a, b có độ dài là 5 không phải là đường đi đơn, do cạnh (a, b) có mặt trong nó 2 lần.

Xét một mạng máy tính. Một câu hỏi đặt ra là hai máy tính bất kỳ trong mạng này có thể trao đổi thông tin được với nhau hoặc là trực tiếp qua kênh nối chúng hoặc thông qua một hoặc vài máy tính trung gian trong mạng? Nếu sử dụng đồ thị để biểu diễn mạng máy tính này (trong đó các đỉnh của đồ thị tương ứng với các máy tính, còn các cạnh tương ứng với các kênh nối) câu hỏi đó được phát biểu trong ngôn ngữ đồ thị như sau: Tồn tại hay không đường đi giữa mọi cặp đỉnh của đồ thị.

Định nghĩa 3.

Đồ thị vô hướng G = (V, E) được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.

Như vậy hai máy tính bất kỳ trong mạng có thể trao đổi thông tin được với nhau khi và chỉ khi đồ thị tương ứng với mạng này là đồ thị liên thông.

Thí dụ 3. Trong hình 2 : Đồ thị G là liên thông, còn đồ thị H là không liên thông.

Hình 2. Đồ thị G và H

Định nghĩa 4.

Ta gọi đồ thị con của đồ thị G = (V, E) là đồ thị H = (W, F), trong đó WÍ V và FÍ E.

Trong trường hợp đồ thị là không liên thông, nó sẽ rã ra thành một số đồ thị con liên thông đôi một không có đỉnh chung. Những đồ thị con liên thông như vậy ta sẽ gọi là các thành phần liên thông của đồ thị.

Thí dụ 4. Đồ thị H trong hình 2 gồm 3 thành phần liên thông H1, H2, H3.

Trong mạng máy tính có thể có những máy (Những kênh nối) mà sự hỏng hóc của nó sẽ ảnh hưởng đến việc trao đổi thông tin trong mạng. Các khái niệm tương ứng với tình huống này được đưa ra trong định nghĩa sau.

Định nghĩa 5.

Đỉnh v được gọi là đỉnh rẽ nhánh nếu việc loại bỏ v cùng với các cạnh liên thuộc với nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị. Cạnh e được gọi là cầu nếu việc loại bỏ nó khỏi đồ thị làm tăng số thành phần liên thông của đồ thị.

Thí dụ 5. Trong đồ thị G ở hình2, đỉnh d và e là đỉnh rẽ nhánh, còn các cạnh (d,g) và (e,f) là cầu.

Đối với đồ thị có hướng có hai khái niệm liên thông phụ thuộc vào việc ta có xét đến hướng trên các cung hay không.

Định nghĩa 6.

Đồ thị có hướng G = (V, A) được gọi là liên thông mạnh nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó.

Định nghĩa 7.

Đồ thị có hướng G = (V, A) được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng với nó là vô hướng liên thông.

Rõ ràng nếu đồ thị là liên thông mạnh thì nó cũng là liên thông yếu, nhưng điều ngược lại là không luôn đúng, như chỉ ra trong ví dụn dưới đây.

Thí dụ 6. Trong hình 3 đồ thị G là liên thông mạnh, còn H là liên thông yếu nhưng không là liên thông mạnh.

Hình 3. Đồ thị liên thông mạnh G và đồ thị liên thông yếu H

Một câu hỏi đặt ra là khi nào có thể định hướng các cạnh của một đồ thị vô hướng liên thông để có thể thu được đồ thị có hướng liên thông mạnh? Ta sẽ gọi đồ thị như vậy là đồ thị định hướng được. Định lý dưới đây cho ta tiêu chuẩn nhận biết một đồ thị có là định hướng được hay không.

Định lý 1.

Đồ thị vô hướng liên thông là định hướng được khi và chỉ khi mỗi cạnh của nó nằm trên ít nhất một chu trình.

Chứng minh.

Điều kiện cần. Giả sử (u,v) là một cạnh của một đồ thị. Từ sự tồn tại đường đi có hướng từ u đến v và ngược lại suy ra (u, v) phải nằm trên ít nhất một chu trình.

Điều kiện đủ. Thủ tục sau đây cho phép định hướng các cạnh của đồ thị để thu được đồ thị có hướng liên thông mạnh. Giả sử C là một chu trình nào đó trong đồ thị. Định hướng các cạnh trên chu trình này theo một hướng đi vòng theo nó. Nếu tất cả các cạnh của đồ thị là đã được định hướng thì kết thúc thủ tục. Ngược lại, chọn e là một cạnh chưa định hướng có chung đỉnh với ít nhất một trong số các cạnh đã định hướng. Theo giả thiết tìm được chu trình C’ chứa cạnh e. Định hướng các cạnh chưa được định hướng của C’ theo một hướng dọc theo chu trình này (không định hướng lại các cạnh đã có định hướng). Thủ tục trên sẽ được lặp lại cho đến khi tất cả các cạnh của đồ thị được định hướng. Khi đó ta thu được đồ thị có hướng liên thông mạnh.