Xem mẫu
- Bi ên soạn: Lê Đình Huy
Lời nói đầu
Tài liệu nhỏ này được biên soạn nhân dịp tôi và các bạn làm đề tài Toán rời
rạc. Nội dung chủ yếu của tài liệu này viết về lí thuyết đ ồ thị, và đi sâu về đồ thị
Halmilton. Xin nói rằng, tôi không lấy làm hãnh diện khi viết xong tài liệu này.
Đây chỉ là một chút sự góp nhặt nhỏ bé từ các tài liệu khác (chủ yếu là: Đại cương
về toán học hữu hạn – Hoàng Chúng) mà được tôi rút ra để tổng hợp l ại những gì
đã được học.
Tất nhiên một mình tôi thì không thể biên soạn được tài liệu này. Trong quá
trình biên soạn, xin chân thành cám ơn nhóm đề tài toán rời rạc của lớp tôi gồm
các bạn: Cù Minh Khương; Phạm Thị Th u H à; Phan Phương Dung; Nguyễn Thi
Thùy Dung; Phạm Thị Nâu. C ám ơn các thầy cô đã đón nhận. Chắc chắn tài liệu
sẽ có những sai sót không tránh khỏi, hi vọng được thầy cô, bạn đọc đón nhận và
góp ý.
Mùa xuân, Canh Dần, TP Hồ Chí Minh
Lê Đình Huy
1
- Bi ên soạn: Lê Đình Huy
Sơ lược về Graph
I Graph (Đồ thị):
H ai chữ “đồ thị” vẫn thường xuyên xuất hi ện trong đời sống toán học và cả
trong đời sống hàng ngày.
Trong các giờ toán, chúng ta từng nói tới đồ thị của các hàm số.Hay trong các
công sở, các nhân viên phải lập các biểu đồ theo dõi lượng tiêu thụ điện … Nói
chung, khái niệm đồ thị là một khái niệm khá quen thuộc với chúng ta nhằm biểu
diễn tương quan qua lại giữa 2 hoặc nhiều đối tượng toán học khác nhau.
Ở đây, khái niệm đồ thị vẫ được dùng theo nghĩa đó nhưng nó mang tính trừu
tượng hơn.
Lí thuyết đồ thị (tiếng Anh và tiếng Đức đọc là “graph”) nghiên cứu những tính
chất toán học, những quan hệ mà không phụ thuộc vào bản chất riêng của những
mối quan hệ này. Để tránh bị hiểu nhầm là đồ thị của hàm số, trong tài liệu này
chúng tôi sẽ dùng thuật ngữ “graph”.
Một graph có thể hiểu đơn giản là một hệ thống các đỉnh và các cạnh nối các
đỉnh này với nhau.
Một graph G được xác định bởi:
_ Tập hợp V những phần tử gọi là đỉnh của G.
_ Tập hợp E những phần tử gọi là cạnh của G.
Giả thuyết rằng V, E là các tập hữu hạn, V không rỗng.Kí hiệu: G(V,E) hay
V(G),V(E) để chỉ rõ V,E lần lượt là tập đỉnh, tập cạnh của graph G.
Một cạnh (u, v) của G thường được viết là uv (hay vu), ta nói cạnh uv nối u
với v, lúc đó, ta nói u và v là 2 đỉnh kề nhau.
VD1: Graph G được xác định bởi:
V = { a,b,c,d,e}
E = { ab,ac,ad,ae,bd,bc,cd,ce}
Tổng quát hơn khái niệm graph, chúng ta có khái niệm đa graph:
Một đa graph G được xác định bởi:
2
- Bi ên soạn: Lê Đình Huy
_ Tập hợp V những phần tử gọi là đỉnh củ a G.
_ Bộ E những phần tử gọi là cạnh của G; mỗi cạnh là một cặp không sắp thứ tự
của 2 đỉnh.
Giả thuyết rằng V là các tập hữu hạn, không rỗng và E là một bộ gồm hữu hạn
phần tử.
Một bộ (khác với một tập hợp) có thể chứa nhiều phần tử trùng n hau.Trong đa
graph, E có thể chứa nhiều cạnh cùng nối một cặp đỉnh.
Mỗi cạnh là một cặp không sắp (không sắp thứ tự) của 2 đỉnh không nhất thiết
khác nhau( như graph).
VD2: Đa graph G được xác định bởi:
V = {u,v,x,y}
E = {uv,uv,ux,xy,yy}
Đ a graph G có 2 cạnh uv cùng nối 1 cặp đỉnh,ta gọi đó là những cạnh song
song (cạnh bội). Cạnh yy có 2 đầu mút trùng nhau, ta gọi là khuyên.
Một đa graph không có cạnh song song và không có khuyên (như VD1) gọi là
một graph.
( Các thuật ngữ về graph hiện chưa thống nhất. Có tác giả dùng đồ thị (đa đồ thị)
thay cho graph (đa graph). Có tác giả gọi đa graph và graph lần lượt là graph và
đơn graph. Có tác giả gọi đa graph là giả graph, một giả graph không có khuyên
gọi là đa gr aph, một đa graph không có cạnh song song gọi là graph. Vì vậy, khi
đọc các tài liệu người đọc cần chú ý đến thuật ngữ mà tác giả sữ dụng.)
II Biểu diễn graph:
Ta thường dùng biểu diễn hình học của graph như sau: biểu diễn các đỉnh của
graph bằng các điểm (vòng tròn nhỏ,ô vuông nhỏ) và nối 2 điểm bằng 1 đường
(cong hay thẳng) khi cặp điểm đó ứng với 1 cạnh của graph.
Đinh lí: Mọi graph G đều có thể biểu diễn bằng 1 hình trong không gian.
3
- Bi ên soạn: Lê Đình Huy
c
d
b
e
a
Biểu diễn của graph trong VD1
Biểu diễn graph G trong VD2
Trong nhiều trường hợp (nhất là với graph có nhiều đỉnh và cạnh),ta thường
biểu diễn graph bằng ma tr ận.
Một graph G có p đỉnh v1 ,v2 ,…,vp có thể biểu diễn bằng ma trận vuông p x p,
trong đó tại dòng thứ i và cột thứ j (1 p).là số aij với :
i, j
1 khi vi keà vj
aij
0 khi vi khoâng keà vj
4
- Bi ên soạn: Lê Đình Huy
VD3:
Biểu diễn graph G trong VD1 như sau:
01111
10010
10011
11100
10100
III Bậc của đỉnh:
Một đỉnh v của graph G là đỉnh bậc n nếu v kề với n đỉnh khác.
VD4:
b
a c
e
d
Đỉnh Bậc
a 3
b 2
c 2
5
- Bi ên soạn: Lê Đình Huy
d 1
e 0
Một đỉnh l à đỉnh lẻ nếu bậc là số lẻ; đỉnh chẵn nếu bậc là số chẵn. Trong
VD4, b,c,e là đỉnh chẵn; a,d là đỉnh lẻ.
Đỉnh có bậc 0 là đỉnh cô lập.
Ta có định lí sau:
Đinh lí: Trong một graph G, tổng số bậc của các đỉnh là một số chẵn (bằng 2 lần
tổng số cạnh của G).
Hệ quả: Số đỉnh lẻ của mọi graph là một số chẵn.
IV Graph đẳng cấu:
G và G’ là hai graph đẳng cấu nếu có một tương ứng 1 -1 giữa các đỉnh của G
và G’ sao cho nếu 2 đỉnh u, v của G là kề nhau thi 2 đỉnh tương ứng u’, v’ của G’
cũng kề nhau và ngược lại.
Dễ thấy rằng nếu 2 graph G và G’ là đẳng cấu thì chúng có:
_ số đỉnh bằng nhau.
_ số cạnh bằng nhau.
_ hai đỉnh tương ứng với nhau là 2 đỉnh cùng bậc.
Đó là những điều kiện cần để 2 graph là đẳng cấu.
VD5: C hứng minh 2 graph G và G’ dưới hình sau là đẳng cấu.
6
- Bi ên soạn: Lê Đình Huy
s
u
a
t
v
x
e
b
h
f
y
d
c g
G'
z
G w
Trước hết, G và G’ có cùng số đỉnh (8 đỉnh), cùng số cạnh (7 cạnh), cùng có một
đỉnh bậc 4, một đỉnh bậc 3, một đỉnh bậc 2 và 5 đỉnh bậc 1.
Ta thiết lập một tương ứng 1 -1 giữa các đỉnh cùng bậc:
v (đỉnh bậc 4);
e
y (đỉnh bậc 3);
b
x (đỉnh bậc 2);
a
Đối với các đỉnh bậc 1 thì f, g, h trong G (cùng kề với e), nên ta cho tương ứng với
s, t, u trong G’ (cùng kề với v). Còn c, d trong G (cùng kề với b), tương ứng với z,
w trong G’ (cùng kề với y).
Như vậy, ta có sự tương ứng sau:
e v;
b y;
a x;
f s;
g t;
h u;
c z;
d w;
Với sự tương ứng đó, ta có:
7
- Bi ên soạn: Lê Đình Huy
ea vx; ef vs; eg vt; eh vu; ba yx; bc yz; bd yw;
( hai cạnh tương ứng có đầu mút là 2 cặp đỉnh tương ứng)
Vậy G và G’ là đẳng cấu.
V Graph con:
C ho 2 graph G(V, E) và G’(V’, E’)
G ’ là graph con của G nếu V’ V và E’ E. Trong trường hợp V = V’ thì G’
là graph con bao trùm của G.
VD6:
a d
a
a
d
e
c c
b b
c b
G2
G1
G
a d
d
a a
d
c
e
b
c b
b c
G5
G3 G4
Trong hình trên, G1, G2, G3 và G4 l à các graph con của G, trong đó G2 và G4 là
graph con bao t rùm của G. Còn G5 không là graph con của G vì G5 c hứa cạnh ad
mà G thì không.
VI Đường đi:
Trong một graph G, một dãy cạnh liên tiếp
v0 v1,v1 v2 ,… , vn-2 vn-1 ,vn-1 vn (n 0)
được gọi là một đường đi từ v0 (đỉn h đầu) đến vn (đỉnh cuối), chứa (qua) các đỉnh
v0 , v1 , … , vn và chứa các cạnh v0 v1,v1 v2 ,… , vn-1 vn. Đường đi này thường được
viết gọn là
v0 v1 v2,… vn-1 vn .
Khi chỉ cần nêu ra đỉnh đầu v0 và đỉnh cuối vn c ủa đườ ng đi thì ta viết:
8
- Bi ên soạn: Lê Đình Huy
Đường đi v0 - vn .
Đường đi qua n cạnh gọi là đường đi có độ dài n.
Một đường đi không qua cạnh nào lần thứ hai là một đường đi đơn giản.
Một đường đi không qua đỉnh nào lần thứ hai là một đường đi sơ cấp.
Một đường đi sơ cấp là một đường đi đơn giản nhưng một đường đi đơn giản có
thể không là đường đi sơ cấp.
Một đường đi khép kín (đỉnh đầu trùng với đỉnh cuối) và có độ dài n 3 gọi là một
chu trình. Một chu trình không qua cạnh nào lần thứ hai là một chu trình đơn giản.
Một chu trình không qua đỉnh nào lần thứ hai, trừ đỉnh đầu và đỉnh cuối trùng
nhau là một chu trình sơ cấp.
VD7:
z
u y
x
v
Trong hình trên, uvyz là đường đi sơ cấp từ u đến z (độ dài 3); u yxvyz là đường đi
không sơ cấp (qua đỉnh y hai lần) từ u đến z (độ dài 5); yvxyv là đường đi không
đơn giản (chứa cạnh yv hai lần) từ y đến v (độ dài 4); vyxv là một chu trình đơn
giản và sơ cấp (độ dài 3); vv là một đường đi độ dài 0.
VII Tính liên thông:
Hai đỉnh u, v của graph G được gọi là hai đỉnh liên thông nếu trong G có đường đi
u – v. G là graph liên thông nếu mọi cặp đỉnh của G là liên thông.
VD8:
9
- Bi ên soạn: Lê Đình Huy
a
h
d
g
b
c
e
G1 G2
Trong hình trên, graph G1 liên thông vì có đường đi nối 2 đỉnh bất kì của G 1 .Gragh
G2 không liên thông vì không có đường đi từ d đến e.
C ho graph G(V, E) và v là một đỉnh của G; gọi V’ là tập hợp các đỉnh của G liên
thông với v và E’ là tập hợp các cạnh của G nối 2 đỉnh của V’. Graph G’(V’, E’),
một graph con của G(V, E), gọi là thành phần liên thông của G chứa v.
Đ ương nhiên, nếu v và u liên thông trong G thì thành phần liên thông của G
chứa v cũng là thành phần liên thông của G chứa u.
Có thể thấy rằng mọi graph G đều có k thành phần liên thông: mỗi đỉnh của
G thuộc mộ t và chỉ một thành phần liên thông; hai đỉnh liên thông với nhau thì
thuộc một thành phần liên thông, hai đỉnh không liên thông thì thuộc hai thành
phần liên thông khác nhau.
VD9:
Xét graph G2 trong VD8 có 3 thành phần liên thông:
+ t hành phần liên t hông chứa a là G1(V1, E1), trong đó:
V1 = {a, b, c, d} và E1 = { ab, bc, cd, ca};
+ t hành phần liên thông chứa e là G2(V2, E2), trong đó:
V2 = {e} và E2 = ;
+ t hành phần liên t hông chứa g là G3(V3, E3), trong đó:
V3 = {g, h} và E3 = { gh};
10
- Bi ên soạn: Lê Đình Huy
Tóm lại: G là một graph liên thông khi và chỉ khi G có duy nhất một thành phần
liên thông.
VIII Một số graph đặc biệt:
1) Graph đều là một graph mà mọi đỉnh cùng bậc; nếu bậc này bằng k thì đó là
graph k – đều.
VD10:
c)
b)
a)
e)
d)
Hình trên cho ta thấy các graph 0 - đều (hình a), 1 - đều (hình b), 2 - đều (hình c,
d), 3 – đều (hình e).
2) Graph đầy đủ là 1 graph mà mọi cặp đỉnh đều kề nhau. Một graph đầy đủ có
p( p 1)
p đỉn h, kí hiệu là Kp . Kp là 1 graph (p -1) – đều, có cạnh.
2
VD11:
K5
K2 K4
K3
11
- Bi ên soạn: Lê Đình Huy
3) Graph hai phe G(V, E) là graph mà tập hợp đỉnh V(G) có thể phân thành 2
tập hợp không rỗng V1 và V2 sao cho cạnh nào của G cũng nối 1 đỉnh trong V1 với
1 đỉnh trong V2 .
VD12:
V1
u x
v
V1
x
u z
z y
v
y
V2
V2
Một graph hai phe mà mỗi đỉnh của V1 (có m đỉnh) đều kề với mọi đỉnh của V2
(có n đỉnh) gọi là một graph hai phe đầy đủ, kí hiệu là K m,n .
VD13:
K3,3
K2,3
IX Một số phép biến đổi về graph:
1) Ta kí hiệu G – { v} là graph con của G, có được bằng cách xóa đỉnh v và các
cạnh của G, nối với v. Nếu xóa 2 đỉnh u, v của G, ta có graph con
G – { u,v}.
Ta kí hiệu G – uv là graph con của G, có được bằng cách xóa cạnh uv của G.
Nếu xóa hai cạnh uv, xy, ta có graph G – {uv, xy}.
v l à một đỉnh cắt (hay khớp) của graph G nếu G liên thông, mà G – { v} thì
không liên thông.
uv là một cầu của G nếu G liên thông mà G - uv không liên thông.
VD14:
12
- Bi ên soạn: Lê Đình Huy
a e
a e
b d
d d b
c c
b c
G - {a}
G - {e}
G
a e
a
e
b d
d c
b
c
G - de
G - ab
Nếu trong G có 2 đỉnh u, v không kề nhau, ta có thể thêm cạnh uv vào G và được
graph, kí hiêu G + uv. Nếu u hoặc v không là đỉnh của G ta kí hiệu G uv là
graph có được bằng cách thêm đỉnh u (hoặc v) và thêm cạnh uv vào G.
VD15:
f
e
a a
e
e a
d
b
d c
d b c
b c
G U cf
G + ce
G
2) Graph G’ (V,E’) là graph bù của graph G(V,E) nếu G và G’ không có cạnh
E’= ) và G(V, E) + E’ là graph đầy đủ. Nói cách khác, G và G’ bù
chung(E
nhau nếu chúng tập đỉnh và cạnh nào đã có trong G thì không có trong G’ và
ngược lại.
VD16:
13
- Bi ên soạn: Lê Đình Huy
d)
c)
a) b)
Hình trên cho ta thấy graph a) và b) bù nhau, graph c) và d) bù nhau.
3) Cho 2 graph G(V, E) và G’(V’, E’). Graph tích G x G’ là graph có:
+ t ập đỉnh là tập hợp tích V x V’,tức là nếu:
V = { v1, v2 ,… vm } và V’ = { v’1 , v’2,… v’n } thì tập hợp đỉnh của G x G’ là
tập hợp tất cả các cặp (vi , v’j ) với mọi i =1, …, m và j = 1,…, n.
+ t ập hợp cạnh được xác định như sau: Hai đỉnh (vi , v’j) và (vk , v’p) trong G x
G’ được nối bằng một cạnh khi chỉ khi
vi = vk và v’j v’p E ’ (a)
hoặc v’j = v’p và vi vk E ( b)
VD17:
Cho graph đầy đủ K2 (2 đỉnh được kí hiệu là 0 và 1,ta có cạnh 01 hoặc10)
Graph tích K2 x K2 có:
+ 4 đỉnh là (0,0); (0,1); (1,0); (1,1).
+ 4 cạnh là cạnh nối (0,0) với (0,1); cạnh nối (1,0) với (1,1)(do thỏa điều kiện a),
cạnh nối (0,0) với (1,0); cạnh nối (0,1) với (1,1)(do thỏa điều kiện b)
00 01
0
11
10
1
K2 x K2
K2
14
- Bi ên soạn: Lê Đình Huy
Để cho gọn, trong K2 x K2 ta kí hiệu các đỉnh 00, 01,… thay cho (0,0), (0,1)…
Dùng khái niệm graph tích, ta có khái niệm hình n – lập phương (siêu lập phương)
Qn như sau:
Q1 = K2
Qn = Qn-1 x K2 với n 2
VD18:
0101
0100
100
101
0001
0000 1101
000 0111
001
1100
111
0110
110
1001
1000
0010 0011 1111
010
011 1110
Q3 1011
1010
Q4
X Graph có hướng:
Trong đa graph có hướng H(V, E), với V là tập hợp đỉnh, thì E là một bộ
nhữn g phần tử gõi là cạnh có hướng hay cung của H; mỗi cung là cặp sắp thứ tự
(u, v) của 2 đỉnh, đỉnh u (đứng trước) gọi là gốc của cung và đỉnh v (đứng sau) gọi
là ngọn của cung. Cung (u, v) cũng được kí hiệu là uv.
Một đa graph có hướng cũng có thể bi ểu diễn hình học tương tự như đa graph
vô hướng, chỉ khác là các cung(các cạnh có hướng) được biểu thị bằng những
đường cong có mũi tên đi từ gốc tới ngọn. Ta cũng nói: cung uv đi ra khỏi u và đi
vào v.
Một đa graph có hướng, không có cạnh song song và không có khuyên gọi là
một graph có hướng.
Trong graph có hướng H, nếu đỉnh v là gốc của k cung thì ta nói v có bậc ra là
k; nếu v là ngọn của m cung thì ta nói v có bậc vào là m. Bậc của đỉnh v là k + m =
n.
15
- Bi ên soạn: Lê Đình Huy
Đường đi trong graph có hướng c ũng được định nghĩa tương tự như trong
graph vô hướng, nhưng chú ý là trên cung uv chỉ có thể đi từ u (gốc) đến v (ngọn).
Trong một graph có hướng H nếu ta thy mọi cung bằng một cạnh (hai cung uv
và vu, nếu có, cũng đều được thay bằng một cạnh uv) t hì ta được graph G, gọi là
graph đối xứng của H.
Một graph có hướng H là liên thông yếu nếu graph đối xứng G của H liên
thông.
H l à liên thông một chiều nếu với 2 đỉnh u, v khác nhau bất kì của H luôn có
đường đi u – v hoặc v – u.
H l à liên thông hai (liên thông mạnh) chiều nếu với 2 đỉnh u, v khác nhau bất
kì của H luôn có đường đi u – v và v – u.
ĐƯỜNG ĐI HAMILTON
VÀ GRAPH HAMILTON
N ăm 1857, nhà toán học người Ailen là Hamilton (1805 – 1865) đưa ra trò
chơi “Đi vòng quanh thế giới” như sau.
C ho một hình thập nhị đều (có 12 mặt, 20 đỉnh và 30 cạnh), mỗi đỉnh của hình
mang tên một thành phố nổi tiếng, mỗi cạnh của hình (nối hai đỉnh) là đường đi lại
giữa hai thành phố tương ứng. Xuất phát từ một thành phố, hãy tìm đườn g đi thăm
tất cả các thành phố khác, mỗi thành phố chỉ một lần, rồi trở về chổ cũ.
16
- Bi ên soạn: Lê Đình Huy
Hình thập nhị diện đều có thể biểu diễn trong mặt phẳng như hình dưới và nếu
cho các thành phố mang tên A, B, C, D… thì ta có một cách “đi vòng quanh thế
giới” như sau:
A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, A
Trước Hamilton, có thể là từ thời Euler, người ta đ biết đến một câu đố hĩc ba
về “đường đi của quân m trn bn cờ”
Trn bn cờ, qun m chỉ cĩ thể đi theo đường chéo hình chữ nhật 2 x 3
hoặc 3 x 2 ơ vuơng.
17
- Bi ên soạn: Lê Đình Huy
Giả sữ bn cờ cĩ 8 x 8 ơ vuơng. Hy tìm đường đi của quân m, qua được tất cả
các ô của bàn cờ (mỗi ô đúng một lần) rồi trở lại ô xuất phát. Hình trn cho ta một
lời giải của cu đố.
Trị chơi và câu đố trên dẫn đến việc khảo sát một lớp graph đặc biệt, graph
Hamilton.
Định nghĩa: C ho graph G. Nếu trong G có một đường đi sơ cấp u – y qua mọi
đỉnh c ủa G chỉ một lần, thì u – y l một đường đi Hamilton trong G. Nếu u = y thì
ta cĩ một chu trình Hamilton. Một graph cĩ chu trình Hamilton gọi l graph
Hamilton.
Mọi graph đầy đủ (với số đỉnh không nhỏ hơn 3) cũng là graph Hamilton.
Đường đi Hami lton tương tự đường đi Euler trong cách phát biểu: đường đi
Euler qua mọi cạnh của graph đúng một lần, đường đi Hamilton qua mọi đỉnh của
18
- Bi ên soạn: Lê Đình Huy
graph đúng một lần. Tuy nhin, nếu như bi tốn tìm đường đi Euler trong một graph
đ được giải quyết trọn vẹn, dấu hiệu nhận biết một graph Euler là khá đơn giản v
dễ sử dụng, thì cc bi tốn về tìm đường đi Hamilton và xác định graph Hamilton lại
khĩ hơn rất nhiều. Đường đi Hamilton và graph Hamilton cĩ nhiều ý nghĩa thực
tiễn v đ được nghin cứu nhiều, nhưng vẫn cịn những khĩ khăn lớn chưa ai vượt qua
được.
N gười ta chỉ mới tìm được một vài điều kiện đủ để nhận biết một lớp rất nhỏ
các graph Hamilton và graph có đường đi Hamilton. Sau đây là một vài kết quả.
Định lý (Dirac, 1952): Nếu G l một graph có n đỉnh và mọi đỉnh của G đều cĩ
n
bậc khơng nhỏ hơn thì G l một graph Hamilton.
2
C hứng minh: Định lý được chứng minh bằng phản chứng. Giả sử G khơng cĩ
chu trình Hamilton. Ta thêm vào G một số đỉnh mới và nối mỗi đỉnh mới này với
mọi đỉnh của G, ta được graph G’. Giả sử k (>0) là số tối thiểu các đỉnh cần thiết
để G’ chứa một chu trình Hamilton. Như vậy, G’ cĩ n + k đỉnh.
Gọi P l chu trình Hamilton ayb ...a trong G’, trong đó a và b là các đỉnh của
G, cịn y là một trong các đỉnh mới. Thế thì b khơng kề với a, vì nếu tri lại thì ta cĩ
thể bỏ đỉnh y và được chu trình ab ...a, mu thuẩn với giả thiết về tính chất nhỏ tối
thiểu của k.
Hơn nửa, nếu a’ là một đỉnh kề nào đó của a (khác với y) và b’ là đỉnh nối
tiếp ngay a’ trong chu trình P thì b’ khơng thể l đỉnh kề với b (vì nếu tri lại thì ta cĩ
thể thay P bởi chu trình aa’ ...bb’ ... a, trong đó không có y).
19
- Bi ên soạn: Lê Đình Huy
N hư vậy, với mỗi đỉnh kề với a, ta có một đỉnh không kề với b, tức là số đỉnh
không kề với b không thể ít hơn số đỉnh kề với a (số đỉnh kề với a không nhỏ hơn
n n
k ). Mặt khác, theo giả thiết số đỉnh kề với b cũng không nhỏ hơn k . Vì
2 2
khơng cĩ đỉnh nào vừa kề với b lại vừa không kề với b, nên số đỉnh của G’ không
n
ít hơn 2 n 2k , mâu thuẩn với giả thiết là số đỉnh của G’ bằng n+k (k >
k
2
0). Định lý được chứng minh.
VD19:
b
g
h
e
c
a
k
d
Graph này có 8 đỉnh, đỉnh nào cũng có bậc 4. Vậy đây là graph Hamilton. Có
thể thấy một chu trình Hamilton l
agc kdhbe a
Hệ quả: Nếu G l graph có n đỉnh và mọi đỉnh của G đều có bậc khơng nhỏ
n1
hơn thì G chứa một đường đi Hamilton.
2
Địn h lý (Ore, 1960): Nếu G l một graph có n đỉnh và bất kỳ hai đỉnh nào
không kề nhau cũng có tổng số bậc không nhỏ hơn n thì G l một graph Hamilton.
VD20:
20
nguon tai.lieu . vn