Matematyka dyskretna - więcej o wykresach
Kolorowanie wykresu
Kolorowanie wykresu to procedura przypisywania kolorów do każdego wierzchołka grafu G w taki sposób, że żadne sąsiednie wierzchołki nie mają tego samego koloru. Celem jest zminimalizowanie liczby kolorów podczas kolorowania wykresu. Najmniejszą liczbę kolorów potrzebnych do pokolorowania wykresu G nazywa się liczbą chromatyczną tego wykresu. Problem z kolorowaniem wykresów jest problemem NP Complete.
Metoda pokolorowania wykresu
Kroki wymagane do pokolorowania wykresu G z liczbą wierzchołków n są następujące -
Step 1 - Ułóż wierzchołki wykresu w określonej kolejności.
Step 2 - Wybierz pierwszy wierzchołek i pokoloruj go pierwszym kolorem.
Step 3- Wybierz następny wierzchołek i pokoloruj go kolorem o najniższym numerze, który nie został pokolorowany na żadnym sąsiadującym z nim wierzchołku. Jeśli wszystkie sąsiednie wierzchołki są pokolorowane tym kolorem, przypisz mu nowy kolor. Powtarzaj ten krok, aż wszystkie wierzchołki zostaną pokolorowane.
Example
Na powyższym rysunku pierwszy wierzchołek $ a $ ma kolor czerwony. Ponieważ sąsiednie wierzchołki wierzchołka a są ponownie sąsiadujące, wierzchołek $ b $ i wierzchołek $ d $ są pokolorowane na inny kolor, odpowiednio zielony i niebieski. Wtedy wierzchołek $ c $ ma kolor czerwony, ponieważ żaden sąsiedni wierzchołek $ c $ nie ma koloru czerwonego. Dlatego mogliśmy pokolorować wykres 3 kolorami. Stąd liczba chromatyczna wykresu wynosi 3.
Zastosowania kolorowania wykresów
Niektóre zastosowania kolorowania wykresów obejmują -
- Zarejestruj alokację
- Kolorowanie mapy
- Dwustronne sprawdzanie wykresów
- Przydzielanie mobilnych częstotliwości radiowych
- Przygotowanie harmonogramu itp.
Graph Traversal
Przechodzenie przez wykres to problem odwiedzania wszystkich wierzchołków wykresu w jakiejś systematycznej kolejności. Istnieją głównie dwa sposoby przechodzenia przez wykres.
- Pierwsze przeszukiwanie szerokości
- Głębokie pierwsze wyszukiwanie
Pierwsze przeszukiwanie szerokości
Breadth First Search (BFS) zaczyna się od wierzchołka poziomu 0 $ X $ wykresu $ G $. Następnie odwiedzamy wszystkie wierzchołki, które są sąsiadami $ X $. Po wizycie zaznaczamy wierzchołki jako „odwiedzone” i umieszczamy je na poziomie-1. Następnie zaczynamy od wierzchołków poziomu 1 i stosujemy tę samą metodę na każdym wierzchołku poziomu 1 i tak dalej. Przechodzenie przez BFS kończy się, gdy odwiedzony zostanie każdy wierzchołek grafu.
BFS Algorithm
Koncepcja polega na odwiedzeniu wszystkich wierzchołków sąsiadów przed odwiedzeniem innych wierzchołków sąsiednich wierzchołków sąsiadów.
Zainicjuj stan wszystkich węzłów jako „Gotowy”.
Umieść wierzchołek źródłowy w kolejce i zmień jego status na „Oczekiwanie”.
Powtarzaj następujące dwa kroki, aż kolejka będzie pusta -
Usuń pierwszy wierzchołek z kolejki i oznacz go jako „Odwiedzony”.
Dodaj na końcu kolejki wszystkich sąsiadów usuniętego wierzchołka, których stan to „Gotowy”. Oznacz ich status jako „Oczekujący”.
Problem
Weźmy wykres (wierzchołkiem źródłowym jest „a”) i zastosujmy algorytm BFS, aby ustalić kolejność przechodzenia.
Solution -
Zainicjuj stan wszystkich wierzchołków na „Gotowy”.
Umieścić w kolejce i zmienić jego status na „Oczekiwanie”.
Usuń z kolejki, oznaczyć ją jako „wizyty”.
Dodaj „s sąsiedzi w«Ready»stan b, d oraz e do końca kolejki i oznaczyć je jako«oczekujące».
Usuń b z kolejki, oznacz go jako „Odwiedzony”, umieść jego „Gotowego” sąsiada c na końcu kolejki i oznacz c jako „Oczekiwanie”.
Usuń d z kolejki i oznacz jako „Odwiedzone”. Nie ma sąsiada w stanie „Gotowy”.
Usuń e z kolejki i oznacz jako „Odwiedzone”. Nie ma sąsiada w stanie „Gotowy”.
Usuń c z kolejki i oznacz jako „Odwiedzone”. Nie ma sąsiada w stanie „Gotowy”.
Kolejka jest pusta, więc zatrzymaj się.
Więc kolejność przechodzenia jest -
$ a \ rightarrow b \ rightarrow d \ rightarrow e \ rightarrow c $
Alternatywne porządki przechodzenia to -
$ a \ rightarrow b \ rightarrow e \ rightarrow d \ rightarrow c $
Lub $ a \ rightarrow d \ rightarrow b \ rightarrow e \ rightarrow c $
Lub $ a \ rightarrow e \ rightarrow b \ rightarrow d \ rightarrow c $
Lub $ a \ rightarrow b \ rightarrow e \ rightarrow d \ rightarrow c $
Lub $ a \ rightarrow d \ rightarrow e \ rightarrow b \ rightarrow c $
Application of BFS
- Znalezienie najkrótszej ścieżki
- Minimalne drzewo rozpinające dla wykresu nieważonego
- System nawigacji GPS
- Wykrywanie cykli na wykresie nieukierunkowanym
- Znajdowanie wszystkich węzłów w jednym podłączonym komponencie
Complexity Analysis
Niech $ G (V, E) $ będzie grafem z $ | V | $ liczbą wierzchołków i $ | E | $ liczbą krawędzi. Gdyby algorytm przeszukiwania wszerz odwiedzał każdy wierzchołek wykresu i sprawdzał każdą krawędź, wówczas jego złożoność czasowa byłaby -
$$ O (| V | + | E |). O (| E |) $$
Może się różnić od $ O (1) $ do $ O (| V2 |) $
Głębokie pierwsze wyszukiwanie
Algorytm wyszukiwania w głębi (DFS) zaczyna się od wierzchołka $ v $, następnie przechodzi do sąsiedniego wierzchołka (powiedzmy x), który nie był wcześniej odwiedzany i zaznacza jako „odwiedzony” i kontynuuje z sąsiednim wierzchołkiem $ x $ i wkrótce.
Jeśli w jakimkolwiek wierzchołku napotka, że wszystkie sąsiednie wierzchołki są odwiedzone, wykonuje cofanie się, dopóki nie znajdzie pierwszego wierzchołka z sąsiednim wierzchołkiem, przez który wcześniej nie przeszedł. Następnie przechodzi przez ten wierzchołek, kontynuuje z sąsiednimi wierzchołkami, aż przecina wszystkie odwiedzone wierzchołki i musi ponownie się cofnąć. W ten sposób przejdzie przez wszystkie wierzchołki osiągalne z początkowego wierzchołka $ v $.
DFS Algorithm
Koncepcja polega na odwiedzeniu wszystkich wierzchołków sąsiednich wierzchołków sąsiadów przed odwiedzeniem innych wierzchołków sąsiadów.
Zainicjuj stan wszystkich węzłów jako „Gotowy”
Umieść wierzchołek źródłowy w stosie i zmień jego stan na „Oczekiwanie”
Powtarzaj następujące dwa kroki, aż stos będzie pusty -
Zdejmij górny wierzchołek ze stosu i oznacz go jako „Odwiedzone”
Wepchnij na górę stosu wszystkich sąsiadów usuniętego wierzchołka, których stan to „Gotowy”. Oznacz ich status jako „Oczekujący”.
Problem
Weźmy wykres (wierzchołkiem źródłowym jest „a”) i zastosujmy algorytm DFS, aby ustalić kolejność przemierzania.
Solution
Zainicjuj stan wszystkich wierzchołków na „Gotowy”.
Wcisnąć w stosie i zmienić jego status na „Oczekiwanie”.
Pop a i oznacz go jako „Odwiedzone”.
Wcisnąć danej „s sąsiadów«gotowy»państwowego E, D i B na górze stosu i oznaczyć je jako«oczekujące».
Zdejmij b ze stosu, oznacz go jako „Odwiedzony” i wepchnij sąsiada „Gotowego” c na stos.
Zdejmij c ze stosu i oznacz jako „Odwiedzone”. Nie ma sąsiada „Gotowego”.
Pop d ze stosu i oznaczyć ją jako „wizyty”. Nie ma sąsiada „Gotowego”.
Pop- e ze stosu i oznaczyć ją jako „wizyty”. Nie ma sąsiada „Gotowego”.
Stos jest pusty. Więc przestań.
Więc kolejność przechodzenia jest -
$ a \ rightarrow b \ rightarrow c \ rightarrow d \ rightarrow e $
Alternatywne porządki przechodzenia to -
$ a \ rightarrow e \ rightarrow b \ rightarrow c \ rightarrow d $
Lub $ a \ rightarrow b \ rightarrow e \ rightarrow c \ rightarrow d $
Lub $ a \ rightarrow d \ rightarrow e \ rightarrow b \ rightarrow c $
Lub $ a \ rightarrow d \ rightarrow c \ rightarrow e \ rightarrow b $
Lub $ a \ rightarrow d \ rightarrow c \ rightarrow b \ rightarrow e $
Complexity Analysis
Niech $ G (V, E) $ będzie grafem z $ | V | $ liczbą wierzchołków i $ | E | $ liczbą krawędzi. Jeśli algorytm DFS odwiedza każdy wierzchołek wykresu i sprawdza każdą krawędź, to złożoność czasowa wynosi -
$$ \ circleddash (| V | + | E |) $$
Applications
- Wykrywanie cyklu na wykresie
- Aby znaleźć sortowanie topologiczne
- Aby sprawdzić, czy wykres jest dwudzielny
- Znajdowanie połączonych komponentów
- Znajdowanie mostów grafu
- Znajdowanie podwójnych połączeń na wykresach
- Rozwiązanie problemu Knight's Tour
- Rozwiązywanie zagadek za pomocą tylko jednego rozwiązania