Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ
NguyÔn Minh §øc - §HQG Hµ Néi
1
v2
v1 v3
v4
....
e1
e2
e3
e4
€GIÁO ÁN
MÔN LÝ THUYẾT ĐỒ THN
Số tiết học: 60 tiết ( 45 tiết lý thuyết + 15 tiết thực hành)
Tài liệu tham khảo:
1) Toán rời rạc, PGS. TS Đỗ Đức Giáo, Nhà xuất bản Đại học Quốc gia Hà Nội 2002
2) Toán rời rạc, Nguyễn Đức Nghĩa, Nguyễn Tô Thành, Nhà xuất bản Đại học Quốc gia Hà Nội
2003
3) Giáo trình Lý thuyết đồ thị, Nguyễn Thanh Hùng, Nguyễn Đức Nghĩa
4) Toán học rời rạc ứng dụng trong tin học, Dịch từ Discrete Mathematics and Its Applications,
Nhà xuất bản khoa học kỹ thuật
Chương 1
CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THN
(9 tiết)
1.1 Giới thiệu
Lý thuyết đồ thị là nghành khoa học đã có từ lâu nhưng lại có rất nhiều ứng dụng hiện đại. Những
ý tưởng cơ sở ban đầu của nó được đưa ra từ những năm đầu thế kỷ 18 bởi nhà toán học người Thuỵ
Sỹ là Leonhard Euler.
Lý thuyết đồ thị được dùng để giải quyết các bài toán thuộc nhiều lĩnh vực khác nhau. Chẳng
hạn: Dùng mô hình đồ thị để xác định xem hai máy tính trong một mạng máy tính có trao đổi thông
tin được với nhau hay không?. Đồ thị với các trọng số được gắn cho các cạnh có thể dùng để giải
quyết bài toán tìm đường đi ngắn nhất giữa hai thành phố trong một mạng lưới giao thông. Chúng ta
cũng có thể phân biệt các hợp chất hoá học có cùng công thức phân tử nhưng có cấu trúc khác nhau
nhờ vào đồ thị...
1.2 Các định nghĩa và tính chất cơ bản
Định nghĩa 1:
Giả sử V là một tập khác rỗng các phần tử nào đó và VxVE ⊆ (E là tập con của tích đề các
VxV). Bộ G = (V, E) được gọi là một đồ thị.
Mỗi phần tử Vv ∈được gọi là một đỉnh của đồ thị, V được gọi là tập các đỉnh của đồ thị.
Mỗi phần tử Evue ∈= ),( được gọi là một cạnh của đồ thị, E được gọi là tập các cạnh của đồ thị.
Ví dụ 1:
G = (V = {v1, v2, v3, v4,...}, E = {e1 = (v1,v2), e2 = (v1,v3), e3 = (v2,v3), e4 = (v3,v4),... })
Như vậy ta có thể hình dung đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh
này với nhau.
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ
NguyÔn Minh §øc - §HQG Hµ Néi
2
Thanh hoá
Nghệ an
Hà nội
TP.HCM
v1
v3 v2
Tây hồ
Hồ gươm CVThủ lệ
TTCPQG
Đồ thị có hướng
Đồ thị vô hướng
v1 v2 v3
e1 e2 e3
Chú ý:
Nếu tập V là tập hữu hạn các phần tử thì G = (V,E) được gọi là đồ thị hữu hạn. Từ đây về sau chủ
yếu ta nghiên cứu các đồ thị hữu hạn. (có thể coi đây là một định nghĩa về đồ thị)
Ví dụ 2:
G = (V={Thanh hoá, Nghệ an, Hà nội, TP.HCM},E={(Thanh hoá,Nghệ an),(Thanh hoá, Hà nội),
(Nghệ an, Hà nội), (Hà nội, TP.HCM) })
Định nghĩa 2:
a) Hai đỉnh được gọi là kề nhau nếu có cạnh nối hai đỉnh đó với nhau. Cạnh nối hai đỉnh được gọi
là cạnh liên thuộc.
b) Hai cạnh được gọi là kề nhau nếu giữa chúng có đỉnh chung.
c) Nếu e = (v,v) là một cạnh của đồ thị thì e được gọi là một khuyên. Trong trường hợp này đồ thị
được gọi là giả đồ thị.
Ví dụ 3:
v1 và v2 được gọi là hai đỉnh kề nhau, e1 được gọi là cạnh liên thuộc hai đỉnh v1 và v2.
e1 và e2 được gọi là hai cạnh kề nhau, e3 được gọi là một khuyên.
Định nghĩa 3:
a) Nếu mỗi cạnh Evue ∈= ),( là không phân biệt thứ tự của các đỉnh u và v, (tức là từ u tới v
không kể hướng) thì ta nói đồ thị G = (V,E) là đồ thị vô hướng.
b) Nếu mỗi cạnh Evue ∈= ),( có phân biệt thứ tự của các đỉnh u và v, (tức là từ u tới v khác với
từ v tới u) thì ta nói đồ thị G = (V,E) là đồ thị có hướng. Cạnh của đồ thị có hướng còn được gọi là
cung.
Ví dụ 4:
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ
NguyÔn Minh §øc - §HQG Hµ Néi
3
R5
R1
R3
R2
R1
Định nghĩa 4:
Đồ thị G =(V,E) được gọi là đơn đồ thị nếu giữa hai đỉnh bất kỳ của đồ thị được nối với nhau bởi
không quá một cạnh (cung).
Ví dụ 5:
Định nghĩa 5:
Đồ thị G = (V,E) được gọi là đa đồ thị nếu có ít nhất một cặp đỉnh được nối với nhau bởi hai cạnh
(hai cung) trở lên.
Ví dụ 6:
Định nghĩa 6:
Đồ thị G = (V,E) được gọi là đồ thị phẳng nếu nó có dạng biểu diễn hình học trên mặt phẳng mà
các cạnh (cung) chỉ cắt nhau ở đỉnh. Cách vẽ như vậy được gọi là biểu diễn phẳng của đồ thị. Trong
trường hợp ngược lại đồ thị là không phẳng.
Ví dụ 7:
Biểu diễn phẳng của một đồ thị chia mặt phẳng thành các miền. Ví dụ biểu diễn phẳng của đồ thị
dưới đây chia mặt phẳng thành 5 miền.
Định nghĩa 7:
Đồ thị G = (V,E) được gọi là đồ thị đầy đủ nếu mỗi cặp đỉnh đều có cạnh (cung) nối giữa chúng.
Ví dụ 8:
Đồ thị phẳng Đồ thị không phẳng
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ
NguyÔn Minh §øc - §HQG Hµ Néi
4
v1
v4 v5
v2
v3
v2
v1
v6
v3
v5 v4
Định nghĩa 8:
Cho đồ thị vô hướng G = (V,E). Với v ∈V là một đỉnh của đồ thị, ta kí hiệu deg(v) là số các cạnh
thuộc đỉnh v, riêng với khuyên thì đựơc tính là 2. deg(v) được gọi là bậc của đỉnh v.
Nếu deg(v) = 0 thì v được gọi là đỉnh cô lập, nếu deg(v) = 1 thì v được gọi là đỉnh treo.
Bậc của đồ thị vô hướng G = (V,E) được kí hiệu là deg(G) và được tính deg(G) = ∑
∈Vv
v)deg(
Ví dụ 9:
Với đồ thị trên ta có:
deg(v5) = 0, v5 được gọi là đỉnh cô lập
deg(v4) = 1, v4 được gọi là đỉnh treo
deg(v3) = 4, deg(v2) = 3, deg(v1) = 2
Định nghĩa 9:
Cho đồ thị có hướng G = (V,E). Với v V∈là một đỉnh của đồ thị, ta ký hiệu deg-(v) là số các
cung vào của đỉnh v, deg+(v) là số các cung ra của đỉnh v. Khi đó deg-(v) được gọi là bậc vào của
đỉnh v, deg+(v) được gọi là bậc ra của đỉnh v và bậc của đỉnh v là deg(v) = deg-(v) + deg+(v).
Nếu deg+(v) = deg-(v) = 0 thì v được gọi là đỉnh cô lập, nếu deg+(v) = 0, deg-(v) = 1 hoặc deg+(v)
= 1, deg-(v) = 0 thì v được gọi là đỉnh treo.
Bậc của đồ thị có hướng G = (V,E) được kí hiệu là deg(G) và được tính deg(G) =
∑∑
∈∈
+− +
VvVv
vv )(deg)(deg
Ví dụ 10:
Với đồ thị trên ta có:
deg-(v1) = 2, deg+(v1) = 5
deg-(v2) = 2, deg+(v2) = 1
deg-(v3) = 1, deg+(v3) = 0, đỉnh v3 được gọi là đỉnh treo
deg-(v4) = deg+(v4) = 0, đỉnh v4 được gọi là đỉnh cô lập
deg-(v5) = 3, deg+(v5) = 0
deg-(v6) = 1, deg+(v6) = 3
Định lý 1:
Giả sử G = (V,E) là đồ thị hữu hạn. Khi đó bậc của đồ thị G bằng hai lần số cạnh của đồ thị, tức
là deg(G) = 2|E|
Chứng minh:
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ
NguyÔn Minh §øc - §HQG Hµ Néi
5
e
d
c
b
a
Giả sử u,v∈V và e = (u,v)∈E
Nhận xét: Giả sử u≠v. Khi đó nếu xoá cạnh (cung) e thì bậc của đồ thị sẽ giảm đi 2. Nếu ta xoá tất
cả các cạnh có dạng như trên thì đồ thị còn lại chỉ gồm các đỉnh cô lập hoặc các đỉnh có khuyên.
Tại mỗi đỉn u có khuyên, nếu ta xoá khuyên thì bậc của đồ thị cũng sẽ giảm đi 2. Như vậy nếu ta
xoá một cạnh hoặc một khuyên thì bậc của đồ thị giảm đi 2 và sau khi xoá hết tất cả các cạnh và các
khuyên của đồ thị thì bậc của đồ thị còn lại là bằng 0.
Từ nhận xét trên, hiên nhiên ta có đẳng thức deg(G) = 2|E| (đpcm)
Định lý 2:
Giả sử G = (V,E) là đồ thị hữu hạn. Khi đó số các đỉnh bậc lẽ của đồ thị là một số chẵn.
Chứng minh:
Giả sử V = {v1,v2,...vn } và trong n đỉnh có k đỉnh bậc lẻ là v1,v2,...,vk. Các đỉnh còn lại có bậc
chẵn là vk+1, vk+2,...vn I Ở đây ta có deg(vi) = 2mi+1 với i=1,2..,k và deg(vj) = 2mj với j=k+1, ...,n.
mi,mj là các số nguyên dương.
Theo định lý 1 ta có: deg(G) = ∑∑ +==
+n
kj
j
k
i
ivv
11
)deg()deg( = 2|V| = 2n
Do ∑∑∑===
+=+= k
i
k
i
ii
k
i
ikmmv
111
2)12()deg(
và ∑∑∑
+=+=+=
==
n
kj
n
kj
n
kj
jjj mmv
111
22)deg(
Suy ra deg(G) = ∑∑ +==
+n
kj
j
k
i
ivv
11
)deg()deg( = kmmmkm
n
kj
j
k
i
i
k
i
n
kj
ji +
+=++ ∑∑∑∑ +===+=1111
222 =2n
Từ đó suy ra k là một số chẵn. (đpcm).
Ví dụ 11:
Có bao nhiêu cạnh trong một đồ thị có 10 đỉnh, mỗi đỉnh có bậc bằng 5?
Giải:
Vì bậc của đồ thị bằng 10.5 = 50, mà 2.e = 50 Suy ra e = 25
1.3 Đường và chu trình trong đồ thị
Định nghĩa 10:
Cho đồ thị G = (V,E). Một đường đi trong đồ thị là một dãy vi1ei1vi2ei2...vijeij...vikeikvik+1, Trong
đó vij V∈là các đỉnh, eij∈E là các cạnh sao cho với k}{1,2,..,∈∀jthì đỉnh vij và đỉnh vij+1 là hai
đỉnh kề nhau. Đường đi đó xuất phát từ đỉnh vij và kết thúc tại đỉnh vik+1(hoặc ngược lại).
Độ dài của đường bằng số các cạnh (hoặc cung) trong đường đi đó.
Chu trình trong đồ thị là một đường đi có đỉnh xuất phát và đỉnh kết thúc trùng nhau.
Ví dụ 12:
Trong đồ thị trên ta co: