Kolorowanie wierzchołków grafu

Omówmy inne zastosowanie teorii grafów. Wykorzystuje przypisanie wierzchołkom grafu takich kolorów, aby nie sąsiadowały ze sobą żadne dwa wierzchołki o takich samych kolorach. Nazywamy to kolorowaniem wierzchołków grafu. Kolory możemy zastąpić również liczbami. Z problemem kolorowania wierzchołków grafu związana jest tzw. liczba chromatyczna grafu, czyli minimalna ilość kolorów do pokolorowania danego grafu.

Zastosowanie

Rozwiązanie problemu kolorowania wierzchołków grafu możemy wykorzystać np. w planowaniu harmonogramów. Każdy kolor reprezentuje jedną jednostkę czasu lub inne ograniczenie, a wierzchołki grafu reprezentują zadania lub zdarzenia.

Polecenie 1

Zapoznaj się z apletem, który pozwala na utworzenie grafu przez dodawanie do niego wierzchołków i krawędzi (lub usuwanie ich). Aplet umożliwia również przeprowadzenie dla grafu procedury kolorowania wierzchołków.

Wykorzystując aplet, utwórz graf, który przedstawia schemat ulic na twoim osiedlu lub układ sal w szkole. Następnie sprawdź, ile wynoszą ich liczby chromatyczne.

Przetestuj działanie apletu dla grafu, który nie jest spójny.

1
Polecenie 2

Uruchom aplet przedstawiający kolorowanie wierzchołków grafu. Zwróć uwagę na kolory, które są wybierane przy kolejnych krokach algorytmu. Czy uzyskana liczba kolorów zawsze jest najmniejsza z możliwych?

R1Q9LZgDG3dZx

Aplet przedstawia kolorowanie wierzchołków grafu. Dzięki przyciskom apletu możliwe jest dodanie oraz usunięcie wierzchołka, dodanie lub usunięcie krawędzi pomiędzy poszczególnymi wierzchołkami. Na ekranie znajdują się również przyciski następny krok oraz od początku. Na ekranie po ustaleniu wszystkich wartości pojawia się tabela zawierająca informacje o kolorach wraz z ich numerami dotyczących odpowiednich wierzchołków oraz rysunek przedstawiający graf składający się z odpowiednie ilości wierzchołków i wybranych krawędzi.

  1. Przykład pierwszy. Graf składa się z trzech wierzchołków oraz trzech krawędzi. Punkty układają się w trójkąt i są ze sobą połączone. Tabela zawiera trzy kolumny odpowiadające za wierzchołki grafu.
    Krok pierwszy:
    Kolorowany wierzchołek: 1
    Pierwszy dostępny kolor 1 (kolor czerwony).
    Pod tabelą zawierającą informacje o kolorach wierzchołków pojawia się tabela zawierająca informację o tym jaki kolor można wykorzystać. Dostępny jest kolor czerwony o numerze jeden, zielony o numerze dwa i żółty o numerze trzy. Dla punktu pierwszego wszystkie kolory mogą zostać wykorzystane.
    Krok drugi:
    Wierzchołek zostaje pomalowany na kolor czerwony, a informacja ta zostaje zawarta w tabeli.
    Krok trzeci:
    Kolorowany wierzchołek: 2
    Pierwszy dostępny kolor 2 (kolor zielony).
    W tabeli opisującej możliwość wykorzystania kolorów, możliwy do wykorzystania jest kolor zielony oraz żółty.
    Krok czwarty:
    Drugi wierzchołek zostaje pomalowany na kolor zielony, informacja ta zostaje zawarta w tabeli.
    Krok piąty:
    Kolorowany wierzchołek : 3.
    Pierwszy dostępny kolor: 3 (żółty).
    W tabeli zawierającej kolory możliwe do wykorzystania jedynym dostępnym kolorem jest kolor żółty.
    Krok szósty:
    Wierzchołek trzeci zostaje pomalowany na kolor żółty. A w tabeli zostaje uzupełniony kolor wierzchołka trzeciego.

  2. Przykład drugi. Graf składa się z czterech punktów i trzech krawędzi. Krawędzie znajdują się pomiędzy punktami jeden i dwa, dwa i trzy oraz trzy i cztery.
    Krok pierwszy:
    Kolorowany wierzchołek: 1
    Pierwszy dostępny kolor: 1 (czerwony)
    Pojawia się tabela zawierająca cztery kolory z oznaczeniami od jeden do cztery, są to kolejno: czerwony, zielony, żółty oraz niebieski. Wszystkie są możliwe do wykorzystania.
    Krok drugi:
    Wierzchołek pierwszy został zamalowany na kolor czerwony, dane te zostały zapisane w tabeli.
    Krok trzeci:
    Kolorowany wierzchołek: 2
    Pierwszy dostępny kolor: 2 (zielony)
    W tabeli z dostępnością kolorów, kolor czerwony jest opisany jako niemożliwy do wykorzystania.
    Krok czwarty:
    Wierzchołek drugi zostaje pomalowany na kolor zielony i dane te zostają zapisane w tabeli.
    Krok piąty:
    Kolorowany wierzchołek: 3
    Pierwszy dostępny kolor: 1 (czerwony)
    W tabeli dostępności kolorów, wszystkie kolory poza zielonym są możliwe do wykorzystania.
    Krok szósty:
    Wierzchołek trzeci zostaje pomalowany na kolor czerwony, dane te zostają zapisane w tabeli.
    Krok siódmy:
    Kolorowany wierzchołek:4
    Pierwszy dostępny kolor: 2 (zielony).
    W tabeli dostępne są wszystkie kolory poza kolorem czerwonym.
    Krok ósmy:
    Wierzchołek czwarty zostaje zamalowany na kolor zielony, dane te zostają zapisane w tabeli.

  3. Przykład trzeci. Graf składa się z czterech punktów i czterech krawędzi. Krawędzie znajdują się pomiędzy punktami jeden i dwa, jeden i trzy, dwa i trzy oraz trzy i cztery. Obok grafu znajduje się tabela z ilością kolumn odpowiadającą ilości punktów.
    Krok pierwszy:
    Kolorowany wierzchołek: 1
    Pierwszy dostępny kolor:1 (czerwony).
    W tabeli przedstawiającej możliwość wykorzystania kolorów znajdują się cztery kolory: czerwony, zielony, żółty i niebieski ponumerowane od jeden do cztery. W pierwszym kroku można wykorzystać każdy z kolorów.
    Krok drugi:
    Wierzchołek pierwszy został pomalowany na kolor czerwony, co zostało zanotowane w tabeli.
    Krok trzeci:
    Kolorowany wierzchołek: 2
    Pierwszy dostępny wierzchołek: 2 (zielony)
    W tabeli zawierające możliwe do wykorzystania kolory można wykorzystać wszystkie kolory oprócz czerwonego.
    Krok czwarty:
    Wierzchołek drugi został pomalowany na kolor zielony, co zostało zapisane w tabeli.
    Krok piąty:
    Kolorowany wierzchołek: 3
    Pierwszy dostępny kolor: 3 (żółty).
    W tabeli do pokazane jest, że do wykorzystania pozostał kolor żółty i niebieski.
    Krok szósty:
    Wierzchołek trzeci został pokolorowany na kolor żółty, co zostało zaznaczone w tabeli.
    Krok siódmy:
    Kolorowany wierzchołek: 1
    Pierwszy dostępny kolor: 1 (czerwony).
    W tabeli do pokazane jest, że jedynie kolor żółty nie może zostać wykorzystany.
    Krok ósmy:
    Wierzchołek czwarty zostaje zamalowany na kolor czerwony, co zostaje zaznaczone w tabeli.

Więcej na temat algorytmu kolorowania grafu znajdziesz w e‑materiale Algorytmy grafoweP17MAekhVAlgorytmy grafowe.

Polecenie 3

Uruchom aplet dla grafu badanego przez Hamiltona (więcej na jego temat znajdziesz niżej w tej sekcji).

Polecenie 4

Zapoznaj się z prezentacją przedstawiającą algorytm, którego zadaniem jest znalezienie w reprezentowanym przez macierz sąsiedztwa grafie nieskierowanym cyklu oraz ścieżki Hamiltona.

R1VvoWNiovfVB1
Polecenie 5
R17pjjrfJYPtU
t
Polecenie 6
RJAw3UCujCKzQ
t
Polecenie 7
R19R7ezZXkMOX
t