klikars.mws

Problem k-kliky grafu

Metoda rozsireneho stromu rieseni

Inicializacia

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

inicializuj

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

Implementacia

Vynulovanie vektora F

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

Zistenie, ci stav F je syn

>    F_je_syn := proc () local V, i, j; global f, u, k, M; V := {}; for i from u+1 to k do if member(f[i],V) then RETURN(false) end if; V := `union`(V,{f[i]}) end do; for i from u+1 to k-1 do for j from i+1...
F_je_syn := proc () local V, i, j; global f, u, k, M; V := {}; for i from u+1 to k do if member(f[i],V) then RETURN(false) end if; V := `union`(V,{f[i]}) end do; for i from u+1 to k-1 do for j from i+1...
F_je_syn := proc () local V, i, j; global f, u, k, M; V := {}; for i from u+1 to k do if member(f[i],V) then RETURN(false) end if; V := `union`(V,{f[i]}) end do; for i from u+1 to k-1 do for j from i+1...
F_je_syn := proc () local V, i, j; global f, u, k, M; V := {}; for i from u+1 to k do if member(f[i],V) then RETURN(false) end if; V := `union`(V,{f[i]}) end do; for i from u+1 to k-1 do for j from i+1...
F_je_syn := proc () local V, i, j; global f, u, k, M; V := {}; for i from u+1 to k do if member(f[i],V) then RETURN(false) end if; V := `union`(V,{f[i]}) end do; for i from u+1 to k-1 do for j from i+1...
F_je_syn := proc () local V, i, j; global f, u, k, M; V := {}; for i from u+1 to k do if member(f[i],V) then RETURN(false) end if; V := `union`(V,{f[i]}) end do; for i from u+1 to k-1 do for j from i+1...
F_je_syn := proc () local V, i, j; global f, u, k, M; V := {}; for i from u+1 to k do if member(f[i],V) then RETURN(false) end if; V := `union`(V,{f[i]}) end do; for i from u+1 to k-1 do for j from i+1...
F_je_syn := proc () local V, i, j; global f, u, k, M; V := {}; for i from u+1 to k do if member(f[i],V) then RETURN(false) end if; V := `union`(V,{f[i]}) end do; for i from u+1 to k-1 do for j from i+1...

>    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 <= k and f[j] = n 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 <= k and f[j] = n 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 <= k and f[j] = n 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 <= k and f[j] = n 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 <= k and f[j] = n 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(); if t then if 0 < u then vpred() else print(`Klika:`,f); koniec := true end if else if j < k+1 then vzad() else lprin...
zostroj_nasledovnika := proc () local t; global u, f, j, n, koniec; t := F_je_syn(); if t then if 0 < u then vpred() else print(`Klika:`,f); koniec := true end if else if j < k+1 then vzad() else lprin...
zostroj_nasledovnika := proc () local t; global u, f, j, n, koniec; t := F_je_syn(); if t then if 0 < u then vpred() else print(`Klika:`,f); koniec := true end if else if j < k+1 then vzad() else lprin...
zostroj_nasledovnika := proc () local t; global u, f, j, n, koniec; t := F_je_syn(); if t then if 0 < u then vpred() else print(`Klika:`,f); koniec := true end if else if j < k+1 then vzad() else lprin...
zostroj_nasledovnika := proc () local t; global u, f, j, n, koniec; t := F_je_syn(); if t then if 0 < u then vpred() else print(`Klika:`,f); koniec := true end if else if j < k+1 then vzad() else lprin...
zostroj_nasledovnika := proc () local t; global u, f, j, n, koniec; t := F_je_syn(); if t then if 0 < u then vpred() else print(`Klika:`,f); koniec := true end if else if j < k+1 then vzad() else lprin...
zostroj_nasledovnika := proc () local t; global u, f, j, n, koniec; t := F_je_syn(); if t then if 0 < u then vpred() else print(`Klika:`,f); koniec := true end if else if j < k+1 then vzad() else lprin...
zostroj_nasledovnika := proc () local t; global u, f, j, n, koniec; t := F_je_syn(); if t then if 0 < u then vpred() else print(`Klika:`,f); koniec := true end if else if j < k+1 then vzad() else lprin...

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

Priklad

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_rozsireny_strom_rieseni():

`Klika:`, vector([5, 2, 1])

>    k := 4: inicializuj(): zostroj_rozsireny_strom_rieseni():

`K-klika v grafe neexistuje\n`

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_rozsireny_strom_rieseni():

`Klika:`, vector([7, 6, 5, 4])

>    k := 5: inicializuj(): zostroj_rozsireny_strom_rieseni():

`K-klika v grafe neexistuje\n`

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

`Klika:`, vector([7, 3, 1])

>