BÀ GIÁO D÷C VÀ
TR◊ÕNG

ÀO TĐO

ĐI H≈C QUY NHÃN

TRÜN TH¿ THANH NHI

MÀT S» VáN ó Vó D◊ÕNG I EULER
VÀ CHU TRÌNH EULER

LN VãN THĐC Sû TỐN H≈C

Bình

‡nh - 2021


BÀ GIÁO D÷C VÀ
TR◊ÕNG

ÀO TĐO

ĐI H≈C QUY NHÃN

TRÜN TH¿ THANH NHI

MÀT S» VáN ó Vó D◊ÕNG I EULER
VÀ CHU TRÌNH EULER
Chuyên ngành: PH◊ÃNG PHÁP TOÁN Sà CáP

Mã sË: 8460113

LUäN VãN THĐC Sû TỐN H≈C

Ng˜Ìi h˜Ĩng d®n: TS. LÊ THANH BÍNH

Bình

‡nh - 2021


Cơng trình ˜Ịc hồn thành t§i
TR◊ÕNG

ĐI H≈C QUY NHÃN

Ng˜Ìi h˜Ĩng dđn: TS. Lấ THANH BNH

PhÊn biên 1: TS. LM TH THANH TÂM
Ph£n biªn 2: PGS.TS PHĐM TIịN SÃN

Lu™n v´n ˜Ịc bÊo vê tĐi Hẻi ng ỏnh giỏ lun vn thĐc sổ chuyờn
ngnh Phẽng phỏp toỏn sẽ còp tĐi Trèng

Đi hc Quy NhÏn,

vào ngày 30 tháng 8 n´m 2021.

Có th∫ tìm hiu lun vn tĐi:
- Th viên, Trèng


Đi hc Quy Nhẽn.

- Khoa Tốn và ThËng kê, Tr˜Ìng

§i hÂc Quy NhÏn.


LếI CAM

OAN

Tụi xin cam oan răng nẻi dung trỡnh by trong lu™n v´n này là trung
th¸c và khơng trùng l∞p vểi ti khỏc. Tụi cng xin cam oan răng các
k∏t qu£ nêu trong lu™n v´n, tài liªu tham kh£o v nẻi dung trớch dđn Êm
bÊo tớnh trung thác, chớnh xác.

Bình

‡nh, tháng 07 n´m 2021
Tác gi£

Tr¶n Th‡ Thanh Nhi


Mc lc
M

ĩU


1

1 Kin thc chuân b

2

4

1.1

Cỏc loĐi th . . . . . . . . . . . . . . . . . . . . . . . .

4

1.2

Nh˙ng thu™t ng˙ cÏ s v∑ Á th‡ . . . . . . . . . . . . . . .

8

1.3

Tính liên thơng . . . . . . . . . . . . . . . . . . . . . . . . 12

˜Ìng i Euler, chu trình Euler

18

2.1


‡nh nghỉa . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.2

Chu trình và ˜Ìng i Euler trong Á th‡ vơ h˜Ĩng . . . . . 22

2.3

Chu trình và ˜Ìng i Euler trong Á th‡ có h˜Ĩng . . . . . 31

3 MỴt sË ˘ng dˆng
3.1

38

Ÿng dˆng cıa ˜Ìng i và chu trình Euler trong mỴt sË bài
tốn tìm ˜Ìng i . . . . . . . . . . . . . . . . . . . . . . . 38

3.2

ng dng chu trỡnh Euler trong viêc xõy dáng tòt c£ các Á
th‡ có dãy b™c cho tr˜Ĩc

3.3

. . . . . . . . . . . . . . . . . . . 43

Ÿng dˆng chu trình Euler trong gi£i trình t¸ gen . . . . . . 52

K∏t lu™n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

TÀI LIõU THAM KHÉO

58


Danh sách hình v≥
1.1

M§ng máy tính. . . . . . . . . . . . . . . . . . . . . . . . .

5

1.2

M§ng mỏy tớnh cú nhiu èng iên thoĐi. . . . . . . . . .

5

1.3

M§ng máy tính có các ˜Ìng nỴi bỴ. . . . . . . . . . . . . .

6

1.4

M§ng máy tính có các ˜Ìng truy∑n mỴt chi∑u. . . . . . . .

7


1.5

MĐng mỏy tớnh vểi nhiu èng truyn mẻt chiu. . . . . .

8

1.6

Á th‡ vơ h˜Ĩng G và H . . . . . . . . . . . . . . . . . . . .

9

1.7

Á th‡ có h˜Ĩng G. . . . . . . . . . . . . . . . . . . . . . . 11

1.8

Á th‡ Ïn.

1.9

Á th‡ G1 và G2 . . . . . . . . . . . . . . . . . . . . . . . . 14

1.10

Á th‡ H và các thành ph¶n liên thơng H1 , H2 và H3 . . . . 15

1.11


Á th‡ G.

. . . . . . . . . . . . . . . . . . . . . . . . . . 13

. . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.12 Các Á th‡ có h˜Ĩng G và H . . . . . . . . . . . . . . . . . . 17
2.1

B£y cây c¶u ca thnh phậ Kăonigsberg. . . . . . . . . . . . 18

2.2

Á th‡ minh ho§ cho b£y cây c¶u. . . . . . . . . . . . . . . 19

