Teoria grafów - podstawowe właściwości
Grafy mają różne właściwości, które służą do charakteryzowania grafów w zależności od ich struktury. Właściwości te są określone w specyficznych terminach związanych z dziedziną teorii grafów. W tym rozdziale omówimy kilka podstawowych właściwości, które są wspólne dla wszystkich wykresów.
Odległość między dwoma wierzchołkami
Jest to liczba krawędzi w najkrótszej ścieżce między wierzchołkiem U i wierzchołkiem V. Jeśli istnieje wiele ścieżek łączących dwa wierzchołki, najkrótsza ścieżka jest traktowana jako odległość między dwoma wierzchołkami.
Notacja - d (U, V)
Może istnieć dowolna liczba ścieżek od jednego wierzchołka do drugiego. Spośród nich musisz wybrać tylko najkrótszą.
Example
Spójrz na poniższy wykres -
Tutaj odległość od wierzchołka „d” do wierzchołka „e” lub po prostu „de” wynosi 1, ponieważ jest między nimi jedna krawędź. Istnieje wiele ścieżek od wierzchołka „d” do wierzchołka „e” -
- da, ab, be
- df, fg, ge
- de (Uwzględnia się odległość między wierzchołkami)
- df, fc, ca, ab, be
- da, ac, cf, fg, ge
Ekscentryczność wierzchołka
Maksymalna odległość między wierzchołkiem a wszystkimi innymi wierzchołkami jest uważana za mimośrodowość wierzchołka.
Notacja - e (V)
Przyjmowana jest odległość od określonego wierzchołka do wszystkich innych wierzchołków na wykresie, a spośród tych odległości mimośrodowość jest największą z odległości.
Example
Na powyższym wykresie mimośrodowość „a” wynosi 3.
Odległość od „a” do „b” wynosi 1 („ab”),
od „a” do „c” to 1 („ac”),
od „a” do „d” wynosi 1 („ad”),
od „a” do „e” to 2 („ab” - „be”) lub („ad” - „de”),
od „a” do „f” to 2 („ac” - „cf”) lub („ad” - „df”),
od „a” do „g” wynosi 3 („ac” - „cf” - „fg”) lub („ad” - „df” - „fg”).
Zatem mimośrodowość wynosi 3, co stanowi maksimum względem wierzchołka „a” z odległości między „ag”, która jest maksimum.
Innymi słowy,
e (b) = 3
e (c) = 3
e (d) = 2
e (e) = 3
e (f) = 3
e (g) = 3
Promień połączonego wykresu
Minimalna mimośrodowość ze wszystkich wierzchołków jest uważana za promień wykresu G.Minimalna spośród wszystkich maksymalnych odległości między wierzchołkiem a wszystkimi innymi wierzchołkami jest uważana za promień wykresu G.
Notacja - r (G)
Ze wszystkich mimośrodów wierzchołków grafu, promień połączonego grafu jest minimum wszystkich tych mimośrodów.
Example
Na powyższym wykresie r (G) = 2, co jest minimalnym mimośrodem dla „d”.
Średnica wykresu
Maksymalny mimośrodowość ze wszystkich wierzchołków jest uważany za średnicę wykresu G.Maksymalne spośród wszystkich odległości między wierzchołkiem a wszystkimi innymi wierzchołkami jest uważane za średnicę wykresu G.
Notation − d(G) - Ze wszystkich mimośrodów wierzchołków wykresu, średnica połączonego grafu jest maksimum wszystkich tych mimośrodów.
Example
Na powyższym wykresie d (G) = 3; czyli maksymalna ekscentryczność.
Punkt centralny
Jeśli mimośrodowość wykresu jest równa jego promieniu, wówczas określa się go jako centralny punkt wykresu. Gdyby
e (V) = r (V),
wtedy „V” jest centralnym punktem wykresu „G”.
Example
Na przykładowym wykresie „d” jest centralnym punktem wykresu.
e (d) = r (d) = 2
Środek
Zbiór wszystkich centralnych punktów „G” nazywany jest środkiem wykresu.
Example
Na przykładowym wykresie {'d'} jest środkiem wykresu.
Obwód
Plik number of edges in the longest cycle of ‘G’ nazywany jest obwodem „G”.
Example
Na przykładowym wykresie obwód wynosi 6, który wyprowadziliśmy z najdłuższego cyklu acfgeba lub acfdeba.
Obwód
Liczba krawędzi w najkrótszym cyklu „G” nazywana jest jego Obwodem.
Notation: g (G).
Example - Na przykładowym wykresie obwód wykresu wynosi 4, który wyprowadziliśmy z najkrótszego cyklu acfda lub dfged lub abeda.
Twierdzenie o sumie stopni wierzchołków
Jeśli G = (V, E) jest grafem niekierowanym z wierzchołkami V = {V 1 , V 2 ,… V n } to
Corollary 1
Jeśli G = (V, E) jest grafem skierowanym z wierzchołkami V = {V 1 , V 2 ,… V n }, to
Corollary 2
Na każdym grafie niekierowanym liczba wierzchołków z nieparzystym stopniem jest parzysta.
Corollary 3
W grafie niekierowanym, jeśli stopień każdego wierzchołka wynosi k, to
Corollary 4
W grafie niekierowanym, jeśli stopień każdego wierzchołka wynosi co najmniej k, to
| Corollary 5
W grafie niekierowanym, jeśli stopień każdego wierzchołka wynosi co najwyżej k, to