Podstawowe definicje

Czym jest graf?

Często zdarza się, że chcemy wykonać schemat relacji pewnych elementów, czy też przedstawić graficznie daną sytuację. Zazwyczaj stosujemy prowizoryczne linie, które łączą punkty przedstawine jako wybrane figury geometryczne. Taki schemat znacznie ułatwia nam pracę i pozwala osiągnąć lepsze rezultaty zamierzonego celu. Poznajmy więc nową konstrukcję matematyczną innego rodzaju, cieszącą się ogromnym zainteresowaniem w wielu dziedzinach nauki.

Całą widoczną strukturę będziemy nazywać grafem, w którym wierzchołki są oznaczone literami $z$, $x$, $y$, $w$, $u$, $v$, $t$. Krawędzie natomiast, będą oznaczane symbolem typu $vz$, co rozumiane jest jako krawędź łączącą wierzołek $v$ z wierzchołkiem $z$.

Ogólnie możemy powiedzieć, że graf $G$ składa się z niepustego zbioru wierzchołków, który oznaczamy symbolem $V(G)$ (ang. verticies - wierzchołki) oraz zbioru krawędzi, oznaczonego symbolem $E(G)$ (ang. edges - krawędzie). Ilość elementów zbioru $V(G)$ - liczbę wierzchołków - będziemy często oznaczać symbolem $n$, a ilość elementów zbioru $E(G)$ - liczbę krawędzi - symbolem $m$. Zatem możemy zapisać: $$G = \big( V(G),E(G) \big) \text{.}$$

Grafy proste

Grafem prostym nazywamy graf $G$ składający się z niepustego i skończnego zbioru wierzchołków $V(G)$ i skończonego zbioru krawędzi $E(G)$ zawierającego różne pary nieuporządkowane różnych elementów zbioru $V(G)$. Ozanacza to, że nie można poprowadzić krawędzi, która łączy dany wierzchołek z samym sobą. Dodatkowao graf prosty może zawierać najwyżej jedną krawędź łączącą dane dwa wierzchołki. Poniżej przedstawione zostały przykłady grafów prostych.

Grafy ogólne i multigrafy

Definicję grafu prostego możemy rozszerzyć tak, aby dotyczyła obieku ogólniejszego. Rezygnujemy z ograniczeń mówiących o tym, że dane dwa wierzchołki grafu mogą być połączone ze sobą co najwyżej jedną krawędzią oraz, że graf nie może posiadać krawędzi łączącej wierzchołek z samym sobą.

Graf, który dopuszcza w posiadanie krwędzi łączącej wierzchołek z samym sobą (pętli) oraz więcej niż jedną krawędź łączącą dwa wierzchołki (krawędzie wielokrotne) nazywamy grafem ogólnym albo po prostu grafem. W grafie ogólnym $G$ mówimy, że zbiór $V(G)$ jest zbiorem wierzchołków, a zbiór $E(G)$ jest rodziną krawędzi, przy czym mówiąc rodzina, dopuszczamy istnienie pętli lub krawędzi wielokrotnych w $G$. Jeśli graf zawiera pętlę lub krawędź wielokrotną wtedy jest nazywany multigrafem.

Sąsiedztwo

Sąsiedztwo dwóch wierzchołków wystepuje, gdy są połączone krawędzią. Wtedy możemy również powiedzieć, że dwa wierzchołki są incydentne z krawędzią, która je łączy. Krawędzie są sąsiednie gdy mają jeden wspólny wierzchołek. Stopień wierzchołka $w$ grafu oznaczamy symbolem $\deg(w)$ a jest to liczba krawędzi incydentnych do wierzchołka $w$. Warto wspomnieć, że każda pętla powiększa stopień wierzchołka, z którego została poprowadzona, o $2$.

Wierzchołek stopnia $0$ nazywamy wierzchołkiem izolowanym, a wierzchołek stopnia $1$ jest nazywany wierzchołkiem końcowym.