2.3

Các Á th‡ vơ h˜Ĩng G1 , G2 và G3 . . . . . . . . . . . . . . . 21

2.4

Các Á th‡ có h˜Ĩng H1 , H2 và H3 . . . . . . . . . . . . . . . 21

2.5

Ba Á th‡ vơ h˜Ĩng. . . . . . . . . . . . . . . . . . . . . . . 26

2.6

Á th‡ có chu trình Euler. . . . . . . . . . . . . . . . . . . . 27


2.7

Á th‡ minh ho§ cho chu trình Euler trong Á th‡ có h˜Ĩng.

2.8

Á th‡ có h˜Ĩng có ˜Ìng i Euler.

33

. . . . . . . . . . . . . 34


2.9

Á th‡ có h˜Ĩng có chu trình Euler. . . . . . . . . . . . . . 35

3.1

Á th‡ cıa bài toán Domino. . . . . . . . . . . . . . . . . . 39

3.2

Á th‡ G minh ho§ cho bài tốn ng˜Ìi ˜a th˜ Trung Hoa.

3.3

Á th‡ GT sau khi bÍ sung c§nh.


41

. . . . . . . . . . . . . . 42

3.4

SÏ Á lâu ài. . . . . . . . . . . . . . . . . . . . . . . . . . 42

3.5

Á th‡ cıa sÏ Á lâu ài. . . . . . . . . . . . . . . . . . . . 43

3.6

Á th‡ có dãy b™c d = (2, 2, 2, 2, 1, 1) theo thu™t toán Hakimi. 45

3.7

Phép toán gi˙a các Á th‡. . . . . . . . . . . . . . . . . . . 46

3.8

MỴt chu trình Euler an màu H = (x1 , x2 , x3 , x4 , x2 , x5 , x1 ). 47

3.9

Á th‡ tô màu sinh bi G - G⇤ . . . . . . . . . . . . . . . . . 47

3.10 T¯ G1 Íi màu các c§nh cıa Á th cõn băng H thu ềc
th G2 = G(H). . . . . . . . . . . . . . . . . . . . . . . 48

3.11 Tßt c£ 7 Á th‡ có cùng dãy b™c d = (2, 2, 2, 1, 1). . . . . . . 50
3.12 Các chu trình an màu.
3.13

. . . . . . . . . . . . . . . . . . . 51

Á th‡ nh™n ˜Òc khi "nËi" các c∞p chuÈi trùng nhau mẻt
k tá. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54


1

M

ĩU

Th giểi tá nhiờn xung quanh ta l mẻt mún q cıa t§o hố mà con
ng˜Ìi t¯ x˜a

∏n nay

ang khơng ng¯ng khám phá, mỴt trong nh˙ng

cơng cˆ mà chúng ta s˚ dˆng ∫ nghiên c˘u chúng ó là Tốn hÂc. Tốn
hÂc khơng chø là l˛ thuy∏t khơ khan mà nó cịn b≠t ngn t¯ th¸c t∏,
trong ó ph£i k∫ ∏n bi toỏn "BÊy cõy cảu Kă
onigsberg". TĐi thnh
phậ Kăonigsberg thc PhÍ (nay là Kaliningrad thc CỴng hồ Liên bang
Nga) có sơng Pregel bao quanh hai £o lĨn. Hai £o này ˜Ịc nËi vĨi các
vùng ßt cıa thành phË bi b£y cây c¶u. C˜ dân thành phË ∞t ra bài

tốn: cú th xuòt phỏt tĐi mẻt im v i qua b£y cây c¶u, mÈi cây c¶u chø
˜Ịc i qua úng mẻt lản v tr v im xuòt phỏt ềc khụng?

õy l

mẻt trong nhng vòn cẽ bÊn ca l thuyt th ềc xuòt t ảu
th k XVIII. V ∏n n´m 1736 bài báo cıa Euler ã ˜Ịc cơng bË liên
quan ∏n lÌi gi£i bài tốn nÍi ti∏ng v∑ cỏc cõy cảu Kăonigsberg. Theo ú
Leonhard Euler (1707-1783), mẻt nhà tốn hÂc ng˜Ìi Thu Sỉ, ã tr£ lÌi
trÂn vµn cho bài tốn này. Ng˜Ìi ta ã lßy tên cıa ơng ∫ ∞t cho bài tốn
nÍi ti∏ng trên.
Cho tĨi ngày nay thì mËi quan tâm v∑ bài tốn này v®n khụng h suy
giÊm. L do ca sá quan tõm òy chớnh l sá vn dng rẻng rói ca nú trong
ròt nhiu lổnh vác khỏc nhau. Do ú, viêc nghiờn cu tìm hi∫u sâu các tính
chßt cıa ˜Ìng i và chu trình Euler cùng vĨi ˘ng dˆng cıa chúng trong
mỴt sË lổnh vác l ht sc nghổa v cản thit. Vì v™y, vĨi s¸ gỊi ˛ cıa


2

