frozstrm.mws

Problem farbenia grafu

Metoda rozsireneho stromu rieseni

Inicializacia

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

inicializuj

>    inicializuj := proc () global n, koniec, f, u, j; n := nops(vertices(G)); f := array(1 .. n); koniec := false end proc

Implementacia

Vynulovanie vektora F

>    nulujF := proc () local i; global f; for i to n do f[i] := 0 end do end proc

Zistenie, ci stav F je syn

>    F_je_syn := proc () local i; global u, n, f, M; for i from u+2 to n do if f[u+1] = f[i] and M[u+1,i] = 1 then RETURN(false) end if end do; RETURN(true) end proc
F_je_syn := proc () local i; global u, n, f, M; for i from u+2 to n do if f[u+1] = f[i] and M[u+1,i] = 1 then RETURN(false) end if end do; RETURN(true) end proc
F_je_syn := proc () local i; global u, n, f, M; for i from u+2 to n do if f[u+1] = f[i] and M[u+1,i] = 1 then RETURN(false) end if end do; RETURN(true) end proc
F_je_syn := proc () local i; global u, n, f, M; for i from u+2 to n do if f[u+1] = f[i] and M[u+1,i] = 1 then RETURN(false) end if end do; RETURN(true) end proc
F_je_syn := proc () local i; global u, n, f, M; for i from u+2 to n do if f[u+1] = f[i] and M[u+1,i] = 1 then RETURN(false) end if end do; RETURN(true) end proc

>    vzad := proc () local i; global u, j, n, k, f; f[j] := f[j]+1; for i to j-1 do f[i] := 0 end do; u := j-1;  while j <= n and f[j] = k do j := j+1 end do end proc
vzad := proc () local i; global u, j, n, k, f; f[j] := f[j]+1; for i to j-1 do f[i] := 0 end do; u := j-1;  while j <= n and f[j] = k do j := j+1 end do end proc
vzad := proc () local i; global u, j, n, k, f; f[j] := f[j]+1; for i to j-1 do f[i] := 0 end do; u := j-1;  while j <= n and f[j] = k do j := j+1 end do end proc
vzad := proc () local i; global u, j, n, k, f; f[j] := f[j]+1; for i to j-1 do f[i] := 0 end do; u := j-1;  while j <= n and f[j] = k do j := j+1 end do end proc
vzad := proc () local i; global u, j, n, k, f; f[j] := f[j]+1; for i to j-1 do f[i] := 0 end do; u := j-1;  while j <= n and f[j] = k do j := j+1 end do end proc

>    vpred := proc () global f, u, j, n; f[u] := 1; j := u; u := u-1 end proc

>    zostroj_nasledovnika := proc () local t; global u, f, j, n, koniec; t := F_je_syn(); print(f,u,t); if t then if 0 < u then vpred() else print(`Zafarbenie:`,f); koniec := true end if else if j < n+1 the...
zostroj_nasledovnika := proc () local t; global u, f, j, n, koniec; t := F_je_syn(); print(f,u,t); if t then if 0 < u then vpred() else print(`Zafarbenie:`,f); koniec := true end if else if j < n+1 the...
zostroj_nasledovnika := proc () local t; global u, f, j, n, koniec; t := F_je_syn(); print(f,u,t); if t then if 0 < u then vpred() else print(`Zafarbenie:`,f); koniec := true end if else if j < n+1 the...
zostroj_nasledovnika := proc () local t; global u, f, j, n, koniec; t := F_je_syn(); print(f,u,t); if t then if 0 < u then vpred() else print(`Zafarbenie:`,f); koniec := true end if else if j < n+1 the...
zostroj_nasledovnika := proc () local t; global u, f, j, n, koniec; t := F_je_syn(); print(f,u,t); if t then if 0 < u then vpred() else print(`Zafarbenie:`,f); koniec := true end if else if j < n+1 the...
zostroj_nasledovnika := proc () local t; global u, f, j, n, koniec; t := F_je_syn(); print(f,u,t); if t then if 0 < u then vpred() else print(`Zafarbenie:`,f); koniec := true end if else if j < n+1 the...
zostroj_nasledovnika := proc () local t; global u, f, j, n, koniec; t := F_je_syn(); print(f,u,t); if t then if 0 < u then vpred() else print(`Zafarbenie:`,f); koniec := true end if else if j < n+1 the...
zostroj_nasledovnika := proc () local t; global u, f, j, n, koniec; t := F_je_syn(); print(f,u,t); if t then if 0 < u then vpred() else print(`Zafarbenie:`,f); koniec := true end if else if j < n+1 the...
zostroj_nasledovnika := proc () local t; global u, f, j, n, koniec; t := F_je_syn(); print(f,u,t); if t then if 0 < u then vpred() else print(`Zafarbenie:`,f); koniec := true end if else if j < n+1 the...

>    zostroj_rozsireny_strom_rieseni := proc () global koniec, k, n, u, j; koniec := false; if k = 1 then RETURN() end if; nulujF(); u := n; j := n+1;  while not koniec do zostroj_nasledovnika() end do end ...
zostroj_rozsireny_strom_rieseni := proc () global koniec, k, n, u, j; koniec := false; if k = 1 then RETURN() end if; nulujF(); u := n; j := n+1;  while not koniec do zostroj_nasledovnika() end do end ...
zostroj_rozsireny_strom_rieseni := proc () global koniec, k, n, u, j; koniec := false; if k = 1 then RETURN() end if; nulujF(); u := n; j := n+1;  while not koniec do zostroj_nasledovnika() end do end ...
zostroj_rozsireny_strom_rieseni := proc () global koniec, k, n, u, j; koniec := false; if k = 1 then RETURN() end if; nulujF(); u := n; j := n+1;  while not koniec do zostroj_nasledovnika() end do end ...
zostroj_rozsireny_strom_rieseni := proc () global koniec, k, n, u, j; koniec := false; if k = 1 then RETURN() end if; nulujF(); u := n; j := n+1;  while not koniec do zostroj_nasledovnika() end do end ...
zostroj_rozsireny_strom_rieseni := proc () global koniec, k, n, u, j; koniec := false; if k = 1 then RETURN() end if; nulujF(); u := n; j := n+1;  while not koniec do zostroj_nasledovnika() end do end ...
zostroj_rozsireny_strom_rieseni := proc () global koniec, k, n, u, j; koniec := false; if k = 1 then RETURN() end if; nulujF(); u := n; j := n+1;  while not koniec do zostroj_nasledovnika() end do end ...
zostroj_rozsireny_strom_rieseni := proc () global koniec, k, n, u, j; koniec := false; if k = 1 then RETURN() end if; nulujF(); u := n; j := n+1;  while not koniec do zostroj_nasledovnika() end do end ...
zostroj_rozsireny_strom_rieseni := proc () global koniec, k, n, u, j; koniec := false; if k = 1 then RETURN() end if; nulujF(); u := n; j := n+1;  while not koniec do zostroj_nasledovnika() end do end ...

Priklad

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

>    draw(G);

[Maple Plot]

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

vector([0, 0, 0, 0]), 4, true

vector([0, 0, 0, 1]), 3, true

vector([0, 0, 1, 1]), 2, false

vector([0, 0, 2, 1]), 2, true

vector([0, 1, 2, 1]), 1, true

vector([1, 1, 2, 1]), 0, false

vector([2, 1, 2, 1]), 0, false

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

`Zafarbenie:`, vector([3, 1, 2, 1])

true

>