Lý thuyết đồ thị - Bài 01 - Các Khái niệm

LÝ THUYẾT ĐỒ THỊ

Giảng viên: PGS.TS. Hoàng Chí Thành
Trường Đại học Khoa học Tự nhiên, ĐHQG HN
2/63
MỞ ĐẦU
- Lý thuyết Đồ thị là một trong những ngành khoa học ra đời khá sớm.
- Lý thuyết Đồ thị giúp mô tả hình học và giải quyết nhiều bài toán thực tế phức tạp liên quan đến các khái niệm như: đường đi, chu trình, tập ổn định, chu số, sắc số, duyệt đồ thị, đường đi ngắn nhất, tâm đồ thị, luồng vận tải, đồ thị phẳng, cây bao trùm, cây biểu thức, cây mã tối ưu …bằng các thuật toán ngắn gọn và lý thú.
- Lý thuyết Đồ thị đã gắn kết nhiều ngành khoa học với nhau.
3/63
MỞ ĐẦU (tiếp)
Bài giảng điện tử “Lý thuyết Đồ thị” này bao gồm: - 11 chương
- phân thành 20 bài học
trình bày những vấn đề cốt lõi nhất của lý thuyết đồ thị cùng các thuật toán tiêu biểu; giúp người học có thể cài đặt trên máy tính và ứng dụng trong thực tế.
4/63
CHƯƠNG 1

ĐẠI CƯƠNG VỀ ĐỒ THỊ
5/63
NỘI DUNG
Các khái niệm về đồ thị
Biểu diễn đồ thị trong máy tính
Một số tính chất về đường đi trên đồ thị
Bậc của đỉnh và tính liên thông
6/63
1.1. CÁC KHÁI NIỆM VỀ ĐỒ THỊ
Định nghĩa 1.1
Đồ thị là một cặp G = (V, E), trong đó:
- V là tập hợp các đỉnh (vertex),
- E  V  V là tập hợp các cạnh (edge).
7/63
VÍ DỤ 1.1
Đồ thị G cho như hình vẽ.
- Tập đỉnh V = {a, b , c, d, e},
- Tập các cạnh E = {(a, b), (a, c), (b, c), (d, b),
(d, c), (e, a), (e, b), (e, d)}.

Hình 1.1: Đồ thị hữu hạn
8/63
TÍNH KỀ TRONG ĐỒ THỊ
Đỉnh kề:
Nếu (a,b) là một cạnh của đồ thị G thì:
- Đỉnh b kề với đỉnh a
Hai đỉnh a và b cùng kề với cạnh (a,b).
Hai cạnh kề nhau: là hai cạnh có ít nhất một đỉnh
chung.
9/63
ĐỊNH NGHĨA ĐỒ THỊ (tiếp)
Định nghĩa 1.2
Đồ thị là một cặp G = (V, F), trong đó:
- V là tập hợp các đỉnh,
- F : V  2V , được gọi là ánh xạ kề.
Sự tương đương của hai định nghĩa:
 x, y  V : (x, y)  E  y  F(x).
10/63
VÍ DỤ 1.2
Ánh xạ kề của đồ thị trên hình vẽ:
F(a) = {b, c} , F(b) = {c} , F(c) =  ,
F(d) = {b, c} và F(e) = {a, b, d} .
Hình 1.1: Đồ thị hữu hạn
11/63
ĐỒ THỊ VÔ HƯỚNG VÀ CÓ HƯỚNG
Cạnh vô hướng: cặp đỉnh (x, y)  E không sắp thứ tự.
Cạnh có hướng: cặp đỉnh (x, y)  E có sắp thứ tự.
12/63
ĐỒ THỊ VÔ HƯỚNG VÀ CÓ HƯỚNG (tiếp)
Định nghĩa 1.3
- Đồ thị chỉ chứa các cạnh vô hướng được gọi là đồ
thị vô hướng
Đồ thị chỉ chứa các cạnh có hướng được gọi là đồ
thị có hướng.

Mỗi đồ thị vô hướng có thể biểu diễn bằng một đồ thị có hướng bằng cách thay mỗi cạnh vô hướng bằng hai cạnh có hướng tương ứng.
13/63
ĐỒ THỊ ĐỐI XỨNG
Định nghĩa 1.4
Đồ thị G = (V, E) được gọi là đối xứng nếu:
 x, y  V : (x, y)  E  (y, x)  E.

- Các đồ thị vô hướng là đối xứng.
14/63
ĐƠN VÀ ĐA ĐỒ THỊ
Định nghĩa 1.5
- Đồ thị G = (V, E) mà mỗi cặp đỉnh được nối với nhau không quá một cạnh được gọi là đơn đồ thị (gọi tắtlà đồ thị).
- Đồ thị có những cặp đỉnh được nối với nhau nhiều hơn một cạnh thì được gọi là đa đồ thị.
15/63
1.2. ĐƯỜNG ĐI VÀ CHU TRÌNH
Định nghĩa 1.6: Cho G = (V, E) là một đồ thị.
Đường đi trong đồ thị là một dãy các đỉnh:

sao cho mỗi đỉnh trong dãy (không kể đỉnh đầu tiên) kề với đỉnh trước nó bằng một cạnh nào đó, nghĩa là:
 i = 2, 3, ... , k-1, k : (xi-1, xi)  E.
Ta nói rằng đường đi này đi từ đỉnh đầu x1 đến đỉnh cuối xk.
16/63
ĐƯỜNG ĐI
Độ dài của đường đi: là số cạnh của đường đi đó.

