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

n Σ i = 1 stopień (V i ) = 2 | E |

Corollary 1

Jeśli G = (V, E) jest grafem skierowanym z wierzchołkami V = {V 1 , V 2 ,… V n }, to

n Σ i = 1 stopień + (V i ) = | E | = n Σ i = 1 deg− (V i )

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

k | V | = 2 | E |

Corollary 4

W grafie niekierowanym, jeśli stopień każdego wierzchołka wynosi co najmniej k, to

k | V | ≤ 2 | E |

| Corollary 5

W grafie niekierowanym, jeśli stopień każdego wierzchołka wynosi co najwyżej k, to

k | V | ≥ 2 | E |