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 1CÁC KHÁI NIỆM CƠ BẢN CỦA LÝ THUYẾT ĐỒ THN
(9 tiết)
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),

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:

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

(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) =
∑∑
∈∈

(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
≠

) = 2m
i
+1 với i=1,2 ,k và deg(v
j
) = 2m
j
với j=k+1, ,n.
m
i
,m
j
là các số nguyên dương.
Theo định lý 1
ta có: deg(G) =
∑∑
+==
+
n
kj
j
k
i
i
vv
11
)deg()deg( = 2|V| = 2n
Do
∑∑∑
===
+=+=

n
kj
j
k
i
i
vv
11
)deg()deg(
=
kmmmkm
n
kj
j
k
i
i
k
i
n
kj
ji
+








v
ik+1
, Trong
đó vij
V∈ là các đỉnh, eij∈E là các cạnh sao cho với k}{1,2, ,∈∀j thì đỉnh v
ij
và đỉnh v
ij+1
là hai
đỉnh kề nhau. Đường đi đó xuất phát từ đỉnh v
ij
và kết thúc tại đỉnh v
ik+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:
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ

NguyÔn Minh §øc - §HQG Hµ Néi
6
c
a
d Trong đồ thị trên ta có:
a,c,d là một đường đi có độ dài 2
c,d,a,b là một đường đi có độ dài 3
a,b,d,a là một chu trình có độ dài 3
a,c,d,b,d,a là một chu trình có độ dài 5
a,c,b không phải là một đường đi
a,b,c,a không phải là một chu trình
Định nghĩa 11:
Đường hay chu trình trong đồ thị được gọi là đơn nếu nó đi qua mỗi cạnh (cạnh của đường hay
chu trình) không quá một lần.
Đường hay chu trình trong đồ thị được gọi là sơ cấp nếu nó đi qua mỗi đỉnh đúng một lần.
Ví dụ 14:
Với đồ thị trên ta có:
a,b,c,d là một đường đi đơn trong đồ thị
d,a,b,c,d là một chu trình đơn trong đồ thị
a,b,c,d,a là một chu trình sơ cấp của đồ thị
a,b,c là một đường sơ cấp
Định lý 3:
Giả sử G = (V,E) là đồ thị vô hướng. Nếu trong đồ thị mà mỗi đỉnh v
∈

v
i0 Theo giả thiết deg(v
ij
) ≥2 nên phải tồn tại ít nhất một đỉnh v
i0
và một cạnh nối đỉnh vi1 và vi0.
Đỉnh vi0 phải trùng với một đỉnh, chẳng hạn là đỉnh vij trong đường w, vì nếu không trùng thì
đường w không phải là đường sơ cấp dài nhất, điều này trái với giả thiết w là đường có độ dài lớn
nhất. Điều này chứng tỏ phải tồn tại một chu trình trong đồ thị đang xét. Vì các đường đang xét là
các đường sơ cấp, cho nên chu trình này là chu trình sơ cấp. Định lý đã được chứng minh.
1.4 Đồ thị con, đồ thị bộ phận và đồ thị liên thông
Định nghĩa 12:
Cho đồ thị G = (V,E)
a) Nếu trong đồ thị G ta bỏ đi một số đỉnh nào đó và các cạnh chứa các đỉnh đó thì phần còn lại
của đồ thị được gọi là đồ thị con của đồ thị G.
b) Nếu trong đồ thị G ta bỏ đi một số cạnh nào đó và giữ nguyên các đỉnh thì phần còn lại của đồ
thị được gọi là đồ thị bộ phận của đồ thị G.
Ví dụ 15:
Đồ thị G

Một số đồ thị con của đồ thị G


Các đồ thị không liên thông
Định nghĩa 14:
Cho đồ thị có hướng G = (V,E)
a) Đồ thị G đượ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ó.
b) Đồ thị G được gọi là liên thông yếu nếu đồ thị vô hướng tương ứng với nó là đồ thị liên
thônng.
Ví dụ 17:
Đồ thị liên thông mạnh

