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

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:
∈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ớ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
+

Đị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 = {v
1
,v
2
,...v
n
} và trong n đỉnh có k đỉnh bậc lẻ là v
1
,v
2
,...,v
k
. Các đỉnh còn lại có bậc
chẵn là v
k+1
, v
k+2
,...v
n
I Ở đây ta có deg(v
i
) = 2m
i
+1 với i=1,2..,k và deg(v
j
) = 2m
j

i
i
kmmv
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
i

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 v
i1
e
i1
v
i2
e
i2
...v
ij
e
ij
...v
ik
e
ik
v
ik+1
, Trong
đó vij
V∈
là các đỉnh, eij

d
b
c
a
d
b
v
i1
v
i2
v
i3
v
ij
v
ij+1

e
i1
e
i2
e
ij

a,b,e,d là một đường đi có độ dài 3
c,e,b,a,d là một đường đi có độ dài 4
a,d,c,a là một chu trình có độ dài 3
d,a,b,c,d là một chu trình có độ dài 4
a,b,d không phải là một đường đi
a,d,e,a không phải là một chu trình

∈
V đều có bậc deg(v)
≥
2
thì đồ thị có chu trình sơ cấp
Chứng minh:
Xét tất cả các đường sơ cấp có thể có trong đồ thị. Rõ ràng số các đường này là hữu hạn, vì vậy
trong số các đường sơ cấp đó sẽ tồn tại một đường có độ dài lớn nhất. Giả sử đó là đường w:
v
i1
e
i1
v
i2
e
i2
...v
ij
e
ij
v
ij+1
dạng hình học của nó là:

Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ Một số đồ thị con của đồ thị G

Mộ số đồ thị bộ phận của đồ thị G
Định nghĩa 13:
Cho đồ thị G = (V,E)
a) Hai đỉnh u,v
∈
V được gọi là liên thông nếu tồn tại một đường đi nối hai đỉnh u,v với nhau.
b) Đồ thị G được gọi là liên thông nếu với hai đỉnh phân biệt bất kỳ trong đồ thị đều là liên thông.
Ví dụ 16:
Các đồ thị liên thông Đị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:

Trong ví dụ này H, I là các thành phần liên thông của G
Định lý 4:
Đồ thị G = (V,E) là liên thông khi và chỉ khi nó có một thành phần liên thông.
Chứng minh:
Điều khẳng định được trực tiếp suy ra từ các định nghĩa.
Định lý 5: (Công thức Euler)
Cho G = (V,E) là một đơn đồ thị phẳng liên thông với e cạnh và v đỉnh. Gọi r là số miền trong
biểu diễn phẳng của G. Khi đó r = e – v +2.
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞNguyÔn Minh §øc
-
§HQG Hµ Néi

, đ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
1
thì biểu thức r
1
= e
1
– v
1
+ 2 là đúng, vì r1 = 1, e1 = 1, v1 = 2, điều này được thể hiện như
hình sau:

Giả sử ta có r
n
= e
n
– v
n
+ 2.

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:

Trường hợp thứ hai, một trong hai đỉnh của cạnh chưa thuộc G
n
. Ta giả sử a
n+1
thuộc G
n
còn b
n+1

không thuộc. Trong trường hợp này cạnh thêm (a
Vậy với mọi n ta đều có r
n
= e
n
– v
n
+2. Vì đồ thị gốc là G
e
nhận được sau khi thêm e cạnh, định lý
được chứng minh.
Ví dụ 19:
Cho đơn đồ thị G phẳng liên thông có 20 đỉnh, mỗi đỉnh đều có bậc là 3. Hỏi biểu diễn phẳng của
đồ thị này chia mặt phẳng thành bao nhiêu miền?
Giải:
Ta có v = 20, deg(G) = v.3 = 20.3 = 60 = 2.e Suy ra e = 30.
Áp dụng công thức Euler : r = e – v +2 = 12. Vậy mặt phẳng bị chia thành 12 miền. G1
R
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞNguyÔn Minh §øc
-


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?
Bài 4:
G1 G2 G3
G4 G5 G6
G7
G8

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 Bài 8:
Cho đơn đồ thị phẳng liên thông G với 5 đỉnh và 9 cạnh. Hỏi đồ thị này chia mặt phẳng
thành bao nhiêu miền?.

Bài 9:

Có bao nhiêu cạnh trong một đồ thị có 6 đỉnh mà hai đỉnh có bậc 4, hai đỉnh có bậc 6, hai
đỉnh có bậc 8 ?.


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
Bài 12:
Mỗi danh sách các đỉnh sau đây có tạo nên đường đi trong đồ thị đã cho hay không? Đường đi
nào là đơn? Đường đi nào là chu trình? Độ dài của các đường đi này là bao nhiêu?
a)

