Lý thuyết đồ thị

LÝ THUYẾT ĐỒ THỊ
Nguyễn Tuấn Anh 0168.638.16.92, [email protected]
http://baigiang.bachkim.vn
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.
CHƯƠNG 1
CÁC KHÁI NIỆM VỀ ĐỒ THỊ
NỘI DUNG
1.1. CÁC KHÁI NIỆM VỀ ĐỒ THỊ
1.2. CÁC THUẬT NGỮ CƠ BẢN
1.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNG
1.4. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT
1.1. CÁC KHÁI NIỆM VỀ ĐỒ THỊ
Định nghĩa 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).
3
1
4
5
2
V={1, 2, 3, 4, 5 }
E={(1, 2), (1,3), (1,4)
(2,3), (2,4), (2, 5), (3,4), (4,5) }
Hình 1. Đồ thị vô hướng
Đồ 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 2: Đồ thị hữu hạn có hướng
1.1. CÁC KHÁI NIỆM VỀ ĐỒ THỊ
3
1
4
5
2
Hình 3: Đa đồ thị
Đa đố thị là G = (V, E), tập đỉnh V, E là tập các cặp không có thứ tự gồm 2 phần tử khác nhau của V gọi là các cạnh.
Hai cạnh e1, e2 được gọi là cạnh lặp nếu chúng cùng tương ứng một cặp đỉnh
Định nghĩa 2.
1.1. CÁC KHÁI NIỆM VỀ ĐỒ THỊ
1.1. CÁC KHÁI NIỆM VỀ ĐỒ THỊ
Đơn đồ thị có thể là đa đồ thị ngược lại có thể không.
Đồ thị có đỉnh có khuyên -> Giả đồ thị vô hướng
C
D
F
E
A
Hình 4: Giả đồ thị vô hướng
1.1. CÁC KHÁI NIỆM VỀ ĐỒ THỊ
Giả đồ thị vô hướng

G(V,E); E là tập các cặp không có thứ tự gồm 2 phần tử(không nhất thiết phải khác nhau) của V gọi là cạnh.
Cạnh e được gọi là khuyên nếu e = (u,u);
C
D
F
E
A
Hình 4: Giả đồ thị vô hướng
1.1. CÁC KHÁI NIỆM VỀ ĐỒ THỊ
C
D
F
E
A
Hình 4: Đồ thị có hướng
Đồ thị có hướng:
G(V,E); E là tập các cặp có thứ tự gồm 2 phần khác nhau của V, được gọi là các cung.
ĐƠN VÀ ĐA ĐỒ THỊ
- Đồ 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ắt là đồ 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ị.

1.1. CÁC KHÁI NIỆM VỀ ĐỒ THỊ
1.1. CÁC KHÁI NIỆM VỀ ĐỒ THỊ
Các phần sau sẽ nghiên cứu:
Đồ thị vô hướng
Đồ thị có hướng
1.2. CÁC THUẬT NGỮ CƠ BẢN
Đỉnh kề:
Nếu hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu tồn tại cạnh (u,v) của đồ thị.
Ta nói cạnh (u,v) là liên thuộc với 2 đỉnh u, v.
u là đỉnh đầu, v là đỉnh cuối.
3
1
4
5
2
Hình 5. Đồ thị vô hướng
Danh sách liền kề - Adjacency Lists
Một bảng với mỗi hàng cho một đỉnh và liệt kê các đỉnh kề với nó.
a
b
d
c
f
e
1.2. CÁC THUẬT NGỮ CƠ BẢN
1.2. CÁC THUẬT NGỮ CƠ BẢN
Bậc của đỉnh : deg(v);
Bậc của đỉnh v là số đỉnh liền kề với nó (số cạnh liên thuộc với v)

