Lý thuyết đồ thị ôn thi học sinh giỏi

v Trong hình trên, uvyz là đường đi sơ cấp từ u đến z độ dài 3; uyxvyz 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

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

Ở đâ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ổ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:

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

5

VD3: Biểu diễn graph G trong VD1 như sau:

0 1 1 1 1 1 0 0 1 0 1 0 0 1 1 1 1 1 0 0 1 0 1 0 0

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: d e a c b Đỉnh Bậc

a 3

b 2

c 2

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: Chứng minh 2 graph G và G’ dưới hình sau là đẳng cấu

7

u

G' G

s

t v

y

x

w z

e b

h g f

a

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:

e v (đỉnh bậc 4);

b y (đỉnh bậc 3);

a x (đỉnh bậc 2);

Đố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:

8

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:

Cho 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

e

d a

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 trùm của G Còn G5 không là graph con của G vì G5 chứ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

v0v1,v1v2,… , vn-2vn-1,vn-1vn (n 0)

được gọi là một đường đi từ v0 (đỉnh đầu) đến vn (đỉnh cuối), chứa (qua) các đỉnh

v0, v1, … , vn và chứa các cạnh v0v1,v1v2,… , vn-1vn Đường đi này thường được viết gọn là

v0v1v2,… vn-1vn

Khi chỉ cần nêu ra đỉnh đầu v0 và đỉnh cuối vn của đường đi thì ta viết:

9

Đườ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

v

Trong hình trên, uvyz là đường đi sơ cấp từ u đến z (độ dài 3); uyxvyz 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:

10

e

h

g b

a

c d

Trong hình trên, graph G1 liên thông vì có đường đi nối 2 đỉnh bất kì của G1.Gragh

G2 không liên thông vì không có đường đi từ d đến e

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

+ thành phần liên thông chứa a là G1(V1, E1), trong đó:

V1 = {a, b, c, d} và E1 = {ab, bc, cd, ca};

+ thành phần liên thông chứa e là G2(V2, E2), trong đó:

V2 = {e} và E2 = ;

+ thành phần liên thông chứa g là G3(V3, E3), trong đó:

V3 = {g, h} và E3 = {gh};

11

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:

e) d)

c) b)

a)

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 đỉnh, kí hiệu là Kp Kp là 1 graph (p -1) – đều, có ( 1)

x x

v u

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à Km,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

b a

b

c

d

e a

e

d c

b d

c b

a a

e

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:

G U cf

G + ce G

e f

a a

e a

e

2) Graph G’ (V,E’) là graph bù của graph G(V,E) nếu G và G’ không có cạnh chung(E E’= ) và G(V, E) + E’ là graph đầy đủ Nói cách khác, G và G’ bù 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:

14

d) c)

b) a)

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

K2 x K2

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

16

Đườ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) thì 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

17

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

18

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: Cho 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 Hamilton 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

19

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

Ngườ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ĩ bậc khơng nhỏ hơn

để 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)

c

d a

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

thì G chứa một đường đi Hamilton

Định 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:

21

g h e b

c

d a

Graph này có 7 đỉnh, bất kì 2 đỉnh nào không kề nhau (a v c; a v g; b v h; d

v e;…) đều có tổng số bậc không nhỏ hơn 7 Vậy đây là graph Hamilton

Định lý: Nếu G l một graph hai phe với hai tập đỉnh là V1, V2 có số đỉnh bằng nhau (bằng n 2) và bậc của mỗi đỉnh lớn hơn

2

n

thì G l một graph Hamilton

VD22:

z

y x

v

u

Trong graph có trọng số ở hình trên ta có:

m(uv) = 3; m( vx) = 2; m(xy) = 1; …

Nếu đường đi u – y là uxy thì m(u, y) = m(ux) + m(xy) = 6+1 = 7

Đường đi u – y ngắn nhất ở đây là

d(u, y) = m(uz) + m(zx) + m(xy) = 1 + 3 +1 = 5

Có thể coi một graph G là một graph có trọng số mà mọi cạnh đều có chiều dài 1 Lúc đó khoảng cách d(u, y) giữa 2 đỉnh u và y là chiều dài của đường đi u –

y ngắn nhất, tức là đường đi qua ít cạnh nhất

BÀI TOÁN NGƯỜI DU LỊCH

Một khách du lịch đang ở thành phố A, muốn đi thăm một số thành phố khác, mỗi thành phố chỉ một lần, rồi trở về A Giữa bất kì 2 thành phố nào cũng có một

“đường thẳng” nối với nhau, không phải đi qua một thành phố nào khác Phải hướng dẫn khách du lịch đi theo đường nào để chiều dài đường đi là ngắn nhất (hoặc thời gian đi là ngắn nhất hoặc phí hao tổn giao thông ít nhất)?

Đó là bài toán du lịch, phát biểu theo ngôn ngữ graph như sau:

Cho G là một graph đầy đủ, có trọng số Tím một chu trình Hamilton ngắn nhất trong G Bài toán người du lịch là bài toán có nhiều ý nghĩa thực tiễn; nhiều bài toán trong giao thông liên lạc, trong sản xuất kinh doanh… được quy về bài toán người du lịch Bài toán người du lịch lại là một bài toán khó nổi tiếng, cho đến nay vẫn chưa có lời giải đầy đủ Người ta chưa tìm được một thuật toán hữu hiệu để giải nó và cũng chưa chứng minh được rằng bài toán không có thuật toán