a, b, e, c, b
b)

a, d, b, e, a G1 G2 G3
G4 G5
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞNguyÔn Minh §øc
-
§HQG Hµ Néi
13
v1
v2
v4
v3
v3
v2
v1

Chương 2

CÁC PH ƯƠNG PHÁP BIỂU DIỄN ĐỒ THN
(6 tiết)

2.1 Biểu diễn bằng hình học
Cho đồ thị G = (V, E), khi đó ta có thể biểu diễn G bằng phương pháp hình học như sau:
Mỗi v
∈

,v
4
), (v
3
,v
4
), (v
4
,v
4
)}) được biểu diễn
hình học như sau:

Đồ thị có hướng G = ({v
1
, v
2
, v
3
}, {(v
1
,v
1
), (v

2
, ..,v
n
}, tập cạnh E = {e
1
, e
2
, .., e
m
}.
Ta gọi ma trận kề của đồ thị G là ma trận:
A = {a
ij
: i,j = 1,2,...,n}
với các phần tử aij được xác định theo quy tắc sau:
a
ij
= 1 nếu (v
i
,v
j
)
∈
E
a
ij
= 0 nếu (v
i
,v
j


NguyÔn Minh §øc
-
§HQG Hµ Néi
14
2
1
4 3 5
1
3
2

V1 v2 v3
v1
1 1 1
v2
1 0 1
v3
1 1 0

Ví dụ 3:
Cho đồ thị vô hướng G như sau:
Ma trận kề của G là



Khi đó
njia
p
ij
,..,2,1,, =
cho ta số đường đi khác nhau từ đỉnh i đến đỉnh j qua p-1 đỉnh trung
gian.

Ma trận kề của đồ thị đơn có hướng cũng được định nghĩa tương tự, nhưng lưu ý ma trận này là
không đối xứng.
Ví dụ 4:
Cho đơn đồ thị có hướng G

Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞNguyÔn Minh §øc
-
§HQG Hµ Néi
15
4
1
2
3
4
5

Ví dụ 5:
Cho đa đồ thị vô hướng G như sau:

Ma trận kề của G là

1 2 3 4 5
1
0 1 1 3 1
2
1 0 1 1 1
3
1 1 1 0 2
4
3 1 0 0 0
5
1 1 2 0 0

Ví dụ 6:
Cho đa đồ thi có hướng G như sau:
v1
0 0 0 0
v2
1 0 2 1
v3
1 1 0 0
v4
1 1 0 0

Trong rất nhiều ứng dụng của lý thuyết đồ thị, mỗi cạnh e = (u,v) của đồ thị được gắn một con số
c nào đó (c(e), c(u,v)) gọi là trọng số của cạnh e. Đồ thị có các cạnh được gán trọng số gọi là đồ thị
có trọng số. Trong trường hợp đồ thị có trọng số, để biểu diễn đồ thị thay vì dùng ma trận kề ta dùng
ma trận trọng số như sau:
C = c
ij
, i,j=1, 2, .., n
Với
cij = c(eij)) nếu eij
∈
E
cij =
θ
nếu eij
∉
E , i = 1,2,..,n; j = 1,2,..,n
Trong đó số
θ
tuỳ từng trường hợp cụ thể, có thể được đặt bằng một trong các giá trị sau: 0, -
∞
,


Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞNguyÔn Minh §øc
-
§HQG Hµ Néi
17
b c
d
e
3
7
7
5
4 9
4
a
v2
v3
e1
v4
e2
v5
e4
e3
e5
e6
v1


2.3 Biểu diễn bằng ma trận liên thuộc đỉnh - cạnh
Giả sử G = (V,E) là một đồ thị vô hướng với tập đỉnh V = {v
1
,v
2
,.., v
n
}, và tập các cạnh E =
{e
1
,e
2
,..,e
m
}. Khi đó ma trận liên thuộc đỉnh - cạnh A = aij, i = 1,2,..n, j = 1,2,...m của nó được xác
định như sau:
A
ij
= 1 nếu cạnh e
j
nối với đỉnh v
i

A
ij
= 0 nếu cạnh e
j
không nối với đinh v
i
, i = 1,2,..,n, j = 1,2,..,m

e8
e7 e6
v1

e1 e2 e3 e4 e5 e6
v1
1 1 0 0 0 0
v2
0 0 1 1 0 1
v3
0 0 0 0 1 1
v4
1 0 1 0 0 0
v5
0 1 0 1 1 0

Ma trận liên thuộc cũng có thể được dùng để biểu diễn đồ thị có cạnh bội và khuyên
Ví dụ 10:
Cho đồ thị G như sau Khi đó ma trận liên thuộc đỉnh cạnh của G là
=-1 nếu đỉnh vi là đỉnh cuối của cung ej
a
ij
= 0 nếu đỉnh vi không là đầu mút của cung ej
e1 e2 e3 e4 e5 e6 e7 e8
v1
1 1 1 0 0 0 0 0
v2
0 1 1 1 0 1 1 0
v3
0 0 0 1 1 0 0 0
v4
0 0 0 0 0 0 1 1
v5
0 0 0 0 1 1 0 0
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞNguyÔn Minh §øc
-
§HQG Hµ Néi
19
6
5
4
3
2

2.4 Biểu diễn bằng danh sách cạnh (cung)
Xét đồ thị G = (V,E), với |V| = n, |E| = m. Để biểu diễn đồ thị theo phương pháp danh sách cạnh
(cung) chúng ta sẽ lưu trữ danh sách tất cả các cạnh (cung) của đồ thị vô hướng (có hướng). Mỗi
cạnh (cung) e = (u,v) của đồ thị sẽ tương ứng với hai biến Dau[e] và Cuoi[e]. Như vậy để lưu trữ đồ
thị ta cần sử dụng 2m đơn vị ô nhớ. Trong trường hợp đồ thị có trọng số ta phải cần thêm m đơn vị ô
nhớ nữa để lưu trữ trọng số của các cạnh.
Ví dụ 12:
Cho đồ thị vô hướng G như sau
Danh sách cạnh của G như sau

Dau Cuoi
1 2
1 3
2 3
2 5
3 4
4 5
4 6
5 6
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞNguyÔn Minh §øc
-

Khi đó, danh sách kề lưu trữ dưới dạng mảng như sau
v1
v2 v4 v5
v2
v1 v3 v4
v3
v2 v4 v5
v4
v1 v2 v3 v5
v5
v1 v3 v4
Danh sách kề lưu trữ dưới dạng danh sách liên kết như sau:

v1
v2 v4 v5 nill
v2
v1 v3 v4 nill
v3
v2 v4 v5 nill
v4
v1 v2 v3 v5 nill
v5
v1 v3 v4 nill


//--------------------------------------------------------------------------
// Ham nhap danh sach ke cua do thi co n dinh
//--------------------------------------------------------------------------
void nhap_dsk(Link *Ke[], int n)
{
int i,v;
Link *pd,*p;
//Khoi tao mang cac danh sach cac dinh ke cua cac dinh
for(i=1;i<=n;i++)
{
Ke[i] = (Link*)malloc(sizeof(Link));
Ke[i]->v=i;
Ke[i]->next = NULL;
}
//Nhap danh sach cac dinh ke cua cac dinh
for(i=1;i<=n;i++)
{
pd = NULL;
printf("\nNhap cac dinh ke voi dinh %d (nhap 0 de ket thuc!):",i);
while(1)
{
scanf("%d",&v);
if(v==0)
break;
if(pd == NULL)
{
pd = (Link*)malloc(sizeof(Link));
p=pd;
}
else

while(pd!=NULL)
{
printf("%5d",pd->v);
pd=pd->next;
}
}
}
// Ham in tieu de cua chuong trinh
//--------------------------------------------------------------------------
void tieu_de()
{
printf("\n CHUONG TRINH CAI DAT CAC THUAT TOAN TIM KIEM TREN DO THI");
printf("\n --------------***--------------\n\n");
}
//--------------------------------------------------------------------------
// Ham hien thi Menu chon chuc nang cua chuong trinh
//--------------------------------------------------------------------------
char menu()
{
printf("\n Menu chon chu nang");
printf("\n ---***---\n");
printf("\n\n 1. Nhap do thi cho boi danh sach ke");
printf("\n\n 2. Hien thi danh sach ke cua do thi");
printf("\n\n 5. Ket thuc chuong trinh");
printf("\n\n ----------------------------------------");
printf("\n\n Ban chon:"); ch=getche();
return ch;
}
//--------------------------------------------------------------------------
Gi¸o ¸n m«n: Lý ThuyÕt §å ThÞ

case '2': //Hien thi danh sach ke cua do thi
clrscr();
tieu_de();
printf("\n\n2.In danh sach ke cua do thi");
printf("\n----------------------------\n\n");
if(kt)
in_dsk(Ke,n);
else
printf("\nDo thi chua duoc nhap vao!");
printf("\n\n\n\n--------------------------------");
printf("\nGo mot phim bat ky de tro ve menu chon chuc nang!");
getch();
break;
case '5': //Ket thuc chuong trinh
printf("\n\nXin cam on ban da su dung chuong trinh!");
getch();
break;
}
}while(ch!='5');
} Giáo án môn: Lý Thuyết Đồ ThịNguyễn Minh Đức
-

