Kolorowanie wykresu
Kolorowanie grafów można opisać jako proces przypisywania kolorów wierzchołkom grafu. W tym przypadku ten sam kolor nie powinien być używany do wypełnienia dwóch sąsiednich wierzchołków. Kolorowanie grafów możemy również nazwać kolorowaniem wierzchołków. Przy kolorowaniu grafów należy zwrócić uwagę, aby graf nie zawierał krawędzi, których wierzchołki końcowe są pokolorowane tym samym kolorem. Ten typ wykresu nazywany jest wykresem prawidłowo pokolorowanym.
Przykład kolorowania wykresu
wyk
Na tym wykresie pokazujemy odpowiednio pokolorowany wykres, który opisano w następujący sposób:
Powyższy wykres zawiera kilka punktów, które opisano w następujący sposób:
- Nie można użyć tego samego koloru do pokolorowania dwóch sąsiednich wierzchołków.
- Dlatego możemy to nazwać odpowiednio pokolorowanym wykresem.
Zastosowania kolorowania grafów
Kolorowanie grafów ma różne zastosowania. Niektóre z ich ważnych zastosowań opisano w następujący sposób:
- Zadanie
- Kolorowanie mapy
- Planowanie zadań
- Sudoku
- Przygotuj tabelę czasu
- Rozwiązanie konfliktu
Liczba chromatyczna
Liczbę chromatyczną można opisać jako minimalną liczbę kolorów wymaganą do prawidłowego pokolorowania dowolnego wykresu. Innymi słowy, liczbę chromatyczną można opisać jako minimalną liczbę kolorów potrzebną do pokolorowania dowolnego grafu w taki sposób, że żadnemu dwóm sąsiednim wierzchołkom grafu nie zostanie przypisany ten sam kolor.
Przykład liczby chromatycznej:
Aby zrozumieć liczbę chromatyczną, rozważymy wykres opisany w następujący sposób:
Powyższy wykres zawiera kilka punktów, które opisano w następujący sposób:
- Ten sam kolor nie jest używany do kolorowania dwóch sąsiednich wierzchołków.
- Minimalna liczba kolorów tego grafu wynosi 3, co jest potrzebne do prawidłowego pokolorowania wierzchołków.
- Zatem na tym wykresie liczba chromatyczna = 3
- Jeśli chcemy odpowiednio pokolorować ten wykres, w tym przypadku potrzebne są nam co najmniej 3 kolory.
Rodzaje chromatycznej liczby wykresów:
Istnieją różne typy chromatycznej liczby grafów, które opisano w następujący sposób:
Wykres cyklu:
Wykres będzie nazywany grafem cyklicznym, jeśli zawiera „n” krawędzi i „n” wierzchołków (n >= 3), które tworzą cykl o długości „n”. Graf cykliczny może mieć tylko 2 lub 3 stopnie wszystkich wierzchołków.
Liczba chromatyczna:
- Liczba chromatyczna na grafie cyklicznym będzie wynosić 2, jeśli liczba wierzchołków na tym grafie jest parzysta.
- Liczba chromatyczna na grafie cyklicznym będzie wynosić 3, jeśli liczba wierzchołków na tym grafie jest nieparzysta.
Przykłady wykresu cyklu:
Istnieją różne przykłady wykresów cykli. Niektóre z nich opisano w następujący sposób:
Przykład 1: Na poniższym wykresie musimy określić liczbę chromatyczną.
Rozwiązanie: Na powyższym wykresie cyklu trzy wierzchołki mają trzy różne kolory i żaden z sąsiednich wierzchołków nie jest pokolorowany tym samym kolorem. Na tym grafie liczba wierzchołków jest nieparzysta. Więc
Liczba chromatyczna = 3
Przykład 2: Na poniższym wykresie musimy określić liczbę chromatyczną.
Rozwiązanie: Na powyższym wykresie cyklicznym cztery wierzchołki mają dwa kolory i żaden z sąsiednich wierzchołków nie jest pokolorowany tym samym kolorem. Na tym grafie liczba wierzchołków jest parzysta. Więc
Liczba chromatyczna = 2
Przykład 3: Na poniższym wykresie musimy określić liczbę chromatyczną.
Rozwiązanie: Na powyższym wykresie pięć wierzchołków ma 4 różne kolory, a dwa sąsiednie wierzchołki są pokolorowane tym samym kolorem (niebieskim). Zatem ten wykres nie jest wykresem cyklicznym i nie zawiera liczby chromatycznej.
Przykład 4: Na poniższym wykresie musimy określić liczbę chromatyczną.
Rozwiązanie: Na powyższym wykresie sześć wierzchołków ma dwa różne kolory i żaden z sąsiednich wierzchołków nie jest pokolorowany tym samym kolorem. Na tym grafie liczba wierzchołków jest parzysta. Więc
Liczba chromatyczna = 2
Wykres planisty
Wykres będzie nazywany wykresem planisty, jeśli zostanie narysowany na płaszczyźnie. Krawędzie wykresu planisty nie mogą się krzyżować.
Liczba chromatyczna:
- Na wykresie planisty liczba chromatyczna musi być mniejsza lub równa 4.
- Wykres planisty można również przedstawić za pomocą wszystkich powyższych wykresów cykli z wyjątkiem przykładu 3.
Przykłady wykresu Planera:
Istnieją różne przykłady wykresów planerowych. Niektóre z nich opisano w następujący sposób:
Przykład 1: Na poniższym wykresie musimy określić liczbę chromatyczną.
Rozwiązanie: Na powyższym wykresie trzy wierzchołki mają 3 różne kolory i żadna z krawędzi tego grafu nie przecina się. Więc
skróty do Linuksa
Liczba chromatyczna = 3
Tutaj liczba chromatyczna jest mniejsza niż 4, więc ten wykres jest wykresem płaskim.
Przykład 2: Na poniższym wykresie musimy określić liczbę chromatyczną.
Rozwiązanie: Na powyższym wykresie cztery wierzchołki mają dwa różne kolory i żadna z krawędzi tego grafu nie przecina się. Więc
Liczba chromatyczna = 2
Tutaj liczba chromatyczna jest mniejsza niż 4, więc ten wykres jest wykresem płaskim.
Przykład 3: Na poniższym wykresie musimy określić liczbę chromatyczną.
Rozwiązanie: Na powyższym wykresie pięć wierzchołków ma 5 różnych kolorów i żadna z krawędzi tego grafu nie przecina się. Więc
Liczba chromatyczna = 5
Tutaj liczba chromatyczna jest większa niż 4, więc ten wykres nie jest wykresem płaskim.
Przykład 4: Na poniższym wykresie musimy określić liczbę chromatyczną.
Rozwiązanie: Na powyższym wykresie sześć wierzchołków ma dwa różne kolory i żadna z krawędzi tego grafu nie przecina się. Więc
Liczba chromatyczna = 2
Tutaj liczba chromatyczna jest mniejsza niż 4, więc ten wykres jest wykresem płaskim.
Kompletny wykres
Graf będzie nazywany grafem pełnym, jeżeli tylko jedna krawędź połączy każde dwa różne wierzchołki. Każdy wierzchołek w pełnym grafie jest połączony z każdym innym wierzchołkiem. Na tym wykresie każdy wierzchołek zostanie pokolorowany innym kolorem. Oznacza to, że w pełnym grafie dwa wierzchołki nie mają tego samego koloru.
Liczba chromatyczna
W pełnym grafie liczba chromatyczna będzie równa liczbie wierzchołków tego wykresu.
Przykłady pełnego wykresu:
Istnieje wiele przykładów pełnych wykresów. Niektóre z nich opisano w następujący sposób:
Przykład 1: Na poniższym wykresie musimy określić liczbę chromatyczną.
Rozwiązanie: Istnieją 4 różne kolory dla 4 różnych wierzchołków i żaden z kolorów nie jest taki sam na powyższym wykresie. Zgodnie z definicją liczba chromatyczna to liczba wierzchołków. Więc,
0,06 jako ułamek
Liczba chromatyczna = 4
Przykład 2: Na poniższym wykresie musimy określić liczbę chromatyczną.
Rozwiązanie: Istnieje 5 różnych kolorów dla 5 różnych wierzchołków i żaden z kolorów nie jest taki sam na powyższym wykresie. Zgodnie z definicją liczba chromatyczna to liczba wierzchołków. Więc,
Liczba chromatyczna = 5
Przykład 3: Na poniższym wykresie musimy określić liczbę chromatyczną.
Rozwiązanie: Istnieją 3 różne kolory dla 4 różnych wierzchołków, a jeden kolor powtarza się w dwóch wierzchołkach na powyższym wykresie. Zatem ten wykres nie jest wykresem kompletnym i nie zawiera liczby chromatycznej.
Wykres dwudzielny
Graf będzie nazywany grafem dwudzielnym, jeśli zawiera dwa zbiory wierzchołków, A i B. Wierzchołek A może łączyć się tylko z wierzchołkami B. Oznacza to, że krawędzie nie mogą łączyć wierzchołków zbiorem.
Liczba chromatyczna
Na każdym grafie dwudzielnym liczba chromatyczna jest zawsze równa 2.
Przykłady wykresu dwudzielnego:
Istnieje wiele przykładów grafów dwudzielnych. Niektóre z nich opisano w następujący sposób:
Przykład 1: Na poniższym wykresie musimy określić liczbę chromatyczną.
Rozwiązanie: Na powyższym grafie znajdują się 2 różne zestawy wierzchołków. Zatem liczba chromatyczna wszystkich grafów dwudzielnych będzie zawsze wynosić 2. Zatem
Liczba chromatyczna = 2
Drzewo:
Połączony wykres będzie nazywany drzewem, jeśli nie ma na nim żadnych obwodów. W drzewie liczba chromatyczna będzie równa 2, niezależnie od liczby wierzchołków w drzewie. Każdy graf dwudzielny jest także drzewem.
Liczba chromatyczna
W każdym drzewie liczba chromatyczna jest równa 2.
25 c do k
Przykłady drzew:
Istnieją różne przykłady drzew. Niektóre z nich opisano w następujący sposób:
Przykład 1: W poniższym drzewie musimy określić liczbę chromatyczną.
Rozwiązanie: Istnieją 2 różne kolory dla czterech wierzchołków. Drzewo o dowolnej liczbie wierzchołków musi zawierać liczbę chromatyczną wynoszącą 2 w powyższym drzewie. Więc,
Liczba chromatyczna = 2
Przykład 2: W poniższym drzewie musimy określić liczbę chromatyczną.
Rozwiązanie: Istnieją 2 różne kolory dla pięciu wierzchołków. Drzewo o dowolnej liczbie wierzchołków musi zawierać liczbę chromatyczną wynoszącą 2 w powyższym drzewie. Więc,
Liczba chromatyczna = 2
Prawdziwy przykład liczby chromatycznej
Załóżmy, że Marry jest menedżerem w firmie Xyz. Firma zatrudnia nowych pracowników i musi przygotować harmonogram szkoleń dla tych nowych pracowników. Musi zaplanować trzy spotkania i stara się jak najlepiej wykorzystać kilka przedziałów czasowych na spotkania. Jeżeli pracownik musi być na dwóch różnych spotkaniach, menedżer musi zastosować różne harmonogramy tych spotkań. Załóżmy, że chcemy uzyskać wizualną reprezentację tego spotkania.
W formie wizualnej Marry używa kropki, aby wskazać spotkanie. Jeśli jest pracownik, który ma dwa spotkania i chce dołączyć do obu spotkań, to oba spotkania zostaną połączone za pomocą Edge’a. Różne przedziały czasowe są reprezentowane za pomocą kolorów. Menedżer wypełnia więc kropki tymi kolorami w taki sposób, aby dwie kropki nie zawierały tego samego koloru, który ma wspólną krawędź. (Oznacza to, że pracownik, który musi uczestniczyć w dwóch spotkaniach, nie może mieć tego samego przedziału czasowego). Wizualna reprezentacja tego jest opisana w następujący sposób:
