Autor Wątek: K-dzielny graf, szukam algorytmu  (Przeczytany 929 razy)

Offline Buyuk

  • Użytkownik
    • Mój blog ;]

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

Offline Mr. Spam

  • Miłośnik przetworów mięsnych

Offline owyn

  • Użytkownik

# Październik 23, 2011, 10:33:36
Algorytm jest bardzo prosty. Dla grafu G o n wierzchołkach:
return n;

Offline Buyuk

  • Użytkownik
    • Mój blog ;]

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

Offline Konon

  • Użytkownik

# Październik 23, 2011, 16:18:22