DO THI
3.2.3. M nh đ :ệ ề Cho đ th G = (V, E). Khi đó ồ ị
2|E| =
∑
∈Vv
v)deg(
.
Ch ng minh:ứ Rõ ràng m i 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 t t c các b c c a các đ nh b ng hai l n sầ ừ ổ ấ ả ậ ủ ỉ ằ ầ ố
c nh.ạ
3.2.4. H qu :ệ ả S đ nh b c l c a m t đ th là m t s ch n.ố ỉ ậ ẻ ủ ộ ồ ị ộ ố ẵ
Ch ng minh:ứ G i Vọ1 và V2 t ng ng là t p các đ nh b c ch n và t p các đ nhươ ứ ậ ỉ ậ ẵ ậ ỉ
b c l c a đ th G = (V, E). Khi đóậ ẻ ủ ồ ị
2|E| =
∑
∈1
)deg(
Vv
v
+
∑
∈2
)deg(
Vv
v
V trái là m t s ch n và t ng th nh t cũng là m t s ch n nên t ng th hai làế ộ ố ẵ ổ ứ ấ ộ ố ẵ ổ ứ
m t s ch n. Vì deg(v) là l v i m i v ộ ố ẵ ẻ ớ ọ ∈ V2 nên |V2| là m t s ch n.ộ ố ẵ
3.2.5. M nh đ : ệ ề Trong m t đ n đ th , luôn t n t i hai đ nh có cùng b c.ộ ơ ồ ị ồ ạ ỉ ậ
Ch ng 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 i, bao gi cũng tìm đ c 2 ng i cóề ộ ọ ườ ờ ượ ườ
s ng i quen trong s nh ng ng i d h p là nh nhau (xem Thí d 6 c aố ườ ố ữ ườ ự ọ ư ụ ủ
2.2.3).
Thí d 13:ụ 1) Hai đ n đ th Gơ ồ ị 1 và G2 sau là đ ng c u qua phép đ ng c u f: aẳ ấ ẳ ấ
x, b
u, c
z, d
v, e
y:
G1 G2
2) Hai đ th Gồ ị 1 và G2 sau đ u có 5 đ nh và 6 c nh nh ng không đ ng c u vìề ỉ ạ ư ẳ ấ
trong G1 có m t đ nh b c 4 mà trong Gộ ỉ ậ 2 không có đ nh b c 4 nào.ỉ ậ
a
b
c e
d
u
v
x
y
z
3) Hai đ th Gồ ị 1 và G2 sau đ u có 7 đ nh, 10 c nh, cùng có m t đ nh b c 4, b nề ỉ ạ ộ ỉ ậ ố
đ nh b c 3 và hai đ nh b c 2. Tuy nhiên Gỉ ậ ỉ ậ 1 và G2 là không đ ng c u vì hai đ nhẳ ấ ỉ
b c 2 c a Gậ ủ 1 (a và d) là không k nhau, trong khi hai đ nh b c 2 c a Gề ỉ ậ ủ 2 (y và z) là
k nhau.ề
G1 G2
4) Hãy xác đ nh xem hai đ th sau có đ ng c u hay không?ị ồ ị ẳ ấ
G1 G2
Hai đ th Gồ ị 1 và G2 là đ ng c u vì hai ma tr n li n k c a Gẳ ấ ậ ề ề ủ 1 theo th tứ ự
các đ nh uỉ1, u2, u3, u4, u5, u6 và c a Gủ2 theo th t các đ nh vứ ự ỉ 6, v3, v4, v5, v1, v2 là như
nhau và b ng:ằ
010010
101000
010101
001010
100101
001010
3.6.4. M nh đ :ệ ề Gi a m i c p đ nh phân bi t c a m t đ th liên thông luônữ ọ ặ ỉ ệ ủ ộ ồ ị
có đ ng đi s c p.ườ ơ ấ
Ch ng minh:ứ Gi s u và v là hai đ nh phân bi t c a m t đ th liên thông G. Vìả ử ỉ ệ ủ ộ ồ ị
G liên thông nên có ít nh t m t đ ng đi gi a u và v. G i xấ ộ ườ ữ ọ 0, x1, ..., xn, v i xớ0=u và
xn=v, là dãy các đ nh c a đ ng đi có đ dài ng n nh t. Đây chính là đ ng đi sỉ ủ ườ ộ ắ ấ ườ ơ
c p c n tìm. Th t v y, gi s nó không là đ ng đi đ n, khi đó xấ ầ ậ ậ ả ử ườ ơ i=xj v i 0 ớ≤ i <
j. Đi u này có nghĩa là gi a các đ nh u và v có đ ng đi ng n h n qua các đ nh xề ữ ỉ ườ ắ ơ ỉ 0,
a d
cb
g e
h u
v x
y
w
t z
u1v3
v1
u2
u4
u6
u5
u3
v6
v2
v4
v5
x1, ..., xi-1, xj, ..., xn nh n đ c b ng cách xoá đi các c nh t ng ng v i dãy cácậ ượ ằ ạ ươ ứ ớ
đ nh xỉi, ..., xj-1.
3.6.5. M nh đ :ệ ề M i đ n đ th n đ nh (n ọ ơ ồ ị ỉ ≥ 2) có t ng b c c a hai đ nh tuỳ ýổ ậ ủ ỉ
không nh h n n đ u là đ th liên thông.ỏ ơ ề ồ ị
Ch ng minh:ứ Cho đ n đ th G=(V,E) có n đ nh (n ơ ồ ị ỉ ≥ 2) và tho mãn yêu c uả ầ
c a bài toán. Gi s G không liên thông, t c là t n t i hai đ nh u và v sao choủ ả ử ứ ồ ạ ỉ
không có đ ng đi nào n i u và v. Khi đó trong đ th G t n t i hai thành ph nườ ố ồ ị ồ ạ ầ
liên thông là G1 có n1 đ nh và ch a u, Gỉ ứ 2 ch a đ nh v và có nứ ỉ 2 đ nh. Vì Gỉ1, G2 là hai
trong s các thành ph n liên thông c a G nên nố ầ ủ 1+n2 ≤ n. ta có:
deg(u)+deg(v) ≤ (n1 −1)+(n2 − 1) = n1+n2−2 ≤ n−2 <n.
Đi u mâu thu n trên d n đ n k t lu n là đ th G ph i liên thông.ề ẫ ở ẫ ế ế ậ ồ ị ả
3.6.7. M nh đ :ệ ề N u m t đ th có đúng hai đ nh b c l thì hai đ nh này ph iế ộ ồ ị ỉ ậ ẻ ỉ ả
liên thông, t c là có m t đ ng đi n i chúng.ứ ộ ườ ố
Ch ng minh:ứ Cho G=(V,E) là đ th th có đúng hai đ nh b c l là u và v. Gi sồ ị ị ỉ ậ ẻ ả ử
u và v không liên thông v i nhau. Khi đó chúng ph i thu c hai thành ph n liênớ ả ộ ầ
thông nào đó c a đ th G, Gủ ồ ị 1 ch a u và Gứ2 ch a v.ứ
B c c a đ nh u trong Gậ ủ ỉ 1 cũng chính là b c c a u trong G, nên trong Gậ ủ 1 đ nhỉ
u v n có b c l và Gẫ ậ ẻ 1 có duy nh t m t đ nh b c l . Đi u này mâu thu n. V y haiấ ộ ỉ ậ ẻ ề ẫ ậ
đ nh u và v ph i liên thông.ỉ ả
3.6.8. M nh đ :ệ ề Cho G=(V,E) là m t đ th liên thông. Khi đó m t đ nh c a Gộ ồ ị ộ ỉ ủ
là đi m kh p khi và ch khi trong G t n t i hai đ nh u và v sao cho m i đ ng điể ớ ỉ ồ ạ ỉ ỗ ườ
n i u và v đ u ph i đi qua đ nh này.ố ề ả ỉ
Ch ng minh:ứ Đi u ki n c nề ệ ầ : Gi s đ nh x là đi m kh p trong đ th G. Khi đóả ử ỉ ể ớ ồ ị
đ th con Gồ ị 1 c a G nh n đ c b ng cách xoá x và các c nh liên thu c v i nó làủ ậ ượ ằ ạ ộ ớ
không liên thông. Gi s Gả ử 2, G3 là hai trong các thành ph n liên thông c a Gầ ủ 1. L yấ
u là đ nh trong Gỉ2 và v là đ nh trong Gỉ3. Do u, v thu c hai thành ph n liên thôngộ ầ
khác nhau, nên trong G1 các đ nh u, v không liên thông. Nh ng trong G các đ nh u,ỉ ư ỉ
v l i liên thông, nên m i đ ng đi n i u, v đ u ph i đi qua đ nh x.ạ ọ ườ ố ề ả ỉ
Đi u ki n đề ệ ủ: Gi s m i đ ng đi n i u, v đ u đi qua đ nh x, nên n u b đ nh xả ử ọ ườ ố ề ỉ ế ỏ ỉ
và các c nh liên thu c v i x thì đ th con Gạ ộ ớ ồ ị 1 nh n đ c t G ch a hai đ nh u, vậ ượ ừ ứ ỉ
không liên thông. Do đó G1 là đ th không liên thông hay đ nh x là đi m kh p c aồ ị ỉ ể ớ ủ
G.
3.6.9. Đ nh lý:ị Cho G là m t đ n đ th có n đ nh, m c nh và k thành ph n liênộ ơ ồ ị ỉ ạ ầ
thông. Khi đó
2
)1)(( +−−
≤≤− knkn
mkn
.
Ch ng minh:ứ B t đ ng th c ấ ẳ ứ
mkn ≤−
đ c ch ng minh b ng quy n p theo m.ượ ứ ằ ạ
N u m=0 thì k=n nên b t đ ng th c đúng. Gi s b t đ ng th c đúng đ n mế ấ ẳ ứ ả ử ấ ẳ ứ ế −1,
v i m ớ≥ 1. G i G’ là đ th con bao trùm c a G có s c nh mọ ồ ị ủ ố ạ 0 là nh nh t saoỏ ấ
cho nó có k thành ph n liên thông. Do đó vi c lo i b b t c c nh nào trong G’ầ ệ ạ ỏ ấ ứ ạ
cũng tăng s thành ph n liên thông lên 1 và khi đó đ th thu đ c s có n đ nh,ố ầ ồ ị ượ ẽ ỉ
k+1 thành ph n liên thông và mầ0−1 c nh. Theo gi thi t quy n p, ta có mạ ả ế ạ 0−1 ≥
n−(k+1) hay m0 ≥ n−k. V y m ậ≥ n-k.
B sung c nh vào G đ nh n đ c đ th G’’ có mổ ạ ể ậ ượ ồ ị 1 c nh sao cho k thànhạ
ph n liên thông là nh ng đ th đ y đ . Ta có m ầ ữ ồ ị ầ ủ ≤ m1 nên ch c n ch ng minhỉ ầ ứ
m1 ≤
2
)1)(( +−− knkn
.
Gi s Gả ử i và Gj là hai thành ph n liên thông c a G’’ v i nầ ủ ớ i và nj đ nh và nỉi ≥ nj >1
(*). N u ta thay Gếi và Gj b ng đ th đ y đ v i nằ ồ ị ầ ủ ớ i+1 và nj−1 đ nh thì t ng s đ nhỉ ổ ố ỉ
không thay đ i nh ng s c nh tăng thêm m t l ng là:ổ ư ố ạ ộ ượ
.
Th t c này đ c l p l i khi hai thành ph n nào đó có s đ nh tho (*). Vì v yủ ụ ượ ặ ạ ầ ố ỉ ả ậ
m1 là l n nh t (n, k là c đ nh) khi đ th g m k-1 đ nh cô l p và m t đ th đ yớ ấ ố ị ồ ị ồ ỉ ậ ộ ồ ị ầ
đ v i n-k+1 đ nh. T đó suy ra b t đ ng th c c n tìm.ủ ớ ỉ ừ ấ ẳ ứ ầ
3.6.11. M nh đ :ệ ề Cho G là m t đ th (vô h ng ho c có h ng) v i ma tr nộ ồ ị ướ ặ ướ ớ ậ
li n k A theo th t các đ nh về ề ứ ự ỉ 1, v2, ..., vn. Khi đó s các đ ng đi khác nhau đố ườ ộ
dài r t vừi t i vớj trong đó r là m t s nguyên d ng, b ng giá tr c a ph n t dòngộ ố ươ ằ ị ủ ầ ử
i c t j c a ma tr n Aộ ủ ậ r.
Ch ng minh:ứ Ta ch ng minh m nh đ b ng quy n p theo r. S các đ ng điứ ệ ề ằ ạ ố ườ
khác nhau đ dài 1 t vộ ừ i t i vớj là s các c nh (ho c cung) t vố ạ ặ ừ i t i vớj, đó chính là
ph n t dòng i c t j c a ma tr n A; nghĩa là, m nh đ đúng khi r=1.ầ ử ộ ủ ậ ệ ề
Gi s m nh đ đúng đ n r; nghĩa là, ph n t dòng i c t j c a Aả ử ệ ề ế ầ ử ộ ủ r là s cácố
đ ng đi khác nhau đ dài r t vườ ộ ừ i t i vớj. Vì Ar+1=Ar.A nên ph n t dòng i c t j c aầ ử ộ ủ
Ar+1 b ngằ
bi1a1j+bi2a2j+ ... +binanj,
trong đó bik là ph n t dòng i c t k c a Aầ ử ộ ủ r. Theo gi thi t quy n p bả ế ạ ik là s đ ngố ườ
đi khác nhau đ dài r t vộ ừ i t i vớk.
Đ ng đi đ dài r+1 t vườ ộ ừ i t i vớj s đ c t o nên t đ ng đi đ dài r t vẽ ượ ạ ừ ườ ộ ừ i
t i đ nh trung gian vớ ỉ k nào đó và m t c nh (ho c cung) t vộ ạ ặ ừ k t i vớj. Theo quy t cắ
nhân s các đ ng đi nh th là tích c a s đ ng đi đ dài r t vố ườ ư ế ủ ố ườ ộ ừ i t i vớk, t c làứ
bik, và s các c nh (ho c cung) t vố ạ ặ ừ k t i vớj, t c là aứkj. C ng các tích này l i theoộ ạ
t t c các đ nh trung gian vấ ả ỉ k ta có m nh đ đúng đ n r+1.ệ ề ế