(http://vdvinh-nd.blogspot.

com/)

th Euler v th Hamilton
16:48 CNTT (http://vdvinh-nd.blogspot.com/search/label/CNTT) 0 Comments

(http://www.blogger.com/post-edit.g?blogID=1910393248346314153&postID=3096976335441239444)1. TH EULER
http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/next.gif nh ngha 1. Chu trnh n trong th G i
qua mi cnh ca n mt ln c gi l chu trnh Euler. ng i n trong G i qua mi cnh ca n mt ln c gi l ng i Euler.
th c gi l th Euler nu n c chu trnh Euler, v gi l th na Euler nu n c ng i Euler.
R rng mi th Euler lun l na Euler, nhng iu ngc li khng lun ng.
http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/bluesq.gif Th d 1. th G1 trong hnh 1 l th
Euler v n c chu trnh Euler a, e, c, d, e, b, a. th G3 khng c chu trnh Euler nhng n c ng i Euler a, c, d, e, b, d, a, b, v th G3 l th
ca Euler. th G2 khng c chu trnh cng nh ng i Euler.

(http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/hinh2_01.gif)

Hnh 1. th G1, G2, G3

http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/bluesq.gif Th d 2. th H2 trong hnh 2 l th
Euler v n c chu trnh Euler a, b, c, d, e, a. th H3 khng c chu trnh Euler nhng n c ng i Euler c, a, b, c, d, b v th H3 l th na
Euler. th H1 khng c chu trnh cng nh ng i Euler.

(http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/hinh2_02.gif)

Hnh 2. th H1, H2, H3

iu kin cn v mt th l mt th Euler c Euler tm ra vo nm 1736 khi ng gii quyt bi ton hc ba ni ting th gii thi v
by ci cu thnh ph
Konigsberg v y l nh l u tin ca l thuyt th.
http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/bluearrow.gif nh l 1 (Euler). th v hng lin
thng G l th Euler khi v ch khi mi nh ca G u c bc chn.
chng minh nh l trc ht ta chng minh b :
http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/bluesq.gif B . Nu bc ca mi nh ca th G
khng nh hn 2 th G cha chu trnh.
Chng minh.
Nu G c cnh lp th khng nh ca b l hin nhin. V vy gi s G l n th. Gi v l mt nh no ca G. Ta s xy dng theo
qui np ng i
v v1 v2 . . .
trong v1 l nh k vi v, cn vi i1 chn vi+1 # vi-l (c th chn vi+1 nh vy l v deg(vi) 2). Do tp nh ca G l hu hn , nn sau mt
s hu hn bc ta phi quay li mt nh xut hin trc . Gi nh u tin nh th l vk. Khi , on ca ng i xy dng nm gia
 hai nh vk l 1 chu trnh cn tm.
Chng minh nh l:
http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/0point.gif Cn. Gi s G l th Euler tc l tn
ti chu trnh Euler P trong G. Khi c mi ln chu trnh P i qua mt nh no ca G bc ca nh tng ln 2. mt khc mi cnh ca
th xut hin trong P ng mt ln, suy ra mi nh ca th iu c bc chn.
http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/0point.gif . Quy np theo s nh v s cnh
ca G. Do G lin thng v deg(v) l s chn nn bc ca mi nh ca n khng nh hn 2. T theo b G phi cha chu trnh C. Nu C i
qua tt c cc cnh ca G th n chnh l chu trnh Euler. Gi s C khng i qua tt c cc cnh ca G. Khi loi b khi G tt c cc cnh
thuc C ta thu c mt th mi H vn c bc l chn. Theo gi thit qui np, trong mi thnh phn lin thng ca H iu tm c chu trnh
Euler. Do G l lin thng nn trong mi thnh phn ca H c t nht mt nh chung vi chu trnh C. V vy, ta c th xy dng chu trnh Euler
trong G nh sau: bt u t mt nh no ca chu trnh C, i theo cc cnh ca C chng no cha gp phi nh khng c lp ca H. Nu gp
phi nh nh vy ta s i theo chu trnh Euler ca thnh phn lin thng ca H cha nh . Sau li tip tc i theo cnh ca C cho n khi
gp phi nh khng c lp ca H th li theo chu trnh Euler ca thnh phn lin thng tng ng trong Hv.v (xem hnh 3). Qu trnh s kt
thc khi ta tr v nh xut pht , tc l thu c chu trnh i qua mi cnh ca th ng mt ln.

(http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/hinh2_03.gif)

Hnh 3. Minh ho cho chng minh nh l 1.

http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/bluesq.gif H qu 2. th v hng lin thng G l
na Euler khi v ch khi n c khng qu 2 nh bc l.
Chng minh. Thc vy , nu G c khng qu 2 nh bc l th s nh bc l ca n ch c th l 0 hoc 2. Nu G khng c nh bc l th
theo nh l 1, n l th Euler. Gi s G c 2 nh bc l l u v v. Gi H l th thu c t G bng cch thm vo G mt nh mi w v hai
cnh (w,u) v(w,v). Khi tt c cc nh ca H iu c bc chn, v th theo nh l 1, n c chu trnh Euler C. Xo b khi chu trnh ny nh
w v hai cnh k n ta thu c ng i Euler trong th G.

Gi s G l th Euler, t chng minh nh l ta c th tc sau tm chu trnh Euler trong G.

 Void Euler_Cycle)
{
STACK= ; CE= ;
Chon u la mot dinh nao do cua do thi;
STACK u;
While STACK<>
{
X=top(STACK); (* x la phan tu dau STACK)
If Ke(x)<>
{
Y=dinh dau tien trong danh sach Ke(x);
STACK y;
(* loai bo canh (x,y) khoi do thi *)
Ke(x)=Ke(x)\{ y} ;
Ke(y)=Ke(y)\{ x} ;
}
Else
{
x STACK; CE x;

Gi s G l th Euler, thut ton n gin sau y cho php xc nh chu trnh Euler khi lm bng tay.
Thut ton Flor
Xut pht t mt nh u no ca G ta i theo cc cnh ca n mt cch tu ch cn tun th 2 qui tc sau:
(1) Xo b cnh i qua ng thi xo b c nhng nh c lp to thnh.
(2) mi bc ta ch i qua cu khi khng cn cch la chon no khc.
* Mt cnh ca th G c gi l cu, nu khi xa cnh khi th th lm tng s thnh phn lin thng ca G.
Chng minh tnh ng n ca thut ton.
Trc tin ta ch ra rng th tc trn c th thc hin mi bc. Gi s ta i n mt nh v no , khi nu v#u th th con cn li H l
lin thng v cha ng hai nh bc l l v v u. Theo h qu trong H c ng i Euler P t v ti u. Do vic xo b cnh u tin
ca ng i P khng lm mt tnh lin thng ca H, t suy ra th tc c th thc hin mi bc. Nu v=u th lp lun trn s vn ng
chng no vn cn cnh k vi u.
Nh vy ch cn phi ch ra th tc trn dn n ng i Euler. Thc vy trong G khng th cn cnh cha i qua khi m ta s dng cnh cui
cng k vi u (trong trng hp ngc li, vic loi b mt cnh no k vi mt trong s nhng cnh cn li cha i qua s dn n mt
th khng lin thng, v iu l mu thun vi gi thit ii).
Chng minh tng t nh trong nh l 1 ta thu c kt qu sau y cho th c hng.
http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/bluearrow.gif nh l 2. th c hng lin thng
mnh l th Euler khi v ch khi
Deg+(v)=deg- (v), " v V.
2. TH HAMILTON
Trong mc ny chng ta xt bi ton tng t nh trong mc trc ch khc l ta quan tm n ng i qua tt c cc nh ca th, mi nh ng
mt ln. S thay i tng chng nh l khng ng k ny trn thc t dn n s phc tp ho vn cn gii quyt.
http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/next.gif nh ngha 2. ng i qua tt c cc nh
ca th mi nh ng mt ln c gi l ng i Hamilton. Chu trnh bt u t mt nh v no qua tt c cc nh cn li mi nh ng mt
ln ri quay tr v v c gi l chu trnh Hamilton. th G c gi l th Hamilton nu n cha chu trnh Hamilton v gi l th na
Hamilton nu n c ng i Hamilton.
R rng th Hamilton l na Hamilton, nhng iu ngc li khng cn ng.
http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/bluesq.gif Th d 3. Trong hnh 4: G3 l Hamilton, G2 l
na Hamilton cn G1 khng l na Hamilton.

(http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/hinh2_04.gif)

Hnh 4. th Hamilton G3, na Hamilton G2 , v G1.

Cho n nay vic tm mt tiu chun nhn bit th Hamilton vn cn l m, mc d y l mt vn trung tm ca l thuyt th. Hn th na,
cho n nay cng cha c thut ton hiu qu kim tra mt th c l Hamilton hay khng. Cc kt qu thu c phn ln l iu kin
mt th l th Hamilton. Phn ln chng iu c dng "nu G c s cnh ln th G l Hamilton". Mt kt qu nh vy c pht biu
trong nh l sau y.
http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/bluearrow.gif nh l 3 (Dirak 1952). n th v
hng G vi n>2 nh, mi nh c bc khng nh hn n/2 l th Hamilton.
Chng minh:
Thm vo th G k nh mi v ni chng vi tt c cc nh ca G. gi s k l s nh nht cc nh cn thm vo cho th thu c G
l th Hamilton. Ta s ch ra rng k=0. Thc vy, gi s ngc li l k >0. K hiu
v, p, w, . . ., v
l chu trnh Hamilton trong G, trong v, w l nh ca G cn p l mt trong s cc nh mi. Khi w khng k vi v v nu ngc li, ta
khng cn s dng p v iu l mu thun vi gi thit k nh nht. Hn th na nh (w chng hn) k vi w khng th i lin sau nh v
(k vi v) v rng khi c th thay
v p w . . . v w . . . v
bi v v . . . w w . . . v
bng cch o ngc on ca chu trnh nm gia w v v. T suy ra l s nh ca th G khng k vi w l khng nh hn s nh k
vi v (tc l t nht cng l bng n/2+k), ng thi s nh ca G k vi w t ra l phi bng n/2+k. Do khng c nh no ca G va khng
k, li va k vi w, cho nn tng s nh ca th G (G c n+k nh) khng t hn n+2k. Mu thun thu c chng minh nh l.
nh l sau l tng qut ho ca nh l Dirak cho th c hng:
http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/bluearrow.gif nh l 4.
Gi s G l c hng lin thng vi n nh. Nu
+
deg (v)n/2, deg (v) n/2, " v

th G l Hamilton.
C mt s dng th m ta c th bit khi no l th Hamilton. Mt v d nh vy l th u loi. th u loi l th c hng m
trong hai nh bt k ca n c ni vi nhau bi ng mt cung. Tn u loi xut hin nh vy v th nh vy c th dng biu din kt
qu thi u bng chuyn, bng bn hay bt c mt tr chi no m khng cho php ho. Ta c nh l sau:
http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/bluearrow.gif nh l 5 ( th y )
i) Mi th u loi l na Hamilton.
ii) Mi th u loi lin thng mnh l Hamilton.
http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/bluesq.gif Th d 4. th u loi D5, D6 c cho
trong hnh 5.
 (http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/hinh2_05.gif)

Hnh 5. th u loi D5, u loi lin thng mnh D6

Thut ton lit k tt c cc chu trnh Hamilton ca th
Thut ton sau y c xy dng da trn c s thut ton quay lui cho php lit k tt c cc chu trnh Hamilton ca th.
Void Hamilton(int k)
(* liet ke cac chu trinh Hamilton thu duoc bang viec phat trien day dinh (X[1],. . . , X[k-1]) cua do thi G=(V,E) cho boi danh sach ke: Ke(v), v V *)
{
For y Ke(X[k-1])
if (k =N+1)&& (y=v0) Ghinhan(X[1],. . . , X[n], v0)
else
if Chuaxet[y] then
{
X[k]=y;
Chuaxet[y]=false;
Hamilton(k+1);
Chuaxet[y]=true;
}
}
(* Main program*)
Void main()
{
for v V Chuaxet[v]=true;
X[1]=0; (* v0 la mot dinh nao do cua do thi *)
Chuaxet[v0]=false;
Hamilton(2);
}

http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/bluesq.gif Th d 5. Hnh 6 di y m t cy tm kim

theo thut ton va m t.

(http://dembinhyen.free.fr/UDS/Ebook/CD1/Ly%20Thuyet%20Do%20Thi/Htm/images/hinh2_06.gif)

Hnh 6. th v cy lit k chu trnh Hamilton ca n theo thut ton quay lui
Trong trng hp th c khng qu nhiu cnh thut ton trn c th s dng kim tra th c phi l Hamilton hay khng.

Nobita
(http://www.facebook.com/sharer.php?u=http://vdvinh-nd.blogspot.com/2012/04/o-thi-euler-va-o-thi-hamilton.html&title= th Euler v
th Hamilton)

(http://twitter.com/share?url=http://vdvinh-nd.blogspot.com/2012/04/o-thi-euler-va-o-thi-hamilton.html&title= th Euler v th Hamilton)

(https://plus.google.com/u/0/share?url=http://vdvinh-nd.blogspot.com/2012/04/o-thi-euler-va-o-thi-hamilton.html)

(http://reddit.com/submit?&url=http://vdvinh-nd.blogspot.com/2012/04/o-thi-euler-va-o-thi-hamilton.html&title= th Euler v th
Hamilton)

(http://del.icio.us/post?url=http://vdvinh-nd.blogspot.com/2012/04/o-thi-euler-va-o-thi-hamilton.html&title= th Euler v th Hamilton)

Related Posts

Ton Ri Rc - L thuyt Bng bm Tm kim da

th trn bng bm

(http://vdvinh (http://vdvinh (http://vdvinh

0 nhn xt:

(https://www.blogger.com/comment-iframe.g?
blogID=1910393248346314153&postID=3096976335441239444&blogspotRpcToken=5051882)

Nhp nhn xt ca bn...

Nhn xt vi tn: Unknown (Goo ng xut

Xut bn Xem trc Thng bo cho ti

Bi ng Mi hn (http://vdvinh-nd.blogspot.com/2012/05/toan-roi-rac-ly-thuyet-o-thi.html) Trang ch (http://vdvinh-nd.blogspot.com/)

Bi ng C hn (http://vdvinh-nd.blogspot.com/2012/03/bang-bam-tim-kiem-dua-tren-bang-bam.html)

Popular Posts

V d v thut ton Johnson (http://vdvinh-nd.blogspot.com/2012/05/vi-du-ve-thuat-toan-johnson.html)

Thut ton JOHNSON 1. Chia cc chi tit thnh 2 nhm: + Nhm 1: gm cc chi tit c thi gian gia cng chi tit trn my A b hn trn my...

Danh sch lin kt kp - Code v d (http://vdvinh-nd.blogspot.com/2012/02/danh-sach-lien-ket-kep-code-vi-du.html)

Danh sch lin kt kp Cho danh sch lin kt kp c cu trc: struct hs { char ht [30]; ...

Li nhun bnh qun v gi c sn xut (http://vdvinh-nd.blogspot.com/2011/10/loi-nhuan-binh-quan-va-gia-ca-san-xuat.html)

Bin php cnh tranh: t do di chuyn t bn t ngnh ny sang ngnh khc, tc l phn phi t bn (c v v) vo cc ngnh sn xut khc nh...

Mt s thut ton c bn (http://vdvinh-nd.blogspot.com/2011/07/mot-so-thuat-toan-co-ban.html)

Kim tra 1 s nguyn t + nh ngha : L s nguyn ln hn 1, ch c 2 c l 1 v chnh n. Cc s nguyn t t 1-100: ...

th Euler v th Hamilton (http://vdvinh-nd.blogspot.com/2012/04/o-thi-euler-va-o-thi-hamilton.html)

 1. TH EULER nh ngha 1 . Chu trnh n trong th G i qua mi cnh ca n mt ln c gi l chu trnh Euler. ...

Thut ton nhnh v cn p dng cho BT Ci ti (http://vdvinh-nd.blogspot.com/2012/03/thuat-toan-nhanh-va-can-ap-dung-cho-bt.html)

I.t vn 1.Bi ton thc t Mt nh thm him cn em theo 1 ci ti c trng lng khng qu b,c n vt mang theo. v...

Ton Ri Rc - L thuyt th (http://vdvinh-nd.blogspot.com/2012/05/toan-roi-rac-ly-thuyet-o-thi.html)

th l mt cu trc ri rc bao gm cc nh v cc cnh ni cc nh . Ta phn bit cc loi th khc nhau bi kiu v s ln...

Labels

Android (http://vdvinh-nd.blogspot.com/search/label/Android?&max-results=7)

CNTT (http://vdvinh-nd.blogspot.com/search/label/CNTT?&max-results=7)

Hnh nh (http://vdvinh-nd.blogspot.com/search/label/H%C3%ACnh%20%E1%BA%A2nh?&max-results=7)

Ios (http://vdvinh-nd.blogspot.com/search/label/Ios?&max-results=7)

Kin Thc (http://vdvinh-nd.blogspot.com/search/label/Ki%E1%BA%BFn%20Th%E1%BB%A9c?&max-results=7)

Linh Tinh (http://vdvinh-nd.blogspot.com/search/label/Linh%20Tinh?&max-results=7)

Th Thut (http://vdvinh-nd.blogspot.com/search/label/Th%E1%BB%A7%20Thu%E1%BA%ADt?&max-results=7)

(https://www.instagram.com/whatsltd4us/)

(https://plus.google.com/u/0/118063353303739108302/)

(https://twitter.com/MoltingMixed)

(https://www.facebook.com/banhmanthau)

About us

Labels
Android (http://vdvinh-nd.blogspot.com/search/label/Android?&max-results=7) CNTT (http://vdvinh-nd.blogspot.com/search/label/CNTT?&max-results=7)

Hnh nh (http://vdvinh-nd.blogspot.com/search/label/H%C3%ACnh%20%E1%BA%A2nh?&max-results=7) Ios (http://vdvinh-nd.blogspot.com/search/label/Ios?&max-results=7)

Kin Thc (http://vdvinh-nd.blogspot.com/search/label/Ki%E1%BA%BFn%20Th%E1%BB%A9c?&max-results=7) Linh Tinh (http://vdvinh-nd.blogspot.com/search/label/Linh%20Tinh?&max-results=7)

Th Thut (http://vdvinh-nd.blogspot.com/search/label/Th%E1%BB%A7%20Thu%E1%BA%ADt?&max-results=7)

Tng s lt xem trang

61233

Copyright 2014 VinhVu (http://vdvinh-nd.blogspot.com/) / Created by ThemeXpose (http://www.themexpose.com/)