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