http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

CHƯƠNG III
ð' TH(
Lý thuyt ñ th là mt ngành khoa hc ñưc phát trin t lâu nhưng l i có nhi"u
#ng d%ng hi&n ñ i. Nh)ng ý tư*ng cơ b-n c.a nó ñưc ñưa ra t th k/ 18 b*i nhà toán
hc Th%y Sĩ tên là Leonhard Euler. Ông ñã dùng ñ th ñ gi-i quyt bài toán 7 chic
c=u Konigsberg n@i ting.
ð th cũng ñưc dùng ñ gi-i các bài toán trong nhi"u lĩnh vDc khác nhau. Thí
d%, dùng ñ th ñ xác ñnh xem có thDc hi&n mt m ch ñi&n trên mt b-ng ñi&n phHng
ñưc không. Chúng ta cũng có th phân bi&t hai hp chLt hóa hc có cùng công th#c
phân tM nhưng có cLu trúc khác nhau nhN ñ th. Chúng ta cũng có th xác ñnh xem hai
máy tính có ñưc nOi vPi nhau bQng mt ñưNng truy"n thông hay không nu dùng mô
hình ñ th m ng máy tính. ð th vPi các trng sO ñưc gán cho các c nh c.a nó có th
dùng ñ gi-i các bài toán như bài toán tìm ñưNng ñi ngSn nhLt gi)a hai thành phO trong
mt m ng giao thông. Chúng ta cũng có th dùng ñ th ñ lTp lch thi và phân chia
kênh cho các ñài truy"n hình.
3.1. ð(NH NGHĨA VÀ THÍ D1.
ð th là mt cLu trúc rNi r c gm các ñUnh và các c nh (vô hưPng hoWc có
hưPng) nOi các ñUnh ñó. NgưNi ta phân lo i ñ th tùy theo ñWc tính và sO các c nh nOi
các cWp ñUnh c.a ñ th. Nhi"u bài toán thuc nh)ng lĩnh vDc rLt khác nhau có th gi-i
ñưc bQng mô hình ñ th. ChHng h n ngưNi ta có th dùng ñ th ñbiu diYn sD c nh
tranh các loài trong mt môi trưNng sinh thái, dùng ñ thñ biu diYn ai có -nh hư*ng
lên ai trong mt t@ ch#c nào ñó, và cũng có th dùng ñ th ñ biu diYn các kt c%c c.a
cuc thi ñLu th thao. Chúng ta cũng có th dùng ñ th ñ gi-i các bài toán như bài toán
tính sO các t@ hp khác nhau c.a các chuyn bay gi)a hai thành phO trong mt m ng
hàng không, hay ñ gi-i bài toán ñi tham quan tLt c- các ñưNng phO c.a mt thành phO
sao cho mZi ñưNng phO ñi qua ñúng mt l=n, hoWc bài toán tìm sO các màu c=n thit ñ
tô các vùng khác nhau c.a mt b-n ñ.
Trong ñNi sOng, chúng ta thưNng gWp nh)ng sơ ñ, như sơ ñ t@ ch#c b máy, sơ
ñ giao thông, sơ ñ hưPng d[n th# tD ñc các chương trong mt cuOn sách, ..., gm
nh)ng ñim biu th các ñOi tưng ñưc xem xét (ngưNi, t@ ch#c, ña danh, chương m%c
sách, ...) và nOi mt sO ñim vPi nhau bQng nh)ng ño n thHng (hoWc cong) hay nh)ng
mũi tên, tưng trưng cho mt quan h& nào ñó gi)a các ñOi tưng. ðó là nh)ng thí d% v"
ñ th.
3.1.1. ð2nh nghĩa:
Mt ñơn ñ thG = (V, E) gm mt tTp khác rZng V mà các ph=n
tM c.a nó gi là các ñUnh và mt tTp E mà các ph=n tM c.a nó gi là các c nh, ñó là các
cWp không có th# tD c.a các ñUnh phân bi&t.
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

