Teoria grafów - przemierzalność

Po wykresie można przejść, jeśli można narysować ścieżkę między wszystkimi wierzchołkami bez odtwarzania tej samej ścieżki. W oparciu o tę ścieżkę istnieją pewne kategorie, takie jak ścieżka Eulera i obwód Eulera, które są opisane w tym rozdziale.

Ścieżka Eulera

Ścieżka Eulera zawiera każdą krawędź „G” dokładnie raz i każdy wierzchołek „G” co najmniej raz. Mówi się, że połączony wykres G jest przejezdny, jeśli zawiera ścieżkę Eulera.

Example

Ścieżka Eulera = dcabde.

Obwód Eulera

Na ścieżce Eulera, jeśli wierzchołek początkowy jest taki sam jak wierzchołek końcowy, wówczas nazywa się to obwodem Eulera.

Example

Euler’s Path = abcdagfeca.

Twierdzenie Eulera o obwodzie

Połączony graf „G” jest możliwy do przejścia wtedy i tylko wtedy, gdy liczba wierzchołków o nieparzystym stopniu w G wynosi dokładnie 2 lub 0. Połączony graf G może zawierać ścieżkę Eulera, ale nie obwód Eulera, jeśli ma dokładnie dwa wierzchołki z dziwny stopień.

Note - Ta ścieżka Eulera zaczyna się wierzchołkiem o nieparzystym stopniu i kończy się drugim wierzchołkiem o nieparzystym stopniu.

Example

Euler’s Path- beabdca nie jest obwodem Eulera, ale jest ścieżką Eulera. Najwyraźniej ma dokładnie 2 nieparzyste wierzchołki.

Note - W połączonym grafie G, jeśli liczba wierzchołków o nieparzystym stopniu = 0, to obwód Eulera istnieje.

Wykres Hamiltona

O połączonym grafie G mówi się, że jest grafem hamiltonowskim, jeśli istnieje cykl, który zawiera wszystkie wierzchołki G.

Każdy cykl jest obwodem, ale obwód może zawierać wiele cykli. Taki cykl nazywa się aHamiltonian cycle G.

Ścieżka Hamiltona

Mówi się, że połączony graf jest hamiltonianem, jeśli zawiera każdy wierzchołek G dokładnie raz. Taka ścieżka nazywa sięHamiltonian path.

Example

Hamiltonian Path- edbac.

Note

• Obwód Eulera zawiera każdą krawędź wykresu dokładnie raz.

• W cyklu hamiltonowskim niektóre krawędzie wykresu można pominąć.

Example

Spójrz na poniższy wykres -

Dla wykresu pokazanego powyżej -

• Ścieżka Eulera istnieje - fałszywa

• Obwód Eulera istnieje - fałsz

• Istnieje cykl Hamiltona - prawda

• Ścieżka Hamiltona istnieje - prawda

G ma cztery wierzchołki o nieparzystym stopniu, dlatego nie można go przejść. Pomijając krawędzie wewnętrzne, wykres ma cykl Hamiltona przechodzący przez wszystkie wierzchołki.