{VERSION 5 0 "IBM INTEL NT" "5.0" }
{USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier" 1 10 128 0 0 1 0 1 0 
0 1 0 0 0 0 1 }{CSTYLE "2D Math" -1 2 "Times" 0 1 0 0 0 0 0 0 2 0 0 0 
0 0 0 1 }{CSTYLE "2D Comment" 2 18 "" 0 0 0 128 0 1 0 0 0 0 0 0 0 0 0 
1 }{CSTYLE "2D Input" 2 19 "" 0 0 128 0 0 1 0 0 0 0 0 0 0 0 0 1 }
{CSTYLE "2D Output" 2 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 1 }
{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 
2 2 1 1 1 1 }1 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 1" -1 3 1 
{CSTYLE "" -1 -1 "Times" 1 18 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 6 
6 1 0 1 0 2 2 0 1 }{PSTYLE "Heading 2" -1 4 1 {CSTYLE "" -1 -1 "Times
" 1 14 0 0 0 1 2 1 2 2 2 2 1 1 1 1 }1 1 0 0 4 4 1 0 1 0 2 2 0 1 }
{PSTYLE "Maple Output" -1 11 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 
2 2 2 2 2 2 1 1 1 1 }3 3 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Maple Plot
" -1 13 1 {CSTYLE "" -1 -1 "Times" 1 12 0 0 0 1 2 2 2 2 2 2 1 1 1 1 }
3 1 0 0 0 0 1 0 1 0 2 2 0 1 }{PSTYLE "Title" -1 18 1 {CSTYLE "" -1 -1 
"Times" 1 18 0 0 0 1 2 1 1 2 2 2 1 1 1 1 }3 1 0 0 12 12 1 0 1 0 2 2 
19 1 }}
{SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 21 "Probl\351m k-kliky grafu
" }{MPLTEXT 1 0 0 "" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 13 "Inicializ
acia" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 69 "restart; with(networ
ks): read `\\\\\\\\Xpc\\\\Math\\\\Maple\\\\pac\\\\netw2.mpl`:" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 49 "r := `r`: max_r := 1000: #ma
ximalna dlzka tabulky" }}}{SECT 0 {PARA 4 "" 0 "" {TEXT -1 13 "inicial
izuj()" }}{EXCHG {PARA 0 "> " 0 "" {XPPEDIT 19 1 "inicializuj := proc \+
()\nglobal n, max_r, otec, alpha, beta, koniec, odpoved, f, r, odkryty
;\n n := nops(vertices(G)); r := 0; \n otec := array(0 .. max_r-1); \n
 alpha := array(0 .. max_r-1); beta := array(0 .. max_r-1); f := array
(1 .. k); \n odkryty := array(0 .. max_r-1);\n koniec := false; odpove
d := false\nend:" "6#>%,inicializujGf*6\"7\"F&F&C+>%\"nG-%%nopsG6#-%)v
erticesG6#%\"GG>%\"rG\"\"!>%%otecG-%&arrayG6#;F4,&%&max_rG\"\"\"F=!\"
\">%&alphaG-F86#;F4,&F<F=F=F>>%%betaG-F86#;F4,&F<F=F=F>>%\"fG-F86#;F=%
\"kG>%(odkrytyG-F86#;F4,&F<F=F=F>>%'koniecG%&falseG>%(odpovedGFYF&6,F*
F<F6F@FFFXFenFLF3FRF&" }}}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 13 "Imple
ment\341cia" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 75 "nulujF := pro
c() local i; global f; for i from 1 to k do f[i] := 0 od; end:" }}
{PARA 0 "" 0 "" {TEXT 18 33 "Pravidlo pre vyber dalsej pozicie" }}
{PARA 0 "> " 0 "" {XPPEDIT 19 1 "pravidloP := proc() #vyber kandidata
\nglobal n, f; local i;\n i := k;\n while (i > 1) and (f[i] <> 0) do\n
  i := i - 1;\n od;\nRETURN(i)\nend:" "6#>%*pravidloPGf*6\"7#%\"iGF&F&
C%>F(%\"kG?(F&\"\"\"F-F&32F-F(0&%\"fG6#F(\"\"!>F(,&F(F-F-!\"\"-%'RETUR
NG6#F(F&6$%\"nGF2F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 18 41 "Zistenie, \+
ci (a, b) je generator prechodu" }}{PARA 0 "> " 0 "" {XPPEDIT 19 1 "a_
b_generuje_syna := proc(a, b)\n#'a' is a position, 'b' is a vertex\nlo
cal V, i, j;\nglobal M, k, f, f1;\n f1 := f; f1[a] := b;\n #print(f1, \+
a, b);\n V := \{\}; #vytvor mnozinu vrcholov\n for i from a to k do\n \+
 if member(f1[i], V) then RETURN(false) fi:\n  V := V union \{f1[i]\} \+
\n od;\n for i from a to k-1 do\n  for j from i+1 to k do\n   #print(f
1[i], f1[j]);\n   if M[f1[i], f1[j]] = 0 then RETURN(false) fi;\n  od;
\n od;\n RETURN(true);\nend:" "6#>%2a_b_generuje_synaGf*6$%\"aG%\"bG7%
%\"VG%\"iG%\"jG6\"F-C(>%#f1G%\"fG>&F06#F'F(>F*<\"?(F+F'\"\"\"%\"kG%%tr
ueGC$@$-%'memberG6$&F06#F+F*-%'RETURNG6#%&falseG>F*-%&unionG6$F*<#&F06
#F+?(F+F'F8,&F9F8F8!\"\"F:?(F,,&F+F8F8F8F8F9F:@$/&%\"MG6$&F06#F+&F06#F
,\"\"!-FC6#FE-FC6#F:F-6&FUF9F1F0F-" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 
18 35 "Zapis informacii o stave do matriky" }}{PARA 0 "> " 0 "" 
{XPPEDIT 19 1 "zapis_syna_do_matriky := proc(v, a, b)\nglobal alpha, b
eta, r, otec, obsadeny, koniec, odkryty;\n if r > max_r-1 then\n  lpri
nt(`Nedostatok pamate`);\n  koniec := true;\n  RETURN();\n else\n  r :
= r + 1;\n  otec[r] := v; alpha[r] := a; beta[r] := b;     odkryty[r] \+
:= false;\n fi\nend:" "6#>%6zapis_syna_do_matrikyGf*6%%\"vG%\"aG%\"bG7
\"6\"F+@%2,&%&max_rG\"\"\"F0!\"\"%\"rGC%-%'lprintG6#%2Nedostatok~pamat
eG>%'koniecG%%trueG-%'RETURNGF+C'>F2,&F2F0F0F0>&%%otecG6#F2F'>&%&alpha
G6#F2F(>&%%betaG6#F2F)>&%(odkrytyG6#F2%&falseGF+6)FFFJF2FB%)obsadenyGF
9FNF+" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 18 16 "Odkrytie vrcholu" }}
{PARA 0 "> " 0 "" {XPPEDIT 19 1 "odkry_v := proc(v)\nlocal a, b;\nglob
al k;\n a := pravidloP(); #vyberiem vrchol podla pravidla\n for b from
 n to 1 by (-1) do\n  if a_b_generuje_syna(a, b) then zapis_syna_do_ma
triky(v, a, b) fi;\n od;\nend:" "6#>%(odkry_vGf*6#%\"vG7$%\"aG%\"bG6\"
F+C$>F)-%*pravidloPGF+?(F*%\"nG,$\"\"\"!\"\"F3%%trueG@$-%2a_b_generuje
_synaG6$F)F*-%6zapis_syna_do_matrikyG6%F'F)F*F+6#%\"kGF+" }}}{EXCHG 
{PARA 0 "> " 0 "" {XPPEDIT 19 1 "nasli_sme_zafarbenie := proc()\ngloba
l odpoved, koniec;\n koniec := true; odpoved := true; print(f);\nend:
" "6#>%5nasli_sme_zafarbenieGf*6\"7\"F&F&C%>%'koniecG%%trueG>%(odpoved
GF+-%&printG6#%\"fGF&6$F-F*F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 18 24 "
Vypocet stavu vrchola 'v" }{TEXT -1 1 "'" }}{PARA 0 "> " 0 "" 
{XPPEDIT 19 1 "zisti_stav_vrchola_v := proc(v)\nglobal alpha, beta, f,
 otec;\nlocal t, a, b, w;\n nulujF();\n t := 0; w := v;\n while w > 0 \+
do\n  a := alpha[w]; b := beta[w];\n  f[a] := b;\n  w := otec[w];\n  t
 := t + 1;\n od;\nRETURN(t);\nend:" "6#>%5zisti_stav_vrchola_vGf*6#%\"
vG7&%\"tG%\"aG%\"bG%\"wG6\"F-C'-%'nulujFGF->F)\"\"!>F,F'?(F-\"\"\"F5F-
2F2F,C'>F*&%&alphaG6#F,>F+&%%betaG6#F,>&%\"fG6#F*F+>F,&%%otecG6#F,>F),
&F)F5F5F5-%'RETURNG6#F)F-6&F:F>FBFFF-" }}}{EXCHG {PARA 0 "> " 0 "" 
{XPPEDIT 19 1 "odkry_vrchol_v := proc(v)\nlocal t;\nglobal n, odkryty;
\n t := zisti_stav_vrchola_v(v);\n if t = n then nasli_sme_zafarbenie(
) else odkry_v(v) fi;\n odkryty[v] := true;\nend:" "6#>%/odkry_vrchol_
vGf*6#%\"vG7#%\"tG6\"F*C%>F)-%5zisti_stav_vrchola_vG6#F'@%/F)%\"nG-%5n
asli_sme_zafarbenieGF*-%(odkry_vG6#F'>&%(odkrytyG6#F'%%trueGF*6$F2F:F*
" }}}{EXCHG {PARA 0 "> " 0 "" {XPPEDIT 19 1 "vyber_vrchol_v := proc()
\nglobal odkryty, koniec, r;\nlocal v;\n v := r; #posledny riadok matr
iky\n while (odkryty[v]) and (v >=0) do\n  if v > 0 then v := v-1 else
 koniec := true; break; fi;\n od;\n RETURN(v);\nend:" "6#>%/vyber_vrch
ol_vGf*6\"7#%\"vGF&F&C%>F(%\"rG?(F&\"\"\"F-F&3&%(odkrytyG6#F(1\"\"!F(@
%2F3F(>F(,&F(F-F-!\"\"C$>%'koniecG%%trueG[-%'RETURNG6#F(F&6%F0F;F+F&" 
}}}{EXCHG {PARA 0 "" 0 "" {TEXT 18 26 "Zostrojenie stromu rieseni" }}
{PARA 0 "> " 0 "" {XPPEDIT 19 1 "zostroj_strom_rieseni := proc()\nglob
al odpoved, koniec, odkryty, r;\nlocal v;\n odpoved := false; koniec :
= false; odkryty[0] := false;\n r := 0;\n while not koniec do\n  v := \+
vyber_vrchol_v();\n  if not koniec then odkry_vrchol_v(v) fi;\n od;\nR
ETURN(odpoved);\nend:" "6#>%6zostroj_strom_rieseniGf*6\"7#%\"vGF&F&C(>
%(odpovedG%&falseG>%'koniecGF,>&%(odkrytyG6#\"\"!F,>%\"rGF3?(F&\"\"\"F
7F&4F.C$>F(-%/vyber_vrchol_vGF&@$4F.-%/odkry_vrchol_vG6#F(-%'RETURNG6#
F+F&6&F+F.F1F5F&" }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 8 "Priklady" }}
{SECT 0 {PARA 4 "" 0 "" {TEXT -1 4 "Pr 1" }}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 100 "G := graph([1, 2, 3, 4, 5], [[1, 2], [2, 5], [1, 5],
 [2, 3], [3, 4], [4, 5]]):\nM := NeighbMatrix(G):" }}}{EXCHG {PARA 0 "
> " 0 "" {MPLTEXT 1 0 8 "draw(G);" }}{PARA 13 "" 1 "" {GLPLOT2D 107 
65 65 {PLOTDATA 2 "63-%'POINTSG6#7$$\"\"\"\"\"!$F)F)-%%TEXTG6$F&Q\"16
\"-F$6#7$$\"+Q*p,4$!#5$\"+l^c5&*F5-F,6$F2Q\"2F/-F$6#7$$!+]*p,4)F5$\"+9
D&y(eF5-F,6$F=Q\"3F/-F$6#7$$!+M*p,4)F5$!+PD&y(eF5-F,6$FGQ\"4F/-F$6#7$$
\"+l*p,4$F5$!+c^c5&*F5-F,6$FQQ\"5F/-%'CURVESG6$7$F&F2-%'COLOURG6&%$RGB
GF)$\"#5!\"\"F)-FZ6$7$F2FQFgn-FZ6$7$F&FQFgn-FZ6$7$F2F=Fgn-FZ6$7$F=FGFg
n-FZ6$7$FGFQFgn-%*AXESSTYLEG6#%%NONEG" 1 2 0 1 10 0 2 9 1 1 2 
1.000000 45.000000 45.000000 0 0 "Curve 1" "Curve 2" "Curve 3" "Curve \+
4" "Curve 5" "Curve 6" "Curve 7" "Curve 8" "Curve 9" "Curve 10" "Curve
 11" "Curve 12" "Curve 13" "Curve 14" "Curve 15" "Curve 16" }}}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "k := 3: inicializuj(): zostr
oj_strom_rieseni();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'vectorG6#7%
\"\"&\"\"#\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}
{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "k := 4: inicializuj(): zostr
oj_strom_rieseni();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&falseG" }}}}
{SECT 0 {PARA 4 "" 0 "" {TEXT -1 4 "Pr 2" }}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 140 "G := graph([1, 2, 3, 4, 5, 6, 7], \n [[1, 3], [1, 7]
, [2, 7], [3, 7], [4, 5], [4, 6], [4, 7], [5, 6], [5, 7], [6, 7]]):\nM
 := NeighbMatrix(G):" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 8 "draw
(G);" }}{PARA 13 "" 1 "" {GLPLOT2D 95 79 79 {PLOTDATA 2 "6;-%'POINTSG6
#7$$\"\"\"\"\"!$F)F)-%%TEXTG6$F&Q\"16\"-F$6#7$$\"+=!)*[B'!#5$\"+D[J=yF
5-F,6$F2Q\"2F/-F$6#7$$!+R$4_A#F5$\"+A\"z#\\(*F5-F,6$F=Q\"3F/-F$6#7$$!+
z')o4!*F5$\"+#RP)QVF5-F,6$FGQ\"4F/-F$6#7$FH$!+!RP)QVF5-F,6$FQQ\"5F/-F$
6#7$$!+J$4_A#F5$!+C\"z#\\(*F5-F,6$FYQ\"6F/-F$6#7$$\"+D!)*[B'F5$!+>[J=y
F5-F,6$F]oQ\"7F/-%'CURVESG6$7$F&F=-%'COLOURG6&%$RGBGF)$\"#5!\"\"F)-Ffo
6$7$F&F]oFio-Ffo6$7$F2F]oFio-Ffo6$7$F=F]oFio-Ffo6$7$FGFQFio-Ffo6$7$FGF
YFio-Ffo6$7$FGF]oFio-Ffo6$7$FQFYFio-Ffo6$7$FQF]oFio-Ffo6$7$FYF]oFio-%*
AXESSTYLEG6#%%NONEG" 1 2 0 1 10 0 2 9 1 1 2 1.000000 45.000000 
45.000000 0 0 "Curve 1" "Curve 2" "Curve 3" "Curve 4" "Curve 5" "Curve
 6" "Curve 7" "Curve 8" "Curve 9" "Curve 10" "Curve 11" "Curve 12" "Cu
rve 13" "Curve 14" "Curve 15" "Curve 16" "Curve 17" "Curve 18" "Curve \+
19" "Curve 20" "Curve 21" "Curve 22" "Curve 23" "Curve 24" }}}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "k := 4: inicializuj(): zostroj_stro
m_rieseni();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'vectorG6#7&\"\"(\"
\"'\"\"&\"\"%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "k := 5: inicializuj(): zostroj_stro
m_rieseni();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%&falseG" }}}{EXCHG 
{PARA 0 "> " 0 "" {MPLTEXT 1 0 47 "k := 3: inicializuj(): zostroj_stro
m_rieseni();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'vectorG6#7%\"\"(\"
\"$\"\"\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%%trueG" }}}{EXCHG {PARA 
0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}}{MARK "1 1 0 0" 19 }{VIEWOPTS 1 1 
0 1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }