Teoria wykresów: podstawowe definicje

Teoria grafów jest gałęzią matematyki stosowaną w informatyce i programowaniu, ekonomii, logistyce i chemii.

Co to jest wykres

Często systemy graficzne służą do opisu struktury systemów. Elementy w nich reprezentowane są przez kółka, kropki, kwadraty itp., A połączenia między elementami są liniami lub strzałkami. Jednocześnie nie ma znaczenia, w jaki sposób przedstawione są elementy, ani długość i kształt linii - tylko jakie elementy są połączone. Zatem wykres jest parą postaci (A, M), gdzie A jest skończonym zbiorem wierzchołków, a M jest zbiorem krawędzi - liniami łączącymi niektóre wierzchołki.

Podstawowe pojęcia teorii grafów

W przypadku skierowanego wykresu lub dwukierunku (patrz rysunek poniżej) krawędzie są zorientowane, zwane łukami i są reprezentowane przez strzałki. Łuk może być wyznaczony przez uporządkowaną parę wierzchołków, które łączy - początkowy i końcowy.

W przypadku wykresu bezkierunkowego (patrz poniższy rysunek) krawędzie są reprezentowane przez linie bez orientacji. W związku z tym para wierzchołków, które łączy krawędź, jest nieuporządkowana. Oba te wierzchołki są końcami krawędzi.

Jeśli wierzchołki a i b są końcami krawędzi (lub początkiem i końcem łuku) wykresu, to mówimy, że wierzchołki a i b padają na tę krawędź (łuk), a także krawędź (łuk) pada na wierzchołki aib. Jeśli wierzchołki a i b są końcami krawędzi, to (a i b) są nazywane sąsiadującymi.

Najczęściej uważają, że wykresy, których krawędzie są tego samego typu - są zorientowane lub nie.

Jeśli krawędzie mają ten sam początek i koniec, to nazywane są wieloma krawędziami, a wykres, w którym są obecne, nazywany jest multigraph.

Teoria grafów wykorzystuje także pojęcie "pętli" - krawędź, która biegnie i ustawia się w tym samym wierzchołku. Wykres, w którym występują pętle, nazywa się pseudografem.

Najczęstsze nieorientowane wykresy, które nie mają wielu krawędzi ani pętli. Takie wykresy nazywane są zwykłymi. Nie mają wielu krawędzi, więc można zidentyfikować krawędź i odpowiadającą parę wierzchołków.

Każdy wierzchołek dwuznaku charakteryzuje się:

• Niedorozwój. Jest to liczba łuków z niego wychodzących.
• Niedorozwój. Jest to liczba łuków, które przechodzą do danego wierzchołka.

Suma pół-stopni wejścia dwuznaku, a także suma pół-stopni wyniku, jest równa całkowitej liczbie łuków wykresu.

Na nieukierunkowanym wykresie każdy wierzchołek charakteryzuje się stopniem jego wierzchołka. Jest to liczba krawędzi, które padają na szczyt. Całkowita suma stopni wierzchołków wykresu to liczba krawędzi pomnożona przez dwa: każda krawędź daje wkład równy dwóm.

Werteks o stopniu 0 nazywany jest izolowanym.

Zawieszony szczyt to wierzchołek o stopniu 1.

Teoria grafu wywołuje pusty wykres, w którym nie ma jednej krawędzi. Kompletny wykres to zwykły wykres, w którym sąsiadują dowolne 2 wierzchołki.

Wykresy ważone to wykresy, do których natychmiast przypisane są wierzchołki lub krawędzie (łuki) lub oba wierzchołki i krawędzie (łuki), niektóre liczby są przypisane. Nazywa się je wagą. Druga ilustracja pokazuje niekierowany wykres, którego krawędzie są ważone.

Liczy: izomorfizm

Pojęcie izomorfizmu jest używane w matematyce. W szczególności teoria grafów definiuje je następująco: dwa wykresy U i V są izomorficzne, jeśli na tych wykresach występuje biempionacja między zestawami ich wierzchołków: co 2 wierzchołki na wykresie U są połączone krawędzią wtedy i tylko wtedy, gdy są takie same na wykresie V wierzchołki (które można nazwać inaczej). Poniższy rysunek pokazuje dwa wykresy izomorficzne, w których pomiędzy wierzchołkami pomalowanymi w tych samych kolorach na pierwszym i drugim wykresie znajduje się wyżej opisany biempion.

Ścieżki i cykle

Ścieżka w nieukierunkowanym lub zorientowanym grafie to ciąg brzegów, z których każdy rozpoczyna się od wierzchołka, w którym kończy się poprzedni. Prosta ścieżka to taka, w której wszystkie wierzchołki, z wyjątkiem, być może, początkowego i końcowego, i krawędzi są różne. Cykl w dwu znaku jest ścieżką, której początkowe i końcowe wierzchołki są zgodne i która obejmuje co najmniej jedną krawędź. Cykl na nieukierunkowanym wykresie to ścieżka zawierająca co najmniej trzy różne krawędzie. Na drugiej figurze cykl jest na przykład ścieżką (3, 1), (6, 3), (1, 6).

Teoria grafów w programowaniu służy do konstruowania wykresów algorytmów.