W grafach czesto pomijamy pojęcia geometryczne takie jak odległość, długość, pole powierzchni itd. Głównym parametrem są tutaj połączenia wierzchołków przez krawędzie, pozostałe traktujemy mniejszym zainteresowaniem.

Izomorfizm

Grafy $G$ i $H$ są izomorficzne, jeżeli isteje jednoznaczna odpowiedniosć międdzy wierzchołkami grafu $G$ i $H$ taka, że liczba krawędzi łączących daną parę wierzchołków grafu $G$ liczbie krawędzi łączących dwa odpowiadające im wierzchołki grafu $H$ jest taka sama. Symbol $G \simeq H$ oznacza, że grafy $G$ i $H$ są izomorficzne. Odpowiedniość wierzchołków $w$ i $p$ oznaczamy symbolem $w \leftrightarrow p$.

Spojność

Grafy możemy łączyć w bardziej skomplikowane struktury składajace się z wielu "części". Oznaczmy dwa nowe grafy jako: $$G = (V(G),E(G)) \qquad H = (V(H),E(H))$$ (gdzie zbiory $V(G)$ i $V(H)$ są rozłączne). Sumą grafów $G \cup H$ będzie graf, którego zbiorem wierzchołków jest zbiór $V(G) \cup V(H)$, a zbiorem krawędzi $E(G) \cup E(H)$.

Graf który można przedstawić za pomocą sumy dwóch grafów nazywamy grafem niespójnym, w przeciwnym razie graf nazywamy grafem spójnym. Naturalnie graf niespójny możemy przedstawić za pomocą sumy grafów spójnych zwanych składowymi grafu.

Zbiory rozspajające i rozdzielające

Zbiór rozspajający grafu spójnego $G$ definiujemy jako zbiór krawędzi, po których usunięciu graf $G$ stanie się grafem niespójnym. Rozcięciem jest zbiór rozspajający, którego żaden podzbiór właściwy nie jest już zbiorem rozspajającym. Jeśli rozcięcie składa się z jednej krawędzi, to tę krawędź nazwiemy mostem.

W przypadku grafów niespójnych, zbiór rozspajający grafu $G$ nazywamy zbiór krawędzi, których usunięcie spowoduje zwiększenie liczby $k$ składowych grafu $G$. Rozcięciem będzie wtedy zbiór rozspajający, którego żaden podzbiór właściwy nie jest zbiorem rozspajającym.

Spójnością krawędziową grafu spójnego $G$ nazywamy liczbę krawędzi należących do najmniej licznego rozcięcia grafu $G$. Oznacza to, że spójność krawędziowa jest najmniejszą liczbą krawędzi grafu $G$, których usunięcie spowoduje, że graf $G$ stanie się grafem niespójnym. Spójność krawędziową oznaczamy symbolem $\lambda(G)$.

Mówimy również, że graf $G$ jest $k$-spójny krawędziowo pod warunkiem, że $\lambda(G) \ge k$. Na przykład o grafie $G$, którego spójność krawędziowa $\lambda(G)$ jest równa $3$ możemy powiedzieć, że jest $1$-spójny krawędziowo, $2$-spójny krawędziowo i $3$-spójny krawędziowo, ale już nie $4$-spójny krawędziowo.

Zbiorem rozdzielającym grafu spójnego $G$ jest zbiór wierzchołków, których usunięcie spowoduje, że graf $G$ przestanie być grafem spójnym (usuwając wierzchołek usuwamy także krawędzie do niego incydentne). Jeśli zbiór rozdzielający składa się tylko z jednego wierzchołka, to ten wierzchołek nazywamy wierzchołkiem rozcinającym.

Jeśli graf $G$ jest spójny i nie jest grafem pełnym, to jego spójnością (wierzchołkową) będzie liczba elementów najmniej licznego zbioru rozdzielającego, czyli spójnością jest liczba elementów najmniej licznego zbioru których usunięcie spowoduje, że graf $G$ przestanie być grafem spójnym. Spójność grafu $G$ oznaczamy symbolem $\kappa (G)$. Podobnie jak w przypadku spójności krawędziowej mówimy, że graf $G$ jest $k$-spójny, jeśli $\kappa (G) \ge k$. Na przykład graf $G$ ma spójność wierzchołkową równą $4$, powiemy zatem, że $G$ jest $1$-spójny, $2$-spójny, $3$-spójny i $4$-spójny, ale już nie $5$-spójny.

Podgrafy

Podgrafem grafu $G$ jest graf, w którym wszystkie wierzchołki należą do $V(G)$, a wszystkie krawędzie należą do $E(G)$. Podgrafy można otrzmać usuwając niektóre wierzchołki oraz krawędzie grafu. Podgraf powstały z $G$ przez usunięcie krawędzi w opisujemy wtedy jako $G - F$, gdzie $F$ jest zbiorem usuniętych krawędzi. Podobnie postępujemy z wierzchołkami. Symbol $G - w$ mówi o tym, że z grafu $G$ usuwany zostaje wierzchołek $w$ i wszystkie krawędzie do niego incydentne. Można również usuwać wiele wierzchołków, które zapisujemy symbolem $G - S$. Oznacza to, że usuwamy z grafu $G$ wszystkie wierzchołki zbioru $S$ oraz wszystkie krawędzie incydentne do wierzchołków w zbiorze $S$.

Symbol $G \setminus e$ oznacza graf otrzymany przez ściągnięcie krawędzi $e$ czyli usunięcie krawędzi $e$ i zidentyfikowanie jej końców tak, że otrzymany wierzchołek jest incydentny z tymi krawędziami (róznymi od $e$), które były incydentne z $v$ lub $w$.

Lista sąsiedztwa

Najprostszą, a zarazem najefektywniejszą metodą reprezentacji grafów jest lista sąsiedztwa. Polega na wypisaniu wszystkich sąsiadów dla każdego wierzchołka $v$ grafu $G$ którego chcemy reprezentować. Na przykład jeśli wierzchołek $v$ sąsiaduje z wierzchołkami $z$, $w$, $x$ i $y$ to zapiszemy wtedy: $$v: z, w, x, y.$$ Powtarzając tę czynność dla pozostałych wierzchołków otrzymamy reprezentację przez listę sąsiedztwa

Macierze

W pewnym uproszczeniu możemy powiedzieć, że macierz jest tablicą prostokątną. Oznaczamy ją zazwyczaj dużymi literami. Macież posiadającą $m$ poziomych wierszy i $n$ pionowych kolumn nazywamy macierzą wymiaru $m \times n$. W macierzy, która ma podwójne indeksy, zawsze numer wiersza jest oznaczony przed numerem kolumny. Wyraz stojący na $i$-tym wierszu i na $j$-ej kolumnie oznaczamy symbolem $a_{ij}$. $$ A = \begin{pmatrix} a_{1 1} & a_{1 2} & \cdots & a_{1 n} \\ a_{2 1} & a_{2 2} & \cdots & a_{2 n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m 1} & a_{m 2} & \cdots & a_{m n} \\ \end{pmatrix} $$

Jednym ze sposobów reprezentacji grafu jest macierz sąsiedztwa. Oznaczmy graf $G$, w którym wierzchołki są kolejno przedstawione liczbami ze zbioru $\{ 1,2,\ldots, n \}$, gdzie $n$ jest ilością wierzchołków grafu $G$. Następnie weźmy pod uwagę macierz wymiaru $n \times n$, w której wyraz $a_{ij}$ jest równy liczbie krawędzi łączących wierzchołek $i$ z wierzchołkiem $j$. Na przykład jeśli:

Innym sposobem jest reprezentacja przez macierz incydencji. Jeśli oznakujemy również krawędzie grafu $G$ liczbami ze zbioru $\{ 1,2,\ldots,m \}$ (gdzie $m$ jest liczbą krawędzi grafu $G$), to macierzą incydencji będzie macierz wymiaru $n \times m$, której wyraz $a_{ij}$ jest równy $1$, jeżeli istnieje krawędź $j$ incydentna z wierzchołkiem $i$, w przeciwnym razie wyraz $a_{ij}$ jest równy $0$. Na przykład:

Grafy puste i pełne

Graf pusty jest grafem, którego zbiór krawędzi jest zbiorem pustym. Oznacza to, że składa się z samych wierzchołków, z których wszystkie są wierzchołkami izolowanymi. Graf pusty mający $n$ wierzchołków oznaczamy symbolem $N_n$.

Grafem pełnym jest grafem prostym, w którym każda para różnych wierzchołków jest połączona krawędzią. Graf pełny mający $n$ wierzchołków oznaczamy symbolem $K_n$. Ilość krawędzi grafu pełnego $K_n$ opisuje wzór: $$m = \frac{n(n - 1)}{2}$$.

Grafy regularne

Grafem regularnym nazywamy graf, którego każdy wierzchołek ma ten sam stopień. Graf regularny, którego stopnie wierzchołków są równe $r$ nazywamygo grafem regularnym stopnia $r$ lub grafem $r$-regularnym. Grafy regularne stopnia $3$-go nazywamy grafami kubicznymi.

Grafy cykliczne, koła, grafy liniowe

Graf spójny, regularny stopnia $2$ nazywamy grafem cykclicznym. Graf cykliczny mający $n$ wierzchołków oznaczamy symbolem $C_n$. Graf powstający z grafu $C_{n-1}$ przez połączenie każdego wierzchołka krawędzią z nowym wierzchołkiem nazywamy kołem o $n$ wierzchołkach i oznaczamy symbolem $W_n$. Grafem powstającym z $C_n$ przez usunięcie jednej krawędzi nazywawy grafem liniowm o $n$ wierzchołkach i oznaczamy symbolem $P_n$

Grafy dwudzielne

Jeśli zbiór wierzchołków grafu $G$ może być podzielony na dwa zbiory rozłączne $A$ oraz $B$ w taki sposób, by każa krawędź grafu $G$ łączyła wierzchołek zbioru $A$ z wierzchołkiem zbioru $B$, to taki graf nazywamy grafem dwudzielnym. Równoważnie, graf dwudzielny to taki, którego wierzchołki możemy pokolorować dwoma kolorami, czerwonym i niebieskim, w taki sposób, by każda krawędź łączyła wierzchołek (czerwony należący do zbioru $A$) z wierzchołkiem niebieskim (należącym do zbioru $B$).

Definicję grafu pełnego i dwudzielnego możemy połączyć tak, aby powstała definicja mówiła o innym typie grafu. Graf pełny, dwudzielny to graf, w którym każdy wierzchołek zbioru $A$ jest połączony z każdym wierzchołkiem zbioru $B$. Graf pełny dwudzielny mający $r$ wierzchołków należących do zbioru $A$ i $s$ wierzchołków należących do zbioru $B$ oznaczamy symbolem $K_{r,s}$. Warto również zwrócić uwagę na to, że graf $K_{r,s}$ ma $r+s$ wierzchołków i $rs$ krawędzi.

Kostki

$k$-kostką nazywamy regularny graf, dwudzielny, którego wierzchołki odpowiadają ciągom $(a_1, a_2, \ldots, a_k)$ takim, że każdy wyraz $a_i$ jest równy $0$ lub $1$, i którego krawędzie łączą sie w ciągi różniące sie dokładnie jednym wyrazem. $k$-kostkę oznaczamy symbolem $Q_k$.

Dopełnienie grafu prostego

Dopełnieniem $\overline{G}$ grafu prostego $G$ nazywamy graf prosty, którego zbiorem wierzchołków jest $V(G)$ i w którym dwa wierzcholki są sąsiednie wtedy i tylko wtedy, gdy nie są sąsiednie w grafie $G$.