3.1.2. ð2nh nghĩa:
Mt ña ñ th G = (V, E) gm mt tTp khác rZng V mà các ph=n tM
c.a nó gi là các ñUnh và mt h E mà các ph=n tM c.a nó gi là các c nh, ñó là các cWp
không có th# tD c.a các ñUnh phân bi&t. Hai c nh ñưc gi là c nh bi hay song song
nu chúng cùng tương #ng vPi mt cWp ñUnh.
Rõ ràng mZi ñơn ñ thlà ña ñ th, nhưng không ph-i ña ñ th nào cũng là ñơn
ñ th.
3.1.3. ð2nh nghĩa:
Mt gi- ñ th G = (V, E) gm mt tTp khác rZng V mà các ph=n tM
c.a nó gi là các ñUnh và mt h E mà các ph=n tM c.a nó gi là các c nh, ñó là các cWp
không có th# tD c.a các ñUnh (không nhLt thit là phân bi&t).
VPi v∈V, nu (v,v)∈E thì ta nói có mt khuyên t i ñUnh v.
Tóm l i, gi- ñ th là lo i ñ th vô hưPng t@ng quát nhLt vì nó có th ch#a các
khuyên và các c nh bi. ða ñ th là lo i ñ th vô hưPng có th ch#a c nh bi nhưng
không th có các khuyên, còn ñơn ñ th là lo i ñ thvô hưPng không ch#a c nh bi
hoWc các khuyên.
Thí d8 1:
ðơn ñ th
Gi- ñ th
3.1.4. ð2nh nghĩa:
Mt ñ th có hưPng G = (V, E) gm mt tTp khác rZng V mà các
ph=n tM c.a nó gi là các ñUnh và mt tTp E mà các ph=n tM c.a nó gi là các cung, ñó là
các cWp có th# tD c.a các ph=n tM thuc V.
3.1.5. ð2nh nghĩa:
Mt ña ñ th có hưPng G = (V, E) gm mt tTp khác rZng V mà
các ph=n tM c.a nó gi là các ñUnh và mt h E mà các ph=n tM c.a nó gi là các cung,
ñó là các cWp có th# tD c.a các ph=n tM thuc V.
ð th vô hưPng nhTn ñưc t ñ th có hưPng G bQng cách xoá be các chi"u mũi
tên trên các cung ñưc gi là ñ th vô hưPng n"n c.a G.
Thí d8 2:
ð th có hưPng ða ñ th có hưPng
v1
v2
v3
v4
v5
v6
v7
v1
v2
v3
v4
v5
v6
v6
v7
v3
v4
v5
v6
v1
v2
v3
v5
V5
v1
v2
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