thảy hểng dđn tụi ó chn ti "Mẻt sậ vßn ∑ v∑ ˜Ìng i Euler
và chu trình Euler" ∫ lm lun vn tật nghiêp ca mỡnh.
Ngoi phản M ảu, Kt lun v Ti liêu tham khÊo, nẻi dung chớnh
ca lu™n v´n ˜Òc chia làm ba ch˜Ïng:
Ch˜Ïng 1. Ki∏n th˘c chuân b
Trong chẽng ny, chỳng tụi nhc lĐi cỏc khỏi niêm, kin thc cẽ bÊn
cản thit lm nn tÊng cho nỴi dung ˜Ịc trình bày  các ch˜Ïng sau.
Ch˜Ïng 2.

˜Ìng i Euler, chu trình Euler.


Trong ch˜Ïng này, chúng tơi s≥ trỡnh by chi tit v hê thậng nhng
tớnh chòt quan trng v mẻt sậ vòn cú liờn quan n ˜Ìng i Euler,
chu trình Euler.
Ch˜Ïng 3. MỴt sË ˘ng dˆng
Trong chẽng ny, chỳng tụi s giểi thiêu mẻt sậ ng dˆng quan trÂng,
thú v‡ cıa ˜Ìng i và chu trình Euler trong mẻt sậ lổnh vác khỏc nhau
ca cuẻc sậng.
Lun vn ềc hon thnh dểi sá hểng dđn v giỳp Ơ t™n tình cıa
th¶y giáo TS. LÊ THANH BÍNH, Khoa Tốn và ThËng kê, Tr˜Ìng

§i

hÂc Quy NhÏn. Tơi xin bày t‰ s¸ kính trÂng và lịng bi∏t Ïn sâu s≠c ∏n
Th¶y ng˜Ìi ã giúp Ơ tơi trong st q trình thác hiên lun vn.
Qua õy, tụi cng xin gi lèi c£m Ïn ∏n Tr˜Ìng
Phịng

§i hÂc Quy NhÏn,

ào t§o Sau §i hÂc, Khoa Tốn và ThËng kê cùng qu˛ Th¶y, Cơ

giáo giÊng dĐy lểp Cao hc Phẽng phỏp toỏn sẽ còp khúa 22 ó giỳp ễ
v tĐo iu kiên thun lềi cho tơi trong st q trình hÂc t™p và nghiên
c˘u. Sau cùng, tơi dành lÌi c£m Ïn ∞c biªt ∏n gia ình ã quan tâm,
ıng hỴ tơi trong st thÌi gian qua.
M∞c dù b£n thân ã ch´m chø, nÈ l¸c v lm viêc nghiờm tỳc trong suật
quỏ trỡnh thác hiên lu™n v´n, nh˜ng do kh£ n´ng, kinh nghiªm nghiên c˘u



3

cịn h§n ch∏ và thÌi gian có h§n nên khó tránh kh‰i nh˙ng thi∏u sót trong
lu™n v´n. Tơi rßt mong nh™n ˜Ịc nh˙ng góp ˛ cıa qu˛ th¶y, cơ và bĐn
c lun vn ềc hon thiên hẽn na.
Bỡnh

nh, thỏng 07 n´m 2021
HÂc viên

Tr¶n Th‡ Thanh Nhi


4

Ch˜Ïng 1

Ki∏n th˘c chu©n b‡
Trong ch˜Ïng này, chúng tơi trình by mẻt sậ khỏi niêm, kin thc cẽ
bÊn cản thit làm n∑n t£ng cho nỴi dung ˜Ịc nghiên c˘u  hai chẽng
sau.

1.1

Cỏc loĐi th
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

ó. Ng˜Ìi ta phân lo§i Á th‡ tu˝ theo ∞c tính và sË các c§nh nËi các c∞p
ønh cıa Á th. Sau õy, chỳng tụi s giểi thiêu cỏc loĐi th băng cỏch
a ra mẩi loĐi mụ hỡnh cỏc mĐng mỏy tớnh khỏc nhau.

GiÊ s mẻt mĐng mỏy tớnh gm cỏc mỏy tớnh v cỏc èng iên thoĐi.
Ta có th∫ bi∫u diπn v‡ trí cıa mÈi máy tính băng mẻt im v mẩi èng
iên thoĐi băng mẻt cĐnh nh trong Hỡnh 1.1. Trong mĐng mỏy tớnh ny,
ta thòy cú nhiu nhòt mẻt èng truyn gia hai mỏy, mẩi èng hoĐt
ẻng theo cÊ hai chiu, v khụng mỏy tớnh nào có ˜Ìng truy∑n nËi ∏n
chính nó.


5

Hình 1.1: M§ng máy tính.

Do v™y, m§ng này có th∫ mụ hỡnh băng mẻt ẽn th, bao gm cỏc
ứnh bi∫u diπn các máy tính và các c§nh vơ h˜Ĩng bi∫u diπn các ˜Ìng
truy∑n nËi hai ønh phân biªt và khụng cú hai cĐnh nậi cựng mẻt cp ứnh.
nh nghổa 1.1.1 (xem [12]). MỴt Ïn Á th‡ G = (X, E) gm mẻt tp
khụng rẩng X m cỏc phản t cıa nó gÂi là các ønh và mỴt t™p E m cỏc
phản t ca nú gi l cỏc cĐnh, ú l cỏc cp khụng th tá ca cỏc ứnh
phõn biêt.
ụi khi có nhi∑u ˜Ìng truy∑n gi˙a các máy tính trong m§ng. M§ng vĨi
nhi∑u ˜Ìng ˜Ịc bi∫u diπn nh˜ Hình 1.2.

