Chương 1 Một số kiến thức chuẩn bị Nội dung của chương hiện tại nhằm hệ thống hóa lại một số khái niệm và thuật ngữ cơ bản trong lý thuyết đồ thị. Hiện nay có rất nhiều tài liệu chuyên khảo về đồ thị phù hợp với các mức độ người đọc khác nhau. Để thống nhất, trong khuôn khổ nội dung sau đây chúng tôi dựa theo các tài liệu [2, 3, 4]. Định nghĩa đồ thị Định nghĩa 1.
Đơn đồ thị vô hướng là một cặp G = (V, E) bao gồm V là tập các đỉnh, và E là tập các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Đa đồ thị vô hướng G = (V, E) bao gồm V là tập các đỉnh, và E là họ các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Hai cạnh e1 và e2 được gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh. Rõ ràng mỗi đơn đồ thị đều là đa đồ thị, nhưng không phải đa đồ thị nào cũng 5 Hình 1.1: Ví dụ đơn đồ thị vô hướng và đa đồ thị vô hướng là đơn đồ thị, vì trong đa đồ thị có thể có hai (hoặc nhiều hơn) cạnh nối một cặp đỉnh nào đó.
Đa đồ thị có hướng G = (V, E) bao gồm V là tập các đỉnh, và E là họ các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. Hai cung e1 , e2 tương ứng với cùng một cặp đỉnh được gọi là cung lặp.2: Ví dụ đơn đồ thị có hướng và đa đồ thị có hướng 6 Trong các phần tiếp theo chủ yếu chúng ta sẽ làm việc với đơn đồ thị vô hướng và đơn đồ thị có hướng. Vì vậy, để cho ngắn gọn, ta sẽ bỏ qua tính từ đơn khi nhắc đến chúng. Các thuật ngữ cơ bản Trong mục này chúng ta sẽ trình bày một số thuật ngữ cơ bản của lý thuyết đồ thị.
Trước tiên, ta xét các thuật ngữ mô tả các đỉnh và cạnh của đồ thị vô hướng. Hai cạnh (cung) a, b được gọi là kề nhau, nếu: (i) Chúng khác nhau. Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu (u, v) là cạnh của đồ thị G. Để đặc trưng cho số cạnh liên thuộc với một đỉnh, người ta đưa vào định nghĩa sau đây.
Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó và sẽ ký hiệu là deg(v). Xét đồ thị cho trong hình 1.3: Đồ thị vô hướng G Đỉnh bậc 0 gọi là đỉnh cô lập. Đỉnh bậc 1 được gọi là đỉnh treo. Trong ví dụ trên đỉnh g là đỉnh cô lập, a và d là các đỉnh treo.
Kết quả sau đây cho ta mối liên hệ giữa dãy bậc đỉnh và số cạnh của đồ thị. Giả sử G = (V, E) là đồ thị vô hướng với m cạnh. Khi đó X 2m = deg(v) i∈V Chứng minh. Rõ ràng mỗi cạnh e = (u, v) được tính một lần trong deg(u) và một lần trong deg(v).
Từ đó suy ra tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh. Đồ thị với n đỉnh và mỗi đỉnh có bậc là 6 có bao nhiêu cạnh? Giải. Từ đó suy ra số cạnh của đồ thị là 3n. Trong đồ thị vô hướng, số đỉnh bậc lẻ là một số chẵn.
Giả sử đồ thị (đa đồ thị) G = (V, E) có n đỉnh, m cạnh V = {x1 , x2 ,. , xn−1 , xn } 8 Các đỉnh x1 , x2 ,. , xk bậc lẻ và xk+1 ,. , xn−1 , xn bậc chẵn.5 ta có đẳng thức: m (x1 ) + m (x2 ) +.
+ m (xn−1 ) + m (xn ) = 2m | {z } | {z } A B Vì B là tổng của các số chẵn nên B là một số chẵn. Do đó, A = 2m − B phải là một số chẵn. Số chẵn A là tổng của k số lẻ, nên k phải chẵn. Bởi vậy, số đỉnh bậc lẻ trong đồ thị (đa đồ thị) bất kỳ phải là một số chẵn.
Ta xét các thuật ngữ tương tự cho đồ thị có hướng. Nếu e = (u, v) là cung của đồ thị có hướng G thì ta nói hai đỉnh u và v là kề nhau, và nói cung (u, v) nối đỉnh u với đỉnh v hoặc cũng nói cung này là đi ra khỏi đỉnh u và đi vào đỉnh v. Tương tự như khái niệm bậc, đối với đồ thị có hướng ta có khái niệm bán bậc ra (vào) của một đỉnh. Ta gọi bán bậc ra (bán bậc vào) của của đỉnh v trong đồ thị có hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và ký hiệu là deg+ (v) (tương ứng deg− (v)).
Xét đồ thị cho trong hình 1.4: Đồ thị có hướng G Do mỗi cung (u, v) sẽ được tính một lần trong bán bậc vào của đỉnh v và một lần trong bán bậc ra của đỉnh u nên sử dụng phương pháp đếm tương tự như trường hợp vô hướng ta đi đến kết quả sau. Giả sử G = (V, E) là đồ thị có hướng. Khi đó X X deg+ (v) = deg− (v) = |E| v∈V v∈V Rất nhiều tính chất của đồ thị có hướng không phụ thuộc vào hướng trên các cung của nó. Vì vậy, trong nhiều trường hợp sẽ thuận tiện hơn nếu ta bỏ qua hướng trên các cung của đồ thị.
Đồ thị vô hướng thu được bằng cách bỏ qua hướng trên các cung được gọi là đồ thị vô hướng nền tương ứng với đồ thị có hướng đã cho. Đường đi, chu trình. Đồ thị liên thông Định nghĩa 1. Đường đi trong G là một dãy hữu hạn hoặc vô hạn các cạnh ((vi,1 , vi,2 ))i=1,.,n trong đó vi,2 = vi+1,1 với mọi i.
Độ dài của đường đi hữu hạn là số cạnh trong dãy. Đường đi độ dài n + 1 từ v1,1 đến vn,2 là dãy (v1,1 , v2,1 ,. , vn,2 ) 10 Đường đi được gọi là khép kín (chu trình) nếu v1,1 = vn,2. Xét đồ thị vô hướng cho trong hình 1.5: Đường đi trên đồ thị Ta có: a, d, c, f, e là đường đi đơn độ dài 4.
Còn d, e, c, a không là đường đi, do (e, c) 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ó hai lần. 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ư trường hợp đồ thị vô hướng chỉ khác là ta có chú ý đến hướng trên các cung.
Đường đi trong G là một dãy hữu hạn hoặc vô hạn các cạnh ((vi,1 , vi,2 ))i=1,.,n trong đó vi,2 = vi+1,1 với mọi i. Độ dài của đường đi hữu hạn là số cạnh trong dãy. Đường đi độ dài n + 1 từ v1,1 đến vn,2 là dãy (v1,1 , v1,2 ,. , vn,2 ) Đường đi được gọi là khép kín (chu trình) nếu v1,1 = vn,2.
Trên đồ thị có hướng cho trong hình 1.5 a, d, c, f, e là đường đi đơn độ dài 4. Còn d, e, c, a không là đường đi, do (e, c) không phải là cung của đồ thị. Dãy b, c, f, e, b là chu trình độ dài 4. Đường đi a, ḃ, e, d, a, b có độ dài là 5 không phải là đường đi đơn, do cung (a, b) có mặt trong nó hai lần.
Sử dụng khái niệm đường đi, người ta định nghĩa tính liên thông của các đồ thị như sau đây. Đồ 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ó.6: Đồ thị G là liên thông, còn đồ thị H là không liên thông.6: Đồ thị liên thông G và đồ thị H gồm 3 thành phần liên thông H1 , H2 , H3 Định nghĩa 1. 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ị H trong hình 1.6 gồm 3 thành phần liên thông H1 , H2 , H3. Đỉ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ị.
Trong đồ thị G ở hình 1.6, đỉ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. Đồ 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ó. Đồ 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à đồ thị 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ụ dưới đây.7 đồ 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. 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.7: Đồ thị liên thông mạnh G và đồ thị liên thông yếu H Đị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.
Điều kiện cần: Giả sử (u, v) là một cạnh của đồ 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.