Thí d8 3: 1) ð< th2“l>n t?” trong sinh thái hc. ð th ñưc dùng trong nhi"u mô
hình có tính ñn sD tương tác c.a các loài vTt. ChHng h n sD c nh tranh c.a các loài
trong mt h& sinh thái có th mô hình hóa bQng ñ th “lLn t@”. MZi loài ñưc biu diYn
bQng mt ñUnh. Mt c nh vô hưPng nOi hai ñUnh nu hai loài ñưc biu diYn bQng các
ñUnh này là c nh tranh vPi nhau.
2) ð< th2 nh hưDng. Khi nghiên c#u tính cách c.a mt nhóm nguNi, ta thLy mt sO
ngưNi có th có -nh hư*ng lên suy nghĩ c.a nh)ng ngưNi khác. ðth có hưPng ñưc
gi là ñ th -nh hư*ng có th dùng ñ mô hình bài toán này. MZi ngưNi c.a nhóm ñưc
biu diYn bQng mt ñUnh. Khi mt ngưNi ñưc biu diYn bQng ñUnh a có -nh hư*ng lên
ngưNi ñưc biu diYn bQng ñUnh b thì có mt cung nOi t ñUnh a ñn ñUnh b.
3) Thi ñ>u vòng tròn. Mt cuc thi ñLu th thao trong ñó mZi ñi ñLu vPi mZi ñi khác
ñúng mt l=n gi là ñLu vòng tròn. Cuc thi ñLu như th có th ñưc mô hình bQng mt
ñ th có hưPng trong ñó mZi ñi là mt ñUnh. Mt cung ñi t ñUnh a ñn ñUnh b nu ñi
a thSng ñi b.
4) Các chương trình máy tính có th thi hành nhanh hơn bQng cách thi hành ñng thNi
mt sO câu l&nh nào ñó. ði"u quan trng là không ñưc thDc hi&n mt câu l&nh ñòi hei
kt qu- c.a câu l&nh khác chưa ñưc thDc hi&n. SD ph% thuc c.a các câu l&nh vào các
câu l&nh trưPc có thbiu diYn bQng mt ñ th có hưPng. MZi câu l&nh ñưc biu diYn
bQng mt ñUnh và có mt cung t mt ñUnh tPi mt ñUnh khác nu câu l&nh ñưc biu
diYn bQng ñUnh th# hai không th thDc hi&n ñưc trưPc khi câu l&nh ñưc biu diYn bQng
ñUnh th# nhLt ñưc thDc hi&n. ð th này ñưc gi là ñ< th2 có ưu tiên trưIc sau.
3.2. BJC CKA ðLNH.
3.2.1. ð2nh nghĩa:
Hai ñUnh u và v trong ñ th (vô hưPng) G=(V,E) ñưc gi là li"n
k" nu (u,v)∈E. Nu e = (u,v) thì e gi là c nh liên thuc vPi các ñUnh u và v. C nh e
cũng ñưc gi là c nh nOi các ñUnh u và v. Các ñUnh u và v gi là các ñim ñ=u mút c.a
c nh e.
3.2.2. ð2nh nghĩa:
BTc c.a ñUnh v trong ñ th G=(V,E), ký hi&u deg(v), là sO các c nh
liên thuc vPi nó, riêng khuyên t i mt ñUnh ñưc tính hai l=n cho bTc c.a nó.
ðUnh v gi là ñUnh treo nu deg(v)=1 và gi là ñUnh cô lTp nu deg(v)=0.
Thí d8 4:
Ta có deg(v
1
)=7, deg(v
2
)=5, deg(v
3
)=3, deg(v
4
)=0, deg(v
5
)=4, deg(v
6
)=1, deg(v
7
)=2.
ðUnh v
4
là ñUnh cô lTp và ñUnh v
6
là ñUnh treo.
v1
v2
v3
v4
v5
v6
v7
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

3.2.3. Mnh ñ:
Cho ñ th G = (V, E). Khi ñó
2|E| =
∑
∈Vv
v)deg(
.
ChNng minh: Rõ ràng mZi c nh e = (u,v) ñưc tính mt l=n trong deg(u) và mt l=n
trong deg(v). T ñó suy ra t@ng tLt c- các bTc c.a các ñUnh bQng hai l=n sO c nh.
3.2.4. H qu:
SO ñUnh bTc lp c.a mt ñ th là mt sO chqn.
ChNng minh: Gi V
1
và V
2
tương #ng là tTp các ñUnh bTc chqn và tTp các ñUnh bTc lp
c.a ñ th G = (V, E). Khi ñó
2|E| =
∑
∈
1
)deg(
Vv
v
+
∑
∈
2
)deg(
Vv
v
V trái là mt sO chqn và t@ng th# nhLt cũng là mt sO chqn nên t@ng th# hai là mt sO
chqn. Vì deg(v) là lp vPi mi v ∈ V
2
nên |V
2
| là mt sO chqn.
3.2.5. Mnh ñ:
Trong mt ñơn ñ th, luôn tn t i hai ñUnh có cùng bTc.
ChNng minh: Xét ñơn ñ th G=(V,E) có |V|=n. Khi ñó phát biu trên ñưc ñưa v" bài
toán: trong mt phòng hp có n ngưNi, bao giN cũng tìm ñưc 2 ngưNi có sO ngưNi quen
trong sO nh)ng ngưNi dD hp là như nhau (xem Thí d% 6 c.a 2.2.3).
3.2.6. ð2nh nghĩa:
ðUnh u ñưc gi là nOi tPi v hay v ñưc gi là ñưc nOi t u trong
ñ th có hưPng G nu (u,v) là mt cung c.a G. ðUnh u gi là ñUnh ñ=u và ñUnh v gi là
ñUnh cuOi c.a cung này.
3.2.7. ð2nh nghĩa:
BTc vào (t.ư. bTc ra) c.a ñUnh v trong ñ th có hưPng G, ký hi&u
deg
t
(v) (t.ư. deg
o
(v)), là sO các cung có ñUnh cuOi là v.
Thí d8 5:
deg
t
(v
1
) = 2, deg
o
(v
1
) = 3,
deg
t
(v
2
) = 5, deg
o
(v
2
) = 1,
deg
t
(v
3
) = 2, deg
o
(v
3
) = 4,
deg
t
(v
4
) = 1, deg
0
(v
4
) = 3,
deg
t
(v
5
) = 1, deg
o
(v
5
) = 0,
deg
t
(v
6
) = 0, deg
o
(v
6
) = 0.
ðUnh có bTc vào và bTc ra cùng bQng 0 gi là ñUnh cô lTp. ðUnh có bTc vào bQng 1
và bTc ra bQng 0 gi là ñUnh treo, cung có ñUnh cuOi là ñUnh treo gi là cung treo.
Mnh ñ:
Cho G =(V, E) là mt ñ th có hưPng. Khi ñó
v1
v2
v3
v4
v5
v6
http://ebook.here.vn Ti min phí ð thi, eBook, Tài liu hc tp