Hình 1.2: MĐng mỏy tớnh cú nhiu èng iên thoĐi.

ẽn th‡ khơng th∫ mơ hình các m§ng nh˜ th∏ này ˜Ịc. Thay vào ó
ng˜Ìi ta dùng a Á th‡.

ó là Á th‡ gÁm các ønh và các c§nh vơ h˜Ĩng,

nh˜ng có th∫ có nhi∑u c§nh nËi mÈi c∞p ønh.

hỊp riêng cıa a Á th‡.

Ïn Á th‡ là mỴt tr˜Ìng


6

Ta khơng th∫ dùng mỴt c∞p ønh ∫ xác ‡nh mẻt cĐnh trong a th.
nh nghổa a th vỡ vy cú phc tĐp hẽn mẻt chỳt.
nh nghổa 1.1.2 (xem [12]). MỴt a Á th‡ G = (X, E) gm mẻt tp
cỏc ứnh X , mẻt tp cỏc cĐnh E và mỴt hàm f t¯ E tĨi {{u, v}|u, v 2

X, u 6= v}. Các c§nh e1 và e2 ềc gi l song song hay cĐnh bẻi nu
f (e1 ) = f (e2 ).

Mẻt mĐng mỏy tớnh cú th có ˜Ìng truy∑n t¯ mỴt máy tính tĨi chính
nó.

ó là m§ng trên Hình 1.3. Ta khơng th∫ dùng a Á th‡ ∫ mơ hình

các m§ng nh˜ th∏ vì a Á th khụng cha cỏc khuyờn, ú l cỏc cĐnh nậi
mẻt ønh vĨi chính nó. Khi ó ta ph£i dùng mỴt lo§i Á th‡ tÍng qt hÏn,
gÂi là gi£ Á th‡.

Hình 1.3: MĐng mỏy tớnh cú cỏc èng nẻi bẻ.

nh nghổa 1.1.3 (xem [12]). MỴt gi£ Á th‡ G = (X, E) gÁm mỴt t™p
các ønh X , mỴt t™p các cĐnh E v mẻt hm f t E tểi {{u, v}|u, v 2 X}.
Mẻt cĐnh l mẻt khuyờn nu f (e) = {u} vĨi mỴt ønh u nào ó.


Gi£ Á th l loĐi th vụ hểng tng quỏt nhòt vỡ nú cú th cha cỏc
khuyờn v cỏc cĐnh bẻi.

a Á th‡ là lo§i vơ h˜Ĩng có th∫ ch˘a c§nh bỴi

nh˜ng khơng th∫ có các khun, cịn Á th‡ Ïn l loĐi th vụ hểng
khụng cha cĐnh bẻi hoc các khuyên.


7

Cỏc èng truyn trong mẻt mĐng mỏy tớnh cú th hoĐt ẻng chứ theo
mẻt chiu. Chỉng hĐn trờn Hỡnh 1.4, máy chı  New York có th∫ chø nh™n
d˙ liªu t¯ các máy khác mà khơng th∫ g˚i d˙ liªu i. Khi ú cỏc èng
iên thoĐi hai chiu ềc biu din băng mẻt cp cĐnh cú chiu ngềc
nhau.

Hỡnh 1.4: MĐng máy tính có các ˜Ìng truy∑n mỴt chi∑u.

Chúng ta dùng Á th‡ có h˜Ĩng ∫ mơ hình hố nh˙ng m§ng nh˜ th∏.
Nh˙ng c§nh cıa Á th‡ có h˜Ĩng là các c∞p ønh có th˘ t¸. Trong Á th‡
có h˜Ĩng ng˜Ìi ta dựng khuyờn, tc l mẻt cp cú th tá ca cựng mẻt
ứnh, nhng khụng dựng cĐnh bẻi cựng chiu nËi cùng c∞p ønh.
‡nh nghỉa 1.1.4 (xem [12]). MỴt Á th‡ có h˜Ĩng G = (X, E) gÁm t™p
các ønh X và t™p các c§nh E là các c∞p có th tá cỏc phản t thuẻc X .
Cuậi cựng trong m§ng máy tính có th∫ có nhi∑u ˜Ìng truy∑n sao cho
có th∫ có nhi∑u ˜Ìng mỴt chi∑u t¯ mÈi ‡a ph˜Ïng tĨi máy chı  New
York và có th∫ có nhi∑u ˜Ìng t¯ máy chı tĨi các máy  xa.
trên Hình 1.5.


ó là m§ng

Á th‡ có h˜Ĩng khơng ı ∫ mơ hình các m§ng lo§i này,

vì trong Á th‡ có hểng khụng cha cỏc cĐnh bẻi. Khi ú, ta cản ph£i
dùng a Á th‡ có h˜Ĩng, trong ó có th∫ cú nhiu cỏc cĐnh cú hểng t
mẻt ứnh tểi mẻt ønh khác (có th∫ tĨi chính nó).
h˜Ĩng nh˜ sau.

‡nh nghỉa a Á th‡ có


8

Hỡnh 1.5: MĐng mỏy tớnh vểi nhiu èng truyn mẻt chi∑u.

