Algorytm dotyczący grafów

popop · Post autor: **popop** » 2 lis 2009, o 15:09

Witam:) mam na zadanie z informatyki dotyczące grafów:
mając dany graf pomaluj jego wierzchołki na czarno lub biało jednak dwa sąsiednie muszą być innego koloru przykładowe dane wejściowe:
4-liczba wierzchołków 4-liczba połączeń miedzy wierzchołkami
1 2 // wierzchołki połączone jedną krawędzią
3 4
2 3
1 4
bardzo proszę o pomoc w jego rozwiązaniu a dokładnie o jakiś algorytm bo zupełnie nie wiem jak się za to zabrać:)
i odpowiedź:
1-czarny
3-czarny
2-biały
4-biały

kadiii · Post autor: **kadiii** » 2 lis 2009, o 16:01

Nie potrzeba tu żadnego algorytmu specjalnego - zauważ, że z samego warunku wynika zasada tworzenia - kolorujesz pierwszy np. na czarno i potem wszystkich sąsiadów na biało sąsiadów sąsiadów na przeciwny itd. aż wszystkie wierzchołki bedą pokolorowane.

popop · Post autor: **popop** » 2 lis 2009, o 18:52

a jak mam
5 6

1 2
3 2
2 4
1 4
1 5
4 5
???

abc666 · Post autor: **abc666** » 2 lis 2009, o 19:16

Tutaj rozwiązania nie ma.

popop · Post autor: **popop** » 2 lis 2009, o 20:30

no właśnie i jak to sprawdzić że się nie da?

matshadow · Post autor: **matshadow** » 2 lis 2009, o 21:05

W algorytmie przeszukiwania grafu sprawdzasz czy przypadkiem kolor wierzchołka obrabianego nie jest równy kolorowi jakiegoś jego sąsiada.