Warsztat.GD

Programowanie => Matematyka i fizyka => Wątek zaczęty przez: Buyuk w Październik 23, 2011, 02:13:37

Tytuł: K-dzielny graf, szukam algorytmu
Wiadomość wysłana przez: Buyuk w Październik 23, 2011, 02:13:37
Hej,

Poszukuję algorytmu, który pozwoli mi obliczyć dla danego grafu G
maksymalną liczbę k, taką, że zbiór wierzchołków w G można podzielić
na k rozłącznych podzbiorów, takich, że żadna krawędź należąca do G
nie łączy dwóch wierzchołków z tego samego podzbioru.
Zna ktoś może podobny algorytm ?

Pozdrawiam, Buyuk.
Tytuł: Odp: K-dzielny graf, szukam algorytmu
Wiadomość wysłana przez: owyn w Październik 23, 2011, 10:33:36
Algorytm jest bardzo prosty. Dla grafu G o n wierzchołkach:
return n;
Tytuł: Odp: K-dzielny graf, szukam algorytmu
Wiadomość wysłana przez: Buyuk w Październik 23, 2011, 15:09:27
Om, zaiste, późno było i się przejęzyczyłem.
Chodziło mi o minimalne k, zamiast maksymalnego.
Maksymalne zaiste jest równe n ;-)

Może ktoś pomóc ?

Pozdrawiam, Buyuk.
Tytuł: Odp: K-dzielny graf, szukam algorytmu
Wiadomość wysłana przez: Konon w Październik 23, 2011, 16:18:22
http://kaims.pl/~jendrek/PAA/035B.pdf chyba powinno pomóc.