Teoria grafów - podstawy

Wykres to diagram punktów i linii połączonych z punktami. Ma co najmniej jedną linię łączącą zestaw dwóch wierzchołków bez żadnego łączącego się wierzchołka. Pojęcie grafów w teorii grafów opiera się na kilku podstawowych terminach, takich jak punkt, linia, wierzchołek, krawędź, stopień wierzchołków, właściwości grafów, itp. W tym rozdziale omówimy te podstawy teorii grafów.

Punkt

A pointjest określoną pozycją w jednowymiarowej, dwuwymiarowej lub trójwymiarowej przestrzeni. Dla lepszego zrozumienia punkt można oznaczyć alfabetem. Można to przedstawić za pomocą kropki.

Przykład

Tutaj kropka to punkt o nazwie „a”.

Linia

ZA Lineto połączenie między dwoma punktami. Można to przedstawić za pomocą linii ciągłej.

Example

Tutaj „a” i „b” to punkty. Połączenie między tymi dwoma punktami nazywa się linią.

Wierzchołek

Wierzchołek to punkt, w którym spotyka się wiele linii. Nazywa się to również anode. Podobnie jak punkty, wierzchołek jest również oznaczany alfabetem.

Example

Tutaj wierzchołek jest nazywany alfabetem „a”.

Brzeg

Krawędź to matematyczny termin oznaczający linię, która łączy dwa wierzchołki. Z jednego wierzchołka można utworzyć wiele krawędzi. Bez wierzchołka nie można utworzyć krawędzi. Dla krawędzi musi istnieć wierzchołek początkowy i końcowy.

Example

Tutaj „a” i „b” to dwa wierzchołki, a połączenie między nimi nazywa się krawędzią.

Wykres

Graf „G” definiuje się jako G = (V, E), gdzie V jest zbiorem wszystkich wierzchołków, a E jest zbiorem wszystkich krawędzi wykresu.

Example 1

W powyższym przykładzie ab, ac, cd i bd to krawędzie wykresu. Podobnie a, b, c i d są wierzchołkami wykresu.

Example 2

Na tym wykresie są cztery wierzchołki a, b, c i d oraz cztery krawędzie ab, ac, ad i cd.

Pętla

Na wykresie, jeśli krawędź jest rysowana od wierzchołka do siebie, nazywa się to pętlą.

Example 1

Na powyższym wykresie V jest wierzchołkiem, którego krawędź (V, V) tworzy pętlę.

Example 2

Na tym wykresie są dwie pętle utworzone w wierzchołku a i wierzchołku b.

Stopień wierzchołka

Jest to liczba wierzchołków sąsiadujących z wierzchołkiem V.

Notation - deg (V).

Na prostym grafie z liczbą n wierzchołków stopień dowolnych wierzchołków wynosi -

deg (v) ≤ n - 1 ∀ v ∈ G

Wierzchołek może tworzyć krawędź ze wszystkimi innymi wierzchołkami z wyjątkiem samego siebie. Więc stopień wierzchołka będzie donumber of vertices in the graph minus 1. To 1 jest dla samo-wierzchołka, ponieważ nie może samodzielnie utworzyć pętli. Jeśli na którymkolwiek z wierzchołków znajduje się pętla, nie jest to prosty wykres.

Stopień wierzchołka można rozpatrywać w dwóch przypadkach grafów -

• Niekierowany wykres

• Kierowany wykres

Stopień wierzchołka na wykresie nieukierunkowanym

Graf nie skierowany nie ma skierowanych krawędzi. Rozważ następujące przykłady.

Example 1

Spójrz na poniższy wykres -

Na powyższym wykresie nieukierunkowanym

• deg (a) = 2, ponieważ w wierzchołku „a” spotykają się 2 krawędzie.

• deg (b) = 3, ponieważ w wierzchołku „b” spotykają się 3 krawędzie.

• deg (c) = 1, ponieważ w wierzchołku „c” jest 1 krawędź

• Więc „c” to a pendent vertex.

• deg (d) = 2, ponieważ w wierzchołku „d” spotykają się 2 krawędzie.

• deg (e) = 0, ponieważ jest 0 krawędzi utworzonych w wierzchołku „e”.

• Więc „e” to isolated vertex.

Example 2

Spójrz na poniższy wykres -

Na powyższym wykresie

deg (a) = 2, deg (b) = 2, deg (c) = 2, deg (d) = 2 i deg (e) = 0.

Wierzchołek „e” jest izolowanym wierzchołkiem. Wykres nie ma żadnego wiszącego wierzchołka.

Stopień wierzchołka na wykresie skierowanym

Na wykresie skierowanym każdy wierzchołek ma rozszerzenie indegree i outdegree.

Niezależność wykresu

• Nieokreślony wierzchołek V to liczba krawędzi, które wchodzą do wierzchołka V.

• Notation - deg− (V).

Stopień zaawansowania wykresu

• Poza wierzchołkiem V to liczba krawędzi wychodzących z wierzchołka V.

• Notation - st + (V).

Rozważ następujące przykłady.

Example 1

Spójrz na poniższy skierowany wykres. Wierzchołek „a” ma dwie krawędzie, „ad” i „ab”, które wychodzą na zewnątrz. W związku z tym jego stopniem zewnętrznym jest 2. Podobnie, istnieje krawędź „ga”, zbliżająca się do wierzchołka „a”. Stąd liczba nieokreślona „a” wynosi 1.

