Matematyka dyskretna 1/Wykład 12: Grafy: Różnice pomiędzy wersjami

Aktualna wersja na dzień 21:49, 11 wrz 2023

Czym jest graf

Wyruszając w daleką podróż zabieramy ze sobą mapę samochodową. Głównymi elementami graficznymi zawartymi w mapie są punkty (małe kółka) symbolizujące miasta, oraz odcinki (lub łuki) obrazujące drogi pomiędzy nimi. Taka mapa jest z grubsza przedstawieniem rzeczywistości za pomocą grafu. Chcąc na przykład znaleźć drogę z Bydgoszczy do Krakowa, szukamy ciągu kolejno połączonych miast zaczynającego się w Bydgoszczy i kończącego się w Krakowie. Jest to nic innego, jak znalezienie odpowiedniej ścieżki w grafie połączeń między miastami.

Graf to para $𝐆 = (V, E)$ , gdzie:

$V$ jest zbiorem wierzchołków,

(czasami zwanymi węzłami lub punktami grafu)

$E$ jest rodziną (być może powtarzających się) krawędzi,

czyli jedno- i dwu-elementowych podzbiorów $V$ .

Graf prosty to para $𝐆 = (V, E)$ , gdzie:

$V$ jest zbiorem wierzchołków,
$E$ jest zbiorem krawędzi między różnymi wierzchołkami,

czyli dwu-elementowych podzbiorów $V$ .

Graf ogólny (a.) oraz prosty (b.)

Uwaga

W grafie w odróżnieniu od grafu prostego dopuszczamy pętle oraz krawędzie wielokrotne. Wierzchołek nazywany jest czasem także węzłem, jak i punktem grafu. Krawędź łącząca $v$ z $w$ oznaczana będzie jako $v w$ . Jeśli istnieje krawędź $v w$ to mówimy, że $v$ i $w$ są sąsiadami; oraz że krawędź $v w$ jest incydentna do $v$ ( $w$ ). Ponadto, dla grafu $𝐆$ symbolem $V (𝐆)$ będziemy oznaczać jego zbiór wierzchołków, zaś symbolem $E (𝐆)$ jego zbiór krawędzi. Czasem, dla odróżnienia grafu od grafu prostego, graf będziemy nazywać też grafem ogólnym.

Stopień wierzchołka $v$ w grafie $𝐆$ to liczba krawędzi incydentnych z $v$ . Stopień wierzchołka $v$ oznaczany jest jako $d e g v$ .

Obserwacja 12.1

Jeśli $𝐆 = (V, E)$ jest grafem ogólnym, to

$\sum_{v \in V} d e g v = 2 | E |$

A zatem liczba wierzchołków o nieparzystym stopniu jest parzysta.

Dowód

Każda krawędź jest incydentna do dwóch wierzchołków. Zliczając krawędzie incydentne do kolejnych wierzchołków, a następnie sumując te wartości, każda krawędź $v w$ zostanie zliczona dwa razy: raz przy rozpatrywaniu wierzchołka $v$ , a drugi raz przy $w$ .

Jeśli $𝐆$ miałby nieparzyście wiele wierzchołków o nieparzystym stopniu to suma $\sum_{v \in V} d e g v$ byłaby nieparzysta, wbrew temu, że jest liczbą parzystą $2 | E |$ .

Ściągnięcie zbioru

{p, q, r}

do wierzchołku

x

(a.) Digraf oraz (b.) jego graf szkieletowy

Uwaga

Dla grafów $𝐆 = (V, E)$ , $𝐆_{1} = (V_{1}, E_{1})$ , $𝐆_{2} = (V_{2}, E_{2})$ definiujemy następujące pojęcia:

suma grafów $𝐆_{1} \cup 𝐆_{2} = (V_{1} \cup V_{2}, E_{1} \cup E_{2})$ ,

przecięcie grafów $𝐆_{1} \cap 𝐆_{2} = (V_{1} \cap V_{2}, E_{1} \cap E_{2})$ ,

różnica grafów $𝐆_{1} - 𝐆_{2} = (V_{1} - V_{2}, E_{1} - E_{2})$ ,

podgraf grafu $𝐆$ to graf $𝐇$ , w którym $V (𝐇) \subseteq V (𝐆)$ i $E (𝐇) \subseteq E (𝐆)$ ,

restrykcja grafu $𝐆$ do podzbioru $X \subseteq V$ to $𝐆 |_{X} = (X, {v w : v, w \in X})$ ,

podgraf indukowany grafu $𝐆$ to graf będący restrykcją grafu $𝐆$ ,

iloraz grafu $𝐆$ przez relację równoważności $θ \subseteq V \times V$ na zbiorze jego wierzchołków to graf postaci

$𝐆 / θ = (V / θ, {{v / θ, w / θ} : {v, w} \in E})$

ściągnięcie zbioru wierzchołków $X \subseteq V$ w grafie $𝐆$ to szczególny przypadek ilorazu $𝐆 / θ$ , w którym klasy równoważności wszystkich wierzchołków spoza $X$ są jednoelementowe, a $X$ stanowi dodatkową klasę, tzn. $V / θ = {{v} : v \in V - X} \cup {X}$ . W ten sposób zbiór $X$ został ściągnięty do punktu, którego sąsiadami są sąsiedzi jakiegokolwiek wierzchołka z $X$ . Z drugiej strony, jeśli $θ \subseteq V \times V$ jest relacją równoważności o klasach $X_{1}, \dots, X_{k}$ , to ściągając w grafie $𝐆$ kolejno zbiory $X_{1}, \dots, X_{k}$ otrzymamy graf ilorazowy $𝐆 / θ$ .

W dotychczasowej interpretacji grafów, jako mapy dróg zakładaliśmy, że istnienie drogi np. z Krakowa do Zakopanego, gwarantowało także możliwość powrotu po tej samej trasie. To oczywiście nie musi być zawsze prawdą, np. w miastach jest wiele dróg jednokierunkowych. Chcąc rozważać również takie jednokierunkowe trasy, tzn uwzględniać kierunek relacji między dwoma obiektami, będziemy mówić o grafach skierowanych.

Graf skierowany (lub inaczej digraf) to para $𝐃 = (V, E)$ , gdzie

$V$ jest zbiorem wierzchołków,

$E$ jest zbiorem krawędzi skierowanych, czyli $E \subseteq V \times V$ .

Uwaga

Krawędź digrafu (czyli uporządkowaną parę) $v w$ graficznie przedstawiamy jako strzałkę $v ∙ ⟶ ∙ w$ .

Graf szkieletowy digrafu $𝐃$ to graf otrzymany z $𝐃$ poprzez zaniedbanie (usunięcie) kierunku krawędzi, ale nie samych krawędzi.

Przegląd niektórych grafów

[[File:Grafy dwudzielne.svg|250x250px|thumb|left|Graf nie będący dwudzielnym (a), niepełny graf dwudzielny (b) oraz pełny graf dwudzielny $𝒦_{3, 4}$ (c)

Graf nieplanarny(a) oraz graf planarny (b) wraz z jego prezentacją w postaci grafu płaskiego (c)

Graf pusty to graf bez krawędzi. Antyklika lub graf niezależny to inne nazwy grafu pustego. Antyklikę o $n$ wierzchołkach oznaczać będziemy przez $𝒜_{n}$ .

Graf pełny to graf, w którym każde dwa wierzchołki połączone są krawędzią. Graf pełny nazywany jest także kliką i oznaczany przez $𝒦_{n}$ , gdzie $n$ jest liczbą jego wierzchołków.

Uwaga

Liczba krawędzi w klice $𝒦_{n}$ wynosi $\frac{n (n - 1)}{2}$ .

Graf dwudzielny to graf $𝐆 = (V, E)$ , w którym zbiór $V$ da się podzielić na dwa rozłączne podzbiory $V_{1}$ oraz $V_{2}$ tak, by żadne dwa wierzchołki w obrębie tego samego podzbioru $V_{i}$ nie były sąsiadami. Czasem, dla podkreślenia takiego podziału, graf dwudzielny będziemy oznaczać przez $(V_{1} \cup V_{2}, E)$ . Zauważmy jednak, że podział taki nie jest jednoznaczny -- np. w antyklice $𝒜_{n}$ dowolny podział zbioru wierzchołków na dwa podzbiory jest podziałem dwudzielnym.

Pełny graf dwudzielny to graf dwudzielny $𝐆 = (V_{1} \cup V_{2}, E)$ , w którym każdy wierzchołek z $V_{1}$ jest połączony z każdym wierzchołkiem z $V_{2}$ . Pełny graf dwudzielny oznaczać będziemy przez $𝒦_{r, s}$ , gdzie $r$ jest rozmiarem $V_{1}$ , a $s$ rozmiarem $V_{2}$ .

Graf płaski to para $\overline{G} = (\overline{V}, \overline{E})$ , gdzie:

$\overline{V}$ jest jakimś zbiorem punktów płaszczyzny $ℝ^{2}$ ,

$\overline{E}$ jest zbiorem nie przecinających się odcinków lub łuków w $R^{2}$ o końcach ze zbiorze $\overline{V}$ .

Graf planarny to graf, który jest prezentowalny jako graf płaski.

Ścieżki, Cykle, oraz Spójność

Grafy marszruta

Marszruta w grafie $𝐆$ z wierzchołka $w$ do wierzchołka $u$ to skończony ciąg krawędzi w postaci $w v_{1}, v_{1} v_{2}, \dots, v_{k - 1} u$ .
W skrócie marszrutę taką oznaczamy przez $w \to v_{1} \to v_{2} \to \dots \to v_{k - 1} \to u$ .
Wierzchołek $w$ nazywać będziemy początkowym, a $u$ końcowym wierzchołkiem marszruty.

Długość marszruty $w \to v_{1} \to v_{2} \to \dots \to v_{k - 1} \to u$ to liczba jej krawędzi.

Marszruta zamknięta to marszruta kończąca się w punkcie wyjścia, czyli taka, w której $w = u$ .

Uwaga

Marszruta może być również zdefiniowana w grafach skierowanych. Definiuje się ją analogicznie, uwzględniając jednak kierunek krawędzi. Marszruta taka, zgodna z kierunkiem krawędzi nazywana jest marszrutą skierowaną.

W grafie z rysunku Grafy marszruta ciąg $u \to v \to w \to z \to z \to y \to v \to w \to v$ jest marszrutą z $u$ do $v$ o długości $8$ . Widzimy, że niektóre jej wierzchołki, a nawet krawędzie, powtarzają się. Wygodnie jest móc wyróżniać marszruty bez powtarzających się wierzchołków.

Droga to marszruta bez powtarzających się wierzchołków. Droga nazywana jest też często ścieżką.

Cykl to marszruta zamknięta, w której jedynym powtarzającym się wierzchołkiem jest jej początek (będący oczywiście również jej końcem).

W grafie z rysunku Grafy marszruta marszruta $y \to v \to w \to u \to x$ jest drogą, zaś marszruta $x \to u \to v \to w \to y \to x$ jest cyklem.
Czasem wygodnie jest traktować marszrutę w grafie $𝐆$ (a więc w szczególności również cykle i ścieżki) jako podgraf

𝐌 = (V (𝐌), E (𝐌)) : = ({v_{0}, \dots, v_{k}}, {{v_{0}, v_{1}}, \dots, {v_{k - 1}, v_{k}}})

Graf spójny to graf, w którym między dwoma dowolnymi wierzchołkami istnieje droga. Graf niespójny to graf, który nie jest spójny.

Spójna składowa grafu $𝐆 = (V, E)$ to maksymalny (w sensie inkluzji) podzbiór $X \subseteq V$ , indukujący graf spójny $𝐆 |_{X}$ .

Graf z rysunku Grafy marszruta jest spójny.

Uwaga

Dowolnym graf $𝐆$ rozpada się na spójne składowe, tworzące podział zbioru $V$ . Grafy spójne mają jedynie jedną spójną składową, w przeciwieństwie do grafów niespójnych posiadających ich więcej.
Rozkład na spójne składowe wyznacza relacją równoważności $σ \subseteq V \times V$ , dla której graf ilorazowy $𝐆 / σ$ jest antykliką.

Wierzchołek izolowany to wierzchołek nie posiadający sąsiadów.

Uwaga

Punkty izolowane tworzą jednoelemetowe spójne składowe.

Graf z rysunku Grafy spojne skladowe ma trzy spójne składowe: ${v, w, y, x}, {u, z}, {t}$ . Ponadto $t$ jest punktem izolowanym.

Intuicyjnie wydaje się, że graf spójny powinien mieć dostatecznie dużo krawędzi w stosunku do liczby wierzchołków. Okazuje się jednak, że w grafie spójnym $𝐆 = (V, E)$ możemy wymusić jedynie $| V | - 1$ krawędzi. Z drugiej jednak strony, gdy graf $𝐆$ ma więcej niż $| V | \cdot (| V | - 1) / 2$ krawędzi, to musi być spójny. Rezultaty te można uzyskać z bardziej ogólnego wyniku:

Twierdzenie 12.2

W grafie prostym $𝐆 = (V, E)$ o $k$ składowych spójnych liczba jego krawędzi spełnia nierówności

| V | - k \leq | E | \leq \frac{(| V | - k) (| V | - k + 1)}{2}

Ponadto, są to najlepsze możliwe ograniczenia, tzn.

istnieje graf prosty $𝐆 = (V, E)$ o dokładnie $k$ składowych spójnych, w którym $| E | = | V | - k$ ,
istnieje graf prosty $𝐆 = (V, E)$ o dokładnie $k$ składowych spójnych, w którym $| E | = \frac{(| V | - k) (| V | - k + 1)}{2}$ .

Dowód

Niech $n$ będzie liczbą wierzchołków grafu $𝐆$ , a $m$ liczbą jego krawędzi. Dowód nierówności $n - k \leq m$ przeprowadzimy indukcyjnie względem liczby krawędzi $m$ w grafie $𝐆$ . Jeżeli $m = 0$ , to wszystkie wierzchołki są punktami izolowanymi czyli $k = n$ , co spełnia żądaną nierówność. Przy $m > 0$ usunięcie krawędzi może nie zmienić liczby składowych spójnych albo zwiększyć ją o jeden. W pierwszym przypadku z założenia indukcyjnego dostaniemy odrazu że $n - k \leq m - 1 \leq m$ , zaś w drugim, założenie indukcyjne daje $n - (k + 1) \leq m - 1$ , czyli rzeczywiście $n - k \leq m$ .

Dla dowodu górnego ograniczenia $m \leq (n - k) (n - k + 1) / 2$ na liczbę krawędzi załóżmy, że $𝐆$ posiada $k$ składowych spójnych i ma największą możliwą liczbę krawędzi wśród $n$ -elementowych grafów o $k$ składowych spójnych. Wtedy każda z tych składowych jest grafem pełnym, jako że inaczej moglibyśmy dołożyć krawędzie w takiej niepełnej składowej, nie zmieniając przy tym liczb $k$ i $n$ . Pokażemy dodatkowo, że co najwyżej jedna z tych składowych może mieć więcej niż jeden wierzchołek. Istotnie, gdyby były dwie składowe $V_{1}, V_{2}$ o odpowiednio $n_{1} \geq n_{2} > 1$ wierzchołkach, to - nie zmieniając pozostałych składowych, i - przenosząc jeden wierzchołek z $V_{2}$ do $V_{1}$ otrzymalibyśmy nowy graf. W oryginalnym grafie sumaryczna liczba krawędzi w (pełnych) składowych $V_{1}, V_{2}$ wynosi $(\binom{n_{1}}{2}) + (\binom{n_{2}}{2})$ , a w nowym grafie te zmodyfikowane (również pełne) składowe posiadają łącznie $(\binom{n_{1} + 1}{2}) + (\binom{n_{2} - 1}{2})$ krawędzi. Różnica między nową a starą liczbą krawędzi wynosi więc

\frac{(n_{1} + 1) n_{1} + (n_{2} - 1) (n_{2} - 2) - n_{1} (n_{1} - 1) - n_{2} (n_{2} - 1)}{2} = n_{1} - n_{2} + 1 \geq 1

co pokazuje, że nowy graf ma przynajmniej o jedną krawędź więcej. Dowodzi to, że graf $𝐆$ maksymalizujący liczbę krawędzi ma opisaną przez nas własność. To z kolei oznacza, że $k - 1$ jego składowych ma po jednym elemencie, a pozostała składowa jest grafem pełnym o $n - (k - 1)$ elementach. Taki graf ma oczywiście $(\binom{n - k + 1}{2})$ krawędzi.

Aby zobaczyć, że podanych ograniczeń na liczbę krawędzi nie można poprawić zauważmy, że

graf o $k$ składowych spójnych, z których każda jest indukowaną ścieżką o liczności odpowiednio $n_{1}, n_{2}, \dots, n_{k}$ ma dokładnie $(n_{1} - 1) + (n_{2} - 1) + \dots + (n_{k} - 1) = | V | - k$ krawędzi.
rozważany w dowodzie graf o dokładnie $k$ składowych spójnych, z których $k - 1$ to wierzchołki izolowane, a pozostałe $| V | - k$ wierzchołków tworzy klikę $𝒦_{n - k}$ , ma dokładnie $\frac{(| V | - k) (| V | - k + 1)}{2}$ krawędzi.

Las to graf nie zawierający cykli jako podgrafy.

Drzewo to graf spójny nie zawierający cykli, czyli spójny las.

Liść drzewa to wierzchołek o stopniu $1$ .

Gwiazda to drzewo, w którym co najwyżej jeden wierzchołek nie jest liściem.

Drzewo rozpinające grafu $𝐆$ to podgraf grafu $𝐆$ zawierający wszystkie jego wierzchołki i będący drzewem.

Drzewa można zdefiniować na kilka równoważnych sposobów:

Twierdzenie 12.3

Dla grafu $𝐓 = (V, E)$ następujące warunki są równoważne:

$𝐓$ jest drzewem,
$𝐓$ nie zawiera cykli i ma $| V | - 1$ krawędzi,
$𝐓$ jest spójny i ma $| V | - 1$ krawędzi,
$𝐓$ jest spójny, zaś usunięcie dowolnej krawędzi tworzy dokładnie dwie składowe,
dowolne dwa wierzchołki grafu $𝐓$ są połączone dokładnie jedną drogą,
$𝐓$ nie zawiera cykli, lecz dodanie dowolnej nowej krawędzi tworzy dokładnie jeden cykl.

Dowód

Dowód przeprowadzimy indukcyjnie ze względu na liczbę wierzchołków $| V |$ grafu $𝐓$ . Oczywiście dla $| V | = 1$ graf $𝐓$ nie ma krawędzi i tym samym spełnia wszystkie sześć warunków dowodzonego Twierdzenia.

1. $\Rightarrow$ 2. Ponieważ $𝐓$ nie posiada cykli, to usunięcie krawędzi rozspaja $𝐓$ na dwa drzewa: pierwsze o $n_{1}$ wierzchołkach oraz drugie o $n_{2}$ , przy czym $n_{1} + n_{2} = | V |$ oraz $0 < n_{1}, n_{2} < | V |$ . Założenie indukcyjne gwarantuje, że nowo powstałe drzewa mają odpowiednio $n_{1} - 1$ oraz $n_{2} - 1$ krawędzi. Sumując te krawędzie wraz z usuniętą otrzymujemy

| E | = (n_{1} - 1) + (n_{2} - 1) + 1 = | V | - 1

2. $\Rightarrow$ 3. Jeżeli $𝐓$ nie byłby spójny, to miałby $k \geq 2$ składowych spójnych. Ponieważ żadna składowa nie ma cykli, założenie indukcyjne daje, że w każdej z $k$ składowych krawędzi jest o jedną mniej niż wierzchołków. A więc, w całym grafie krawędzi jest o $k \geq 2$ mniej niż wierzchołków co daje sprzeczność z $| E | = | V | - 1$ .

3. $\Rightarrow$ 4. Usunięcie dowolnej krawędzi spowoduje, że nowy graf będzie miał $| V | - 2$ krawędzie. Na mocy Twierdzenia 12.2 okazuje się, że jest to za mało aby graf był spójny.

4. $\Rightarrow$ 5. Jeżeli istniałyby dwie różne ścieżki $P_{1}$ oraz $P_{2}$ o wspólnym początku i końcu, to usunięcie krawędzi $e \in P_{1} - P_{2}$ nierozspajałoby grafu $𝐓$ .

5. $\Rightarrow$ 6. Pomiędzy dwoma punktami dowolnego cyklu $C$ istnieją dwie rozłączne ścieżki zawarte w $C$ . Tak więc istnienie dokładnie jednej ścieżki pomiędzy dowolnymi punktami w $𝐓$ wyklucza istnienie cykli w $𝐓$ . Z drugiej zaś strony dodanie dodatkowej krawędzi $u v$ stworzy cykl składający się z krawędzi $u v$ oraz ścieżki łączącej wierzchołek $u$ z $v$ zawartej w grafie $𝐓$ . Powyższy cykl jest jedyny. Wynika to z tego, że jeżeli istnieją dwa cykle zawierające krawędź $u v$ , to musi istnieć trzeci cykl niezawierajacy $u v$ , czyli zawarty w $𝐓$ co nie jest możliwe.

6. $\Rightarrow$ 1. Gdyby, mimo spełniania warunku 6, graf $𝐓$ nie był spójny, to dodanie jednej krawędzi łączącej dwa wierzchołki w różnych składowych spójnych nie utworzy cyklu.

Z charakteryzacji drzew podanej w Twierdzeniu 12.3 natychmiast dostajemy następujący związek miedzy liczbą krawędzi i wierzchołków w dowolnym lesie.

Wniosek 12.4

Każdy las $𝐆 = (V, E)$ o $k$ składowych spójnych posiada $| E | = | V | - k$ krawędzi.

@@ Linia 24: / Linia 24: @@
 czyli dwu-elementowych podzbiorów <math>V</math>.
-<div class="thumb tright"><div style="width:250px;">
+[[File:Grafy graf ogolny i prosty.mp4|250x250px|thumb|right|Graf ogólny (a.) oraz prosty (b.)]]
-<flashwrap>file=Grafy graf ogolny i prosty.swf|size=small</flashwrap>
-<div.thumbcaption>Graf ogólny (a.) oraz prosty (b.)</div></div>
-</div>
 {{uwaga|||
@@ Linia 51: / Linia 48: @@
 <center>
-<math>\displaystyle\sum_{v\in V}\mathsf{ deg}\ v=2\left\vert E \right\vert.
+<math>\sum_{v\in V}\mathsf{ deg}\ v=2\left\vert E \right\vert</math>
-</math>
 </center>
@@ Linia 67: / Linia 63: @@
 Jeśli <math>\mathbf{G}</math> miałby nieparzyście wiele wierzchołków o nieparzystym stopniu
-to suma <math>\displaystyle\sum_{v\in V}\mathsf{ deg}\ v</math> byłaby nieparzysta,
+to suma <math>\sum_{v\in V}\mathsf{ deg}\ v</math> byłaby nieparzysta,
 wbrew temu, że jest liczbą parzystą <math>2\left\vert E \right\vert</math>.
 }}
-<div class="thumb tleft"><div style="width:250px;">
+[[File:Grafy sciagniecie.mp4|250x250px|thumb|left|Ściągnięcie zbioru <math>\left\lbrace p,q,r \right\rbrace</math> do wierzchołku <math>x</math>]]
-<flashwrap>file=Grafy sciagniecie.swf|size=small</flashwrap>
-<div.thumbcaption>Ściągnięcie zbioru <math>\left\lbrace p,q,r \right\rbrace</math> do wierzchołku <math>x</math></div></div>
-</div>
-<div class="thumb tright"><div style="width:250px;">
+[[File:Grafy digraf.mp4|250x250px|thumb|right|(a.) Digraf oraz (b.) jego graf szkieletowy]]
-<flashwrap>file=Grafy digraf.swf|size=small</flashwrap>
-<div.thumbcaption>(a.) Digraf oraz (b.) jego graf szkieletowy</div></div>
-</div>
 {{uwaga|||
@@ Linia 102: / Linia 92: @@
 <center>
-<math>\mathbf{G}/\theta=\left( V/\theta,\left\lbrace \left\lbrace v/\theta,w/\theta \right\rbrace:\left\lbrace v,w \right\rbrace\in E \right\rbrace \right), </math>
+<math>\mathbf{G}/\theta=\left( V/\theta,\left\lbrace \left\lbrace v/\theta,w/\theta \right\rbrace:\left\lbrace v,w \right\rbrace\in E \right\rbrace \right)</math>
 </center>
@@ Linia 135: / Linia 125: @@
 ==Przegląd niektórych grafów==
-<div class="thumb tleft">
+[[File:Grafy antyklika.svg|250x250px|thumb|left|Antyklika <math>\mathcal{A}_{5}</math>]]
-<div style="width:250px;">
-<flash>file=Grafy antyklika.swf|width=250|height=250</flash>
-<div.thumbcaption>Antyklika <math>\mathcal{A}_{5}</math></div></div>
-<div style="width:250px;">
-<flash>file=Grafy dwudzielne.swf|width=250|height=250</flash>
-<div.thumbcaption>Graf nie będący dwudzielnym (a), niepełny graf dwudzielny (b)
-oraz pełny graf dwudzielny <math>\mathcal{K}_{3,4}</math> (c)</div></div>
-</div>
-<div class="thumb tright">
+[[File:Grafy dwudzielne.svg|250x250px|thumb|left|Graf nie będący dwudzielnym (a), niepełny graf dwudzielny (b)
-<div style="width:250px;">
+oraz pełny graf dwudzielny <math>\mathcal{K}_{3,4}</math> (c)
-<flash>file=Grafy klika.swf|width=250|height=250</flash>
-<div.thumbcaption>Klika <math>\mathcal{K}_{5}</math></div></div>
+[[File:Grafy klika.svg|250x250px|thumb|right|Klika <math>\mathcal{K}_{5}</math>]]
-<div style="width:250px;">
+[[File:Grafy planarne.mp4|250x250px|thumb|right|Graf nieplanarny(a) oraz graf planarny (b) wraz z jego prezentacją w postaci grafu płaskiego (c)]]
-<flashwrap>file=Grafy planarne.swf|size=small</flashwrap>
-<div.thumbcaption>Graf nieplanarny(a) oraz graf planarny (b) wraz z jego prezentacją w postaci grafu płaskiego (c)</div></div>
-</div>
 '''Graf pusty''' to graf bez krawędzi.
@@ Linia 200: / Linia 176: @@
 ==Ścieżki, Cykle, oraz Spójność==
 {{kotwica|marszruta||}}
-<div class="thumb tright"><div style="width:250px;">
+[[File:Grafy marszruta.mp4|250x250px|thumb|right|Grafy marszruta]]
-<flashwrap>file=Grafy marszruta.swf|size=small</flashwrap>
-<div.thumbcaption>Grafy marszruta</div></div>
-</div>
 '''Marszruta''' w grafie <math>\mathbf{G}</math> z wierzchołka <math>w</math> do wierzchołka <math>u</math>
@@ Linia 245: / Linia 218: @@
 jako podgraf
 <center><math>\mathbf{M}=\left( \mathsf{ V}\!\left(\mathbf{M}\right),\mathsf{ E}\!\left(\mathbf{M}\right) \right)
-:=\left( \left\lbrace v_0,\ldots,v_k \right\rbrace,\left\lbrace \left\lbrace v_0,v_1 \right\rbrace,\ldots,\left\lbrace v_{k-1},v_k \right\rbrace \right\rbrace \right).
+:=\left( \left\lbrace v_0,\ldots,v_k \right\rbrace,\left\lbrace \left\lbrace v_0,v_1 \right\rbrace,\ldots,\left\lbrace v_{k-1},v_k \right\rbrace \right\rbrace \right)</math></center>
-</math></center>
 '''Graf spójny''' to graf, w którym między dwoma dowolnymi wierzchołkami
@@ Linia 273: / Linia 245: @@
 }}
-<div class="thumb tright" id="grafy_spojne_skladowe"><div style="width:250px;">
+[[File:Grafy spojne skladowe.svg|250x150px|thumb|right|Grafy spójne skladowe]]
-<flash>file=Grafy spojne skladowe.swf|width=250|height=150</flash>
-<div.thumbcaption>Grafy spójne skladowe</div></div>
-</div>
 Graf z rysunku [[#grafy spojne skladowe|Grafy spojne skladowe]] ma trzy spójne składowe:
@@ Linia 294: / Linia 263: @@
-<center><math>\left\vert V \right\vert-k\leq \left\vert E \right\vert\leq\frac{(\left\vert V \right\vert-k)(\left\vert V \right\vert-k+1)}{2}.
+<center><math>\left\vert V \right\vert-k\leq \left\vert E \right\vert\leq\frac{(\left\vert V \right\vert-k)(\left\vert V \right\vert-k+1)}{2}</math></center>
-</math></center>
@@ Linia 317: / Linia 285: @@
 czyli rzeczywiście <math>n-k\leq m</math>.
-Dla dowodu górnego ograniczenia <math>m\leq (n-k)(n-k+1)/2 </math> na liczbę krawędzi
+Dla dowodu górnego ograniczenia <math>m\leq (n-k)(n-k+1)/2</math> na liczbę krawędzi
 załóżmy, że <math>\mathbf{G}</math> posiada <math>k</math> składowych spójnych
 i ma największą możliwą liczbę krawędzi wśród <math>n</math>-elementowych grafów
@@ Linia 332: / Linia 300: @@
 W oryginalnym grafie sumaryczna liczba krawędzi w (pełnych) składowych <math>V_1, V_2</math>
 wynosi
-<math>{{n_1}\choose{2}} + {{n_2}\choose{2}},
+<math>{{n_1}\choose{2}} + {{n_2}\choose{2}}</math>,
-</math>
 a w nowym grafie te zmodyfikowane (również pełne) składowe posiadają łącznie
 <math>{{n_1+1}\choose{2}} + {{n_2-1}\choose{2}}
@@ Linia 359: / Linia 326: @@
 }}
-<div class="thumb tleft"><div style="width:300px;">
+[[File:Grafy las.svg|300x150px|thumb|left|Drzewo (a); las nie będący drzewem ale z dwiema gwiazdami jako składowymi spójnymi (b);
-<flash>file=Grafy las.swf|width=300|height=150</flash>
+oraz graf nie będący lasem (c)]]
-<div.thumbcaption>Drzewo (a); las nie będący drzewem ale z dwiema gwiazdami jako składowymi spójnymi (b);
-oraz graf nie będący lasem (c)</div>
-</div></div>
 [[File:Grafy drzewo rozp.svg|250x250px|thumb|right|Drzewo rozpinające]]
@@ Linia 407: / Linia 371: @@
-<center><math>\left\vert E \right\vert=(n_1-1)+(n_2-1)+1=\left\vert V \right\vert-1.
+<center><math>\left\vert E \right\vert=(n_1-1)+(n_2-1)+1=\left\vert V \right\vert-1</math></center>
-</math></center>

Matematyka dyskretna 1/Wykład 12: Grafy: Różnice pomiędzy wersjami

Aktualna wersja na dzień 21:49, 11 wrz 2023

Czym jest graf

Przegląd niektórych grafów

Ścieżki, Cykle, oraz Spójność

Menu nawigacyjne

Działania na stronie

Opcje strony

Narzędzia osobiste

Nawigacja

Szukaj

Narzędzia