Deg(1)=3
Deg(3)=2,…
Bậc 0 là đỉnh cô lập, bậc 1 là đỉnh treo.
3
1
4
5
2
Hình 5. Đồ thị vô hướng
1.2. CÁC THUẬT NGỮ CƠ BẢN
Định lý 1.
Giả sử G=(V,E) vô hướng có m cạnh. Khi đó tổng bậc của tất cả các đỉnh bằng 2 lần số cung.
Chứng minh:
Với mỗi cạnh ta tính bậc của đỉnh đầu u và đỉnh cuối v
Do đó tổng số bậc của 1 cạnh là deg(u)+deg(v) suy ra tổng số bậc của cả đồ thị là m *2.
Hệ quả:
Trong đồ thị vô hướng, số đỉnh có bậc là 1 số lẻ( đỉnh bậc lẻ) là số chẵn.
3
1
4
5
2
Hình 5. Đồ thị vô hướng
Bán bậc ra và bán bậc vào của đỉnh v
Bán bậc ra là số cung đi ra từ v : deg+(v)
Bán bậc vào là số cung đi vào đỉnh v : deg-(v)
1.2. CÁC THUẬT NGỮ CƠ BẢN
C
D
F
E
A
Hình 5. Đồ thị có hướng
1.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNG
Định nghĩa 1. Cho G = (V, E) là một đồ thị vô hướng:
Đường đi độ dài n từ đỉnh u đến đỉnh v (với n>0) là:
x0, x1,…, xi, xi+1,…, xn-1, xn
Trong đó u= x0 , v=xn, (xi, xi+1)  E, i=0,1,2..n-1

Ta có : x0, x1,…, xi, xi+1,…, xn-1, xn
có thể được viết như sau:
(x0, x1), (x1, x2),,…, (xn-1, xn)
Đỉnh u được gọi là đỉnh đầu, v đỉnh cuố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.
1.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNG
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.
- Ký hiệu: n là số đỉnh, m là số cạnh của một đồ thị.
Chu trình đơn: là chu trình mà các đỉnh trên nó khác nhau từng đôi(không có cạnh nào lặp lại).
1.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNG
a, d, c, f, e
a, d, c, f, e, a
d, e, c, a

