Dzis nadal pozostaniemy w tematyce grafów i dziś powiemy sobie o pojęciu drzewa i lasu. Lasem nazywamy dowolny graf nieskierowany niezawierający cyklu. Drzewem z kolei nazywamy las spójny. Czyli jest to dowolny graf nieskierowany spójny niezawierający cyklu (usunięcie wierzchołka traci spójność). Załóżmy, że mamy taki graf spójny:

Drzewem rozpinającym grafu spójnego G = (V, E) nazywamy dowolne drzewo
. Elementy zbioru T nazywamy gałęziami drzewa, zaś elementy zbioru E - T nazywamy cięciwami względem drzewa rozpinającego. Przejdźmy teraz do pojęcia cyklu fundamentalnego grafu G = (V, E). Przyjmijmy takie oznaczenia, że
i jest to cięciwa. Cykl fundamentalny określamy wzorem
. Stosujemy tez takie oznaczenia. Za
oznaczamy cykl fundamentalny względem drzewa, za C oznaczamy zbiór cykli fundamentalnych, a za
oznaczamy zbiór wszystkich cykli fundamentalnych.

Kolejnym tematem jakim się na dzisiejszych zajęciach zajmiemy będize temat związany z kolorowaniem 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. Najczęsciej stosuje się zwykle cztery różne barwy. I tu pojawia się twierdzenie czterech barw. Nim jednak do niego przejdziemy należy powiedzieć o tym, co to jest graf planarny. Graf planarny to graf, który można narysować na płaszczyźnie tak, by krzywe obrazujące krawędzie grafu nie przecinały się ze sobą. Odwzorowanie grafu planarnego na płaszczyznę o tej własności nazywane jest jego rysunkiem płaskim (mapą płaską). Graf planarny o zbiorze wierzchołków i krawędzi zdefiniowanym poprzez rysunek płaski nazywany jest grafem płaskim. Istnieje więc coś takiego, jak twierdzenie o czterech barwach, które mówi, że każdy graf planarny jest czterobarwny. Możliwe jest pokolorowanie grafu na trzy kolory, ale to już nie będize graf planarny.

1 3

5

2 4

---