klika.mws

Problém k-kliky grafu

Inicializacia

>    restart; with(networks): read `\\\\Xpc\\Math\\Maple\\pac\\netw2.mpl`:

>    r := `r`: max_r := 1000: #maximalna dlzka tabulky

inicializuj()

>    inicializuj := proc () global n, max_r, otec, alpha, beta, koniec, odpoved, f, r, odkryty; n := nops(vertices(G)); r := 0; otec := array(0 .. max_r-1); alpha := array(0 .. max_r-1); beta := array(0 .. ...
inicializuj := proc () global n, max_r, otec, alpha, beta, koniec, odpoved, f, r, odkryty; n := nops(vertices(G)); r := 0; otec := array(0 .. max_r-1); alpha := array(0 .. max_r-1); beta := array(0 .. ...
inicializuj := proc () global n, max_r, otec, alpha, beta, koniec, odpoved, f, r, odkryty; n := nops(vertices(G)); r := 0; otec := array(0 .. max_r-1); alpha := array(0 .. max_r-1); beta := array(0 .. ...
inicializuj := proc () global n, max_r, otec, alpha, beta, koniec, odpoved, f, r, odkryty; n := nops(vertices(G)); r := 0; otec := array(0 .. max_r-1); alpha := array(0 .. max_r-1); beta := array(0 .. ...
inicializuj := proc () global n, max_r, otec, alpha, beta, koniec, odpoved, f, r, odkryty; n := nops(vertices(G)); r := 0; otec := array(0 .. max_r-1); alpha := array(0 .. max_r-1); beta := array(0 .. ...
inicializuj := proc () global n, max_r, otec, alpha, beta, koniec, odpoved, f, r, odkryty; n := nops(vertices(G)); r := 0; otec := array(0 .. max_r-1); alpha := array(0 .. max_r-1); beta := array(0 .. ...
inicializuj := proc () global n, max_r, otec, alpha, beta, koniec, odpoved, f, r, odkryty; n := nops(vertices(G)); r := 0; otec := array(0 .. max_r-1); alpha := array(0 .. max_r-1); beta := array(0 .. ...
inicializuj := proc () global n, max_r, otec, alpha, beta, koniec, odpoved, f, r, odkryty; n := nops(vertices(G)); r := 0; otec := array(0 .. max_r-1); alpha := array(0 .. max_r-1); beta := array(0 .. ...
inicializuj := proc () global n, max_r, otec, alpha, beta, koniec, odpoved, f, r, odkryty; n := nops(vertices(G)); r := 0; otec := array(0 .. max_r-1); alpha := array(0 .. max_r-1); beta := array(0 .. ...
inicializuj := proc () global n, max_r, otec, alpha, beta, koniec, odpoved, f, r, odkryty; n := nops(vertices(G)); r := 0; otec := array(0 .. max_r-1); alpha := array(0 .. max_r-1); beta := array(0 .. ...
inicializuj := proc () global n, max_r, otec, alpha, beta, koniec, odpoved, f, r, odkryty; n := nops(vertices(G)); r := 0; otec := array(0 .. max_r-1); alpha := array(0 .. max_r-1); beta := array(0 .. ...
inicializuj := proc () global n, max_r, otec, alpha, beta, koniec, odpoved, f, r, odkryty; n := nops(vertices(G)); r := 0; otec := array(0 .. max_r-1); alpha := array(0 .. max_r-1); beta := array(0 .. ...

Implementácia

>    nulujF := proc() local i; global f; for i from 1 to k do f[i] := 0 od; end:

Pravidlo pre vyber dalsej pozicie

>    pravidloP := proc () local i; global n, f; i := k;  while 1 < i and f[i] <> 0 do i := i-1 end do; RETURN(i) end proc

Zistenie, ci (a, b) je generator prechodu

>    a_b_generuje_syna := proc (a, b) local V, i, j; global M, k, f, f1; f1 := f; f1[a] := b; V := {}; for i from a to k do if member(f1[i],V) then RETURN(false) end if; V := `union`(V,{f1[i]}) end do; for ...
a_b_generuje_syna := proc (a, b) local V, i, j; global M, k, f, f1; f1 := f; f1[a] := b; V := {}; for i from a to k do if member(f1[i],V) then RETURN(false) end if; V := `union`(V,{f1[i]}) end do; for ...
a_b_generuje_syna := proc (a, b) local V, i, j; global M, k, f, f1; f1 := f; f1[a] := b; V := {}; for i from a to k do if member(f1[i],V) then RETURN(false) end if; V := `union`(V,{f1[i]}) end do; for ...
a_b_generuje_syna := proc (a, b) local V, i, j; global M, k, f, f1; f1 := f; f1[a] := b; V := {}; for i from a to k do if member(f1[i],V) then RETURN(false) end if; V := `union`(V,{f1[i]}) end do; for ...
a_b_generuje_syna := proc (a, b) local V, i, j; global M, k, f, f1; f1 := f; f1[a] := b; V := {}; for i from a to k do if member(f1[i],V) then RETURN(false) end if; V := `union`(V,{f1[i]}) end do; for ...
a_b_generuje_syna := proc (a, b) local V, i, j; global M, k, f, f1; f1 := f; f1[a] := b; V := {}; for i from a to k do if member(f1[i],V) then RETURN(false) end if; V := `union`(V,{f1[i]}) end do; for ...
a_b_generuje_syna := proc (a, b) local V, i, j; global M, k, f, f1; f1 := f; f1[a] := b; V := {}; for i from a to k do if member(f1[i],V) then RETURN(false) end if; V := `union`(V,{f1[i]}) end do; for ...
a_b_generuje_syna := proc (a, b) local V, i, j; global M, k, f, f1; f1 := f; f1[a] := b; V := {}; for i from a to k do if member(f1[i],V) then RETURN(false) end if; V := `union`(V,{f1[i]}) end do; for ...
a_b_generuje_syna := proc (a, b) local V, i, j; global M, k, f, f1; f1 := f; f1[a] := b; V := {}; for i from a to k do if member(f1[i],V) then RETURN(false) end if; V := `union`(V,{f1[i]}) end do; for ...
a_b_generuje_syna := proc (a, b) local V, i, j; global M, k, f, f1; f1 := f; f1[a] := b; V := {}; for i from a to k do if member(f1[i],V) then RETURN(false) end if; V := `union`(V,{f1[i]}) end do; for ...

Zapis informacii o stave do matriky

>    zapis_syna_do_matriky := proc (v, a, b) global alpha, beta, r, otec, obsadeny, koniec, odkryty; if max_r-1 < r then lprint(`Nedostatok pamate`); koniec := true; RETURN() else r := r+1; otec[r] := v; al...
zapis_syna_do_matriky := proc (v, a, b) global alpha, beta, r, otec, obsadeny, koniec, odkryty; if max_r-1 < r then lprint(`Nedostatok pamate`); koniec := true; RETURN() else r := r+1; otec[r] := v; al...
zapis_syna_do_matriky := proc (v, a, b) global alpha, beta, r, otec, obsadeny, koniec, odkryty; if max_r-1 < r then lprint(`Nedostatok pamate`); koniec := true; RETURN() else r := r+1; otec[r] := v; al...
zapis_syna_do_matriky := proc (v, a, b) global alpha, beta, r, otec, obsadeny, koniec, odkryty; if max_r-1 < r then lprint(`Nedostatok pamate`); koniec := true; RETURN() else r := r+1; otec[r] := v; al...
zapis_syna_do_matriky := proc (v, a, b) global alpha, beta, r, otec, obsadeny, koniec, odkryty; if max_r-1 < r then lprint(`Nedostatok pamate`); koniec := true; RETURN() else r := r+1; otec[r] := v; al...
zapis_syna_do_matriky := proc (v, a, b) global alpha, beta, r, otec, obsadeny, koniec, odkryty; if max_r-1 < r then lprint(`Nedostatok pamate`); koniec := true; RETURN() else r := r+1; otec[r] := v; al...

Odkrytie vrcholu

>    odkry_v := proc (v) local a, b; global k; a := pravidloP(); for b from n by -1 to 1 do if a_b_generuje_syna(a,b) then zapis_syna_do_matriky(v,a,b) end if end do end proc
odkry_v := proc (v) local a, b; global k; a := pravidloP(); for b from n by -1 to 1 do if a_b_generuje_syna(a,b) then zapis_syna_do_matriky(v,a,b) end if end do end proc
odkry_v := proc (v) local a, b; global k; a := pravidloP(); for b from n by -1 to 1 do if a_b_generuje_syna(a,b) then zapis_syna_do_matriky(v,a,b) end if end do end proc
odkry_v := proc (v) local a, b; global k; a := pravidloP(); for b from n by -1 to 1 do if a_b_generuje_syna(a,b) then zapis_syna_do_matriky(v,a,b) end if end do end proc
odkry_v := proc (v) local a, b; global k; a := pravidloP(); for b from n by -1 to 1 do if a_b_generuje_syna(a,b) then zapis_syna_do_matriky(v,a,b) end if end do end proc
odkry_v := proc (v) local a, b; global k; a := pravidloP(); for b from n by -1 to 1 do if a_b_generuje_syna(a,b) then zapis_syna_do_matriky(v,a,b) end if end do end proc

>    nasli_sme_zafarbenie := proc () global odpoved, koniec; koniec := true; odpoved := true; print(f) end proc

Vypocet stavu vrchola 'v '

>    zisti_stav_vrchola_v := proc (v) local t, a, b, w; global alpha, beta, f, otec; nulujF(); t := 0; w := v;  while 0 < w do a := alpha[w]; b := beta[w]; f[a] := b; w := otec[w]; t := t+1 end do; RETURN(t...
zisti_stav_vrchola_v := proc (v) local t, a, b, w; global alpha, beta, f, otec; nulujF(); t := 0; w := v;  while 0 < w do a := alpha[w]; b := beta[w]; f[a] := b; w := otec[w]; t := t+1 end do; RETURN(t...
zisti_stav_vrchola_v := proc (v) local t, a, b, w; global alpha, beta, f, otec; nulujF(); t := 0; w := v;  while 0 < w do a := alpha[w]; b := beta[w]; f[a] := b; w := otec[w]; t := t+1 end do; RETURN(t...
zisti_stav_vrchola_v := proc (v) local t, a, b, w; global alpha, beta, f, otec; nulujF(); t := 0; w := v;  while 0 < w do a := alpha[w]; b := beta[w]; f[a] := b; w := otec[w]; t := t+1 end do; RETURN(t...
zisti_stav_vrchola_v := proc (v) local t, a, b, w; global alpha, beta, f, otec; nulujF(); t := 0; w := v;  while 0 < w do a := alpha[w]; b := beta[w]; f[a] := b; w := otec[w]; t := t+1 end do; RETURN(t...

>    odkry_vrchol_v := proc (v) local t; global n, odkryty; t := zisti_stav_vrchola_v(v); if t = n then nasli_sme_zafarbenie() else odkry_v(v) end if; odkryty[v] := true end proc
odkry_vrchol_v := proc (v) local t; global n, odkryty; t := zisti_stav_vrchola_v(v); if t = n then nasli_sme_zafarbenie() else odkry_v(v) end if; odkryty[v] := true end proc
odkry_vrchol_v := proc (v) local t; global n, odkryty; t := zisti_stav_vrchola_v(v); if t = n then nasli_sme_zafarbenie() else odkry_v(v) end if; odkryty[v] := true end proc
odkry_vrchol_v := proc (v) local t; global n, odkryty; t := zisti_stav_vrchola_v(v); if t = n then nasli_sme_zafarbenie() else odkry_v(v) end if; odkryty[v] := true end proc
odkry_vrchol_v := proc (v) local t; global n, odkryty; t := zisti_stav_vrchola_v(v); if t = n then nasli_sme_zafarbenie() else odkry_v(v) end if; odkryty[v] := true end proc

>    vyber_vrchol_v := proc () local v; global odkryty, koniec, r; v := r;  while odkryty[v] and 0 <= v do if 0 < v then v := v-1 else koniec := true; break end if end do; RETURN(v) end proc
vyber_vrchol_v := proc () local v; global odkryty, koniec, r; v := r;  while odkryty[v] and 0 <= v do if 0 < v then v := v-1 else koniec := true; break end if end do; RETURN(v) end proc
vyber_vrchol_v := proc () local v; global odkryty, koniec, r; v := r;  while odkryty[v] and 0 <= v do if 0 < v then v := v-1 else koniec := true; break end if end do; RETURN(v) end proc
vyber_vrchol_v := proc () local v; global odkryty, koniec, r; v := r;  while odkryty[v] and 0 <= v do if 0 < v then v := v-1 else koniec := true; break end if end do; RETURN(v) end proc
vyber_vrchol_v := proc () local v; global odkryty, koniec, r; v := r;  while odkryty[v] and 0 <= v do if 0 < v then v := v-1 else koniec := true; break end if end do; RETURN(v) end proc

Zostrojenie stromu rieseni

>    zostroj_strom_rieseni := proc () local v; global odpoved, koniec, odkryty, r; odpoved := false; koniec := false; odkryty[0] := false; r := 0;  while not koniec do v := vyber_vrchol_v(); if not koniec t...
zostroj_strom_rieseni := proc () local v; global odpoved, koniec, odkryty, r; odpoved := false; koniec := false; odkryty[0] := false; r := 0;  while not koniec do v := vyber_vrchol_v(); if not koniec t...
zostroj_strom_rieseni := proc () local v; global odpoved, koniec, odkryty, r; odpoved := false; koniec := false; odkryty[0] := false; r := 0;  while not koniec do v := vyber_vrchol_v(); if not koniec t...
zostroj_strom_rieseni := proc () local v; global odpoved, koniec, odkryty, r; odpoved := false; koniec := false; odkryty[0] := false; r := 0;  while not koniec do v := vyber_vrchol_v(); if not koniec t...
zostroj_strom_rieseni := proc () local v; global odpoved, koniec, odkryty, r; odpoved := false; koniec := false; odkryty[0] := false; r := 0;  while not koniec do v := vyber_vrchol_v(); if not koniec t...
zostroj_strom_rieseni := proc () local v; global odpoved, koniec, odkryty, r; odpoved := false; koniec := false; odkryty[0] := false; r := 0;  while not koniec do v := vyber_vrchol_v(); if not koniec t...
zostroj_strom_rieseni := proc () local v; global odpoved, koniec, odkryty, r; odpoved := false; koniec := false; odkryty[0] := false; r := 0;  while not koniec do v := vyber_vrchol_v(); if not koniec t...
zostroj_strom_rieseni := proc () local v; global odpoved, koniec, odkryty, r; odpoved := false; koniec := false; odkryty[0] := false; r := 0;  while not koniec do v := vyber_vrchol_v(); if not koniec t...
zostroj_strom_rieseni := proc () local v; global odpoved, koniec, odkryty, r; odpoved := false; koniec := false; odkryty[0] := false; r := 0;  while not koniec do v := vyber_vrchol_v(); if not koniec t...
zostroj_strom_rieseni := proc () local v; global odpoved, koniec, odkryty, r; odpoved := false; koniec := false; odkryty[0] := false; r := 0;  while not koniec do v := vyber_vrchol_v(); if not koniec t...

Priklady

Pr 1

>    G := graph([1, 2, 3, 4, 5], [[1, 2], [2, 5], [1, 5], [2, 3], [3, 4], [4, 5]]):
M := NeighbMatrix(G):

>    draw(G);

[Maple Plot]

>    k := 3: inicializuj(): zostroj_strom_rieseni();

vector([5, 2, 1])

true

>    k := 4: inicializuj(): zostroj_strom_rieseni();

false

Pr 2

>    G := graph([1, 2, 3, 4, 5, 6, 7],
 [[1, 3], [1, 7], [2, 7], [3, 7], [4, 5], [4, 6], [4, 7], [5, 6], [5, 7], [6, 7]]):
M := NeighbMatrix(G):

>    draw(G);

[Maple Plot]

>    k := 4: inicializuj(): zostroj_strom_rieseni();

vector([7, 6, 5, 4])

true

>    k := 5: inicializuj(): zostroj_strom_rieseni();

false

>    k := 3: inicializuj(): zostroj_strom_rieseni();

vector([7, 3, 1])

true

>