W1: 04.10.2021: Pojęcie grafu

1. Graf ogólny (multigraf): trójka $(V,E,\phi)$: taka, że $\phi:E\to [V]^{\leq 2}\setminus\emptyset$
2. Graf (graf prosty): taki graf, że $(V,E,\phi)$, że $(\forall e\in E)(|\phi(e)|=2)$ i $\phi$ jest różnowartościowa
3. Równoważna definicja grafu prostego: para $(V,E)$ taka, że $E\subseteq [V]^2$
4. Stopień (rząd) wierzchołka: $$ deg(v) = 2 |\{e\in E: \phi(e)=\{v\}\}| + |\{e\in E: |\phi(e)|=2 \land v \in \phi(e)\}| $$
5. Twierdzenie (Euler) Dla dowolnego grafu ogólnego $(V,E,\phi)$ mamy
   $$\sum_{v\in V} \deg(v) = 2\cdot|E|$$
6. Wniosek: $|\{v\in V: \neg (2|\deg(v))\}|$ jest liczbą parzystą

W2: 11.10.2021: Pojęcia wstępne, oznaczenia

1. Pojęcie izomorfizmu grafów.
2. Fakt (bez dowodu): liczba grafów prostych o zbiorze wierzchołków $\{1,\ldots,n\} (=[n])$ jest asymptotycznie równa $2^{\binom{n}{2}}/n!$
3. Przyklady grafów:
   1. graf zupełny: $K_n = ([n],[n]^2)$
   2. graf pusty: $E_n = ([n],\emptyset)$
   3. graf cykliczny: $C_n = ([n],\{\{1,2\},\{2,3\},\ldots, \{n-1,n\},\{n,1\}\})$
   4. Scieżka (graf liniowy): $P_n = ([n],\{\{1,2\},\{2,3\},\ldots, \{n-1,n\}\})$
   5. graf $(V,E)$ jest dwudzielny, jaśli istnieje rozbicie $X\cup Y = V$ ($X\cap Y = \emptyset$) takie, że $E \subseteq \{\{x,y\}:x\in X \land y\in Y\}$.
   6. $K_{n,m} = ([n+m],\{\{x,y\}: 1\leq x \leq n \land n \land n \lt y\leq n+m\})$.
4. Obserwacja: graf $K_{m,m}$ ma $2m (= n)$ wierzchołków oraz $n^2/4$ krawędzi
5. Tw. Jeśli $(V,E)$ jest grafem prostym, to $$\sum_{\{x,y\}\in E}(deg(x)+deg(y)) = \sum_{x\in V} deg^2(x)$$
6. Tw. Jeśli graf prosty $(V,E)$ nie zawiera trójkątów, to $|E| \leq |V|^2/4$
7. Definicje:
   1. Trasa w grafie: ciąg $x_1e_1x_2e_2\ldots x_{k-1}e_{k-1}x_k$ takie, że $\gamma(e_i) = \{x_i,x_{i+1}\}$ dla $i=1,\ldots,k-1$
   2. Ścieżka: trasa bez powtórzeń krawędzi
   3. Droga: trasa bez powtórzonych wierzchołków.
8. Odległość w grafie: $d(x,y)$ = najkrótsza długość drogi od $x$ do $y$ (lub d(x,y) = $\infty$, jeśli nie ma takiej drogi)
9. Fakt: relacja $x\sim y \IFF d(x,y) \lt \infty$ jest relacją równoważności na zbiorzez wierzchołków $V$. Jej klasy abstrakcji nazywamy składowymi spójnymi grafu.
10. Def. Graf jest spójny jeśli ma tylko jedną składową spójną.
11. Fakt. Jeśli graf $(V,E)$ jest spójny, to para $(V,d)$ jest przestrzenią metryczną.
12. Definicje:
    1. Pętla: taka ścieżka $x_1e_1x_2e_2\ldots x_{k-1}e_{k-1}x_k$, że $x_k = x_1$
    2. Cykl: taka pętla $x_1e_1x_2e_2\ldots x_{k-1}e_{k-1}x_k$, że $x_i \neq x_j$ dla wszystkich $1\leq i \lt j \leq n-1$
13. Definicje:
    1. LAS: graf bez pętli (graf acykliczny)
    2. DRZEWO: graf spójny acykliczny

W3: 18.10.2021: Drzewa

1. Fakt: w każdym drzewie jest liść (wierzchołek o rzędzie 1)
2. Fakt: w drzewie pomiędzy dowolnymi różnymi wierzchołkami istnieje dokładnie jedna droga
3. Następujące własności grafu $\mathcal{G} = (V,E)$ są równoważne

   1. $\mathcal{G}$ jest drzewem
   2. $\mathcal{G}$ jest spójny i $|E| = |V|-1$
   3. $\mathcal{G}$ jest spójny i usunięcie dowolnej krawędzi rozspójnia go
   4. $\mathcal{G}$ jest acykliczny i dodanie dowolnej krawędzi produkuje cykl
4. Wniosek: Jeśli $(V,E)$ na $k$ składowych i $|V|=n$, to $n-k\leq |E| \leq \binom{n-k+1}{2}$

W4: 25.10.2021: Algorytmy wyznaczania drzew rozspinających

1. Algorytm Kruskala
2. Algorytm Priama
3. Grafy eulerowskie; na razie mamy dowód w jedną stronę: w grafie eulerowskim każdy wierzchołek ma rząd parzysty
4. Obejrzyjcie Graph Theory: Euler Paths and Euler Circuits

W5: 8.11.2021: Grafy eulerowskie

1. Def. Graf jest parzysty, jeśli rząd każdego wierzchołka jest liczbą parzystą.
2. Tw. Jeśli $(G,E)$ jest parzysty, to można rozbić $E$ na zbiory $E_1,\ldots,E_k$ tak, że dla każdego $i$ graf $(X,E_i)$ jest cyklem.
3. Tw. Graf jest eulerowski wtedy i tylko wtedy, gdy jest spójny i parzysty
4. Wniosek: Graf jest pół-eulerowski wtedy i tylko wtedy, gdy jest spójny i dokładnie dwa wierzchołki mają rząd nieparzysty.
5. Def. $E(X,Y) = \{e\in E: \gamma(e)\cap X \neq\emptyset \land \gamma(e)\cap Y \neq\emptyset\}$
6. Def. co-brzeg: $\partial(X) = E(X,X^c)$
7. Tw. Graf jest parzysty IFF $(\forall X\subseteq V)(2|card(\partial(X)))$
8. Def. MOST $\equiv$ taka krawędź $e$, że $c(G\setminus e)>c(G)$,
   gdzie $c(G)$ oznacza liczbę komponent grafu $G$.
9. $e$ nie jest mostem IFF $e$ występuje na cyklu
10. Wniosek: w grafie parzystym nie ma mostów
11. Algorytm Fleury'ego wyznaczania cyklu Eulera (zwięzły opis: UNIKAJ MOSTÓW JAK DLUGO SIĘ DA);
    dowód poprawności: następny wykład.

W6: 22.11.2021: Grafy eulerowskie

1. Dowód poprawności algorytmu Fleury'ego
2. Tw. Graf jest dwudzielny wtedy i tylko wtedy, gdy każdy cykl w tym grafie ma długość parzystą
3. Def. Niech $G = (V,E)$ będzie grafem spójnym. Definiujemy
   1. $ \kappa(G) = \begin{cases} n-1 &: G \cong K_n \\ \min\{|X|: X\subseteq V \land G\setminus X \text{nie jest spójny}\} &: \text{w przeciwnym przypadku}\end{cases} $
   2. $ \lambda(G) = \min\{|F|: F\subseteq E \land (V,E\setminus F) \text{ nie jest spójny}\}. $
   3. $ \delta(G) = =\min\{deg(v):v\in V\} $
4. Tw. $\kappa(G) \leq \lambda(G) \leq \delta(G) (=\min\{deg(v):v\in V\})$
5. Pojęcie grafu Hamiltonowskiego

W7: 29.11.2021: Grafy hamiltonowskie

1. Uwaga: problem "czy dany graf grafem hamiltonowskim" jest problemem NP trudnym. W przyszłości omówimy to zagadnienie i pokażemy jak ten problem możemy sprowadzić do problemu spełnialności formuł boolowskich.
2. Tw (Ore) Niech $G=(V,E)$ będzie grafem prostym. Załóżmy że dla dowolnych dwóch różnych wierzchołków $x$ i $y$ takiech, że $xy\notin E$ mamy $$ deg(x) + deg(y) \geq |V|~.$$ Wtedy graf $G$ jest hamiltonowski.
3. Pojęcie grafu planarnego
4. Twierdzenie Jordana
5. Tw. Grafy $K_{3,3}$ oraz $K_5$ nie są planarne

29.11.2021: Grafy planarne

1. Kilka pojęć pomocniczych
   • Krzywa w $\RR^n$: dowolne ciągłe odwzorowanie $\gamma:[a,b]\to\RR^n$ ($a\lt b$).
     Bez straty ogólności możemy zakładać, że $[a,b]=[0,1]$
   • Krzywa Jordana: taka krzywa $\gamma:[a,b]\to\RR^n$, że $\gamma(a)=\gamma(b)$ oraz że $\gamma$ jest różnowartościowe na $(a,b)$. Wyobrażać ją sobie możemy jaka pętlę bez przecięć.
   • Twierdzenie o krzywej Jordana: Każda krzywa Jordana rozdziela płaszczyznę na dwa rozłączne obszary i jest ich wspólnym brzegiem.
     Nie będziemy dowodzili tego twierdzenia. Wbrew pozorom dowod tego twierdzenia jest dosyć trudny (znacznie się upraszcza jeśli założymy coś na temat regularności krzywej, np. że jest ciągle różniczkowalna).
2. Def: Graf $G=(V,E,\phi)$ jest planarny jeśli jego wierzchołki możemy przedstawić punkty płaszczyzny, a krawędzie jako krzywe na płaszczyżnie łączace wierzchołki, przy czym punktami wspólnymi dwóch różnych krawędzi mogą być tylko ich końcowe wierzchołki.
   
3. TW [Euler] Jeśli $G$ jest grafem planarnym, $F$ oznacza liczbę ścian, $E$ - liczbę krawędzi i $V$ liczbę wierzchołków, to
   $$F - E + V = 2 $$

06.12.2021: Twierdzenia Kuratowskiego i Robertsona - Seymoura

15.12.2021: Twierdzenie Mengera

1. DEF: Niech $A,B\subseteq V$. $(A,B)$-scieżką nazywamy drogę $x_0,x_1,\ldots,x_{n-1},x_n$ w grafie taką, że $x_0\in A$, $x_n\in B$ oraz $\{x_1,\ldots,x_{n-1}\}\cap (A\cup B) = \emptyset$.
   Uwaga: jeśli $A\cap B \neq \emptyset$ i $c\in A\cap B$, to ciąg $(c)$ jest $(A,B)$-ścieżką długości 0.
2. DEF: Niech $A,B\subseteq V$. $(A,B)$-konektorem nazywamy dowolny zbiór parami rozłącznych $(A,B)-ścieżek.
3. DEF: Niech $A,B\subseteq V$. $(A,B)$-separatorem nazywamy dowolny zbiór wierzchołków $X$, taki, że dla dowolnej $(A,B)$-ścieżki $P$ mamy $P\cap X\neq \emptyset$.
4. Oznaczenia. Dla grafu prostego $G$ definiujemy:
   1. $\lambda_G(A,B)$: największa moc $(A,B)-konektora
   2. $\kappa_G(A,B)$: najmniejszą mocą $(A,B)$-separatora.
5. Wniosek. Jeśli $G=(V,E)$ jest grafem prostym oraz $A,B\subseteq V$ to $\lambda_G(A,B) \leq \kappa_G(A,B)$.
6. Twierdzenie [Menger]. Jeśli $G=(V,E)$ jest grafem prostym oraz $A,B\subseteq V$ to $$\lambda_G(A,B) = \kappa_G(A,B)~.$$
7. Wniosek [Tw. Hall'a o małżeństwach] Niech $G$ będzie grafem dwudzielnym o rozbiciu $A, B$. Następujęce warunki są równoważne:
   1. istnieje różnowartościwa $f:A\to B$, taka, że $(\forall a\in A)(\{a,f(a)\} \in E(G))$
   2. $(\forall X \subseteq A)(|X| \leq |\mathcal{N}(X)|)$
   Uwaga: warunek (1) można wysłowić następująco: istnieje $A$ - doskonałe skojarzenie