‡nh nghỉa 1.1.5 (xem [12]). MỴt a Á th‡ có h˜Óng G = (X, E) gÁm
t™p các ønh X và tp cỏc cĐnh E v mẻt hm f t E tĨi {(u, v)|u, v 2 X}.
Các c§nh e1 và e2 l cỏc cĐnh bẻi nu f (e1 ) = f (e2 ).

Các thu™t ng˙ dùng cho các lo§i Á th‡ khỏc nhau cho thòy rừ cỏc cĐnh
ca th cú k∏t hỊp vĨi các c∞p ønh có th˘ t¸ hay khụng th tá, cỏc
cĐnh bẻi, cỏc khuyờn cú ềc dựng hay khơng.

‡nh nghỉa các lo§i Á th‡

˜Ịc tÍng k∏t trong b£ng sau.

Lo§i


C§nh

Có khun

hay khơng?

khơng?

Ïn Á th‡

Vơ h˜Ĩng

Khơng

Khơng

a Á th‡

Vơ h˜Ĩng

Có

Khơng

Gi£ Á th‡

Vơ h˜Ĩng

Có


Có

Có h˜Ĩng

Khơng

Có

Có

Có

Á th‡ có h˜Ĩng

a Á th‡ có hểng Cú hểng

1.2

Cú cĐnh bẻi

Nhng thut ng cẽ s v th
ảu tiờn chỳng ta nh nghổa mẻt vi thut ng˙ mơ t£ các ønh và c§nh

cıa Á th‡ vơ h˜Óng.


9

‡nh nghæa 1.2.1 (xem [12]). Hai ønh u và v trong mỴt Á th‡ vơ h˜Ĩng


G ˜Ịc gÂi là li∑n k (hay lỏng ging) nu {u, v} l mẻt cĐnh cıa G. N∏u

e = {u, v} thì e gÂi là cĐnh liờn thuẻc vểi cỏc ứnh u v v . C§nh e cÙng
˜Ịc gÂi là c§nh nËi các ønh u và v . Các ønh u và v gÂi là cỏc im ảu

mỳt ca cỏc cĐnh {u, v}.
ghi nhn sậ cỏc cĐnh liờn thuẻc vểi mẻt ứnh ta cú ‡nh nghỉa sau.
‡nh nghỉa 1.2.2 (xem [12]). B™c cıa mỴt ønh trong Á th‡ vơ h˜Ĩng
là sË các c§nh liên thuẻc vểi nú, riờng khuyờn tĐi mẻt ứnh ềc tớnh hai
lản cho bc ca nú. Ngèi ta k hiêu bc cıa ønh v là deg(v).
Ví dˆ 1.2.1. B™c cıa các ønh trong các Á th‡ G và H trên Hình 1.6 là
bao nhiêu?

Hình 1.6:

Á th‡ vơ h˜Ĩng G và H.

LÌi gi£i.
Trong G, deg(a) = 2, deg(b) = deg(c) = deg(f ) = 4, deg(d) = 1,

deg(e) = 3 và deg(g) = 0.
Trong H , deg(a) = 4, deg(b) = deg(e) = 6, deg(c) = 1 và deg(d) = 5.
ønh b™c 0 ˜Ịc gÂi là ønh cơ l™p. T¯ ó suy ra ønh cơ l™p khơng nËi
vĨi bßt kì ønh nào.

ønh g trên Á th‡ G trong Ví dˆ 1.2.1 là cơ l™p.

ønh b™c 1 ˜Ịc gÂi là ønh treo (móc). Do v™y ønh treo nËi vĨi úng
mỴt ønh khác.


ønh d trên Á th‡ G trong Ví dˆ 1.2.1 là mỴt ønh treo.


10

Chúng ta s≥ nh™n ˜Ịc gì n∏u ta cỴng b™c ca tòt cÊ cỏc ứnh lĐi vểi
nhau? Mẩi mẻt cĐnh óng góp hai Ïn v‡ vào tÍng các b™c cıa tòt cÊ cỏc
ứnh vỡ mẩi cĐnh nậi vểi ỳng hai ønh.

i∑u này có nghỉa là tÍng các b™c

cıa tßt c£ cỏc ứnh gòp ụi sậ cỏc cĐnh ca th. Ta có k∏t qu£ sau ây,
k∏t qu£ này th˜Ìng ˜Ịc gi l

nh l bt tay, vỡ mẻt cĐnh cú hai ¶u

mút giËng nh˜ mỴt cái b≠t tay có hai bàn tay.
‡nh l˛ 1.2.1 ( ‡nh l˛ b≠t tay [12]). Cho G = (X, E) là mỴt Á th‡ vơ
X
h˜Ĩng có e c§nh. Khi ó 2e =
deg(x).
x2X

‡nh l˛ này úng c£ khi th cú cĐnh bẻi hoc cỏc khuyờn.

nh l 1.2.1 chứ ra răng tng cỏc bc ca tòt cÊ các ønh cıa mỴt Á
th‡ vơ h˜Ĩng là mỴt sË chặn. Sá kiên ẽn giÊn ny cú ròt nhiu hê qu£
hay, mỴt trong sË ó là

‡nh l˛ 1.2.2.


