Witam,
Zastanawiam się na ile sposobów można podzielić graf nieskierowany tak, że będziemy mieli takie dwa zbiory, klikę, oraz drugi, w którym wierzchołki nie są połączone, żaden z żadnym.
Zastanawiałem się nad dwudzielnością, jednak nie na za wiele mi się to zda chyba.
Jakie macie sugestie?
[Algorytmy][Grafy] Podział grafu na dwa zbiory
-
matinf
- Użytkownik
- Posty: 1922
- Rejestracja: 26 mar 2012, o 18:52
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Podziękował: 695 razy
- Pomógł: 4 razy
[Algorytmy][Grafy] Podział grafu na dwa zbiory
Ostatnio zmieniony 27 mar 2012, o 13:51 przez Afish, łącznie zmieniany 1 raz.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.
Powód: Staraj się lepiej dobierać nazwy tematów, tak by wskazywały o czym jest treść zadania.
-
paladin
- Użytkownik
- Posty: 148
- Rejestracja: 24 sty 2005, o 22:15
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 19 razy
[Algorytmy][Grafy] Podział grafu na dwa zbiory
Czyżby to zadanie: ? W opracowaniu XVIII Olimpiady Informatycznej (tzw. "niebieskiej książeczce"), dostępnym na stronie Olimpiady, jest to dość dobrze przedyskutowane.