Lý thuyết đồ thị - Bài 02 - Một số tính chất về đường đi trên đồ thị

1/63
1.6. MỘT SỐ TÍNH CHẤT VỀ
ĐƯỜNG ĐI TRÊN ĐỒ THỊ

Định lý 1.2: Giả sử đồ thị G có n đỉnh. Tồn tại đường đi từ đỉnh a đến đỉnh b trên đồ thị G khi và chỉ khi tồn tại đường đi từ a đến b trên đồ thị này với độ dài không quá n-1.
2/63
1.6. MỘT SỐ TÍNH CHẤT VỀ
ĐƯỜNG ĐI TRÊN ĐỒ THỊ (tiếp)
Chứng minh:
Giả sử có đường đi ngắn nhất từ a đến b
. Đường đi này có độ dài k-1.
Hình 1.6. Một đường đi từ đỉnh a đến đỉnh b
3/63
1.6. MỘT SỐ TÍNH CHẤT VỀ
ĐƯỜNG ĐI TRÊN ĐỒ THỊ (tiếp)
Chứng minh:
- Nếu k-1 ≤ n-1 thì định lý được chứng minh.
Ngược lại (nghĩa là k > n), trong dãy đỉnh của đường đi có ít nhất hai đỉnh trùng nhau, chẳng hạn: xi = xj. Khi đó cũng là đường đi từ a tới b nhưng với độ dài ngắn hơn. Mâu thuẫn với giả thiết đường đi là ngắn nhất. 
4/63
BÀI TOÁN ĐƯỜNG ĐI TRÊN ĐỒ THỊ

Bài toán đường đi
Cho đồ thị G và hai đỉnh a, b thuộc G.
Có hay không một đường đi từ đỉnh a đến đỉnh b trên đồ thị G ?
5/63
BÀI TOÁN ĐƯỜNG ĐI TRÊN ĐỒ THỊ (tiếp)
Thuật toán 1.1
Xây dựng ma trận kề A cho đồ thị G.
Tính tổng các ma trận luỹ thừa:
T = A + A2 + … + An-1
3. Nếu T[a,b]  1 thì kết luận là có đường đi từ đỉnh a đến đỉnh b, ngược lại thì kết luận là không có.
6/63
BÀI TOÁN ĐƯỜNG ĐI TRÊN ĐỒ THỊ (tiếp)

Ma trận tổng T còn được gọi là bao đóng bắc cầu của ma trận kề A.
Các phần tử của ma trận T có thể rất lớn, hơn nữa ta chỉ quan tâm đến tính chất khác 0 của các phần tử này.
7/63
BÀI TOÁN ĐƯỜNG ĐI TRÊN ĐỒ THỊ (tiếp)
Cải tiến thuật toán 1.1
- Có thể xem ma trận kề A như ma trận logic.
- Trong phép nhân ma trận ta thay các phép toán số học + , * bằng các phép toán logic OR và AND.
- Dùng thuật toán Warshall để tính ma trận bao đóng bắc cầu logic AS. Các phần tử logic của ma trận AS cho biết có hay không đường đi giữa các cặp đỉnh của đồ thị đã cho.
8/63
BÀI TOÁN ĐƯỜNG ĐI TRÊN ĐỒ THỊ (tiếp)

Thuật toán 1.2 (Warshall)
Dữ liệu: Ma trận kề logic A của đồ thị G.
Kết quả: Ma trận bao đóng bắc cầu logic AS.
9/63
BÀI TOÁN ĐƯỜNG ĐI TRÊN ĐỒ THỊ (tiếp)
Thuật toán 1.2 (Warshall)
1 Begin
2 for i := 1 to n do
3 for j := 1 to n do AS[i,j] := A[i,j] ;
4 for k := 1 to n-1 do
5 for i := 1 to n do
6 for j := 1 to n do
if ! AS[i,j] then AS[i,j] := AS[i,k] and
AS[k,j]
8 End .
Độ phức tạp: O(n3).
10/63
1.7. BẬC CỦA ĐỈNH VÀ
TÍNH LIÊN THÔNG CỦA ĐỒ THỊ