f(n) = O(g(n))
. iu ny cú ngha tng ng vi vic tỡm c cỏc hng s dng C v N sao
cho:
NnnCgnf

);()(

Trng hp m rng, nu
f(n
1
,n
2
,..,n
k
)
v
g(n
1
,n
2
,..,n
k
)
l cỏc hm biu din, ta vit:
f(n
1
,n
2
,..,n
k

O(g(n))
thỡ ta núi l thut toỏn cú thi gian tớnh toỏn
c
O(g(n)).

3.1 Thut toỏn tỡm kim theo chiu sõu trờn th (Depth First Search)
í tng chớnh ca thut toỏn tỡm kim theo chiu sõu cú th c hiu nh sau:
Ban u tt c cỏc nh ca th u cha c duyt n, ta s bt u vic tỡm kim t mt nh
no ú, gi s nh ú l v
1
. Sau ú chn u l mt nh (cú th chn tu ý) trong danh sỏch cỏc nh
k vi nh v
1
m cha c xột n v lp li quỏ trỡnh tỡm kim i vi nh u ny. bc tng
quỏt, gi s ang xột nh v
k
, nu trong cỏc nh k vi nh v
k
ta tỡm c nh w l nh cha
c duyt n thỡ ta s li bt u quỏ trỡnh tỡm kim t ú v w s tr thnh nh ó c duyt
qua. Nu khụng cũn nh no k vi nh v
k
l cha c duyt n thỡ ta núi rng nh ny ó c
duyt xong v quay li tip tc tỡm kim t nh m trc ú ta n c nh v
k
. Quỏ trỡnh c tip
tc nh vy cho n khi tt c cỏc nh ca th ó c duyt ht. Nh vy ta cú th hiu mt
cỏch n gin l vic tỡm kim theo chiu sõu trờn th bt u t nh v c thc hin trờn c s
tỡm kim theo chiu sõu t cỏc nh cha c duyt k vi v.
Quỏ trỡnh ny c mụ t bng th tc quy sau:


Ke(v) do
If Chuaxet[u] Then
DFS(u);

End;
(* Chng trỡnh chớnh thc hin th tc *)

BEGIN
(* Khi to bin ton cc Chuaxet *)
For v

V do
Chuaxet[v]:=True;
(* Duyt th *)
For v

V do
If Chuaxet[v] Then
DFS(v);

END.
Nh vy, vi thut toỏn trờn õy rừ rng mi lnh gi DFS(v) s thc hin duyt qua tt c cỏc
nh cựng thnh phn liờn thụng vi nh v, bi vỡ sau mi khi xột nh v l lnh gi n th tc
DFS i vi cỏc nh k vi v. Mt khỏc, do mi khi thm nh v xong, bin Chuaxet[v] c gỏn
giỏ tr False nờn mi nh s c thm ỳng mt ln. Thut toỏn ln lt s tin hnh tỡm kim t
cỏc nh cha c xột n, vỡ vy nú s duyt c qua tt c cỏc nh ca th. (K c th
khụng liờn thụng).
D phc tp tớnh toỏn ca thut toỏn c ỏnh giỏ nh sau:
Trc ht ta thõy rng s phộp toỏn cn thc hin trong hai chu trỡnh ca thut toỏn (Hai vũng