farbgraf.mws

Problém farbenia grafu

Inicializácia

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

>    r := 'r'; max_r := 1000

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 to n do f[i] := 0 end do end proc

Pravidlo pre vyber vrchola na dalsie farbenie

>    pravidloP := proc () local i; global n, f; i := n;  while 0 < 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 i; global M, f; for i to n do if M[i,a] = 1 and f[i] = b then RETURN(false) end if end do; RETURN(true) end proc
a_b_generuje_syna := proc (a, b) local i; global M, f; for i to n do if M[i,a] = 1 and f[i] = b then RETURN(false) end if end do; RETURN(true) end proc
a_b_generuje_syna := proc (a, b) local i; global M, f; for i to n do if M[i,a] = 1 and f[i] = b then RETURN(false) end if end do; RETURN(true) end proc
a_b_generuje_syna := proc (a, b) local i; global M, f; for i to n do if M[i,a] = 1 and f[i] = b then RETURN(false) end if end do; RETURN(true) end proc
a_b_generuje_syna := proc (a, b) local i; global M, f; for i to n do if M[i,a] = 1 and f[i] = b then RETURN(false) end if end do; RETURN(true) end proc

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 k 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 k 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 k 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 k 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 k 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 k 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...

Príklady

Ak sa da zafarbit

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

>    draw(G);

[Maple Plot]

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

vector([3, 2, 2, 1, 1])

true

Ak sa neda zafarbit

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

>    draw(G);

[Maple Plot]

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

false

Petersenov graf

>    G := petersen(): M := NeighbMatrix(G):

>    draw(G);

[Maple Plot]

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

vector([2, 3, 2, 3, 1, 3, 2, 1, 2, 1])

true