Delta 8/2024

Przeliczenia w grafach

Bartłomiej Bzdęga

matematyka kombinatoryka szkoła teoria grafów

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 $v w .$ 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}, \dots, w_{m}),$ że $E = {w_{0} w_{1}, w_{1} w_{2}, \dots, w_{m - 1} w_{m}} .$ Cyklem długości $m \geq 3$ – graf, którego wierzchołki można ułożyć w ciąg $(w_{1}, w_{2}, \dots, w_{m}),$ dla którego $E = {w_{1} w_{2}, w_{2} w_{3}, \dots, w_{m - 1} w_{m}, w_{m} w_{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}, \dots, v_{n}}$ oraz $d_{i} = \deg (v_{i})$ dla $i = 1, 2, \dots, n .$

Twierdzenie 1 (o uściskach dłoni). Zachodzi równość $d_{1} + d_{2} + \dots + d_{n} = 2 k .$

Dowód. ,,Przetnijmy” każdą krawędź na dwie półkrawędzie. Liczba wszystkich półkrawędzi jest oczywiście równa $2 k .$ 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} + \dots + d_{n} .$ $◻$

Niech $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}) + \dots + (\binom{d_{n}}{2}) = \sum_{1 \leq i < j \leq 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} .$ $◻$

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 \leq \frac{1}{4} n^{2} .$ (twierdzenie Mantela)

Wskazówka

Niech $v$ będzie wierzchołkiem z najwyższym stopniem, który oznaczymy przez $Δ .$ 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 - Δ .$ Każdy wierzchołek ze zbioru $B$ ma stopień co najwyżej $Δ .$ Suma stopni wierzchołków nie przekracza zatem $2 Δ (n - Δ) \leq \frac{1}{2} n^{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 $λ$ wspólnych sąsiadów oraz każde dwa niepołączone wierzchołki mają dokładnie $μ$ wspólnych sąsiadów (graf taki nazywamy silnie regularnym). Wykazać, że $(n - d - 1) μ = (d - λ - 1) d .$

Wskazówka

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ż $\frac{1}{9} n^{3}$ trójkolorowych trójkątów.

Wskazówka

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_{i} b_{i} + b_{i} c_{i} + c_{i} a_{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 $Δ_{23}^{3} .$
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 $\frac{1}{24} n (n - 1) (n - 5) .$ (twierdzenie Goodmana)

Wskazówka

Lepiej oszacować liczbę dwukolorowych trójkątów i odjąć ją od liczby wszystkich trójkątów, czyli $(\binom{n}{3}) .$ Liczba dwukolorowych trójkątów jest równa połowie liczby dwukolorowych ścieżek.

5. Dowieść, że $9 t^{2} \leq 2 k^{3} .$ (LVI OM)

Wskazówka

Niech $t_{i}$ będzie liczbą trójkątów, których jednym z wierzchołków jest $v_{i} .$ Wówczas $t_{i} \leq (\binom{d_{i}}{2}) \leq \frac{1}{2} d_{i}^{2},$ ale również $t_{i} \leq k - d_{i} \leq k .$ Stąd $t_{i} \leq \sqrt{\frac{1}{2} d_{i}^{2} k} = d_{i} \sqrt{k / 2} .$

6. Niech $G = (V, E),$ przy czym $V = A \cup B$ dla $A = {a_{1}, a_{2}, \dots, a_{n}}$ i $B = {b_{1}, b_{2}, \dots, b_{n}}$ oraz $A \cap B = \emptyset .$ Wiadomo, że w grafie $G$ każda krawędź jest postaci $a_{i} b_{j}$ i nie ma żadnego cyklu długości $4.$ Dowieść, że ten graf ma co najwyżej $\frac{1}{2} n (\sqrt{4 n - 3} + 1)$ krawędzi.

Wskazówka

Niech $d_{i} = \deg (a_{i})$ oraz $c_{i, j} = 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} \leq \sum_{i = 1}^{n} d_{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.

Afiliacja: Uniwersytet im. A. Mickiewicza w Poznaniu