‡nh l˛ 1.2.2 (xem [12]). MỴt Á th‡ vơ h˜Ĩng có mỴt sË chặn cỏc ứnh
bc lƠ.
c giÊ tham khÊo chng minh chi tit

nh l tĐi [12].

Cú mẻt sậ thut ng ròt hay dùng Ëi vĨi Á th‡ có h˜Ĩng.
‡nh nghỉa 1.2.3 (xem [12]). Khi (u, v) là c§nh cıa Á th‡ có h˜Ĩng G,
thì u ˜Ịc gÂi là nËi tĨi v , và v ˜Ịc gÂi là ˜Ịc nËi t¯ u.
ønh ¶u, ønh v gÂi là ønh cuËi cıa c§nh u, v .

ønh u gÂi là

ønh ¶u và ønh cuËi cıa

khuyên là trùng nhau.
Vì các c§nh cıa Á th‡ có h˜Ĩng là các c∞p có th˘ t¸, nên ‡nh nghỉa
b™c cıa ønh c¶n ph£i tinh t∏ hÏn ∫ ph£n ánh ˜Ịc sË cỏc cĐnh nhn
ứnh ny l ứnh ảu (ra khi ứnh này) và sË các c§nh nh™n ønh này là
ønh cuËi ( i vào ønh này).
‡nh nghæa 1.2.4 (xem [12]). Trong Á th‡ có h˜Ĩng b™c vào cıa ønh

v k˛ hiªu là deg (v) là sË các c§nh có ønh ci là v . B™c ra cıa ønh v ,


11

k hiêu l deg + (v) l sậ cỏc cĐnh cú ứnh ảu l v . Chỳ , mẻt khuyờn tĐi
mẻt ứnh s gúp thờm mẻt ẽn v vo bc vào và mỴt Ïn v‡ vào b™c ra

cıa ønh này.
Ví dˆ 1.2.2. Tìm b™c vào và b™c ra cıa mÈi ønh trong Á th‡ có h˜Ĩng

G trên Hình 1.7.

Hình 1.7:

Á th‡ có h˜Ĩng G.

LÌi gi£i.
Các b™c vào là deg (a) = 2, deg (b) = 2, deg (c) = 3, deg (d) =

2, deg (e) = 3, deg (f ) = 0.
Các b™c ra là deg + (a) = 4, deg + (b) = 1, deg + (c) = 2, deg + (d) =

2, deg + (e) = 3, deg + (f ) = 0.
Vì mÈi c§nh (hay cịn gÂi l cung) cú mẻt ứnh ảu v ứnh cuậi nờn
tng các b™c vào và tÍng các b™c ra cıa tßt c£ các ønh trong mỴt Á th‡
có h˜Ĩng là nh˜ nhau v băng sậ cĐnh ca nú.

ú chớnh l nẻi dung cıa

‡nh l˛ sau.
‡nh l˛ 1.2.3 (xem [12]). GÂi G = (X, E) là mỴt Á th‡ có h˜Ĩng. Khi
ó:

X

x2X


.

deg (x) =

X

x2X

deg + (x) = |E|


12

Mẻt sậ tớnh chòt ca th cú hểng khụng ph thuẻc vo hểng ca
cỏc cĐnh ca nú. Do ú, s≥ có lỊi hÏn khi ta lÌ i các h˜Ĩng ny.

th

vụ hểng nhn ềc băng cỏch ny ềc gi là Á th‡ vơ h˜Ĩng n∑n.

Á

th‡ vơ h˜Ĩng và Á th‡ vơ h˜Ĩng n∑n cıa nó có cùng sË c§nh.

1.3

Tính liên thơng

Nhi∑u bài tốn có th∫ ˜Ịc mơ hình vĨi các ˜Ìng i dÂc theo các c§nh
cıa Á th‡. Ví dˆ, ng˜Ìi ta dùng mơ hình có ˜Ìng i trong Á th‡ ∫ gi£i

˜Ịc các bài tốn tËi ˜u cho xe phỏt th, xe rỏc, cho viêc chân oỏn
trong mĐng mỏy tớnh.
Chỳng ta bt ảu băng nh nghổa thut ng˙ cÏ s cıa l˛ thuy∏t Á th‡
có liên quan ∏n ˜Ìng i.
‡nh nghỉa 1.3.1 (xem [12]).

˜Ìng i Ỵ dài n t¯ u tĨi v , vĨi n là mỴt sË

ngun d˜Ïng, trong mỴt Á th‡ vơ h˜Ĩng là mỴt dãy các c§nh e1 , e2 , . . . , en
cıa Á th‡ sao cho f (e1 ) = {x0 , x1 }, f (e2 ) = {x1 , x2 }, . . . , f (en ) = {xn 1 , xn },
vÓi x0 = u và xn = v . Khi Á th‡ là Ïn, ta k˛ hiêu èng i ny băng
dóy cỏc ứnh x0 , x1 , . . . , xn (vì danh sách các ønh này xác ‡nh duy nhßt
˜Ìng i).

˜Ìng i ˜Ịc gÂi l mẻt chu trỡnh nu nú bt ảu v kt thỳc

tĐi cựng mẻt ứnh, tc l u = v .
qua các ønh x1 , x2 , . . . , xn 1 .

˜Ìng i ho∞c chu trình khi ó gÂi là i
˜Ìng i hay chu trình gÂi là Ïn n∏u nú

