Kolorowanie grafów:

Zadanie:

Moduł 1:

Losowe generowanie grafu spójnego, z zadanym z góry wypełnieniem krawędzi (np. 50%), o licznie wierzchołków n (parametr). Dodatkowo program ma umożliwiać wprowadzanie grafu zdefiniowanego przez użytkownika.

Moduł2.

Program koloruje graf trzema metodami (parametr metody). Koloruje, tzn. indeksuje wierzchołki.

metoda 1 – LF

metoda 2 – SL

metoda 3 – SLF

Moduł3.

Program bada złożoność czasową, tzn. rysuje funkcję średniego czasu (po np. 1000 symulacji) vs ilość wierzchołków dla każdej z 3 metod. Finalnie – prezentowany jest wykres 3 przebiegów (dla każdej z metod) czasu w funkcji liczby wierzchołków. Ważne jest aby wszystkie 3 metody były zapuszczane na tej samej instancji grafu (tzn. jeżeli odbywa się symulacja 1000 grafów o np. 10-ci wierzchołkach – to ten sam zbiór 1000 grafów jest podany kolorowaniu metodą 1,2,3).

Dodatkowo – program wychwytuje wszystkie przypadki kolorowania tego samego grafu, różną ilością kolorów (w postaci odłożenia struktury danego grafu, liczby kolorów dla metod 1,2,3 do pliku).

Termin: 13 stycznia 2014
--------

Znajdywanie cyklu i przeszukiwanie w głąb:

Przykłady:

G_bez_cyklu=[0 1 0 0 0

1 0 1 0 0

0 1 0 1 1

0 0 1 0 0

0 0 1 0 0];

G_z_cyklem=[0 1 0 0 1 0 0

1 0 1 1 0 0 0

0 1 0 0 1 1 0

0 1 0 0 0 0 0

1 0 1 0 0 0 0

0 0 1 0 0 0 1

0 0 0 0 0 1 0

];

>> dfs_new(G_bez_cyklu)

tabela_poprzednikow =

1

tabela_poprzednikow =

1 2

tabela_poprzednikow =

1 2 3

tabela_poprzednikow =

1 2 3 4

tabela_poprzednikow =

1 2 3 5

>> znajdz_cykl_new(G_z_cyklem)

cykl: 1 2 3 5 1

>> znajdz_cykl_new(G_bez_cyklu)

brak cyklu