Đồ thị liên thông yếu Định nghĩa 15:
Cho đồ thị G = (V,E), H = (W,F) là đồ thị con của G.
Nếu H là đồ thị liên thông thì H được gọi là thành phần liên thông của G.
Ví dụ 18:



R
Chứng minh:
Trước tiên ta xác định biểu diễn phẳng của G. Ta sẽ chứng minh định lý bằng cách xây dựng một
dãy các đồ thị con G1, G2, ,Ge = G, ở mỗi bước ghép thêm một cạnh vào đồ thị ở bước trước. Để
làm điều này ta sử dụng định nghĩa đệ quy say: Lấy tuỳ ý một cạnh của G để nhận được G
1
.
Để nhận được G
n
từ G
n-1
ta thêm tuỳ ý một cạnh liên thuộc với một cạnh của G
n-1
và thêm một đỉnh
khác liên thuộc với cạnh mới đó nếu đỉnh đó chưa có trong G
n-1
, điều này làm được vì G là liên
thông. G sẽ nhận được sau khi e cạnh được ghép thêm vào các đồ thị tạo ra trước. Gọi r
n
, e
n
, và v
n

tương ứng là số miền, số cạnh, số đỉnh của biểu diễn phẳng của G
n
sinh ra. Ta sẽ chứng minh bằng
quy nạp biểu thức r = e – v +2
Với G

đã thuộc G
n
. Khi đó nó phải ở trên biên của miền chung
R nếu không thì không thể gộp cạnh (a
n+1
,b
n+1
) vào G
n
mà không có các cạnh cắt nhau (G
n+1
là
phẳng). Cạnh mới này sẽ chia miền R thành hai miền con. Do đó r
n+1
=r
n
+1, e
n+1
= e
n+1
, v
n+1
= vn.
Do vậy ta có công thức r
n+1
= e
n+1
– v
n+1
+2. Trường hợp này được minh hoạ như sau:

n+1
= e
n
+1 và
v
n+1
= v
n
+1. Mỗi vế của công thức không đổi nên công thức vẫn đúng, hay r
n+1
=e
n+1
– v
n+1
+2.
Trường hợp này được minh hoạ như sau:
Vậy với mọi n ta đều có r
n
= e
n
– v
n
+2. Vì đồ thị gốc là G
e

Bài 2:
Vẽ đồ thị vô hướng và đồ thị có hướng cho bởi G = (V,E)
V = {A, B, C, D, E, G, H}
G = {(A,B), (B,C), (A,C), (G,H), (H,E), (E,A), (D,A)}

Bài 3:
Hãy tìm số đỉnh, số cạnh, bậc của mỗi đỉnh trong các đồ thị vô hướng cho dưới đây. Xác
định các đỉnh cô lập và đỉnh treo. Xác định bậc của đồ thị và kiểm tra xem nó có bằng hai lần số
cạnh không?

v2 v1
e4 e3 e2 e1
Hãy tìm số đỉnh, số cạnh, bậc ra, bậc vào và bậc của mỗi đỉnh trong các đồ thị vô hướng cho
dưới đây. Xác định các đỉnh cô lập và đỉnh treo. Xác định bậc của đồ thị và kiểm tra xem nó có bằng
hai lần số cạnh không? Bài 5:
Có tồn tại đồ thị đơn có 10 đỉnh, mỗi đỉnh có bậc bằng 5 không?
Bài 6:
Trong một cuộc liện hoan mọi người bắt tay nhau. Hãy chỉ ra rằng tổng số lượt người được
bắt tay được bắt tay là một số chẵn.(Giả sử rằng không ai tự bắt tay mình)
Bài 7:
Liệt kê tất cả các đồ thị con của đồ thị sau


v4
v5
e6
e5
v1
v2
v3
v4
e6 e5
e1
e2
e3 e4
a
b
d
c
e
Bài 11:
Chỉ ra tất cả các đường sơ cấp và chu trình sơ cấp có thể có của đồ thị sau

G1 G2 G3
G4 G5