khụng cha cựng mẻt cĐnh quỏ mẻt lản.
Khi khụng cản phõn biêt cỏc cĐnh bẻi ta s k hiêu èng i e1 , e2 , . . . , en
trong ó f (ei ) = {xi 1 , xi } vÓi i = 1, 2, . . . , n băng dóy cỏc ứnh x0 , x1 , . . . ,

xn . K˛ hiªu này xác ‡nh ˜Ìng i chø theo các ønh mà nó i qua. Có th∫
có nhi∑u ˜Ìng i qua dãy các ønh này.
Ví dˆ 1.3.1. Xét Á th‡ Ïn trên Hình 1.8. Ta có a, d, c, f, e là ˜Ìng



13

i Ïn, Ỵ dài 4 vì {a, d}, {d, c}, {c, f } và {f, e} ∑u là các c§nh. Tuy

v™y, d, e, c, a khơng là ˜Ìng i vì {e, c} khơng là c§nh cıa Á th‡. Cịn

b, c, f, e, b là mỴt chu trình Ỵ dài 4 vì {b, c}, {c, f }, {f, e} và {e, b} l cỏc
cĐnh v èng i ny bt ảu v k∏t thúc t§i b.

˜Ìng i a, b, e, d, a, b Ỵ

dài 5 khơng là ˜Ìng i Ïn vì nó cha cĐnh {a, b} hai lản.

Hỡnh 1.8:

th ẽn.

Bõy giè ta ‡nh nghỉa ˜Ìng i nh˜ th∏ cho a Á th‡ có h˜Ĩng.
‡nh nghỉa 1.3.2 (xem [12]).

˜Ìng i Ỵ dài n, vÓi n là sË nguyên

d˜Ïng, t¯ u tÓi v trong a Á th‡ có h˜Ĩng là dãy các c§nh e1 , e2 , . . . , en cıa
Á th‡ sao cho f (e1 ) = (x0 , x1 ), f (e2 ) = (x1 , x2 ), . . . , f (en ) = (xn 1 , xn ),
vÓi x0 = u và xn = v . Khi khụng cú cĐnh bẻi trong th ta k hiêu èng
i ny băng dóy cỏc ứnh x0 , x1 , . . . , xn .

˜Ìng i b≠t ¶u v kt thỳc tĐi


cựng mẻt ứnh ềc gi l mẻt chu trình.

˜Ìng i hay chu trình gÂi là

Ïn n∏u nó khụng cha cựng mẻt cĐnh quỏ mẻt lản.
Khi khụng cản phõn biêt cỏc cĐnh bẻi ta s k hiêu èng i e1 , e2 , . . . , en
trong ó f (ei ) = (xi 1 , xi ) vÓi i = 1, 2, . . . , n băng dóy cỏc ứnh x0 , x1 , . . . ,

xn . K˛ hiªu này xác ‡nh ˜Ìng i chø theo các ønh mà nó i qua. Có th∫
có nhi∑u ˜Ìng i qua dãy các ønh này.
Khi nào mÂi cp mỏy tớnh trong mẻt mĐng cú th trao i thơng tin vĨi
nhau, n∏u các thơng báo có th∫ g˚i qua mỴt hay nhi∑u máy trung gian?


14

Nu mĐng mỏy tớnh ny ềc biu din băng mẻt th trong ú mẩi mỏy
ềc biu th băng mẻt ứnh cũn mẩi èng truyn ềc biu din băng
mẻt cĐnh, thì câu h‰i trên có d§ng: Có ph£i ln tÁn tĐi mẻt èng i
gia hai ứnh trong mẻt th khơng?
‡nh nghỉa 1.3.3 (xem [12]). MỴt a Á th‡ vơ h˜Ĩng ˜Ịc gÂi là liên
thơng n∏u có ˜Ìng i gi˙a mÂi c∞p ønh phân biªt cıa Á th‡.
Nh˜ v™y, hai mỏy tớnh bòt k trong mĐng cú th trao i thơng tin vĨi
nhau ˜Ịc n∏u và chø n∏u Á th‡ cıa m§ng này là liên thơng.
Ví dˆ 1.3.2.

Á th‡ G1 trên Hình 1.9 là liên thơng, vì gi˙a mÂi c∞p ønh

phân biªt ∑u có ˜Ìng i. Tuy v™y, Á th‡ G2 trên Hình 1.9 là khơng liên
thơng. ChØng h§n gi˙a các ønh a và d khơng có ˜Ìng i trong G2 .


Hình 1.9:

Á th‡ G1 và G2 .

Trong Ch˜Ïng 2 chúng ta s≥ c¶n tĨi

‡nh l˛ sau ây.

‡nh l˛ 1.3.1 (xem [12]). Gia mi cp ứnh phõn biêt ca mẻt Á th‡ vơ
h˜Ĩng liên thơng ln có ˜Ìng i Ïn.
Ph¶n ch˘ng minh chi ti∏t

‡nh l˛ Âc gi£ tham kh£o t§i [12].

MỴt Á th‡ khơng liên thơng là hỊp cıa hai hay nhi∑u Á th‡ con liên
thông, mÈi c∞p các Á th‡ con này khơng có ønh chung. Các Á th‡ con


15

