ĐẠI HỌC CÔNG NGHỆ THÔNG TIN
!"#$%&'"'&()*+,-./
!"#$%#%&#
0
TP.HCM, Tháng 01 - 2014
'"('"
1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111112
345611111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111117
60 389:3;<=>4?3@11111111111111111111111111111A
01$B&.CDEFG1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111A
010101H&IF111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111A
010121/JKL1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111A
010171/JK.M111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111N
21!""!&(O"&$BPGH111111111111111111111111111111111111111111111111111111111111110Q
210101RKO"11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110Q
210121$%&'"'",!111111111111111111111111111111111111111111111111111111111111111111111111111111111111110Q
210171%STGUG!MF'V'"111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
2101A1FD!DW&X11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
2101Y1Z"11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111100
2101[1M\X'Z"1111111111111111111111111111111111111111111111111111111111111111111111111111111102
2101N1X2]^&11111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111102
62 :_:`ab?c3defg<=1111111111111111107
01+J+-DWPhGK1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111107
21!"1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111107
210101DW&X111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111107
210121M\'Z"111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111110Y
-&$BPGH1Z*G'$%&'"'$%&.]J•wD&†G!*”
-,U$T&C,$R&Px.yC•&$DEO*‚".%&(
-)F.••.$ƒ‚"EJ",R""&(D*/]&O"*1
*}€DEO*O]'LSF.Z*
L0 3U*+Gw)F.+O"&$BPGH1
L2 +J+-DWPhGK,.y$%&DE1
L7 —&Š$%&DE1
LA {%G$ƒ,/&(O"&$BPGHOz&'u&,MF.
J+D&vw
eRh&J+Ž+MF}w\wMFO*”z
\.„X!',E†CF&„-XFU$T&G„.†D†JF
h&&EE.—,.$ƒO+1
˜€Z(%{1{1™e•%.—•h&O&(&SW„
,SZSt.†(Ž&SvDF.BMFO*1
7
,#(.-/0(*12-345*678)*9-(:"
# ;<=>?@ABC>D
### EFA
.ŠH|•$R&~š|eC˜~1
Chu trình (có hướng) Hamilton GDE|•$R&~S%-')FX.”.ŠH1
Đường đi (có hướng) Hamilton G.$B&.|•$R&~S%-')FX.”.ŠH1
$,!*XDEFG•.‚POz&S].”C,X.$B&.FG
•.‚POz&S].”D•01
ŠHŽFDE|•$R&~FG&XGđồ thị Hamilton.
Ví dụ1›V.ŠH
@#
ŠHDwJ&•.$B&.˜G}D,E".”&CC}CŒ•O!G…C$&•
DEFG
F→O→→P→}→Œ→&→F
##G HIJK
J&‚
DE1{]•GGAwJ&†•Y.$ƒCZx1
F•&•†"'P\&Dv+'HGUDw1+Ou.2.”,
2
,,
A
^&
"Gw‚W&E.ŠH•GG7.”.‚G!'C•7'LGw
&1$,!*}K./|~MFHGUDwE.ŠHJ&•DE
FG1
Ví dụ 21Ž&Dz&.ŠHSFJ&•.$B&.FG1
@$
(S’G.$B&.FG1ŠHDw•0[.”Cw.$B&.•0Y
|ž~1
‘Cách 11eE.ŠH•2NwS]J&zDw.$B&'(G02
|žž~1
›V".”‚!'šŸ0C2C7CACYC[CN 1X˜
Cš0C111CNCG!'ƒ'"
Gw‚.”∈J&zDw.$B&.1eEXy'.”D&J&J/
Fw"!'˜
•&DBF•&y'‚1$,!*S]Gw‚".”
MFJ&zDwG
Jš
( )
∑
=
N
0i
FG!'.ŠH“.”0C2C111C“C.””&$B1F.y.”0Z,"
.”•GDw.$B&D•$E,–1™"€+'G‚DEFGMF
.ŠH1
DEŽ-$E,–G
0→2→7→A→Y→[→N→•→“→0
@L
›F*GLG$ƒDE"&•π¡A}/J.Š&ŠF!.$ƒ"
DEC•&G""€+'CSF
@&
0→7→Y→2→N→A→“→[→•→0
[
@M
0→Y→N→7→“→2→•→A→[→0
@N
0→N→“→Y→•→7→[→2→A→0
##$ HIJ<O
Định lý 1ŠH.M_
,RnG…|n≥7~•|n−0~¡2DEFG•&.
‚J&&FF|ŽGJ&•&~1
Chứng minh
$%&v$GB&(O"€+'“&$BDwOD•CF€Z*Pv&"€+'
}DEFGDw.ŠHSF|š2J•0~
0→2→7→111→2J→2J•0→0
@P
N
›F*DEGLG$ƒ‚&•π¡J}/J.Š&ŠF!.$ƒJ
"€+'1
FG1
Định lý 8: +OF.•&|~š_
|≥7~E.ŠH•DEFG1
Định lý 9RECS6?TUG.%.ŠH.”|≥7~1+P}&|~•P}&|,~≥
,RXy'.”J&J/FE.ŠH•DEFG1
Định lý 10:G.%.ŠH.”|≥7~,1+≥|−0C2~•2E
.ŠH•DEFG1
•
Định lý 11:.ŠH.%G.ŠHG$¥&'Z,RF!'.”e
0
,e
2
SF
FDP|e
0
~šFDP|e
2
~š≥2
+O!P}&|,~¢¡2,RX.”,MFCE•DEFG1
Đồ thị có hướng.
.ŠH•$R&,Rn.”1F•"J+)('"O†D&".H
GUSF
Định lý 12:|điều kiện đủ tồn tại chu trình có hướng Hamilton~
F1|}*}G~+.ŠHGw&,
P}&|~•P}&|,~≥2n−0∀C,∈J&J/F
E•DE•$R&FG1
O1|GF‘D~+.ŠHGw&,
P}&|,~≥n∀,∈
P}&
|,~≥¡2#P}&
<
|,~≥¡2∀,∈
thì G có đường đi có hướng Hamilton.
Z*&BW&FS–&wŽ.$B&.,DE•$R&FGD&
.ŠH•$R&.M|•.ŠHG•.M~1D$R+G.HGUJ¦&.HSvŠ.$B&
.•$R&FGD&.ŠH•$R&.M1
Định lý 14 (Konig)X.ŠH•$R&.M./•.$B&.•$R&FG1
Định lý 15 (Camion)ŠH•$R&.M•DE•$R&FGJ,”
J•Gw&1
“
G V>>DWWVX>DW;CE
G## >JX>DW
‚&$B€-'"•‚'].•]R•
−
0
']J"C™'].W&‚GLCDŠ)F*,/']OF.L1uw.
}DEv.†.‚P‹&‚&" . .$B&.)FG&t-|J(&
"&hFF']•††GvG*&$B&yB&FL.y
'„MFDEC111,€}$D$R~1
›V .Š H .L* .M š|eC˜~C ,R ešŸ0C 2C 111C C • DX& S] ,R DX& S]
§
š|C§~•†J"
§
š|§C~1$,!*CF•†€}$G‚.ŠH•
$R&.L*.M¨¤}&IF,RXC§š0C2C111CC©§CG•|C§~C
|§C~
O"&$BPGH1{F.•F”L€Vh&!'•!P$Ru%&"DH
\wE.$ƒ1
0Q
G#$ " ZCSCVOAY[Y>DW
+ J& €" .H '] €- '" E•ª DEC ™ DE
Ž&,R‚",H.•MF!'Ÿ0C2C111C 1•+D$R']€-
'"E•-(G|
−
0~ªDE1
G#L A>?V?\>
a«D&‹&'„MF‚DES–ŽF.W&‚'L’Dw™P•&
,™‚MFFD!'„š|
§
~1?.•+FD•OR™'L’MF‚
P•&|F*‚‚~.^&‚&"DHE'„MF-(DES–&(.‚
G$ƒ&C,E+DE]$S–J&F*.‹1eE,!*++D•OR"
'L’MF™P•&,™‚.‚z&S]SF.$ƒFD!J&Z
,™‚•&$™P•&ŽF„-‚S]QCE‹&"z&S]D•..•S–
F!P$RMFXDE1M\D•OR*&XGM\DW&XC"z&
S]D•T™P•&|‚~&XGz&S]DW&XP•&|‚~CFD!.$ƒ&XGF
D!DW&X1
Thủ tục rút gọn:
◊Đầu vào FD!'„š|c
ij
~
◊Đầu ra FD!DW&X,‹&z&S]DW&XSum
◊Thuật toán
|~_T
Sum šQ¬|”"'P\&FD!'„OF.L~
|~aW&XP•&
→ 111 → 111 →
|C§~ 111 |DCS~ 111 |JC~
,--("P&|C~Oz&".y
š∞1
aW&XFD!'„F•!P$Rβ šβ•|‹&z&S]DW&X~1
00
F•†+'\M\'Z"}"*,RFD!'„.—
.$ƒK”,&(0O!1eKX.†'Z"FS–OT\
+'}1
•"!'
2
‘-|DCS~Oz&".y
DS
š∞1
‘vKM\DW&X,RFD!'„$%&Ž&,„!P$R
β šβ•|‹&z&S]DW&X~"1
F•†+'\M\'Z"}"*,RFD!'„.—
.$ƒK”^&!P$R$%&Ž&1eKX.†'Z"FS–
OT\+'}1
G#M O>^_Y]W
‚"G&GFX'Z"|DCS~SF!P$RMF"
J&ŽF|DCS~S–•&/-1
Thủ tục chọn cạnh phân nhánh (r,s)
◊Đầu vào FD!DW&XO!J1
◊Đầu ra 'Z"|DCS~1
◊Thuật toán
|~_T α š−∞¬
|~eR™y'|C§~(c
∞
2Q Y 0Y
2 0Q
∞
0Y 2Q
7 • Y
∞
2Q
A Y 2 2Y
∞
G V>>DW
?vF,'LGU*+TDw!""!.$ƒ.H&IFOT"
$%&DESF
G## B?\>
Thủ tục rút gọn:
•Đầu vào FD!'„š|
§
~
•Đầu ra FD!DW&X,‹&z&S]DW&XSum
•Thuật toán
|~_T { šQ¬
|~aW&XP•&
eR™P•&D•0.+MFFD!vK
‘E'L’
D§
šαu-DwP•&1
‘D•-("'L’DwP•&.‚G$ƒ&α1
‘‚&PŠ { š{•α
|~aW&X‚
07
7 AY 0N ∞ 7[ 0[ 2• 0[
A 7“ “Q •Q ∞ Y[ N N
Y 2• A[ •• 77 ∞ 2Y 2Y
[ 7 •• 0• A[ “2 ∞ 7
F+DW&XFD!*.†E!P$R-(DE
‘Khởi tạo
y { šQ¬
‘Rút gọn các dòng
"'L’u-Dw"P•&}Žv0C2C7CACYC[G7CAC0[CNC2YC
71
D•OR"'L’P•&0C2C7CACYC[."z&S]DW&X$%&Ž&Dw
‚F.$ƒFD!
0 2 7 A Y [
0 ∞ Q “Q 0Q 7Q [
2 Q ∞ N7 7• 0N 02
7 2“ 0 ∞ 2Q Q 02
A 72 •7 N2 ∞ A“ Q
Y 7 20 [7 • ∞ Q
[ Q •Y 0Y A7 •“ ∞
α Q Q 0Y • Q Q
‚&PŠ"z&S]DW&XF.$ƒ
{ š{•7•A•0[•N•2Y•7šY•
‘Rút gọn các cột
"'L’u-Dw"‚}Žv0C2C7CACYC[GQCQC0YC•CQCQ1
D•OR"'L’‚0C2C7CACYC[."z&S]DW&X$%&Ž&Dw
&|F.$ƒFD!DW&X~
0A
0 2 7 A Y [
0 ∞ Q NY 2 7Q [
2 Q ∞ Y• 7Q 0N 02
aW&XFD!'„F•!P$Rβ šβ•|‹&z&S]DW&X~1
F•†+'\M\'Z"}"*,RFD!'„.—
.$ƒK”,&(0O!1eKX.†'Z"FS–OT\
+'}1
•"!'
2
‘-|DCS~Oz&".y
DS
š∞1
‘vKM\DW&X,RFD!'„$%&Ž&,„!P$R
β šβ•|‹&z&S]DW&X~"1
F•†+'\M\'Z"}"*,RFD!'„.—
.$ƒK”^&!P$R$%&Ž&1eKX.†'Z"FS–
OT\+'}1
•Ví dụ1›V+',„P\Dw1(S’FX'Z"G|DCS~š|[C7~1"
DES–.$ƒ'ZF"
0
ŽF"DE)F|[C7~,
2
ŽF"DEJ&)F|[C7~1
•›V"!'
0
‘(-'FD!'„Oz&"GP•&[,‚71
‘&•-DE
0Y
-|7C[~Oz&".y7[š∞1
0 2 7 A Y [
0 ∞ Q 2N 2 7Q [
2 Q ∞ 0Q 7Q 0N 02
7 2“ 0 ∞ 02 Q 02
A 72 •7 0Q ∞ A“ Q
Y 7 20 Q Q ∞ Q
[ Q •Y ∞ 7Y •“ ∞
,!P$R
β š β•αš •0•A• š 02“
F•†+'\M\'Z"}"*,RFD!'„.—
.$ƒK”^&!P$R$%&Ž&|02“~1eKX.†'Z"F
S–OT\+'}1
0[
G#$ O>^_Y]W
‚"G&GFX'Z"|DCS~SF!P$RMF"J&
ŽF|DCS~S–•&/-1
Thủ tục chọn cạnh phân nhánh (r,s)
•Đầu vào FD!DW&XO!J
•Đầu ra 'Z"|DCS~1
•Thuật toán
|~_T α š‘∞¬
|~eR™y'|C§~(
§
šQ|š0C111CJ¬§š0C111CJ~vK
‘›".H
DšŸ
≠§
SšŸ
§
S–.$ƒ'Z2"
00
&Š"DE)F|AC[~,
02
&Š"DEJ&)F|AC[~1
•"
02
•FD!'„$%&Ž&$SF
0N
0 2 A Y [
0 ∞ Q 2 7Q [
2 Q ∞ 7Q 0N 02
7 2“ 0 02 Q ∞
A 72 •7 ∞ A“ ∞ 72
Y 7 20 Q ∞ Q
α
vKM\DW&XF.$ƒFD!DW&X
0 2 A Y [
0 ∞ Q 2 7Q [
2 Q ∞ 7Q 0N 02
7 2“ 0 02 Q ∞
A Q Y0 ∞ 0N ∞
Y 7 20 Q ∞ Q
,R‹&z&S]DW&Xαš72,!P$Rβšβ•αš•0•72š0071
•"
00
‘3&A,‚[F•S–•FD!'„-'A$%&Ž&
!'
000
&Š"DED&
00
)F|2C0~S–•FD!'„
-'7$%&Ž&CSFJ.—G&2,‚0
2 A Y
0 Q 2 7Q
7 0 ∞ Q
Y 20 Q ∞
‘ &•-DE
y
02
š∞.†-|0C2~1
|2C0~J&]+'^&"XD$RG|[C7~,|AC[~CwFJ&
'(-"J"1F•FD!'„
2 A Y
0 ∞ 2 7Q 2
7 0 ∞ Q
Y 20 Q ∞
0 α
FD!'„.$ƒDW&X$SF
2 A Y
0 ∞ Q 2•
7 Q ∞ Q
Y 2Q Q ∞
!P$Rβšβ•αš•0•7š•A1
$%&vF+'\M\X'Z"C'Z",DW&X.]
,R
000
™DE•1{FJ.—X‘2CF'(X]2
•G13W*FD!DW&X•O!2,G‚D&FP&SF
, ,
' Q ∞ ' ∞ Q
) ∞ Q ) Q ∞
|~ |~
^&!P$Rβ1
D&D$B&ƒ'|~FXF|'C~,|)C,~C•D&D$B&ƒ'|~
FXF|'C,~,|)C~1‹&'„Gβ1
•Ví dụ1›V+',„P\Dw1{FJX"|[C7~C|AC[~C|2C0~C|0CA~F•FD!
DW&X
2 Y
7 ∞ Q
Y Q ∞
2Q
,!P$Rβš0QA1FX]F•GG|7CY~,|YC2~,.$ƒ
DE
|0CA~C|AC[~C|[C7~C|7CY~C|YC2~C|2C0~
,R‹&'„Oz&βš0QA1
"DEDw•†O†P®Oz&S%.ŠSF
Cận dưới Cận dưới
βš βš
2
-( DE
•0 DE J&ŽF|[C7~ 02“
0
02
0002
•!P$RGR%
'
š0QAC
,E+"DEMF"".••‹&'„GR%
'
1”•"
002
•!P$RG0Q0u%
'
1+'}FEDER}"*1
20
•"
002
S–•FD!'„-'A$%&Ž&
0 2 A Y
0 ∞ Q 2 7Q
2 ∞ ∞ 7Q 0N 0N
7 2“ 0 ∞ Q
Y 7 20 Q ∞
7 α
T.Z*
20
š∞.†-|2C0~1!P$R€-'"MF
00
Gβš•01
aW&XFD!'„F.$ƒFD!
0 2 A Y
0 ∞ Q 2 7Q
2 ∞ ∞ 07 Q
|0CA~•!P$ROz&0Q7•00š00A¢0QAš
'
1FGJ&€V"
*hF1
•"
00200
&Š"DE)F|0CA~•FD!'„
2 Y
2 ∞ Q
7 0 ∞ 0
α
|0CA~^&,R".—XP—*
|YC0~C|0CA~C|AC[~C|[C7~
,E+F-|7CY~COz&".y
7Y
š∞1aW&XF.$ƒFD!
2 Y
2 ∞ Q
7 Q ∞
,!P$Rβš0Q7•0š0QA1
X+'2•G|7C2~,|2CY~F.$ƒDE
|YC0~C|0CA~C|AC[~C|[C7~C|7C2~C|2CY~
,R‹&'„G0QA1
•Kết luận FDEE.$ƒG]$,R'„-'-G0QA
|0CA~C|AC[~C|[C7~C|7CY~C|YC2~C|2C0~
,
|0CA~C|AC[~C|[C7~C|7C2~C|2CY~C|YC0~
27
,$n-o"8pcq
r"WIAXWD`<sC>?k
02
111F
0
|FD!'„~
F
20
F
22
111F
2
11111111111111111111
F
0
F
2
111F
◊µG}PhGK.LDF ae˜31<•-DW
‘D$B&ƒ'J&ŠDEFG
<3<93˜
‘D$B&ƒ'ŠDEFG
<3<{ |'„]$~
<393˜ |DE]$~
€
0
→€
2
→111→€
→€
A <3<93˜
∞ 7 A ∞
A ∞ Y ∞
2 0 ∞ ∞
∞ ∞ ∞ ∞
2Y
Copyright: Tài liệu đại học ©