Teoria grafów — wierzchołki, krawędzie i podstawowe pojęcia

Teoria grafów to dział matematyki badający grafy, czyli struktury złożone z wierzchołków i krawędzi. Wierzchołek oznacza obiekt, a krawędź pokazuje relację między dwoma obiektami.

Jeśli szukasz podstaw teorii grafów, zacznij od tej idei: graf to prosty sposób modelowania połączeń. Osoby w sieci społecznościowej, miasta połączone drogami i strony internetowe linkujące do siebie można przedstawić za pomocą grafów.

Co oznacza graf w matematyce

W grafie nieskierowanym krawędź mówi, że dwa wierzchołki są połączone, a samo połączenie nie ma kierunku. Jeśli $A$ jest połączone z $B$, to $B$ jest też połączone z $A$.

W grafie skierowanym krawędzie mają kierunek, więc $A \to B$ i $B \to A$ to różne stwierdzenia. W wielu przykładach dla początkujących używa się prostych grafów nieskierowanych, co oznacza brak pętli i brak powtarzających się krawędzi między tą samą parą wierzchołków.

Ten warunek ma znaczenie, ponieważ definicje najczęściej wprowadza się najpierw dla prostych grafów nieskierowanych. Gdy zmienia się typ grafu, znaczenie terminów też może się zmienić.

Podstawowe pojęcia teorii grafów, które warto znać najpierw

Wierzchołki i krawędzie

Wierzchołek to obiekt, który chcesz śledzić. Krawędź to połączenie, które chcesz śledzić.

Jeśli graf przedstawia miasta i drogi, to miasta są wierzchołkami, a drogi są krawędziami.

Stopień

W grafie nieskierowanym stopień wierzchołka to liczba krawędzi, które do niego przylegają.

Jeśli jedno miasto ma drogi do trzech innych miast, jego stopień wynosi $3$.

Ścieżka

Ścieżka to ciąg wierzchołków, w którym każda kolejna para jest połączona krawędzią.

Jeśli istnieje ścieżka z jednego wierzchołka do drugiego, można przejść od jednego do drugiego, poruszając się po krawędziach.

Cykl

Cykl to ścieżka, która zaczyna się i kończy w tym samym wierzchołku. W standardowej podstawowej definicji żaden inny wierzchołek się nie powtarza.

Cykl pokazuje, że w grafie istnieje zamknięta pętla.

Graf spójny i składowe spójności

Graf nieskierowany jest spójny, jeśli z każdego wierzchołka można dojść do każdego innego pewną ścieżką.

Jeśli tak nie jest, graf dzieli się na składowe spójności. Każda składowa jest spójną częścią grafu.

Przykład: jeden mały graf

Załóżmy, że graf ma wierzchołki $A$, $B$, $C$, $D$ i $E$ oraz krawędzie

$$AB,\ AC,\ BC,\ CD$$

Daje to trójkąt na wierzchołkach $A$, $B$ i $C$, jedną dodatkową krawędź z $C$ do $D$ oraz izolowany wierzchołek $E$.

Teraz łatwo zobaczyć główne pojęcia.

Stopnie wynoszą

$$\deg(A)=2,\ \deg(B)=2,\ \deg(C)=3,\ \deg(D)=1,\ \deg(E)=0$$

Istnieje ścieżka z $A$ do $D$:

$$A-C-D$$

Istnieje cykl:

$$A-B-C-A$$

Graf nie jest spójny, ponieważ do $E$ nie da się dojść z pozostałych wierzchołków. Zatem graf ma dwie składowe spójności: jedną zawierającą $A,B,C,D$ oraz drugą zawierającą tylko $E$.

Ten jeden przykład pokazuje, jak stopień, ścieżka, cykl, wierzchołki izolowane i składowe spójności łączą się w całość.

Szybkie sprawdzenie: suma stopni

Dla każdego skończonego grafu nieskierowanego zachodzi

$$\sum \deg(v) = 2|E|$$

Dzieje się tak, ponieważ każda krawędź ma dokładnie dwa końce, więc każda dodaje $1$ do dwóch stopni.

W powyższym przykładzie suma stopni wynosi

$$2+2+3+1+0=8$$

a liczba krawędzi to $4$, więc

$$2|E| = 2 \cdot 4 = 8$$

To przydatna kontrola, gdy liczysz stopnie ręcznie. Jeśli liczby się nie zgadzają, gdzieś jest błąd.

Częste błędy w teorii grafów

Mylenie wierzchołków i krawędzi

Wierzchołki to obiekty. Krawędzie to relacje między nimi.

Zapominanie, jaki masz typ grafu

Stwierdzenie prawdziwe dla prostego grafu nieskierowanego może wymagać zmiany dla grafu skierowanego albo dla grafu dopuszczającego pętle.

Traktowanie ścieżki jak cyklu

Ścieżka nie musi wracać do punktu startowego. Cykl musi.

Pomijanie wierzchołków izolowanych

Wierzchołek o stopniu $0$ nadal należy do grafu. Może wpływać na to, czy graf jest spójny.

Gdzie wykorzystuje się podstawy teorii grafów

Te pojęcia pojawiają się w sieciach komputerowych, planowaniu tras, harmonogramowaniu, systemach rekomendacji i sieciach społecznościowych. Kontekst się zmienia, ale wciąż wracają te same pytania: co jest połączone, dokąd można dojść i gdzie występują pętle?

Dlatego teoria grafów pojawia się wcześnie zarówno w matematyce dyskretnej, jak i informatyce.

Spróbuj z podobnym grafem

Narysuj cztery wierzchołki $P$, $Q$, $R$ i $S$. Dodaj krawędzie $PQ$, $QR$, $RS$ i $SP$.

Następnie odpowiedz na trzy pytania: jaki jest stopień każdego wierzchołka, czy graf jest spójny i czy graf zawiera cykl?