liên thơng rÌi nhau nh˜ v™y ˜Ịc gÂi là các thành ph¶n liên thơng cıa Á
th‡ ang xét.
Ví dˆ 1.3.3.

Á th‡ H là hÒp cıa ba Á th‡ con liên thơng rÌi nhau H1 , H2

và H3 nh˜ chø ra trên Hình 1.10. Ba Á th‡ con này là 3 thành ph¶n liên
thơng cıa H .


Hình 1.10:

Á th‡ H và các thành ph¶n liên thơng H1 , H2 và H3 .

ụi khi viêc xoỏ i mẻt ứnh v tòt cÊ cỏc cĐnh liờn thuẻc vểi nú s tĐo
ra mẻt th‡ con mĨi có nhi∑u thành ph¶n liên thơng hÏn Á th‡ xußt
phát. Các ønh nh˜ th∏ gÂi là ønh ct hay im khểp. Viêc xoỏ ứnh ct
khi mẻt th liờn thụng s tĐo ra mẻt th con khụng liờn thụng. Hon
ton tẽng tá, mẻt cĐnh m khi ta b nú i s tĐo ra mẻt th có nhi∑u
thành ph¶n liên thơng hÏn so vĨi Á th‡ xuòt phỏt ềc gi l mẻt cĐnh
ct hay mẻt cảu.
Vớ dˆ 1.3.4. Tìm các ønh c≠t và c§nh c≠t cıa Á th‡ G trên Hình 1.11.


16

Hình 1.11:

Á th‡ G.

LÌi gi£i.
ønh c≠t cıa G là b, c và e. Xố mỴt trong các ønh này (và cỏc cĐnh
nậi vểi nú) s lm mòt tớnh liờn thụng ca th.
Cỏc cĐnh ct (cảu) l {a, b} v {c, e}. Xoỏ mẻt trong cỏc cảu ny s

lm th mòt tớnh liờn thụng.

Cú hai khỏi niêm liờn thụng cıa Á th‡ có h˜Ĩng tu˝ theo chúng ta có
quan tâm tĨi h˜Ĩng cıa các c§nh hay khơng.
‡nh nghỉa 1.3.4 (xem [12]).


Á th‡ có h˜Ĩng gÂi là liên thơng m§nh

n∏u có ˜Ìng i t¯ a ∏n b và t¯ b ∏n a vÓi mÂi ønh a và b cıa Á th‡.
Trong Á th‡ có h˜Ĩng liên thơng m§nh ln tÁn tĐi dóy cỏc cĐnh cú
hểng t mẻt ứnh bòt k tểi mẻt ứnh bòt k khỏc ca th.

th

cú hểng cú th khụng l liờn thụng mĐnh nhng vđn cịn liên thơng theo
mỴt nghỉa nào ó.

∫ chính xác i∑u này ta có ‡nh nghỉa sau.

‡nh nghỉa 1.3.5 (xem [12]).

Á th‡ có h˜Ĩng gÂi là liên thơng y∏u n∏u

có ˜Ìng i gi˙a hai ønh bßt k˝ cıa Á th‡ vơ h˜Ĩng n∑n.
Do v™y, Á th‡ có h˜Ĩng là liên thơng y∏u n∏u và chø n∏u ln tÁn t§i
˜Ìng i gi˙a gi˙a hai ønh khi ta khơng quan tâm tĨi h˜Ĩng cıa các c§nh.
Rõ ràng mÂi Á th‡ có h˜Ĩng liên thơng m§nh cÙng là Á th‡ liên thơng
y∏u.


17

Ví dˆ 1.3.5. Các Á th‡ có h˜Ĩng trên Hình 1.12 có là liên thơng m§nh
khơng? Có là liên thơng y∏u khơng?


Hình 1.12: Các Á th‡ có h˜Ĩng G và H.

LÌi gi£i.

G là liên thơng m§nh vì có ˜Ìng i gi˙a hai ønh bßt kì cıa Á th‡ có
h˜Ĩng này. Vì v™y G cÙng là liên thơng y∏u.

H khơng là liên thơng m§nh. Khơng có ˜Ìng i có h˜Ĩng t¯ a tÓi b
trong Á th‡ này. Tuy v™y H là liên thơng y∏u vì có ˜Ìng i gi˙a bßt k˝
hai ønh cıa Á th‡ vơ h˜Ĩng n∑n cıa H .


18

Ch˜Ïng 2

˜Ìng i Euler, chu trình Euler
Bài tốn cÍ i∫n v lớ thỳ v èng i Euler xuòt hiên tĐi n˜Ĩc PhÍ
nay là CỴng hồ Liên bang Nga (xem [7]). Thnh phậ Kăonigsberg cú sụng
Pregel chÊy qua, gia sụng cú cù lao Kneiphof và b£y cây c¶u nh˜ hình v≥
sau:

Hình 2.1: BÊy cõy cảu ca thnh phậ Kă
onigsberg.

T khi xuòt hiên bÊy cõy cảu ngèi dõn õy ó t vòn : liêu cú cỏch
no i dĐo ềc qua cÊ bÊy cõy cảu v qua mẩi cảu ỳng mẻt lản ˜Ịc
khơng? Bài tốn này ã làm say mê nh˙ng ng˜Ìi dõn Kăonigsberg trong