Đường đi đơn: Các đỉnh trên nó khác nhau từng đôi một.
17/63
CHU TRÌNH
Định nghĩa 1.7
Chu trình là một đường đi khép kín (đỉnh cuối trùng
với đỉnh đầu của đường).
[x1, x2,…, xi, xi+1,…, xk-1, xk]
trong đó x1 = xk.
- Để cho gọn, trong ký hiệu của chu trình thường không viết đỉnh cuối:
[x1, x2,…, xi, xi+1,…, xk-1]
Ký hiệu: n là số đỉnh, m là số cạnh của một đồ thị.
18/63
CHU TRÌNH (tiếp)
Chu trình đơn: là chu trình mà các đỉnh trên nó khác nhau từng đôi.
Đỉnh nút: là đỉnh kề với chính nó.

19/63
1.3. ĐỒ THỊ CON VÀ ĐỒ THỊ RIÊNG
Định nghĩa 1.8
Giả sử G = (V, E) là một đồ thị.
- Đồ thị G’ = (V’, E’) được gọi là đồ thị con của đồ thị G nếu:
V’  V và E’ = E  (V’  V’).
- Đồ thị G” = (V, E”) với E”  E, được gọi là đồ thị riêng của đồ thị G.
20/63
1.3. ĐỒ THỊ CON VÀ ĐỒ THỊ RIÊNG (tiếp)
Một số kết quả
- Mỗi tập con các đỉnh V’ của đồ thị tương ứng duy nhất với một đồ thị con.
- Để xác định một đồ thị con ta chỉ cần nêu tập đỉnh của nó.
- Đồ thị riêng là đồ thị giữ nguyên tập đỉnh và bỏ bớt một số cạnh.
21/63
1.4. SỰ ĐẲNG HÌNH
Sự đẳng hình của hai đồ thị dựa trên sự đẳng cấu của hai tập đỉnh sao cho sự đẳng cấu ấy bảo toàn được các cạnh của đồ thị.
Định nghĩa 1.9
Hai đồ thị G1 = (V1, E1) và G2 = (V2, E2 ) được gọi là
đẳng hình với nhau nếu tồn tại một song ánh S trên
các tập đỉnh bảo toàn các cạnh:
 x, y  V1 : (x, y)  E1  (S(x), S(y))  E2.
22/63
1.4. SỰ ĐẲNG HÌNH (tiếp)
Hai đồ thị đẳng hình chỉ khác nhau về tên gọi của các đỉnh và cách biểu diễn bằng hình vẽ.
Do vậy, ta không phân biệt hai đồ thị đẳng hình với nhau
23/63
VÍ DỤ 1.3
Hai đồ thị sau là đẳng hình với song ánh:
S(ai) = xi , i = 1, 2, 3, 4.
Hình 1.3. Hai đồ thị đẳng hình
24/63
1.5. BIỂU DIỄN ĐỒ THỊ
TRONG MÁY TÍNH

Biểu diễn bằng ma trận kề
Biểu diễn bằng danh sách kề
25/63
BIỂU DIỄN BẰNG MA TRẬN KỀ
Định nghĩa 1.10
Cho G = (V, E) là một đồ thị có các đỉnh được đánh
số là các số tự nhiên: 1, 2, ... , n.
Ma trận vuông A cấp n được gọi là ma trận kề của
đồ thị G nếu:  i, j  V, A[i,j] = số cạnh nối đỉnh
i với đỉnh j trong G.
Đồ thị G là đối xứng khi và chỉ khi ma trận kề A là đối xứng
26/63
VÍ DỤ 1.4
Ma trận kề của đa đồ thị có hướng:

0 1 1 2 A = 0 0 1 0 0 0 1 0 0 0 1 0

Hình 1.3. Đồ thị có hướng và ma trận kề


27/63
BIỂU DIỄN BẰNG MA TRẬN KỀ (tiếp)

Định lý 1.1
Phần tử ở hàng i và cột j của ma trận luỹ thừa Ak
chính là số các đường đi khác nhau có độ dài k nối
đỉnh i với đỉnh j trong đồ thị G.
28/63
BIỂU DIỄN BẰNG MA TRẬN KỀ (tiếp)
Chứng minh:
Quy nạp theo độ dài k của đường đi
- k = 1: suy từ định nghĩa ma trận kề.
- (k)  (k+1)
Ký hiệu A = [aij], Ak = [bij], C = Ak.A = [cij]
Khi đó cij =  biq aqj
Hình 1.4: Các đường đi từ đỉnh i đến đỉnh j qua đỉnh q
29/63
BIỂU DIỄN BẰNG MA TRẬN KỀ (tiếp)
Chứng minh:
Theo giả thiết quy nạp, với q bất kỳ (1  q  n), biq
chính là số đường đi từ đỉnh i đến đỉnh q có độ dài k.
- Nếu aqj = d  1 thì có cạnh đi từ q đến j, do vậy có các đường đi từ i đến j qua q với độ dài k+1, mà số các đường đi đó chính là d * biq .
30/63
BIỂU DIỄN BẰNG MA TRẬN KỀ (tiếp)
Chứng minh:
- Nếu aqj = 0 thì không có cạnh từ q đến j, do đó cũng không có đường đi từ i đến j qua q với độ dài k+1.
Vậy tính theo tổng trên, ta sẽ có tất cả các đường đi
từ i đến j với độ dài k+1. 
31/63
BIỂU DIỄN BẰNG DANH SÁCH KỀ
Với mỗi đỉnh của đồ thị ta xây dựng một danh sách móc nối chứa các đỉnh kề với đỉnh này: Danh sách này được gọi là danh sách kề.

Một đồ thị được biểu diễn bằng một mảng các danh sách kề.

32/63
VÍ DỤ 1.5
Đồ thị và danh sách kề biểu diễn đồ thị tương ứng:
Hình 1.5. Mảng các danh sách kề biểu diễn đồ thị