Liczba chromatyczna grafu konpopoz: Czym jest liczba chromatyczna grafu? Mam takie zadanie: Ile wynosi liczba chromatyczna χ(G) grafu G opisanego macierzą M9? 0 1 0 0 1 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 0 0 1 0 1 1 0 0 Prawidłowa odpowiedź ma wynosić 3

I'm back: Narysuj sobie ten graf i go pokoloruj

konpopoz: Ale jak mam go pokolorować? :<

wredulus_pospolitus: najpierw nam narysuj ten graf

konpopoz: Ok, podsyłam link do narysowanego grafu: https://imgur.com/FU2cdMO Z każdym dniem jestem coraz ciekawszy o co chodzi z tym kolorowaniem xD

konpopoz: To jak to jest z tą liczbą chromatyczną grafu?

konpopoz: halo

kerajs: Skoro masz już graf to go kolorujesz tak, aby dwa wierzchołki połączone krawędzią nie miały takiego samego koloru. Liczba chromatyczna to minimalna ilość kolorów potrzebnych do pokolorowania całego grafu. Tu liczbą chromatyczną nie może być 2 (np z powodu cyklu o wierzchołkach 1,2,7,10,5,1) ale trzy kolory wystarczą. Wskaż przykład takiego kolorowania.