Wersja z 00:39, 13 mar 2013 edytuj Addbot (dyskusja \| edycje) 748 218 edycji m Bot: Przenoszę 25 linków interwiki do Wikidata, znajdziesz je teraz w zasobie d:q504843 ← poprzednia edycja		Wersja z 13:00, 16 sie 2015 edytuj anuluj edycję Vebace (dyskusja \| edycje) Redaktorzy 13 046 edycji drobne techniczne, źródła/przypisy następna edycja →
Linia 1: {{Teoria grafów}} '''Kolorowanie grafu''' polega w ogólności na przypisaniu określonym elementom składowym grafu (najczęściej wierzchołkom, rzadziej krawędziom lub ścianom) wybranych kolorów według ściśle określonych reguł. Klasyczne (czyli wierzchołkowe) kolorowanie grafu jest związane z przypisaniem wszystkim wierzchołkom w grafie jednej z wybranych barw w ten sposób, aby żadne dwa sąsiednie wierzchołki nie miały tego samego koloru. Innymi słowy, pewne pokolorowanie wierzchołkowe jest poprawne (legalne, dozwolone) wtedy, gdy końcom żadnej krawędzi nie przypisano tego samego koloru<ref name="colouring">{{Cytuj książkę \| nazwisko = Diestel \| imię = Reinhard \| tytuł = Graph Theory \| url=http://diestel-graph-theory.com/index.html \| miejsce = Nowy Jork \| rok = 2000 \| strony = 95\| isbn= 0-387-95014-1}}</ref>. == Podstawowe definicje == '''Klasyczne (wierzchołkowe) kolorowanie grafu''' -– przyporządkowywanie wierzchołkom [[graf (matematyka)\|grafu]] [[Liczby naturalne\|liczb naturalnych]] w taki sposób, aby końce żadnej [[Graf (matematyka)\|krawędzi]] nie miały przypisanej tej samej liczby. Ze względów historycznych oraz dla lepszego zobrazowania problemu mówi się o kolorowaniu, przy czym różnym kolorom odpowiadają różne liczby. '''Pokolorowaniem''' wierzchołków grafu nazywamy jedno konkretne przyporządkowanie kolorów wierzchołkom. Pokolorowanie jest '''legalne''' ('''dozwolone'''), gdy końcom żadnej krawędzi nie przyporządkowano tego samego koloru. Linia 57: == Bibliografia == * {{cytuj książkę \|autor = Marek Kubale i inni \|tytuł=Optymalizacja dyskretna. Modele i metody kolorowania grafów

Kolorowanie grafu: Różnice pomiędzy wersjami