Wykresy i modele wykresów
W poprzedniej części przedstawiono różne narzędzia do rozumowania, sprawdzania i rozwiązywania problemów. W tej części przyjrzymy się dyskretnym strukturom, które stanowią podstawę formułowania wielu problemów z życia wziętych.
Dwie dyskretne struktury, które omówimy, to wykresy i drzewa. Graf to zbiór punktów zwanych węzłami lub wierzchołkami, które są połączone zestawem linii zwanych krawędziami. Badanie wykresów lubgraph theory jest ważną częścią wielu dyscyplin z zakresu matematyki, inżynierii i informatyki.
Co to jest wykres?
Definition - Graf (oznaczony jako $ G = (V, E) $) składa się z niepustego zbioru wierzchołków lub węzłów V i zbioru krawędzi E.
Example - Rozważmy, że wykres to $ G = (V, E) $, gdzie $ V = \ lbrace a, b, c, d \ rbrace $ i $ E = \ lbrace \ lbrace a, b \ rbrace, \ lbrace a , c \ rbrace, \ lbrace b, c \ rbrace, \ lbrace c, d \ rbrace \ rbrace $
Degree of a Vertex - Stopień wierzchołka V grafu G (oznaczony przez deg (V)) to liczba krawędzi przypadających na wierzchołek V.
| Wierzchołek | Stopień | Nawet dziwne |
|---|---|---|
| za | 2 | parzysty |
| b | 2 | parzysty |
| do | 3 | dziwny |
| re | 1 | dziwny |
Even and Odd Vertex - Jeśli stopień wierzchołka jest parzysty, nazywa się go parzystym, a jeśli stopień wierzchołka jest nieparzysty, nazywany jest nieparzystym.
Degree of a Graph- Stopień wykresu to największy stopień wierzchołka tego wykresu. Dla powyższego wykresu stopień wykresu wynosi 3.
The Handshaking Lemma - Na wykresie suma wszystkich stopni wszystkich wierzchołków jest równa dwukrotnej liczbie krawędzi.
Rodzaje wykresów
Istnieją różne rodzaje wykresów, o których dowiemy się w następnej sekcji.
Wykres zerowy
Wykres zerowy nie ma krawędzi. Wykres zerowy $ n $ wierzchołków jest oznaczony przez $ N_n $
Prosty wykres
Graf nazywa się grafem prostym / wykresem ścisłym, jeśli jest on niekierowany i nie zawiera żadnych pętli ani wielu krawędzi.
Multi-Graph
Jeśli na wykresie dozwolonych jest wiele krawędzi między tym samym zestawem wierzchołków, nazywa się to Multigraph. Innymi słowy, jest to wykres mający co najmniej jedną pętlę lub wiele krawędzi.
Wykres skierowany i nie skierowany
Graf $ G = (V, E) $ nazywany jest grafem skierowanym, jeśli zbiór krawędzi składa się z uporządkowanej pary wierzchołków, a graf nazywany jest niekierowanym, jeśli zestaw krawędzi składa się z nieuporządkowanej pary wierzchołków.
Wykres połączonych i rozłączonych
Graf jest połączony, jeśli dowolne dwa wierzchołki grafu są połączone ścieżką; gdy wykres jest odłączony, jeśli co najmniej dwa wierzchołki wykresu nie są połączone ścieżką. Jeśli wykres G jest odłączony, to każdy maksymalny połączony podgraf $ G $ nazywany jest połączonym składnikiem wykresu $ G $.
Regularny wykres
Wykres jest regularny, jeśli wszystkie jego wierzchołki mają ten sam stopień. Na wykresie regularnym G o stopniu $ r $ stopień każdego wierzchołka $ G $ wynosi r.
Kompletny wykres
Graf nazywa się grafem całkowitym, jeśli każda para dwóch wierzchołków jest połączona dokładnie jedną krawędzią. Cały graf z n wierzchołkami jest oznaczony przez $ K_n $
Wykres cyklu
Jeśli wykres składa się z pojedynczego cyklu, nazywa się go wykresem cyklu. Wykres cyklu z n wierzchołkami jest oznaczony przez $ C_n $
Wykres dwudzielny
Jeśli zbiór wierzchołków grafu G można podzielić na dwa rozłączne zbiory, $ V_1 $ i $ V_2 $, w taki sposób, że każda krawędź wykresu łączy wierzchołek w $ V_1 $ z wierzchołkiem w $ V_2 $, i nie ma krawędzi w G, które łączą dwa wierzchołki w $ V_1 $ lub dwa wierzchołki w $ V_2 $, wtedy graf $ G $ nazywany jest grafem dwudzielnym.
Kompletny wykres dwudzielny
Kompletny graf dwudzielny jest grafem dwudzielnym, w którym każdy wierzchołek w pierwszym zestawie jest połączony z każdym pojedynczym wierzchołkiem w drugim zestawie. Pełny wykres dwudzielny jest oznaczony jako $ K_ {x, y} $, gdzie wykres $ G $ zawiera $ x $ wierzchołków w pierwszym zbiorze i $ y $ wierzchołków w drugim zbiorze.
Reprezentacja wykresów
Wykres można przedstawić głównie na dwa sposoby -
- Macierz sąsiedztwa
- Lista sąsiedztwa
Macierz sąsiedztwa
Macierz sąsiedztwa $ A [V] [V] $ to dwuwymiarowa tablica o rozmiarze $ V \ razy V $, gdzie $ V $ to liczba wierzchołków w grafie niekierowanym. Jeśli istnieje krawędź między $ V_x $ a $ V_y $, wówczas wartość $ A [V_x] [V_y] = 1 $ i $ A [V_y] [V_x] = 1 $, w przeciwnym razie wartość będzie wynosić zero. A dla wykresu skierowanego, jeśli istnieje krawędź między $ V_x $ a $ V_y $, to wartość $ A [V_x] [V_y] = 1 $, w przeciwnym razie wartość będzie wynosić zero.
Adjacency Matrix of an Undirected Graph
Rozważmy następujący nieukierunkowany wykres i skonstruujmy macierz sąsiedztwa -
Macierz sąsiedztwa powyższego niekierowanego wykresu będzie wynosić -
a |
b |
c |
d |
|
a |
0 |
1 |
1 |
0 |
b |
1 |
0 |
1 |
0 |
c |
1 |
1 |
0 |
1 |
d |
0 |
0 |
1 |
0 |
Adjacency Matrix of a Directed Graph
Rozważmy następujący wykres skierowany i skonstruujmy jego macierz sąsiedztwa -
Macierz sąsiedztwa powyższego skierowanego wykresu będzie wynosić -
a |
b |
c |
d |
|
a |
0 |
1 |
1 |
0 |
b |
0 |
0 |
1 |
0 |
c |
0 |
0 |
0 |
1 |
d |
0 |
0 |
0 |
0 |
Lista sąsiedztwa
Na liście przylegania tablica $ (A [V]) $ połączonych list jest używana do reprezentowania grafu G z liczbą wierzchołków $ V $. Wpis $ A [V_x] $ reprezentuje połączoną listę wierzchołków sąsiadujących z $ Vx-tym $ wierzchołkiem. Lista sąsiedztwa nieukierunkowanego wykresu jest pokazana na poniższym rysunku -
Wykres planarny a niepłaski
Planar graph- Graf $ G $ nazywany jest grafem planarnym, jeśli można go narysować na płaszczyźnie bez skrzyżowanych krawędzi. Jeśli rysujemy wykres w płaszczyźnie bez przecinania krawędzi, nazywa się to osadzeniem wykresu w płaszczyźnie.
Non-planar graph - Wykres jest niepłaski, jeśli nie można go narysować na płaszczyźnie bez przecinania się krawędzi wykresu.
Izomorfizm
Jeśli dwa grafy G i H zawierają taką samą liczbę wierzchołków połączonych w ten sam sposób, nazywane są grafami izomorficznymi (oznaczane przez $ G \ cong H $).
Łatwiej jest sprawdzić brak izomorfizmu niż izomorfizm. Jeśli wystąpi którykolwiek z poniższych warunków, dwa wykresy są nieizomorficzne -
- Liczba połączonych komponentów jest różna
- Mocy ustawione w wierzchołkach są różne
- Kardynalności ustawione na krawędziach są różne
- Sekwencje stopni są różne
Przykład
Poniższe wykresy są izomorficzne -
Homomorfizm
Homomorfizm z wykresu $ G $ do wykresu $ H $ jest odwzorowaniem (może nie być odwzorowaniem bijektywnym) $ h: G \ rightarrow H $ takim, że - $ (x, y) \ in E (G) \ rightarrow (h (x), h (y)) \ w E (H) $. Odwzorowuje sąsiednie wierzchołki wykresu $ G $ na sąsiednie wierzchołki wykresu $ H $.
Właściwości homomorfizmów
Homomorfizm jest izomorfizmem, jeśli jest odwzorowaniem bijektywnym.
Homomorfizm zawsze zachowuje krawędzie i spójność wykresu.
Kompozycje homomorfizmów są również homomorfizmami.
Dowiedzenie się, czy istnieje jakiś homomorficzny wykres innego wykresu jest NPkompletnym problemem.
Wykresy Eulera
Połączony wykres $ G $ nazywany jest wykresem Eulera, jeśli istnieje zamknięty ślad, który obejmuje każdą krawędź wykresu $ G $. Ścieżka Eulera to ścieżka, która używa każdej krawędzi wykresu dokładnie raz. Ścieżka Eulera zaczyna się i kończy na różnych wierzchołkach.
Obwód Eulera to obwód, który wykorzystuje każdą krawędź wykresu dokładnie raz. Obwód Eulera zawsze zaczyna się i kończy w tym samym wierzchołku. Graf połączony $ G $ jest grafem Eulera wtedy i tylko wtedy, gdy wszystkie wierzchołki $ G $ mają równe stopnie, a połączony graf $ G $ jest grafem Eulera wtedy i tylko wtedy, gdy jego zestaw krawędzi można rozłożyć na cykle.
Powyższy wykres to wykres Eulera jako $ “a \: 1 \: b \: 2 \: c \: 3 \: d \: 4 \: e \: 5 \: c \: 6 \: f \: 7 \: g ”$ obejmuje wszystkie krawędzie wykresu.
Wykresy Hamiltona
Graf połączony $ G $ nazywany jest grafem Hamiltona, jeśli istnieje cykl, który zawiera każdy wierzchołek $ G $, a cykl nazywa się cyklem Hamiltona. Spacer Hamiltona na wykresie $ G $ to spacer, który przechodzi przez każdy wierzchołek dokładnie raz.
Jeśli $ G $ jest prostym grafem z n wierzchołkami, gdzie $ n \ geq 3 $ Jeśli $ deg (v) \ geq \ frac {n} {2} $ dla każdego wierzchołka $ v $, to wykres $ G $ jest Wykres Hamiltona. To się nazywaDirac's Theorem.
Jeśli $ G $ jest prostym grafem z $ n $ wierzchołkami, gdzie $ n \ geq 2 $ jeśli $ deg (x) + deg (y) \ geq n $ dla każdej pary niesąsiadujących wierzchołków x i y, to wykres $ G $ jest wykresem Hamiltona. To się nazywaOre's theorem.