Bậc của đỉnh
Tính liên thông của đồ thị
Đồ thị đầy đủ
Một số tính chất




11/63
BẬC CỦA ĐỈNH
Định nghĩa 1.11:
Giả sử G = (V, E) là một đồ thị, ta gọi bậc của một đỉnh là số cạnh kề với đỉnh đó.

Ký hiệu: r(a) là bậc của đỉnh a trong đồ thị G.
12/63
TÍNH LIÊN THÔNG CỦA ĐỒ THỊ
Định nghĩa 1.12
Hai đỉnh của đồ thị G được gọi là liên thông, nếu trên đồ thị có đường đi vô hướng nối chúng với nhau.

Đồ thị được gọi là liên thông nếu mọi cặp đỉnh của đồ thị đều liên thông với nhau.
13/63
TÍNH LIÊN THÔNG CỦA ĐỒ THỊ (tiếp)
Quan hệ liên thông trên tập đỉnh là một quan hệ tương đương. Quan hệ đó cho một phân hoạch trên tập các đỉnh.
Mỗi lớp tương đương của quan hệ này được gọi là một mảng liên thông (hay thành phần liên thông) của đồ thị.
14/63
VÍ DỤ 1.6
Hình 1.7. Một đồ thị liên thông
15/63
Mỗi mảng liên thông của một đồ thị là một đồ thị con
không rỗng liên thông.
2. Hai mảng liên thông khác nhau thì không giao nhau.
3. Hai đỉnh ở hai mảng liên thông khác nhau thì không
liên thông với nhau.
4. Hợp các mảng liên thông cho ta đồ thị ban đầu.
Ký hiệu: p là số mảng liên thông của một đồ thị.
TÍNH LIÊN THÔNG CỦA ĐỒ THỊ (tiếp)
16/63
BẬC VÀ TÍNH LIÊN THÔNG
Định lý 1.3
Tổng tất cả các bậc của các đỉnh trong một đồ thị bằng hai lần số cạnh của đồ thị đó.
Chứng minh:
Ta tính bậc của các đỉnh. Mỗi đỉnh thuộc một cạnh nào đó thì bậc của nó tăng thêm một.
Mà mỗi cạnh thì có hai đỉnh. 
17/63
BẬC VÀ TÍNH LIÊN THÔNG (tiếp)
Hệ quả 1.1: Số đỉnh có bậc lẻ trong một đồ thị phải là một số chẵn.

Hệ quả 1.2: Nếu đồ thị G có đúng hai đỉnh bậc lẻ thì hai đỉnh đó phải liên thông với nhau.
18/63
BẬC VÀ TÍNH LIÊN THÔNG (tiếp)
Định lý 1.4
Đồ thị G có n đỉnh. Nếu bậc của mỗi đỉnh trong G không nhỏ hơn n/2 thì đồ thị G liên thông.
19/63
BẬC VÀ TÍNH LIÊN THÔNG (tiếp)
Chứng minh:
Phản chứng: Giả sử đồ thị G không liên thông.
Khi đó, có ít nhất hai đỉnh a và b nằm trong hai mảng liên thông khác nhau.
Vậy thì, n ≤ r(a) + r(b) ≤ n-2.
Suy ra điều mâu thuẫn. 
20/63
BẬC VÀ TÍNH LIÊN THÔNG (tiếp)
Định lý 1.5
Giả sử đồ thị G có n đỉnh, m cạnh, p mảng liên thông và không có đỉnh nút. Khi đó:

21/63
BẬC VÀ TÍNH LIÊN THÔNG (tiếp)
Chứng minh:
Giả sử mảng Gi có ni đỉnh. Thế thì ni ≥ 1.
Không mất tính tổng quát có thể xem G1 là mảng có nhiều đỉnh nhất.
Ta "dồn" các đỉnh cho mảng G1 mà không làm thay đổi số đỉnh, số cạnh và số mảng liên thông của đồ thị cho đến khi n2 = n3 = . . . = np = 1.
22/63
BẬC VÀ TÍNH LIÊN THÔNG (tiếp)
Chứng minh:
Cách “dồn” các đỉnh vào mảng G1:
Giả sử còn mảng Gi mà n1  ni  2.
Chọn a là một đỉnh của Gi sao cho nếu ta bỏ a và
các cạnh kề với nó thì phần còn lại vẫn liên thông.
Giả sử a được nối với k đỉnh trong Gi.
23/63
BẬC VÀ TÍNH LIÊN THÔNG (tiếp)
Chứng minh:
Hiển nhiên 1  k  ni -1 < n1.
Ta chọn k đỉnh bất kỳ trong mảng G1 và:
- Thêm k cạnh mới nối a với các đỉnh đã chọn trong G1.
Xoá bỏ k cạnh nối a với các đỉnh trong Gi.
Đỉnh a liên thông với đỉnh trong G1 nên thuộc vào
mảng G1.

24/63
BẬC VÀ TÍNH LIÊN THÔNG (tiếp)
Chứng minh:
Ta được một đồ thị mới với số đỉnh, số cạnh, số mảng liên thông không thay đổi vì mảng Gi bớt a và k cạnh vẫn còn ít nhất một đỉnh, G1 thêm đỉnh a và k cạnh mới.
25/63
BẬC VÀ TÍNH LIÊN THÔNG (tiếp)
Minh hoạ cách “dồn” các đỉnh:
Hình 1.8. Cách dồn đỉnh cho mảng G1
26/63
BẬC VÀ TÍNH LIÊN THÔNG (tiếp)
Chứng minh:
Thực hiện phép “dồn” trên cho đến khi:
n1 = n -p +1, n2 = n3 = . .. = np = 1
và G1 có m cạnh.
Vậy m = số cạnh trong G1, do đó:



Định lý được chứng minh. 
27/63
BẬC VÀ TÍNH LIÊN THÔNG (tiếp)
Hệ quả 1.3
Đồ thị G có n đỉnh và số cạnh thì G liên thông.
Chứng minh:
Theo Định lý 1.9. thì:
Suy ra:
Bất đẳng thức trên chỉ thỏa mãn khi p = 1, vậy G là liên thông. 
28/63
ĐỒ THỊ ĐẦY ĐỦ
Đồ thị được gọi là đầy đủ nếu hai đỉnh bất kỳ đều có cạnh nối.
Ký hiệu Kn là đồ thị vô hướng đầy đủ n đỉnh.
- Đồ thị đầy đủ Kn là đồ thị liên thông.
- Mỗi đỉnh của Kn đều có bậc n-1.
- Hai đỉnh bất kỳ được nối với nhau bằng một đường đi ngắn nhất có độ dài bằng 1, đó chính là cạnh nối hai đỉnh ấy.
29/63
MỘT SỐ TÍNH CHẤT
1. Đồ thị vô hướng n đỉnh (n  3), không có đỉnh nút và bậc của mỗi đỉnh đều không nhỏ hơn 2, luôn có chu trình đơn.
2. Đồ thị n đỉnh (n  4) và bậc của mỗi đỉnh đều không nhỏ hơn 3 luôn có chu trình đơn độ dài chẵn
30/63
MỘT SỐ TÍNH CHẤT (tiếp)
3. Đồ thị n đỉnh (n  2) không có đỉnh nút luôn có ít nhất hai đỉnh cùng bậc.
4. Nếu đồ thị n đỉnh (n  4) có đúng hai đỉnh cùng bậc thì hai đỉnh này không thể đồng thời có bậc 0 hoặc bậc n-1.
5. Trong đồ thị n đỉnh (n  4) mà cứ bốn đỉnh tuỳ ý thì có ít nhất một đỉnh kề với ba đỉnh còn lại, thì số đỉnh bậc n-1 của đồ thị này không ít hơn n-3.