Ocena oparta będzie na ocenie uzyskanej z ćwiczeń (uwzględniania będzie aktywność + wyniki dwóch kolokwiów). Kto będzie chciał uzyskać wyższą ocenę, to będzie się musiał umówić ze mną na egzamin ustny (pewnie na Teams).
Literatura
R. J. Wilson, Wprowadzenie to Teorii Grafów, PWN,
Bela Bollobas, Modern Graph Theory, Springer,
J.A. Bondy U.S.R. Murty, Graph Theory, Springer,
Lista zadań: ostatnia wersja: 11.01.2022 (lista ta będzie rozbudowywana)
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\}.
K_{n,m} = ([n+m],\{\{x,y\}: 1\leq x \leq n \land n \land n \lt y\leq n+m\}).
Obserwacja: graf K_{m,m} ma 2m (= n) wierzchołków oraz n^2/4 krawędzi
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)
Tw. Jeśli graf prosty (V,E) nie zawiera trójkątów, to |E| \leq |V|^2/4
Definicje:
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
Ścieżka: trasa bez powtórzeń krawędzi
Droga: trasa bez powtórzonych wierzchołków.
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)
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.
Def. Graf jest spójny jeśli ma tylko jedną składową spójną.
Fakt. Jeśli graf (V,E) jest spójny, to para (V,d) jest przestrzenią metryczną.
Definicje:
Pętla: taka ścieżka x_1e_1x_2e_2\ldots x_{k-1}e_{k-1}x_k, że x_k = x_1
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
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.
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.
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).
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.
TW [Euler]
Jeśli G jest grafem planarnym, F oznacza liczbę ścian, E - liczbę krawędzi i V liczbę wierzchołków, to
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.
DEF: Niech A,B\subseteq V. (A,B)-konektorem nazywamy dowolny zbiór parami rozłącznych $(A,B)-ścieżek.
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.
Oznaczenia. Dla grafu prostego G definiujemy:
\lambda_G(A,B): największa moc $(A,B)-konektora
\kappa_G(A,B): najmniejszą mocą (A,B)-separatora.
Wniosek. Jeśli G=(V,E) jest grafem prostym oraz A,B\subseteq V to \lambda_G(A,B) \leq \kappa_G(A,B).
Twierdzenie [Menger]. Jeśli G=(V,E) jest grafem prostym oraz A,B\subseteq V to \lambda_G(A,B) = \kappa_G(A,B)~.
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:
istnieje różnowartościwa f:A\to B, taka, że (\forall a\in A)(\{a,f(a)\} \in E(G))
(\forall X \subseteq A)(|X| \leq |\mathcal{N}(X)|)
Uwaga: warunek (1) można wysłowić następująco: istnieje A - doskonałe skojarzenie