Chu trình đường đi EULER và HAMILTON trong đồ thị.DOC

LuËn v¨n tèt nghiÖp Phan Thanh Long

Ch¬ng 3

Chu tr×nh, ®êng ®i Euler vµ

Hamilton trong ®å thÞ

Lý thuyÕt vÒ chu tr×nh, ®êng ®i Euler vµ Hamilton ®· cã tõ l©u vµ ®îc nghiªn

cøu nhiÒu. Ta cã thÓ b¾t gÆp nhiÒu bµi to¸n trong thùc tiÔn mµ cã thÓ sö dông c¸c

lý thuyÕt vÒ chu tr×nh, ®êng ®i Euler vµ Hamilton ®Ó gi¶i quyÕt, vÝ dô sö dông lý

thuyÕt ®êng ®i, chu tr×nh Euler ®Ó t×m hµnh tr×nh ®êng ®i cho ngêi ph¸t th, cho xe

röa ®êng... sao cho hµnh tr×nh lµ tèi u nhÊt. HoÆc lµ trong mét hÖ thèng m¹ng, mét

m¸y ®¬n cÇn göi 1 th«ng ®iÖp ®Õn tÊt c¶ c¸c m¸y cßn l¹i vËy th× ®êng truyÒn tin sÏ

®i nh thÕ nµo ®Ó cho hiÖu qu¶ nhÊt, bµi to¸n nµy cã thÓ ®îc gi¶i quyÕt b»ng c¸ch

vËn dông c¸c lý thuyÕt chu tr×nh vµ ®êng ®i Hamilton.

I. Chu tr×nh vµ ®êng ®i Euler

1. Chu tr×nh Euler

1.1 §Þnh nghÜa

Cho ®å thÞ v« híng G = <X,U>. Mét chu tr×nh trong ®å thÞ G ®îc gäi lµ chu

tr×nh Euler nÕu nã ®i qua tÊt c¶ c¸c c¹nh cña G vµ ®i qua mçi c¹nh ®óng mét lÇn.

§Þnh lý 1: §å thÞ v« híng G = <X,U> cã chu tr×nh Euler khi vµ chØ khi G lµ liªn

th«ng vµ bËc cña tÊt c¶ c¸c ®Ønh trong ®å thÞ G lµ sè ch½n.

Chøng minh

- §iÒu kiÖn cÇn: Gi¶ sö ®å thÞ G = <X, U> cã chu tr×nh Euler. Ta cÇn chøng minh

G lµ ®å thÞ liªn th«ng vµ víi mçi x ∈ X cã m(x) = 2k víi k lµ mét sè nguyªn d-

¬ng nµo ®ã.

ThËt vËy, gi¶ sö G = <X, U> kh«ng liªn th«ng hay G cã Ýt nhÊt hai thµnh phÇn

liªn th«ng G1 = <X1, U1> vµ G2 = <X2, U2>. Trong ®ã X1 ∪ X2 = X , U1 ∪ U2 = U,

gi÷a c¸c ®Ønh trong X1 vµ trong X2 kh«ng cã c¹nh hoÆc ®êng nèi víi nhau. Gi¶ sö

ω lµ 1 chu tr×nh Euler trong G. Theo ®Þnh nghÜa cña chu tr×nh Euler th× ω lµ chu

tr×nh ®i qua tÊt c¶ c¸c c¹nh trong G, mçi c¹nh ®óng 1 lÇn. NÕu ω cã ®Ønh chung

víi G1 = <X1, U1> th× ω lµ chu tr×nh n»m gän trong ®å thÞ G1. §iÒu nµy m©u thuÉn

víi ®Þnh nghÜa cña ω. Chøng tá ®å thÞ G = <X, U> lµ liªn th«ng.

B©y giê ta chøng minh mçi ®Ønh x ∈ X trong G ®Òu cã bËc ch½n, tøc lµ cÇn chØ ra

m(x) = 2k, víi k ∈ {1,2,...}. Tríc hÕt thÊy r»ng k ≠ 0 bëi v× nÕu k = 0 th× x lµ ®iÓm

c« lËp trong G, tøc lµ G kh«ng liªn th«ng, tr¸i víi ®iÒu ®· chØ ra. Gi¶ sö ngîc l¹i

35

G

1

= <X

1

, U1

>