1.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNG
Đồ thị liên thông:
Đồ thị G là liên thông nếu tìm được đường đi giữa 2 đỉnh bất kỳ.
a
b
d
c
e
f
g
Đồ thị G liên thông
1.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNG
Đồ thị con
Giả sử G = (V, E) là một đồ thị.
- Đồ thị H = (W, F) được gọi là đồ thị con của đồ thị G nếu:
W  V và F  E
c
d
a
b
e
f
G=({a,b,c,d,e,f},
{ (a,b),(a,d),(a,e),(b,c),
(b,e),(b,f), (c,d),(c,f) } )
H=({a,d,e},
{ (a,d),(a,e)(d,e) } )
1.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNG
Thành phần liên thông của đồ thị
- Khi đồ thị không liên thông thì nó sẽ có các đồ thị con liên thông thì ta gọi các đồ thị con này là các thành phần liên thông của đồ thị
1
2
6
4
5
Đồ thị Không liên thông
3
1.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNG
Đỉnh rẽ nhánh
Nếu ta loại bỏ đỉnh v và các cung đi từ v thì sẽ làm tăng số thành phần liên thông, đỉnh v đó gọi là đỉnh rẽ nhánh.
a
b
d
c
e
f
g
Đỉnh d và e là đỉnh rẽ nhánh
1.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNG
Đỉnh rẽ nhánh
Nếu ta loại bỏ đỉnh v và các cung đi từ v thì sẽ làm tăng số thành phần liên thông, đỉnh v đó gọi là đỉnh rẽ nhánh.
a
b
c
f
g
Đỉnh d và e là đỉnh rẽ nhánh
1.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNG
Cạnh cầu
Nếu cạnh e mà bị loại bỏ khỏi đồ thị mà làm tăng số thành phần liên thông thì e được gọi là cạnh cầu
a
b
d
c
e
f
g
Cạnh (d,f) và (e,g) là các cạnh cầu
1.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNG
Đồ thị liên thông mạnh:
Đồ thị có hướng G=(V,A) được gọi là liên thông mạnh nếu luôn luôn tìm được đường đi giữa hai đỉnh bất kỳ.
c
a
b
d
e
Đồ thị G liên thông mạnh
c
a
b
d
e
Đồ thị H liên thông yếu
Đồ thị định hướng:
Đồ 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
1.3. ĐƯỜNG ĐI, CHU TRÌNH VÀ ĐỒ THỊ LIÊN THÔNG
a) Đồ thị định hướng b) Đồ thị không định hướng
5
4
3
2
1
5
4
3
2
1
1.4. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT
Đồ thị đầy đủ:
Đồ thị đầy đủ có n đỉnh(ký hiệu là Kn) là đồ thị vô hướng mà 2 đỉnh bất kỳ của nó có cạnh nối.
K3
K4
K5
Đồ thị đầy đủ có n đỉnh thì có n(n-1) / 2 cạnh
1.4. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT
Đồ thị vòng:
Đồ thị vòng Cn, n3, gồm n đỉnh V1, V2,..,Vn và các cạnh (V1,V2).(V2,V3),…,(Vn-1,Vn), (Vn,V1).
C3
C4
C5
Các đồ thị vòng
V3
V2
V1
V2
V3
V4
V1
V4
V5
V3
V2
V1
1.4. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT
Đồ thị bánh xe:
Đồ thị bánh xe Wn thu được từ Cn bằng cách bổ sung vào một số đỉnh nối với tất cả các đỉnh của Cn.
W4
W5
Các đồ thị bánh xe
V3
V2
V1
V2
V3
V4
V1
V4
V5
1.4. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT
Đồ thị lập phương:
Đồ thị lập phương có n đỉnh Qn là đồ thị với các đỉnh biểu diễn 2n xâu nhị phân đọ dài n.
Hai đỉnh của nó gọi là kề nhau nếu như hai xâu nhị phân tương ứng chỉ khác nhau 1 bit.
Q1
Q2
Các đồ thị lập phương
0
10
11
01
00
1
010
011
001
000
100
110
111
101
Q3
1.4. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT
Đồ thị hai phía:
Đồ thị G = (V,E) được gọi là đồ thị 2 phía nếu tập V phân hoạch thành X và Y sao cho mỗi cạnh của đồ thị chỉ nối được 1 đỉnh nào đó trong X với 1 đỉnh nào đó trong Y.
G= (XY, E).
Đơn đồ thị là đồ thị hai phía(định lý)
Đơn đồ thị là đồ thị hai phía khi và chỉ khi nó không chứa chu trình độ dài lẻ.
Đồ thị hai phía K2,3
1
2
3
4
5
1.4. MỘT SỐ DẠNG ĐỒ THỊ ĐẶC BIỆT
Đồ thị phẳng:
Đồ thị G = (V,E) được gọi là đồ thị phẳng nếu ta có thể vẽ nó trên mặt phẳng sao cho các canhjh của nó không cắt nhau ngoài ở đỉnh. (Biểu diễn phẳng của đồ thị)
Đồ thị phẳng
V3
V2
V1
V4
V3
V4
V1
V2
1.5. BIỂU DIỄN ĐỒ THỊ
TRONG MÁY TÍNH
Đồ thị có trọng số (weighted graph).
5
4
3
2
1
Đồ thị không có trọng số:

Biểu diễn bằng ma trận kề
Biểu diễn bằng danh sách kề
Danh sách cạnh
1.5. BIỂU DIỄN ĐỒ THỊ
TRONG MÁY TÍNH
1.5.1. Biểu diễn bằng ma trận kề
(adjacency matrice)
Xét một đồ thị G (V, E) định hướng với V gồm có n đỉnh (n >= 1) mà giả sử các đỉnh đã được đánh số theo một quy định nào đó.

Ma trận kề A biểu diễn G là một ma trận vuông kích thước n×n.

Các phần tử của ma trận có giá trị 0 hoặc 1.
Nếu phần tử aịj=1 thì điều đó có nghĩa là tồn tại mọt cung định hướng (vi, vj) trong E;
còn aij=0 thì không tồn tại cung như vậy.
1.5.1. Biểu diễn bằng ma trận kề
(adjacency matrice)
A=
0 1 2 3 4 5 6 7
0
1
2
3
4
5
6
7
Rõ ràng với đồ thị không định hướng thì ma trận kề biểu diễn nó có các phần tử đối xứng qua đường chéo chính, nghĩa là có phần tử bằng 1 ở hàng i cột j thì cũng có phần tử 1 ở hàng j cột i.

Còn đồ thị định hướng thì không phải như vậy.
1.5.1. Biểu diễn bằng ma trận kề
(adjacency matrice)
1.5.1. Biểu diễn bằng ma trận kề
(adjacency matrice)
1.5.1. Biểu diễn bằng ma trận kề
(adjacency matrice)
1.5.1. Biểu diễn bằng ma trận kề
(adjacency matrice)
1.5.1. Biểu diễn bằng ma trận kề (adjacency matrice)
1.5.1. Biểu diễn bằng ma trận kề (adjacency matrice)
A=
2
3
4
5
1
1
2
3
4
5
0
100


60
100
0
98
55
170

98
0

250

55

0

60
170
250

0
1.5.1. Biểu diễn bằng ma trận kề (adjacency matrice)
Đối với đồ thị có trọng số thì ma trận kề có thể lập bằng cách thay giá trị 1 bởi trọng số tương ứng của các cung.

Ta cũng thấy ngay không gian nhớ cần cho cách biểu diễn này là các bit (với đồ thị không định hướng thì có thể giảm bớt một nửa bằng cách chỉ lưu trữ phần trên (hoặc dưới), đường chéo chính bằng một ma trận tam giác).

Trong trường hợp mà đồ thị có ít cung (ma trận kề chứa nhiều phần tử 0), thì ta thấy ngay nhược điểm của cách biểu diễn này.

Điều đó sẽ khắc phục trong cách biểu diễn tiếp theo.
Nhận xét
1.5.2. Biểu diễn bằng danh sách kề
1.5.2. Biểu diễn bằng danh sách kề
Trong cách biểu diễn này, n hàng của ma trận kề được thay bởi n danh sách móc nối.

Với mỗi đỉnh của G có một danh sách tương ứng.

Các nút trong danh sách thứ i biểu diễn các đỉnh lân cận của nút i.

Mỗi nút có hai trường tên đỉnh và trường liên kết.
[0]
[1]
[2]
[3]
1
2
0
2
3
0
1
3
1
2
0
1
2
3
1.5.2. Biểu diễn bằng danh sách kề
1.5.2. Biểu diễn bằng danh sách kề
// Định nghĩa một đỉnh (Node)
typedef struct Node{
Data info; //Mô tả đỉnh : số thứ tự đỉnh,hoặc tên đỉnh
Node * Next ;
};
// Khai báo mảng các danh sách liên kết G
Node *G[MAX];
Đây là mảng cong trỏ các đỉnh, mỗi đỉnh là một nút con trỏ.
2.3.Danh sách cạnh
(đồ thị không có trọng số)
1
2
3
4
Đầu Cuối
cạnh 1: 1 2
cạnh 2: 1 3
cạnh 3: 2 4
cạnh 2: 3 4



Dùng một mảng các cạnh để lưu trữ
Mỗi cạnh là 1 bản ghi gồm có đỉnh đầu và đỉnh cuối
2.3.Danh sách cạnh
(đồ thị không có trọng số)
typedef struct Canh{
int dau, cuoi;
};
Canh DC[MAX]; // mảng DC để lưu danh sách cạnh

Chúng ta cũng có thể sử dụng ds liên kết để lưu các cạnh của đồ thị
Nếu đồ thị có trọng số thì ta thêm vào Canh thành phần trọng số.
2.3.Danh sách cạnh
(đồ thị có trọng số)
Đầu Cuối trọng số
cạnh 1: 1 2 1
cạnh 2: 1 3 3
cạnh 3: 1 6 2
cạnh 4: 2 3 5
cạnh 5: 2 4 1
cạnh 6: 3 4 2
cạnh 7: 3 5 1
cạnh 8: 4 5 4
cạnh 9: 5 6 5
2.3.Danh sách cạnh
(đồ thị có trọng số)
typedef struct Canh{
int d,c; // d: dinh dau , c: dinh cuoi
int trongso;
};
Canh DC[100]; // danh sách cạnh có trọng số