Grafy - definicje, własności, przykłady

Drukuj

Poziom studiów

Graf – to zbiór wierzchołków, które mogą być połączone krawędziami.

Przykładowy graf o \(6\) wierzchołkach i \(5\) krawędziach:

Zbiór wierzchołków tego grafu to: \[V = \{1,2,3,4,5,6\}\] Zbiór krawędzi to: \[E = \{\{1,2\}, \{2,3\}, \{2,4\}, \{2,5\}, \{5,6\}\}\] Ten sam graf można też zilustrować graficznie np. w taki sposób:

Definicja

Grafem nazywamy parę uporządkowaną \(G = (V, E)\), gdzie:

\(V\) – to niepusty zbiór wierzchołków.
\(E\subset \bigl\{\{u,v\}: u,v\in V\bigr\}\) – to zbiór krawędzi, czyli dwuelementowych podzbiorów zbioru wierzchołków.

Dla \(V = \{1,2,3\}\) i \(E = \{\{1,2\},\,\{2,3\}\}\) mamy graf o trzech wierzchołkach i dwóch krawędziach. Jedna krawędź łączy wierzchołek \(1\) z \(2\), a druga wierzchołek \(2\) z \(3\):
Jeżeli \(V = \{a,b,c,d\}\) i \(E = \{\{a,b\},\,\{b,c\},\,\{c,d\},\,\{d,a\}\}\), to mamy graf o czterech wierzchołkach i czterech krawędziach:

Definicja

Graf prosty – to taki graf, w którym nie ma pętli (krawędzi łączących wierzchołek z samym sobą) oraz nie ma krawędzi wielokrotnych (między tymi samymi parami wierzchołków jest najwyżej jedna krawędź).

Definicja

Stopień wierzchołka \(v\in V\) – to liczba krawędzi wychodzących z wierzchołka \(v\): \[ \deg(v)=\bigl|\{\,u\in V:\{v,u\}\in E\bigr\}\bigr|. \]

W grafie: \(V=\{1,2,3,4\}\), \(E=\{\{1,2\},\{1,3\},\{1,4\},\{2,3\}\}\) mamy: \[\deg(1)=3\] \[\deg(2)=2\] \[\deg(3)=2\] \[\deg(4)=1\]

Definicja

Macierz sąsiedztwa dla grafu o \(n\) wierzchołkach: \(V=\{v_1,v_2,\dots,v_n\}\) – to macierz kwadratowa \(n\times n\), w której:

\(a_{ij} =\) liczba krawędzi między wierzchołkami \(v_i\) oraz \(v_j\).

Jeżeli graf jest nieskierowany, to macierz sąsiedztwa jest symetryczna.
Jeżeli graf nie ma pętli, to na głównej przekątnej stoją zera.

Dla grafu \(G\) o wierzchołkach \(V=\{1,2,3,4\}\) i krawędziach \(E=\{\{1,2\},\{1,3\},\{2,4\}\}\):

mamy macierz sąsiedztwa: \[ A(G)= \begin{pmatrix} 0 & 1 & 1 & 0\\ 1 & 0 & 0 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0 \end{pmatrix} \]

Wyznaczyć graf \(G\) mający podaną poniżej macierz sąsiedztwa \[ M=\left(\begin{array}{lllll} 0 & 1 & 1 & 2 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 2 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0 \end{array}\right) \]

Macierz jest wymiaru \(5\times 5\), czyli ma \(5\) wierzchołków. Z macierzy odczytujemy ile krawędzi łączy wierzchołek \(i\)-ty z \(j\)-tym. Przykładowo: \(a_{14}=2\), zatem między wierzchołkiem \(1\) i \(4\) są dwie krawędzie.

Definicja

Graf pełny – to graf w którym każde dwa różne wierzchołki są połączone krawędzią.

Graf pełny o \(n\) wierzchołkach oznaczamy \(K_n\), a liczba jego krawędzi to: \[\binom{n}{2} = \frac{n(n-1)}{2}\]

Definicja

Graf jest spójny jeżeli istnieje droga między każdymi dwoma wierzchołkami grafu.

Definicja

Dopełnienie grafu \(G\) – to graf \({\overline {G}}\) w którym dwa wierzchołki są połączone krawędzią wtedy i tylko wtedy, gdy nie były połączone w grafie \(G\).

Oto przykład grafu \(G\), który nie jest spójny:

Graf \(G\) nie jest spójny, ponieważ nie istnieje droga np. między wierzchołkiem \(1\) i \(4\).

Dopełnienie \({\overline {G}}\) jest spójne i wygląda tak:

Własności grafu pełnego \(K_n\)

Stopień dowolnego wierzchołka wynosi \(n-1\).
Macierz sąsiedztwa \(A(K_n)\) to macierz samych jedynek poza główną przekątną, gdzie są zera: \[ A(K_n)_{ij} = \begin{cases} 1, & i\neq j,\\ 0, & i=j. \end{cases} \]
Graf \(K_n\) jest spójny.
Dopełnienie grafu \(K_n\) jest grafem pustym (bez krawędzi) o \(n\) wierzchołkach.

\(K_4\) ma \(4\) wierzchołki i \(\binom{4}{2}=6\) krawędzi:

Macierz sąsiedztwa: \[ A(K_4)= \begin{pmatrix} 0&1&1&1\\ 1&0&1&1\\ 1&1&0&1\\ 1&1&1&0 \end{pmatrix} \] Dopełnieniem grafu \(K_4\) jest graf pusty \({\overline {K_4}}\):

Macierz sąsiedztwa: \[ A(\overline {K_4})= \begin{pmatrix} 0&0&0&0\\ 0&0&0&0\\ 0&0&0&0\\ 0&0&0&0 \end{pmatrix} \]

\(K_6\) ma \(6\) wierzchołków i \(\binom{6}{2}=15\) krawędzi:

Macierz sąsiedztwa: \[ A(K_6)= \begin{pmatrix} 0&1&1&1&1&1\\ 1&0&1&1&1&1\\ 1&1&0&1&1&1\\ 1&1&1&0&1&1\\ 1&1&1&1&0&1\\ 1&1&1&1&1&0 \end{pmatrix} \] Dopełnieniem grafu \(K_6\) jest graf pusty \({\overline {K_6}}\) składający się z samych \(6\) wierzchołków, bez żadnej krawędzi.

Definicja

Graf dwudzielny \(K_{m,n}\) – to taki graf, którego wierzchołki dzielimy na dwie rozłączne zbiory: \[ X=\{x_1,x_2,\dots,x_m\},\quad Y=\{y_1,y_2,\dots,y_n\} \] i krawędzie mogą być tylko pomiędzy wierzchołkami z tych rozłącznych zbiorów. Nie ma krawędzi wewnątrz \(X\) ani wewnątrz \(Y\).

Graf pełny dwudzielny \(K_{m,n}\) – to taki graf dwudzielny, w którym każdy wierzchołek z \(X\) jest połączony krawędzią z każdym wierzchołkiem z \(Y\). Wówczas liczba krawędzi takiego grafu wynosi: \[ \bigl|E(K_{m,n})\bigr| = m\cdot n. \]

Własności grafu pełnego \(K_{m,n}\)

Stopień wierzchołka \(x_i\in X\) to \(n\), a stopień \(y_j\in Y\) to \(m\). Czyli: \[ \deg(x_i)=n,\quad \deg(y_j)=m. \]
Graf jest spójny.
Macierz sąsiedztwa w kolejności wierzchołków \((x_1,\dots,x_m,y_1,\dots,y_n)\) ma blokową postać: \[ A(K_{m,n}) = \begin{pmatrix} 0_{m\times m} & J_{m\times n}\\ J_{n\times m} & 0_{n\times n} \end{pmatrix}, \] gdzie \(0_{k\times k}\) to macierz zerowa stopnia \(k\), a \(J_{p\times q}\) to macierz samych jedynek wymiaru \(p\times q\).
Dopełnieniem \(K_{m,n}\) jest suma grafu pełnego \(K_m\) o wierzchołkach \(X\) oraz grafu pełnego \(K_n\) o wierzchołkach \(Y\): \[\overline{K_{m,n}} = K_m \cup K_n\]

Graf pełny dwudzielny \(K_{2,4}\):

\(X=\{1,2\},\;Y=\{3,4,5,6\}\).
\(E=\{\{1,3\},\{1,4\},\{1,5\},\{1,6\},\{2,3\},\{2,4\},\{2,5\},\{2,6\}\}\)
Macierz sąsiedztwa \(6\times6\) w kolejności \((1,2,3,4,5,6)\): \[ A(K_{2,4})= \begin{pmatrix} 0&0&1&1&1&1\\ 0&0&1&1&1&1\\ 1&1&0&0&0&0\\ 1&1&0&0&0&0\\ 1&1&0&0&0&0\\ 1&1&0&0&0&0 \end{pmatrix}. \]
Ilustracja:
Graf dopełniający \(\overline{K_{2,4}}\): Macierz sąsiedztwa grafu dopełniającego: \[ A\bigl(\overline{K_{2,4}}\bigr)= \begin{pmatrix} 0&1&0&0&0&0\\ 1&0&0&0&0&0\\ 0&0&0&1&1&1\\ 0&0&1&0&1&1\\ 0&0&1&1&0&1\\ 0&0&1&1&1&0 \end{pmatrix} \]

Graf pełny dwudzielny \(K_{1,7}\):

\(X=\{1\},\;Y=\{2,3,4,5,6,7,8\}\).
\(E=\{\{1,2\},\{1,3\},\{1,4\},\{1,5\},\{1,6\},\{1,7\},\{1,8\}\}\).
Macierz sąsiedztwa \(8\times8\) w kolejności \((1,2,3,4,5,6,7,8)\): \[ A(K_{1,7})= \begin{pmatrix} 0&1&1&1&1&1&1&1\\ 1&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0\\ 1&0&0&0&0&0&0&0 \end{pmatrix} \]

Grafy dwudzielne pełne typu: \(K_{1,n}\) nazywane są "gwiazdą":

Definicja

Cykl \(C_n\) – to graf prosty o \(n\) wierzchołkach \(V=\{1,2,\dots,n\}\) i \(n\) krawędziach: \[ E = \bigl\{\{1,2\},\,\{2,3\},\,\dots,\,\{n-1,n\},\,\{n,1\}\bigr\}. \] Innymi słowy, wierzchołki są połączone kolejno i ostatni wraca do pierwszego.

Własności cyklu \(C_n\)

\(\bigl|E(C_n)\bigr| = n\), \(\bigl|V(C_n)\bigr| = n\).
Stopień każdego wierzchołka jest równy \(2\) (czyli graf jest \(2\)-regularny).
Graf jest spójny.
Macierz sąsiedztwa w kolejności \((1,2,\dots,n)\): \[ A(C_n)_{i,j} = \begin{cases} 1, & \text{jeśli }j=i+1\text{ lub }j=i-1\\ 0, & \text{w przeciwnym razie}. \end{cases} \] Przykładowo dla \(n=6\): \[ A(C_6)= \begin{pmatrix} 0&1&0&0&0&1\\ 1&0&1&0&0&0\\ 0&1&0&1&0&0\\ 0&0&1&0&1&0\\ 0&0&0&1&0&1\\ 1&0&0&0&1&0 \end{pmatrix}. \]

Cykl \(C_6\):

\(V=\{1,2,3,4,5,6\}\).
\(E=\{\{1,2\},\{2,3\},\{3,4\},\{4,5\},\{5,6\},\{6,1\}\}\).
Macierz sąsiedztwa \(6\times6\) w kolejności \((1,2,3,4,5,6)\): \[ A(C_6)= \begin{pmatrix} 0&1&0&0&0&1\\ 1&0&1&0&0&0\\ 0&1&0&1&0&0\\ 0&0&1&0&1&0\\ 0&0&0&1&0&1\\ 1&0&0&0&1&0 \end{pmatrix} \]
Graf dla cyklu \(C_6\):
Graf dopełniający \(\overline{C_6}\): Macierz sąsiedztwa grafu dopełniającego: \[ A\bigl(\overline{C_6}\bigr)= \begin{pmatrix} 0&0&1&1&1&0\\ 0&0&0&1&1&1\\ 1&0&0&0&1&1\\ 1&1&0&0&0&1\\ 1&1&1&0&0&0\\ 0&1&1&1&0&0 \end{pmatrix} \]