W poniższej tabeli przedstawiono stopnie i stopnie innych wierzchołków -

Wierzchołek	Indegree	Outdegree
za	1	2
b	2	0
do	2	1
re	1	1
mi	1	1
fa	1	1
sol	0	2

Example 2

Spójrz na poniższy skierowany wykres. Wierzchołek „a” ma krawędź „ae” wychodzącą na zewnątrz z wierzchołka „a”. Stąd jego stopień wyprzedza wynosi 1. Podobnie, wykres ma krawędź „ba” zbliżającą się do wierzchołka „a”. Stąd liczba nieokreślona „a” wynosi 1.

W poniższej tabeli przedstawiono stopnie i stopnie innych wierzchołków -

Wierzchołek	Indegree	Outdegree
za	1	1
b	0	2
do	2	0
re	1	1
mi	1	1

Wiszący wierzchołek

Używając stopnia wierzchołka, mamy dwa specjalne typy wierzchołków. Wierzchołek o stopniu pierwszym nazywa się wiszącym wierzchołkiem.

Example

Tutaj, w tym przykładzie, wierzchołek „a” i wierzchołek „b” mają połączoną krawędź „ab”. Tak więc w odniesieniu do wierzchołka „a” jest tylko jedna krawędź w kierunku wierzchołka „b” i podobnie w przypadku wierzchołka „b” jest tylko jedna krawędź w kierunku wierzchołka „a”. Wreszcie, wierzchołek „a” i wierzchołek „b” mają stopień, który jest również nazywany wierzchołkiem wiszącym.

Izolowany wierzchołek

Wierzchołek o stopniu zerowym nazywany jest wierzchołkiem izolowanym.

Example

Tutaj wierzchołek „a” i wierzchołek „b” nie mają żadnej łączności między sobą, a także z innymi wierzchołkami. Zatem stopień obu wierzchołków „a” i „b” wynosi zero. Są one również nazywane izolowanymi wierzchołkami.

Przyleganie

Oto normy sąsiedztwa -

• Na wykresie mówi się, że dwa wierzchołki są adjacent, jeśli między dwoma wierzchołkami jest krawędź. Tutaj przyleganie wierzchołków jest utrzymywane przez pojedynczą krawędź, która łączy te dwa wierzchołki.

• Na wykresie mówi się, że dwie krawędzie sąsiadują ze sobą, jeśli między nimi znajduje się wspólny wierzchołek. Tutaj przyleganie krawędzi jest utrzymywane przez pojedynczy wierzchołek, który łączy dwie krawędzie.

Example 1

Na powyższym wykresie -

• „a” i „b” to sąsiednie wierzchołki, ponieważ między nimi istnieje wspólna krawędź „ab”.

• „a” i „d” to sąsiednie wierzchołki, ponieważ między nimi istnieje wspólna krawędź „ad”.

• ab ”i„ be ”to sąsiednie krawędzie, ponieważ między nimi znajduje się wspólny wierzchołek„ b ”.

• be ”i„ de ”to sąsiednie krawędzie, ponieważ między nimi znajduje się wspólny wierzchołek„ e ”.

Example 2

Na powyższym wykresie -

• „a” i „d” to sąsiednie wierzchołki, ponieważ między nimi istnieje wspólna krawędź „ad”.

• „c” i „b” to sąsiednie wierzchołki, ponieważ między nimi istnieje wspólna krawędź „cb”.

• „ad” i „cd” to sąsiednie krawędzie, ponieważ między nimi znajduje się wspólny wierzchołek „d”.

• „ac” i „cd” to sąsiednie krawędzie, ponieważ między nimi znajduje się wspólny wierzchołek „c”.

Równoległe krawędzie

Na wykresie, jeśli para wierzchołków jest połączona więcej niż jedną krawędzią, wtedy te krawędzie nazywane są krawędziami równoległymi.

Na powyższym wykresie „a” i „b” to dwa wierzchołki połączone między nimi dwoma krawędziami „ab” i „ab”. Nazywa się to więc równoległą krawędzią.

Multi Graph

Wykres mający równoległe krawędzie jest znany jako Multigraph.

Example 1

Na powyższym wykresie jest pięć krawędzi „ab”, „ac”, „cd”, „cd” i „bd”. Ponieważ „c” i „d” mają między sobą dwie równoległe krawędzie, jest to Multigraph.

Example 2

Na powyższym wykresie wierzchołki „b” i „c” mają dwie krawędzie. Wierzchołki „e” i „d” również mają między sobą dwie krawędzie. Dlatego jest to Multigraph.

Sekwencja stopni na wykresie

Jeśli stopnie wszystkich wierzchołków na wykresie są ułożone w porządku malejącym lub rosnącym, to uzyskana sekwencja nazywana jest sekwencją stopni na wykresie.

Example 1

Wierzchołek	ZA	b	do	re	mi
Łączenie z	pne	ogłoszenie	ogłoszenie	c, b, e	re
Stopień	2	2	2	3	1

Na powyższym wykresie, dla wierzchołków {d, a, b, c, e}, sekwencja stopni wynosi {3, 2, 2, 2, 1}.

Example 2

Wierzchołek	ZA	b	do	re	mi	fa
Łączenie z	być	a, c	b, d	c, e	ogłoszenie	-
Stopień	2	2	2	2	2	0

Na powyższym wykresie, dla wierzchołków {a, b, c, d, e, f}, sekwencja stopni wynosi {2, 2, 2, 2, 2, 0}.