Bài giảng Lý thuyết đồ thị - Chương 1: Các khái niệm cơ bản của lý thuyết đồ thị - Nguyễn Trần Phi Phượng

Chương 1
CÁC KHÁI NIỆM CƠ BẢN CỦA 
LÝ THUYẾT ĐỒ THỊ
218/02/2011
1.1 Định nghĩa đồ thị
Lý thuyết đồ thị
Định nghĩa 1.
Đơn đồ thị vô hướng 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.
Ví dụ
a. Đơn đồ thị vô hướng b. Không phải đơn đồ thị
vô hướng do có các cặp
cạnh nối cùng một cặp
đỉnh
c. Không phải đơn đồ thị
vô hướng do có cạnh nối
một đỉnh với chính nó.
318/02/2011
1.1 Định nghĩa đồ thị
Lý thuyết đồ thị
Định nghĩa 2.
Đ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 song song nếu chúng cùng tương ứng một cặp
đỉnh.
Ví dụ
Đa đồ thị vô hướng. e1 và e2 là
các cạnh song song.
e1e2
418/02/2011
1.1 Định nghĩa đồ thị
Lý thuyết đồ thị
Định nghĩa 3.
Giả đồ 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ông nhất thiết phải khác nhau) của V gọi là các cạnh.
Cạnh e được gọi là khuyên nếu nó có dạng e=(u,u).
Ví dụ
Giả đồ thị vô hướng. e
là khuyên
e
518/02/2011
1.1 Định nghĩa đồ thị
Lý thuyết đồ thị
Định nghĩa 4.
Đơn đồ thị có hướng G = (V,E) bao gồm V là tập các
đỉnh, và E là tập 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.
Ví dụ
a. Đơn đồ thị có hướng b. Không phải đơn đồ thị
có hướng do có cặp cạnh
nối cùng một cặp đỉnh
618/02/2011
1.1 Định nghĩa đồ thị
Lý thuyết đồ thị
Định nghĩa 5.
Đ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 song song.
Ví dụ
e2 e1
Đa đồ thị có hướng. e1 và e2 là
các cung song song
718/02/2011
1.2 Các thuật ngữ cơ bản
Lý thuyết đồ thị
Xét đồ thị vô hướng G = (V,E)
– Nếu e = (u,v) là một cạnh của G thì:
• Hai đỉnh u, v được gọi là hai đỉnh kề nhau
• Cạnh e được gọi là cạnh liên thuộc với đỉnh u và
đỉnh v
• Đỉnh u, đỉnh v được gọi là đỉnh đầu của cạnh e
– Bậc của một đỉnh v (deg(v))
là số cạnh liên thuộc với nó.
– VD: deg(0) = 3, deg(5) = 4,
deg(2) = 6, deg(8) = 2,
u
v
e
818/02/2011
1.2 Các thuật ngữ cơ bản
Lý thuyết đồ thị
Đỉnh có bậc 0 được gọi là đỉnh cô lập.
Đỉnh có bậc 1 được gọi là đỉnh treo.
Định lý. Xét đồ thị vô hướng G = (V,E). Khi đó, tổng bậc
của tất cả các đỉnh của đồ thị sẽ bằng hai lần số cạnh của
nó.
deg( ) 2 | |
v V
v E
Hệ quả. Trong đồ thị vô
hướng, số đỉnh bậc lẻ là một
số chẵn.
918/02/2011
1.2 Các thuật ngữ cơ bản
Lý thuyết đồ thị
Xét đồ thị có hướng G = (V,E)
– Nếu e = (u,v) là một cung của G thì:
• Đỉnh v được gọi là đỉnh kề của đỉnh u
• Cung e được gọi là cung đi ra khỏi đỉnh u và là cung đi vào
đỉnh v
• Đỉnh u được gọi là đỉnh đầu của cung e, đỉnh v được gọi là đỉnh
cuối của cạnh e
– Bán bậc ra của một đỉnh v (deg+(v))
là số cung đi ra khỏi nó.
– Bán bậc vào của một đỉnh v (deg-(v))
là số cung đi vào nó.
– VD: deg+(t) = 1, deg-(t) = 1,
deg+(v) = 0, deg-(v) = 3,
u
v
e
t
s x
1018/02/2011
1.2 Các thuật ngữ cơ bản
Lý thuyết đồ thị
Định lý. Xét đồ thị có hướng G = (V,E). Khi đó, tổng
bán bậc ra của tất cả các đỉnh sẽ bằng tổng bán bậc vào
của tất cả các đỉnh và bằng số cung của đồ thị.
deg ( ) deg ( ) | |
v V v V
v v E
1118/02/2011
1.2 Các thuật ngữ cơ bản
Lý thuyết đồ thị
Định nghĩa. Xét đồ thị G = (V,E). Đồ thị H = (W,F) là
một đồ thị con của G nếu và chỉ nếu mọi đỉnh của H
cũng là đỉnh của G và mọi cạnh/cung của H cũng là
cạnh/cung của G. (W V, F E).
Ví dụ: 321
54
1 2
54
Đồ thị con của G
321
54
Đồ thị con của G
321
54
Không là đồ thị con của G
1218/02/2011
1.2 Các thuật ngữ cơ bản
Lý thuyết đồ thị
Định nghĩa. 
Cho hai đồ thị G=(V,E) và G’=(V’,E’). Ta nói rằng G đẳng
cấu G’, ký hiệu G G’, nếu tồn tại song ánh f:V→ V’ sao
cho:
uv là cạnh của G f(u)f(v) là cạnh của G
1318/02/2011
1.3 Đường đi, chu trình, đồ thị liên thông
Lý thuyết đồ thị
Đị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ị 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.
Đỉnh u gọi là đỉnh đầu, đỉ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 không có cạnh/cung nào xuất hiện quá một lần
được gọi là đường đi đơn.
Đường đi không có đỉnh nào xuất hiện quá một lần được gọi
là đường đi sơ cấp.
1418/02/2011
1.3 Đường đi, chu trình, đồ thị liên thông
Lý thuyết đồ thị
Ví dụ:
Các đường đi từ 1 đến 5:
d1: 1 2 5
d2: 1 2 4 3 9 2 5
d3: 1 9 2 3 9 2 5
Các chu trình trong đồ thị:
C1: 1 2 9 1
C2: 1 9 0 3 9 2 1
C3: 1 9 2 3 9 1
Độ dài 2
Độ dài 6
Độ dài 6
Độ dài 3
Độ dài 6
Độ dài 5
Đường đi sơ cấp
(hiển nhiên đơn)
Đường đi đơn
(không sơ cấp)
Đường đi không
đơn (không sơ
cấp)
Chu trình sơ cấp (hiển nhiên đơn)
Chu trình đơn (không sơ cấp)
Chu trình không đơn (không sơ cấp)
1518/02/2011
1.3 Đường đi, chu trình, đồ thị liên thông
Lý thuyết đồ thị
Ví dụ:
Các đường đi từ a đến e:
d1: a b e
d2: a b c f b e
Các chu trình trong đồ thị:
C1: a b e d a
C2: a d c f e d a
C3: a b e d c f e d a
Độ dài 2
Độ dài 5
Độ dài 4
Độ dài 6
Độ dài 8
Đường đi sơ cấp
(hiển nhiên đơn)
Đường đi đơn
(không sơ cấp)
Chu trình sơ cấp (hiển nhiên đơn)
Chu trình đơn (không sơ cấp)
Chu trình không đơn (không sơ cấp)
c b a
def
1618/02/2011
1.3 Đường đi, chu trình, đồ thị liên thông
Lý thuyết đồ thị
Định nghĩa 2.
Đồ 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ó.
Đồ thị vô hướng liên thông Đồ thị vô hướng không liên thông
1718/02/2011
1.3 Đường đi, chu trình, đồ thị liên thông
Lý thuyết đồ thị
Một đồ thị không liên thông là hợp của nhiều đồ thị con
liên thông rời nhau. Mỗi đồ thị con này được gọi là một
thành phần liên thông của đồ thị ban đầu.
Đồ thị trên có 3 thành phần liên thông
1818/02/2011
1.3 Đường đi, chu trình, đồ thị liên thông
Lý thuyết đồ thị
Định nghĩa 3.
Đỉnh v được gọi là đỉnh rẽ nhánh (đỉnh khớp) 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ị.
Ví dụ:
Đỉnh khớp: e, x, y
Cầu: (e,x), (y,w)
1918/02/2011
1.3 Đường đi, chu trình, đồ thị liên thông
Lý thuyết đồ thị
Định nghĩa 4.
Đồ thị có hướng G=(V,E) đượ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,E) đượ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.
Ví dụ:
Đồ thị có hướng không liên thông yếu 
(hiển nhiên không liên thông mạnh)
Đồ thị có hướng liên thông mạnh 
(hiển nhiên cũng là liên thông yếu)
2018/02/2011
1.4 Một số dạng đồ thị đặc biệt
Lý thuyết đồ thị
Đồ thị đầy đủ.
Đồ thị đầy đủ n đỉnh, ký hiệu là Kn là đơn đồ thị vô hướng
mà giữa hai đỉnh bất kỳ của nó luôn có cạnh nối.
Số đỉnh: n
Số cạnh:
Bậc của mỗi đỉnh: n-1
( 1)
2
n n
2118/02/2011
1.4 Một số dạng đồ thị đặc biệt
Lý thuyết đồ thị
Đồ 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)
Số đỉnh: n
Số cạnh: n
Số bậc của mỗi đỉnh: 2
C3 C4 C5 C6
2218/02/2011
1.4 Một số dạng đồ thị đặc biệt
Lý thuyết đồ thị
Đồ thị bánh xe.
Đồ thị Wn thu được từ Cn bằng cách bổ sung vào một đỉnh
mới nối với tất cả các đỉnh của Cn
Số đỉnh: n+1
Số cạnh: 2n
n đỉnh bậc 3, 1 đỉnh bậc n
2318/02/2011
1.4 Một số dạng đồ thị đặc biệt
Lý thuyết đồ thị
Đồ thị lập phương.
Đồ thị lập phương Qn là đồ thị với các đỉnh biểu diễn 2
n
chuỗi nhị phân độ dài n. Hai đỉnh của nó kề nhau nếu hai chuỗi
nhị phân tương ứng chỉ khác nhau 1 bit.
Số đỉnh: 2n
Số cạnh: n.2n-1
Bậc của mỗi đỉnh: n
2418/02/2011
1.4 Một số dạng đồ thị đặc biệt
Lý thuyết đồ thị
Đồ thị lưỡng phân (đồ thị hai phía).
Đơn đồ thị G=(V,E) được gọi là lưỡng phân nếu như tập
đỉnh V của nó có thể phân hoạch thành hai tập X và Y sao cho
mỗi cạnh của đồ thị chỉ nối một đỉnh nào đó trong X với một
đỉnh nào đó trong Y.
2518/02/2011
1.4 Một số dạng đồ thị đặc biệt
Lý thuyết đồ thị
Đồ thị lưỡng phân đầy đủ.
Đồ thị G=(V,E) được gọi là lưỡng phân đầy đủ nếu G là đồ
thị lưỡng phân và mọi cặp đỉnh giữa hai tập X và Y đều được
nối với nhau.
Số đỉnh: m + n
Số cạnh: m n
m đỉnh bậc n,
n đỉnh bậc m
X Y
K3x4
2618/02/2011
1.4 Một số dạng đồ thị đặc biệt
Lý thuyết đồ thị
Ví dụ
?
Không là đồ thị lưỡng phân
Đồ thị lưỡng phân
Định lý:
Một đồ thị vô hướng là đồ thị lưỡng phân khi và chỉ khi nó
không chứa chu trình với độ dài lẻ