∑
∑
∈ ∈
=
Vv Vv
ot
vv )(deg)(deg
= |E|.
ChNng minh: Kt qu- có ngay là vì mZi cung ñưc tính mt l=n cho ñUnh ñ=u và mt
l=n cho ñUnh cuOi.
3.3. NHRNG ðƠN ð' TH( ðSC BITT.
3.3.1. ð< th2 ñUy ñW:
ð th ñ=y ñ. n ñUnh, ký hi&u là K
n
, là ñơn ñ th mà hai ñUnh
phân bi&t bLt kỳ c.a nó luôn li"n k". Như vTy, K
n
có
2
)1(
−
nn
c nh và mZi ñUnh c.a K
n
có bTc là n−1.
Thí d8 6:
K
1
K
2
K
3
K
4
K
5
3.3.2. ð< th2 vòng:
ðơn ñ th n ñUnh v
1
, v
2
, ..., v
n
(n≥3) và n c nh (v
1
,v
2
), (v
2
,v
3
), ...,
(v
nv1
,v
n
), (v
n
,v
1
) ñưc gi là ñ th vòng, ký hi&u là C
n
. Như vTy, mZi ñUnh c.a C
n
có bTc
là 2.
Thí d8 7:
C
3
C
4
C
5
C
6
3.3.3. ð< th2 bánh xe:
T ñ th vòng C
n
, thêm vào ñUnh v
n+1
và các c nh (v
n+1
,v
1
),
(v
n+1
,v
2
), ..., (v
n+1
,v
n
), ta nhTn ñưc ñơn ñ th gi là ñ th bánh xe, ký hi&u là W
n
. Như
vTy, ñ th W
n
có n+1 ñUnh, 2n c nh, mt ñUnh bTc n và n ñUnh bTc 3.
Thí d8 8:
W
3
W
4
W
5
W
6
3.3.4. ð< th2 lp phương:
ðơn ñ th 2
n
ñUnh, tương #ng vPi 2
n
xâu nh phân ñ dài n
và hai ñUnh k" nhau khi và chU khi 2 xâu nh phân tương #ng vPi hai ñUnh này chU khác
nhau ñúng mt bit ñưc gi là ñ th lTp phương, ký hi&u là Q
n
. Như vTy, mZi ñUnh c.a
Q
n
có bTc là n và sO c nh c.a Q
n
là n.2
nv1
(t công th#c 2|E| =
∑
∈Vv
v)deg(
).
v1
v1
v2
v1
v2
v3
v1
v2
v3
v4
v5
v2
v1
v3
V4
v1
v2
v3
v1
v2
v4
v3
v1
v5
v2
v4
v3
v1
v6
v5
v2
v3
v4
v2
v3
v1
v2
v4
v3
v1
v5
v2
v4
v3
v6
v5
v2
v3
v4
v1
v4
v5
v6
v7
v1