{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 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 
0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 
{CSTYLE "" -1 -1 "Courier" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 0 1 }1 0 0 
-1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Heading 1" 0 3 1 {CSTYLE "" -1 -1 
"" 1 18 0 0 0 0 0 1 0 0 0 0 0 0 0 1 }1 0 0 0 6 6 0 0 0 0 0 0 -1 0 }
{PSTYLE "Heading 2" 3 4 1 {CSTYLE "" -1 -1 "" 1 14 0 0 0 0 0 0 0 0 0 
0 0 0 0 1 }0 0 0 -1 4 4 0 0 0 0 0 0 -1 0 }{PSTYLE "" 2 6 1 {CSTYLE "" 
-1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 1 }0 0 0 -1 -1 -1 0 0 0 0 0 0 
-1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 
0 0 0 0 0 0 0 0 1 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Plo
t" 0 13 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 }3 0 0 
-1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Title" 0 18 1 {CSTYLE "" -1 -1 "" 
1 18 0 0 0 0 0 1 1 0 0 0 0 0 0 1 }3 0 0 -1 12 12 0 0 0 0 0 0 19 0 }
{PSTYLE "" 0 256 1 {CSTYLE "" -1 -1 "" 0 1 74 0 47 0 0 0 0 0 0 0 0 0 
0 1 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }}
{SECT 0 {EXCHG {PARA 18 "" 0 "" {TEXT -1 21 "Problem k-kliky grafu" }
{MPLTEXT 1 0 0 "" }}{PARA 256 "" 0 "" {TEXT -1 33 "Metoda rozsireneho \+
stromu rieseni" }}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 13 "Inicializacia
" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 70 "restart; with(networks):
 read `h:\\\\Data\\\\Math\\\\Maple\\\\pac\\\\netw2.mpl`:" }}}{SECT 0 
{PARA 4 "" 0 "" {TEXT -1 11 "inicializuj" }}{EXCHG {PARA 0 "> " 0 "" 
{XPPEDIT 19 1 "inicializuj := proc ()\nglobal n, koniec, f, u, j;\n n \+
:= nops(vertices(G)); \n f := array(1 .. k); \n koniec := false;\nend:
" "6#>%,inicializujGf*6\"7\"F&F&C%>%\"nG-%%nopsG6#-%)verticesG6#%\"GG>
%\"fG-%&arrayG6#;\"\"\"%\"kG>%'koniecG%&falseGF&6'F*F;F3%\"uG%\"jGF&" 
}}}}}{SECT 0 {PARA 3 "" 0 "" {TEXT -1 13 "Implementacia" }}{EXCHG 
{PARA 0 "" 0 "" {TEXT 18 21 "Vynulovanie vektora F" }}{PARA 0 "> " 0 "
" {XPPEDIT 19 1 "nulujF := proc() local i; global f; for i from 1 to k
 do f[i] := 0 od; end:" "6#>%'nulujFGf*6\"7#%\"iGF&F&?(F(\"\"\"F*%\"kG
%%trueG>&%\"fG6#F(\"\"!F&6#F/F&" }}}{EXCHG {PARA 0 "" 0 "" {TEXT 18 
26 "Zistenie, ci stav F je syn" }}{PARA 0 "> " 0 "" {XPPEDIT 19 1 "F_j
e_syn := proc()\nglobal f, u, k, M;\nlocal V, i, j;\n V := \{\}; #vytv
or mnozinu vrcholov\n for i from u+1 to k do\n  if member(f[i], V) the
n RETURN(false) fi:\n  V := V union \{f[i]\} \n od;\nfor i from u+1 to
 k-1 do\n for j from i+1 to k do\n  #print(f[i], f[j]);\n  if M[f[i], \+
f[j]] = 0 then RETURN(false) fi;\n od;\nod;\nRETURN(true); \nend:  " "
6#>%)F_je_synGf*6\"7%%\"VG%\"iG%\"jGF&F&C&>F(<\"?(F),&%\"uG\"\"\"F1F1F
1%\"kG%%trueGC$@$-%'memberG6$&%\"fG6#F)F(-%'RETURNG6#%&falseG>F(-%&uni
onG6$F(<#&F:6#F)?(F),&F0F1F1F1F1,&F2F1F1!\"\"F3?(F*,&F)F1F1F1F1F2F3@$/
&%\"MG6$&F:6#F)&F:6#F*\"\"!-F=6#F?-F=6#F3F&6&F:F0F2FPF&" }}}{EXCHG 
{PARA 0 "> " 0 "" {XPPEDIT 19 1 "vzad := proc()\nglobal u, j, n, k, f;
\nlocal i;\n f[j] := f[j] + 1;\n for i from 1 to j-1 do f[i] := 0 od;
\n u := j-1;\n while (j <= k) and (f[j] = n) do j := j + 1 od;\nend:" 
"6#>%%vzadGf*6\"7#%\"iGF&F&C&>&%\"fG6#%\"jG,&&F,6#F.\"\"\"F2F2?(F(F2F2
,&F.F2F2!\"\"%%trueG>&F,6#F(\"\"!>%\"uG,&F.F2F2F5?(F&F2F2F&31F.%\"kG/&
F,6#F.%\"nG>F.,&F.F2F2F2F&6'F<F.FEFAF,F&" }}}{EXCHG {PARA 0 "> " 0 "" 
{XPPEDIT 19 1 "vpred := proc()\nglobal f, u, j, n;\n f[u] := 1; j := u
; u := u - 1;\nend: " "6#>%&vpredGf*6\"7\"F&F&C%>&%\"fG6#%\"uG\"\"\">%
\"jGF->F-,&F-F.F.!\"\"F&6&F+F-F0%\"nGF&" }}}{EXCHG {PARA 0 "> " 0 "" 
{XPPEDIT 19 1 "zostroj_nasledovnika := proc()\nglobal u, f, j, n, koni
ec;\nlocal t;\n t := F_je_syn();\n  if t then\n  if u > 0 then\n   vpr
ed()\n  else\n   print(`Klika:`, f); koniec := true;\n  fi;\n else\n  \+
if j < k+1 then\n   vzad()\n  else\n   lprint(`K-klika v grafe neexist
uje\\n`); koniec := true;\n  fi;\n fi;\nend:" "6#>%5zostroj_nasledovni
kaGf*6\"7#%\"tGF&F&C$>F(-%)F_je_synGF&@%F(@%2\"\"!%\"uG-%&vpredGF&C$-%
&printG6$%'Klika:G%\"fG>%'koniecG%%trueG@%2%\"jG,&%\"kG\"\"\"FBFB-%%vz
adGF&C$-%'lprintG6#%<K-klika~v~grafe~neexistuje|+G>F;F<F&6'F1F9F?%\"nG
F;F&" }}}{EXCHG {PARA 0 "> " 0 "" {XPPEDIT 19 1 "zostroj_rozsireny_str
om_rieseni := proc()\nglobal koniec, k, n, u, j;\n koniec := false;\n \+
if k = n then RETURN() fi;\n nulujF();\n u := k; j := k + 1;\n while n
ot koniec do\n  zostroj_nasledovnika();\n od;\nend:" "6#>%@zostroj_roz
sireny_strom_rieseniGf*6\"7\"F&F&C(>%'koniecG%&falseG@$/%\"kG%\"nG-%'R
ETURNGF&-%'nulujFGF&>%\"uGF.>%\"jG,&F.\"\"\"F9F9?(F&F9F9F&4F*-%5zostro
j_nasledovnikaGF&F&6'F*F.F/F5F7F&" }}}}{SECT 0 {PARA 3 "" 0 "" {TEXT 
-1 7 "Priklad" }}{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 90 57 57 {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$\"+9D&y(eF5-F,6$F=Q\"3F/-F$6#7$$!+M*p,4)F5$!+PD&y(eF5-F,6$FG
Q\"4F/-F$6#7$$\"+l*p,4$F5$!+c^c5&*F5-F,6$FQQ\"5F/-%'CURVESG6$7$F&F2-%'
COLOURG6&%$RGBGF)$\"#5!\"\"F)-FZ6$7$F2FQFgn-FZ6$7$F&FQFgn-FZ6$7$F2F=Fg
n-FZ6$7$F=FGFgn-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 57 "k := 3: inicializuj(): zostr
oj_rozsireny_strom_rieseni():" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%'Kli
ka:G-%'vectorG6#7%\"\"&\"\"#\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 57 "k := 4: inicializuj(): zostroj_rozsireny_strom_riesen
i():" }}{PARA 6 "" 1 "" {TEXT -1 30 "`K-klika v grafe neexistuje\\n`" 
}}}}{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 "d
raw(G);" }}{PARA 13 "" 1 "" {GLPLOT2D 121 78 78 {PLOTDATA 2 "6;-%'POIN
TSG6#7$$\"+=!)*[B'!#5$\"+D[J=yF)-%%TEXTG6$F&Q\"26\"-F$6#7$$!+R$4_A#F)$
\"+A\"z#\\(*F)-F-6$F3Q\"3F0-F$6#7$$!+z')o4!*F)$\"+#RP)QVF)-%'CURVESG6$
7$F&7$$\"+D!)*[B'F)$!+>[J=yF)-%'COLOURG6&%$RGBG\"\"!$\"#5!\"\"FO-FC6$7
$7$$\"\"\"FO$FOFOFFFK-FC6$7$FVF3FK-FC6$7$7$$!+J$4_A#F)$!+C\"z#\\(*F)FF
FK-FC6$7$7$F>$!+!RP)QVF)FFFK-F-6$F=Q\"4F0-FC6$7$FboFjnFK-FC6$7$F=FFFK-
F-6$FFQ\"7F0-F-6$FjnQ\"6F0-F$6#FF-F$6#Fbo-F-6$FboQ\"5F0-F$6#Fjn-FC6$7$
F=FjnFK-FC6$7$F=FboFK-FC6$7$F3FFFK-F$6#FV-F-6$FVQ\"1F0-%*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" "Curve 17" "Curve 18" "Curve 19" "Curve 20" "Curv
e 21" "Curve 22" "Curve 23" "Curve 24" }}}}{EXCHG {PARA 0 "> " 0 "" 
{MPLTEXT 1 0 57 "k := 4: inicializuj(): zostroj_rozsireny_strom_riesen
i():" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%'Klika:G-%'vectorG6#7&\"\"(\"
\"'\"\"&\"\"%" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 57 "k := 5: in
icializuj(): zostroj_rozsireny_strom_rieseni():" }}{PARA 6 "" 1 "" 
{TEXT -1 30 "`K-klika v grafe neexistuje\\n`" }}}{EXCHG {PARA 0 "> " 
0 "" {MPLTEXT 1 0 57 "k := 3: inicializuj(): zostroj_rozsireny_strom_r
ieseni():" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%'Klika:G-%'vectorG6#7%\"
\"(\"\"$\"\"\"" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 0 "" }}}}}
{PARA 3 "" 0 "" {TEXT -1 0 "" }}}{MARK "2 2 0 0" 26 }{VIEWOPTS 1 1 0 
1 1 1803 1 1 1 1 }{PAGENUMBERS 0 1 2 33 1 1 }