Afiliacja: Uniwersytet im. A. Mickiewicza w Poznaniu
Grafem (prostym) nazywamy parę uporządkowaną \((V,E),\) w której \(V\) jest dowolnym niepustym zbiorem skończonym, natomiast \(E\) jest zbiorem wybranych dwuelementowych podzbiorów zbioru \(V.\) Bardziej po ludzku – mamy pewien zbiór \(V,\) którego elementy nazywamy wierzchołkami; elementy zbioru \(E,\) zwane krawędziami, interpretujemy jako połączenia wybranych par wierzchołków. Wierzchołki \(v\) i \(w,\) które są połączone krawędzią, nazywamy sąsiednimi. Często zamiast krawędź \(\{v,w\}\) piszemy po prostu \(vw.\) Liczbę sąsiadów wierzchołka \(v\) nazywamy jego stopniem i oznaczamy \(\deg(v).\)
Ścieżką długości \(m\) nazywamy graf, którego wierzchołki można ustawić w taki ciąg \((w_0,w_1,\ldots,w_m),\) że \(E=\{w_0w_1,w_1w_2,\ldots,w_{m-1}w_m\}.\) Cyklem długości \(m\ge3\) – graf, którego wierzchołki można ułożyć w ciąg \((w_1,w_2,\ldots,w_m),\) dla którego \(E=\{w_1w_2,w_2w_3,\ldots,w_{m-1}w_m,w_mw_1\}.\) Graf nazywamy pełnym lub kliką, jeśli każde dwa jego wierzchołki są połączone.
Graf \(G'=(V',E')\) nazywamy podgrafem grafu \(G=(V,E),\) jeśli \(V'\subseteq V\) i \({E'\subseteq E}.\) Mówiąc, dla przykładu, graf \(G\) ma cykl długości \(5\), mamy na myśli to, że pewien podgraf grafu \(G\) jest cyklem długości \(5.\) Podobnie przez liczbę ścieżek długości \(3\) w grafie \(G\) rozumiemy liczbę tych podgrafów grafu \(G,\) które są ścieżkami długości \(3.\)
Dalej, o ile nie napisano inaczej, przyjmujemy \(n=|V|\) oraz \(k=|E|\) dla danego grafu. Niech \(l\) oznacza liczbę ścieżek długości \(2\) w danym grafie, a \(t\) – liczbę trójkątów (cykli długości \(3\)). Stosujemy też konwencję \(V=\{v_1,v_2,\ldots,v_n\}\) oraz \(d_i=\deg(v_i)\) dla \(i=1,2,\ldots,n.\)
Twierdzenie 1 (o uściskach dłoni). Zachodzi równość \(d_1+d_2+\ldots+d_n=2k.\)
Dowód. ,,Przetnijmy” każdą krawędź na dwie półkrawędzie. Liczba wszystkich półkrawędzi jest oczywiście równa \(2k.\) Z drugiej strony, każdy wierzchołek \(v_i\) jest jedynym końcem \(d_i\) półkrawędzi, więc liczba półkrawędzi jest równa \(d_1+d_2+\ldots+d_n.\) \(\square\)
Niech \(\operatorname{com}(v_i,v_j)=c_{i,j}\) oznacza liczbę wspólnych sąsiadów wierzchołków \(v_i\) i \(v_j.\)
Twierdzenie 2. Zachodzą równości: \(l=\binom{d_1}2+\binom{d_{2}}2+\ldots+\binom{d_n}2 = \sum_{1\le i<j\le n} c_{i,j}.\)
Dowód. Pierwsza równość wynika z tego, że liczbą ścieżek ze środkowym wierzchołkiem \(v_i\) jest \(\binom{d_i}2.\) Druga – z tego, że liczbą ścieżek z końcami \(v_i\) i \(v_j\) jest \(c_{i,j}.\) \(\square\)
Wiele zadań na Olimpiadzie Matematycznej można wysłowić w języku grafów, zwłaszcza te o połączeniach drogowych miast, przyjaźniach w pewnej grupie osób itp. Początkującemu w tej materii Czytelnikowi polecam, jako cenne ćwiczenie, dokonać przeglądu zadań OM/OMJ, znaleźć te o grafowej naturze i je ,,przetłumaczyć”.
Zadania
1. Wykazać, że jeśli w grafie nie ma trójkątów, to \(k\le\frac14n^2.\) (twierdzenie Mantela)
Niech \(v\) będzie wierzchołkiem z najwyższym stopniem, który oznaczymy przez \(\Delta.\) Podzielmy wierzchołki na dwa zbiory: \(A\) – wszyscy sąsiedzi \(v\) oraz \(B\) – wierzchołki niewystępujące w \(A\) (dla jasności, \(v\in B\)). Wierzchołki w zbiorze \(A\) nie mogą sąsiadować, więc każdy z nich ma stopień co najwyżej \(|B|=n-\Delta.\) Każdy wierzchołek ze zbioru \(B\) ma stopień co najwyżej \(\Delta.\) Suma stopni wierzchołków nie przekracza zatem \(2\Delta(n-\Delta)\le\frac 12n^2\) i wystarczy teraz skorzystać z twierdzenia 1.
2. Dany jest graf o \(n\) wierzchołkach, w którym każdy wierzchołek ma stopień \(d,\) każde dwa połączone wierzchołki mają dokładnie \(\lambda\) wspólnych sąsiadów oraz każde dwa niepołączone wierzchołki mają dokładnie \(\mu\) wspólnych sąsiadów (graf taki nazywamy silnie regularnym). Wykazać, że \({(n-d-1)\mu=(d-\lambda-1)d}.\)
Obliczyć na dwa sposoby liczbę ścieżek długości \(2\) i porównać otrzymane wyniki.
3. Każda krawędź danego grafu pełnego jest czerwona, zielona lub niebieska. Udowodnić, że w tym grafie jest mniej niż \(\frac19n^3\) trójkolorowych trójkątów.
Liczba trójkolorowych trójkątów nie przekracza jednej trzeciej liczby
dwukolorowych ścieżek długości \(2\) (dlaczego?). Liczba tych ścieżek jest równa
\(\sum_{i=1}^n(a_ib_i+b_ic_i+c_ia_i),\) przy czym \(a_i,\) \(b_i,\) \(c_i\) oznaczają,
odpowiednio, stopień wierzchołka \(v_i\) w podgrafie czerwonym, zielonym,
niebieskim. Pozostaje wykazać, że każdy ze składników jest mniejszy od
\(\frac{1}{3}n^2,\) w czym może przydać się
KPO z \(\Delta^{3}_{23}.\)
Ciekawostka. Niedawno udowodniono, że optymalną
stałą jest \(\frac 1{15}.\) Wykorzystano nowe i potężne narzędzie – algebry
flagowe.
(Rainbow triangles in three-colored graphs, Journal of Combinatorial Theory, B, Vol. 126, 2017, 83–113)
4. Każda krawędź danego grafu pełnego jest czerwona lub niebieska. Udowodnić, że liczba jednokolorowych trójkątów w tym grafie jest równa co najmniej \(\frac1{24}n(n-1)(n-5).\) (twierdzenie Goodmana)
Lepiej oszacować liczbę dwukolorowych trójkątów i odjąć ją od liczby wszystkich trójkątów, czyli \(\binom n3.\) Liczba dwukolorowych trójkątów jest równa połowie liczby dwukolorowych ścieżek.
5. Dowieść, że \(9t^2\le 2k^3.\) (LVI OM)
Niech \(t_i\) będzie liczbą trójkątów, których jednym z wierzchołków jest \(v_i.\) Wówczas \(t_i\le\binom{d_i}2\le\frac 12d_i^2,\) ale również \(t_i\le k-d_i\le k.\) Stąd \(t_i \le \sqrt{\frac 12d_i^2k} = d_i\sqrt{k/2}.\)
6. Niech \(G=(V,E),\) przy czym \(V=A\cup B\) dla \(A=\{a_1,a_2,\ldots,a_n\}\) i \(B=\{b_1,b_2,\ldots,b_n\}\) oraz \(A\cap B=\emptyset.\) Wiadomo, że w grafie \(G\) każda krawędź jest postaci \(a_ib_j\) i nie ma żadnego cyklu długości \(4.\) Dowieść, że ten graf ma co najwyżej \(\frac12n(\sqrt{4n-3}+1)\) krawędzi.
Niech \(d_i=\deg(a_i)\) oraz \(c_{i,j}=\operatorname{com}(b_i,b_j).\)
Brak cyklu długości \(4\) jest równoważny temu, że
\(c_{i,j}\leq 1\) dla wszystkich \(i,\) \(j.\) Liczba
ścieżek długości \(2\) o środku w zbiorze \(A\) jest taka sama, jak liczba ścieżek
długości \(2\) o końcach w zbiorze \(B.\)
Obserwacje te prowadzą nas do nierówności
\(\sum_{i=1}^n d_i^2-\sum_{i=1}^n d_i \leq n^2-n.\)
Na mocy nierówności między średnią arytmetyczną i kwadratową oraz twierdzenia 1 otrzymujemy \(\frac{k^2}n \le \sum_{i=1}^nd_i^2.\)
Ciekawostka. Dokładne
wyznaczanie największej możliwej liczby krawędzi w takim grafie jest
bezpośrednio związane z konstruowalnością skończonych płaszczyzn rzutowych –
bardzo ważnym i trudnym zagadnieniem z pogranicza geometrii, kombinatoryki,
teorii liczb i algebry.