Definicja

Graf jest \(n\)-regularny jeżeli każdy jego wierzchołek jest stopnia \(n\).

Definicja

Graf platoński – to graf, utworzony z wierzchołków i krawędzi wielościanu foremnego. Istnieje dokładnie \(5\) wielościanów foremnych:

Czworościan foremny (graf \(K_4\)).
Sześcian (graf o \(6\) wierzchołkach i \(12\) krawędziach, \(3\)-regularny).
Ośmiościan foremny (graf o \(6\) wierzchołkach i \(12\) krawędziach, \(4\)-regularny).
Dwunastościan foremny (graf o \(20\) wierzchołkach i \(30\) krawędziach, \(3\)-regularny).
Dwudziestościan foremny (graf o \(12\) wierzchołkach i \(30\) krawędziach, \(5\)-regularny).

Izomorfizm grafów

Jeżeli dwa grafy mają taką samą liczbę wierzchołków i strukturę krawędzi między nimi, a różnią się jedynie położeniem wierzchołków, to powiemy, że są izomorficzne.

Definicja

Dwa grafy \(G=(V,E)\) i \(G'=(V',E')\) nazywamy izomorficznymi, jeśli istnieje bijekcja (funkcja wzajemnie jednoznaczna) \(\varphi:V\to V'\) taka, że: \[ \{u,v\}\in E \;\Longleftrightarrow\; \{\varphi(u),\varphi(v)\}\in E'. \]

Własności grafów izomorficznych

Grafy izomorficzne mają:

taką samą liczbę wierzchołków i krawędzi,
odpowiednie wierzchołki mają te same stopnie.

Oto przykład dwóch grafów izomorficznych:

Jeden graf powstał z drugiego przez przeniesienie jednego czerwonego wierzchołka na drugą stronę.

Aby udowodnić, że grafy są izomorficzne, to należy zapisać formalnie bijekcję \(\varphi(v)\) przekształcającą jeden graf na drugi: \[\varphi(1)=A\] \[\varphi(2)=B\] \[\varphi(3)=C\] \[\varphi(4)=D\] \[\varphi(5)=E\] \[\varphi(6)=F\] Należy sprawdzić czy tak zdefiniowana bijekcja zachowuje krawędzie: Wszystkie krawędzie są przekształcone wzajemnie jednoznacznie, zatem grafy są izomorficzne.

Wykaż, że grafy:

\(G_1\): \(V_1=\{1,2,3,4\}\), \(E_1=\{\{1,2\},\{1,3\},\{1,4\},\{2,3\}\}.\)
\(G_2\): \(V_2=\{a,b,c,d\}\), \(E_2=\{\{a,b\},\{a,c\},\{a,d\},\{b,c\}\}.\)

są izomorficzne.

Ustalmy bijekcję \(\varphi:V_1\to V_2\) następująco: \(\varphi(1)=a,\;\varphi(2)=b,\;\varphi(3)=c,\;\varphi(4)=d\).

Widać, że każda krawędź w \(G_1\) przechodzi na odpowiadającą krawędź w \(G_2\): \[\{1,2\}\xrightarrow{\varphi}\{a,b\}\] \[\{1,3\}\xrightarrow{\varphi}\{a,c\}\] \[\{1,4\}\xrightarrow{\varphi}\{a,d\}\] \[\{2,3\}\xrightarrow{\varphi}\{b,c\}\] Zatem grafy są izomorficzne.

Definicja: Ścieżka i odległość

Ścieżką w grafie \(G=(V,E)\) nazywamy ciąg kolejnych wierzchołków \((v_{i_0},v_{i_1},\dots,v_{i_k})\), taki że \(\{v_{i_j},v_{i_{j+1}}\}\in E\) dla \(j=0,1,\dots,k-1\).
Długość ścieżki to liczba krawędzi, czyli \(k\).
Graf jest spójny, jeśli dla każdej pary wierzchołków istnieje ścieżka między nimi.
Odległością \(\mathrm{dist}(u,v)\) nazywamy najmniejszą długość ścieżki łączącej \(u\) z \(v\). Jeśli nie ma ścieżki, odległość jest nieskończona (lub ?brak połączenia?).

Dla grafu:

odległość między \(1\) a \(6\) wynosi \(3\), bo ścieżka to \((1,2,5,6)\).

Wykaż izomorfizm poniższych grafów:

Na początku sprawdzamy czy liczba wierzchołków i krawędzi w obu grafach jest taka sama. Zgadza się - w obu mamy \(10\) wierzchołków i wszystkie są tego samego stopnia.

Musimy znaleźć bijekcję \(\varphi\) przekształcającą jeden graf w drugi. W tym celu spróbujmy znaleźć w obu grafach taką samą liczbę niezależnych cykli wykorzystujące w sumie wszystkie wierzchołki.

Na powyższym rysunku zaznaczyłem dla każdego grafu dwa przykładowe niezależnych cykle. W pierwszym grafie numerujemy kolejne wierzchołki w jednym cyklu kolejno liczbami \(1-5\), a w drugim cyklu liczbami \(6-10\). W grugim grafie wybieramy sobie jeden cykl i numerujemy go liczbami \(1-5\).

Następnie musimy ponumerować wierzchołki drugiego cyklu, tak żeby wszystkie krawędzie się zgadzały. Patrzymy, że w pierwszym grafiw wierzchołek \(1\) łączy się z wierzchołkami: \(2\), \(5\) oraz \(6\). Zatem w drugim grafie tak wybieramy wierzołek numer \(6\), żeby też powstała krawędź \(\{1,6\}\):

Numerując kolejne wierzchołki sprawdzamy czy powstają krawędzie: \(\{2,8\}\), \(\{3,10\}\), \(\{4,7\}\), \(\{5,9\}\).

Wszystkie krawędzie się zgadzają, więc mamy bijekcję przekształcającą jeden graf w drugi. Czyli grafy są izomorficzne.

Wiedząc, że atom węgla \(C\) ma \(4\) wiązania, a atom wodoru \(H\) ma \(1\) wiązanie:

Narysuj graf odpowiadający cząsteczce metanu \(CH_4\).
Narysuj graf odpowiadający cząsteczce propanu \(C_3H_8\).
Istnieją dwa różne węglowodory mające wzór sumaryczny \(C_4H_{10}\). Narysuj grafy odpowiadające ich cząstkom.

Metan \(CH_4\):
Graf to gwiazda \(K_{1,4}\). Jeden węzeł odpowiada atomowi węgla stopnia \(4\), a cztery węzły stopnia \(1\) to atomy wodoru.
Propan \(C_3H_8\):
Trzy atomy węgla tworzą środkowy łańcuch, a każdy węgiel dopełnia \(4\) wiązania atomami wodoru:
Izomery \(C_4H_{10}\):
- czterowęglowy łańcuch \(\,C_1 - C_2 - C_3 - C_4\,\), z wodorem tak, aby każdy \(C\) miał sumarycznie \(4\) krawędzie:
- jeden atom węgla \(C_1\) w centrum, łączy trzy końcowe węgle \(C_2,C_3,C_4\) i jednocześnie wiąże się z wodorem:

Narysuj wszystkie grafy proste nieoznakowane mające cztery wierzchołki.

Grafy będą różniły się liczbą i rozmieszczeniem krawędzi. Wszystkich nieizomorficznych grafów z \(4\) wierzchołkami będzie łącznie \(11\). Narysujmy wszystkie w zależności od liczby krawędzi:

Czy poniższe grafy są izomorficzne? Odpowiedź uzasadnij.

Tak - są izomorficzne. Żeby to zobaczyć, to wystarczy przesunąć jeden wierzchołek w drugim grafie: