Strona główna › Statystyka i prawdopodobieństwo › Grafy — definicje, własności, przykłady

Grafy — definicje, własności, przykłady

Graf to kropki połączone kreskami — i tyle wystarczy, żeby opisać sieć dróg, znajomości w klasie, mecze w turnieju albo ruchy skoczka szachowego. Siła tego pojęcia bierze się stąd, że kształt rysunku nie ma znaczenia: liczy się wyłącznie, co jest z czym połączone. Dlatego zadania, które wyglądają na zliczanie po omacku, po narysowaniu grafu stają się oczywiste.

Dział: Statystyka i prawdopodobieństwoPoziom: liceum — poza podstawą od 2025

1Słownik: wierzchołki, krawędzie, stopnie

Graf składa się z wierzchołków (kropek) i krawędzi (połączeń między nimi).

pojęcieco znaczyprzykład z życia
wierzchołekpojedynczy obiektosoba, miasto, drużyna
krawędźpołączenie dwóch wierzchołkówznajomość, droga, rozegrany mecz
stopień wierzchołkaliczba krawędzi z niego wychodzącychliczba znajomych danej osoby
graf spójnyz każdego wierzchołka da się dojść do każdegosieć bez odciętych wysp
cykldroga wracająca do punktu wyjścia bez powtórektrasa okrężna

Najważniejsza jest myśl ze środka wstępu — ta o tym, że liczy się wyłącznie, co jest z czym połączone: graf to informacja o połączeniach, a nie rysunek. Ten sam graf można narysować na wiele sposobów — z przecinającymi się krawędziami albo bez — i nadal będzie tym samym grafem.

Co wolno, a czego nie w rysunku

Krawędzie wolno rysować krzywo, długość i kąty nie znaczą nic.

Przecięcie dwóch krawędzi nie jest wierzchołkiem — to tylko efekt rysowania na płaskiej kartce.

Dwa rysunki przedstawiają ten sam graf, jeśli da się je „przenumerować” tak, żeby zgadzały się wszystkie połączenia.

2Lemat o uściskach dłoni

To pierwsze prawdziwe twierdzenie o grafach i jednocześnie najczęściej używane narzędzie w zadaniach.

suma stopni wszystkich wierzchołkoˊw=2⋅liczba krawędzi\text{suma stopni wszystkich wierzchołków} = 2 \cdot \text{liczba krawędzi}

Dowód mieści się w jednym zdaniu: każda krawędź ma dwa końce, więc licząc stopnie, liczymy każdą krawędź dokładnie dwa razy.

Wynika stąd wniosek, który bywa całą treścią zadania:

Wierzchołków nieparzystego stopnia jest parzyście wiele

Suma wszystkich stopni jest parzysta, bo równa się podwojonej liczbie krawędzi.

Stopnie parzyste sumują się do liczby parzystej, więc reszta — czyli stopnie nieparzyste — też musi dawać sumę parzystą.

A suma liczb nieparzystych jest parzysta dokładnie wtedy, gdy jest ich parzyście wiele.

Praktycznie: nie istnieje towarzystwo, w którym dokładnie trzy osoby mają nieparzystą liczbę znajomych.

Z lematu wynika też szybki test niemożliwości: jeśli w zadaniu suma podanych stopni jest nieparzysta, taki graf po prostu nie istnieje i nie ma czego szukać.

3Drzewa i cykle

Drzewo to graf spójny bez cykli — czyli taki, w którym między każdymi dwoma wierzchołkami istnieje dokładnie jedna droga.

drzewo o n wierzchołkach ma dokładnie n−1 krawędzi\text{drzewo o } n \text{ wierzchołkach ma dokładnie } n-1 \text{ krawędzi}

Ten wzór też ma jednozdaniowe uzasadnienie: zaczynamy od jednego wierzchołka i za każdym razem, gdy dokładamy nowy, musimy dołożyć dokładnie jedną krawędź — mniej rozspójniłoby graf, więcej utworzyłoby cykl.

Drugim skrajnym przypadkiem jest graf pełny, w którym każde dwa wierzchołki są połączone. Liczba jego krawędzi to liczba par, czyli dokładnie tyle, ile wynosi liczba uścisków dłoni w kombinatoryce:

graf pełny o n wierzchołkach ma n(n−1)2 krawędzi\text{graf pełny o } n \text{ wierzchołkach ma } \frac{n(n-1)}{2} \text{ krawędzi}

Te dwa wzory wyznaczają widełki: graf spójny o nn wierzchołkach ma od n−1n-1 do n(n−1)2\frac{n(n-1)}{2} krawędzi.

4Czy grafy są na maturze

Nie. Słowo „graf” nie występuje w podstawie programowej z matematyki od 2025 roku — sprawdziłem cały dokument.

Jak zawsze warto rozdzielić dwa pytania:

  1. Czy to jest w wymaganiach? Nie ma i żadne zadanie maturalne z matematyki tego nie sprawdzi.
  2. Czy warto to znać? Tak — grafy są podstawowym narzędziem informatyki (sieci, drogi, zależności), pojawiają się w zadaniach konkursowych i olimpijskich, a w zwykłych zadaniach kombinatorycznych bywają najszybszą drogą do wyniku.

Ostatni punkt jest najbardziej praktyczny: zadania o „uściskach dłoni”, „meczach każdy z każdym” czy „liczbie przekątnych wielokąta” to te same zadania — a graf pokazuje, dlaczego wszystkie mają jeden wzór.

W podstawie programowej z informatyki grafy są wymienione wprost, więc uczeń liceum spotyka je na lekcjach — tylko w innym przedmiocie niż matematyka.

5Przykłady krok po kroku

Cztery zadania: zliczanie krawędzi z lematu, graf niemożliwy, drzewo oraz klasyczne zadanie o przekątnych rozwiązane grafem.

Przykład 1 Ile krawędzi ma graf

W pewnej grupie każda z  10\,10 osób zna dokładnie 33 inne osoby (znajomość jest wzajemna). Ile jest par znajomych?

  1. Buduję graf: wierzchołki to osoby, krawędzie to znajomości. Każdy wierzchołek ma stopień 3\textcolor{#16A06A}{3}.
  2. Suma stopni: 10⋅3=3010 \cdot 3 = 30.
  3. Z lematu o uściskach dłoni suma stopni to podwojona liczba krawędzi, więc krawędzi jest 302=15\frac{30}{2} = \textcolor{#E0453A}{15}.
  4. Kontrola parzystości: suma stopni wyszła parzysta, więc taki graf w ogóle może istnieć ✓
  5. Kontrola widełkami: graf pełny na 1010 wierzchołkach miałby 10⋅92=45\frac{10 \cdot 9}{2} = 45 krawędzi, a spójny co najmniej 99. Liczba 1515 mieści się w tym przedziale ✓
  6. Kontrola sensu: gdyby każdy znał każdego, stopnie wynosiłyby 99, a nie 33 — mniejszy stopień to mniej krawędzi ✓

Odpowiedź: 1515 par znajomych.

Dzielenie przez dwa jest tu całą treścią zadania. Odpowiedź „3030” liczyłaby każdą znajomość dwa razy — raz z perspektywy każdej z dwóch osób.

Przykład 2 Graf, który nie istnieje

Czy w grupie 55 osób każda może znać dokładnie 33 inne?

  1. Suma stopni wynosiłaby 5⋅3=155 \cdot 3 = \textcolor{#16A06A}{15}.
  2. Z lematu suma stopni musi być parzysta, bo równa się podwojonej liczbie krawędzi.
  3. Liczba 1515 jest nieparzysta, więc taki graf nie istnieje ✓
  4. Kontrola drugą drogą: liczba krawędzi wyszłaby 152=7,5\frac{15}{2} = 7{,}5, a krawędzi nie da się mieć połowy ✓
  5. Kontrola wnioskiem o nieparzystych stopniach: wszystkie 55 wierzchołków miałoby stopień nieparzysty, a takich wierzchołków musi być parzyście wiele — pięć to liczba nieparzysta ✓
  6. Kontrola przez modyfikację: dla 66 osób po 33 znajomych suma wynosi 1818, czyli krawędzi jest 99 — i taki graf już istnieje ✓

Odpowiedź: Nie istnieje.

To najkrótszy typ dowodu w teorii grafów: pokazujemy, że pewna liczba musiałaby być jednocześnie parzysta i nieparzysta. Nie trzeba niczego rysować ani sprawdzać przypadków.

Przykład 3 Drzewo

Sieć wodociągowa łączy 1212 budynków tak, że z każdego można dojść do każdego, a rur jest jak najmniej. Ile jest rur? Co się stanie po dołożeniu jednej?

  1. „Można dojść do każdego” oznacza graf spójny, a „jak najmniej” — brak cykli. To definicja drzewa.
  2. Drzewo o n=12n = \textcolor{#16A06A}{12} wierzchołkach ma n−1n - 1 krawędzi, czyli 11\textcolor{#E0453A}{11} rur.
  3. Kontrola stopniami: suma stopni wynosi 2⋅11=222 \cdot 11 = 22, więc średni stopień to 2212\frac{22}{12}, czyli mniej niż 22 ✓ — w drzewie o co najmniej dwóch wierzchołkach zawsze są co najmniej dwa wierzchołki stopnia 11, czyli budynki z jedną tylko rurą.
  4. Po dołożeniu dwunastej rury krawędzi jest więcej niż n−1n-1, więc powstaje cykl ✓
  5. Kontrola sensu: cykl oznacza, że do jednego budynku prowadzą dwie różne drogi — sieć staje się odporna na awarię, ale przestaje być najtańsza ✓
  6. Kontrola widełkami: sieć pełna miałaby 12⋅112=66\frac{12 \cdot 11}{2} = 66 rur, czyli sześć razy więcej ✓

Odpowiedź: 1111 rur; dołożenie dwunastej tworzy cykl.

Ta sama liczba n−1n-1 opisuje minimalną sieć dróg, minimalną liczbę meczów w turnieju pucharowym i liczbę cięć potrzebnych do podzielenia czekolady. To nie przypadek — wszystkie te zadania są o drzewach.

Przykład 4 Przekątne wielokąta jako graf

Ile przekątnych ma dwunastokąt wypukły?

  1. Wierzchołki wielokąta to wierzchołki grafu, a wszystkie odcinki między nimi to krawędzie grafu pełnego.
  2. Graf pełny na n=12n = \textcolor{#16A06A}{12} wierzchołkach ma 12⋅112=66\frac{12 \cdot 11}{2} = 66 krawędzi.
  3. Te odcinki to boki i przekątne razem. Boków jest 12\textcolor{#16A06A}{12}.
  4. Przekątnych: 66−12=5466 - 12 = \textcolor{#E0453A}{54}.
  5. Kontrola wzorem szkolnym: n(n−3)2=12⋅92=54\frac{n(n-3)}{2} = \frac{12 \cdot 9}{2} = 54 ✓
  6. Kontrola na małym przypadku: dla n=4n = 4 graf pełny ma 66 krawędzi, boków są 44, więc przekątne 22 — i rzeczywiście kwadrat, jak każdy czworokąt, ma dwie przekątne ✓
  7. Kontrola na trójkącie: 33 krawędzie minus 33 boki daje 00 przekątnych ✓

Odpowiedź: 5454 przekątne.

Szkolny wzór n(n−3)2\frac{n(n-3)}{2} przestaje być czymś do zapamiętania: to po prostu wszystkie pary wierzchołków minus boki. Graf pokazuje, skąd bierze się każdy jego składnik.

6Najczęstsze błędy

Błędy pierwszy, czwarty i piąty dotyczą liczenia krawędzi, drugi — czytania rysunku, trzeci — pochopnego założenia, że graf o zadanych stopniach w ogóle istnieje.

Podanie sumy stopni jako liczby krawędzi.

Skąd się bierze: Suma stopni jest tym, co liczy się bezpośrednio z danych.

Jak zrobić dobrze: Każda krawędź ma dwa końce, więc krawędzi jest połowa sumy stopni. Przy dziesięciu osobach po trzech znajomych wychodzi 1515, a nie 3030.

Uznanie przecięcia krawędzi na rysunku za wierzchołek.

Skąd się bierze: Na kartce wygląda jak skrzyżowanie.

Jak zrobić dobrze: Wierzchołki to tylko zaznaczone kropki. Ten sam graf da się zwykle narysować bez przecięć — przecięcie jest cechą rysunku, nie grafu. „Zwykle” nie znaczy „zawsze”: grafu pełnego o pięciu wierzchołkach nie da się już narysować bez przecięcia, a grafu pełnego na dwunastu wierzchołkach z przykładu 4. tym bardziej. Przecięcie i tak nie staje się przez to wierzchołkiem.

Zakładanie, że graf o zadanych stopniach zawsze istnieje.

Skąd się bierze: Dane w zadaniu wyglądają na wykonalne.

Jak zrobić dobrze: Najpierw sprawdź parzystość sumy stopni. Pięć osób po trzech znajomych daje sumę 1515 — taki graf nie istnieje. Parzystość jest jednak warunkiem koniecznym, ale nie wystarczającym: dla stopni 33, 33, 11, 11 suma wynosi 88, a takiego grafu też nie ma — oba wierzchołki stopnia 33 musiałyby sąsiadować ze wszystkimi pozostałymi, więc każdy z dwóch pozostałych miałby stopień co najmniej 22, a nie 11.

Mylenie liczby krawędzi drzewa z liczbą wierzchołków.

Skąd się bierze: Obie liczby są bliskie i występują w tym samym zdaniu.

Jak zrobić dobrze: Drzewo o nn wierzchołkach ma n−1n-1 krawędzi. Zapis 12−1=12\textcolor{#9b1c14}{12 - 1 = 12} jest oczywiście fałszywy, ale w rachunku łatwo o taką pomyłkę.

Liczenie boków wielokąta jako przekątnych.

Skąd się bierze: W grafie pełnym boki i przekątne są takimi samymi krawędziami.

Jak zrobić dobrze: Od wszystkich par trzeba odjąć boki: n(n−1)2−n\frac{n(n-1)}{2} - n. Dla dwunastokąta daje to 66−12=5466 - 12 = 54.

7Pytania i odpowiedzi

Co to jest graf w matematyce?

Zbiór wierzchołków i łączących je krawędzi. Liczy się wyłącznie informacja o tym, co jest z czym połączone — długości, kąty i sposób narysowania nie mają żadnego znaczenia.

Na czym polega lemat o uściskach dłoni?

Suma stopni wszystkich wierzchołków równa się podwojonej liczbie krawędzi, bo każda krawędź ma dwa końce. Wynika z niego, że wierzchołków o nieparzystym stopniu jest zawsze parzyście wiele.

Ile krawędzi ma drzewo?

Dokładnie o jedną mniej niż wierzchołków. Każdy nowy wierzchołek wymaga jednej krawędzi: mniej rozspójniłoby graf, a więcej utworzyłoby cykl.

Jak sprawdzić, czy graf o zadanych stopniach istnieje?

Najpierw policzyć sumę stopni. Jeśli wyjdzie nieparzysta, taki graf nie istnieje, bo suma stopni musi być podwojoną liczbą krawędzi, a więc liczbą parzystą. Parzysta suma niczego jeszcze nie gwarantuje: dla stopni 3, 3, 1, 1 suma wynosi 8, a taki graf i tak nie istnieje. Parzystość odsiewa więc część przypadków, ale reszty trzeba dowieść osobno.

Czy grafy są na maturze z matematyki?

Nie, słowo graf nie występuje w podstawie programowej z matematyki. Pojawiają się natomiast w informatyce, w zadaniach konkursowych i jako wygodny sposób rozwiązywania zwykłych zadań kombinatorycznych.

Czytaj dalej

KombinatorykaZliczanie par i uściski dłoni — ten sam wzór, tylko bez rysunku.SilniaNarzędzie do liczenia ustawień, przydatne przy zliczaniu dróg w grafie.Liczba przekątnych a liczba bokówPrzekątne wielokąta wypukłego — wzór, który przykład 4. wyprowadza z grafu pełnego.Reguła mnożeniaPodstawowe narzędzie zliczania, od którego zaczyna się każde takie zadanie.
Mateusz Będkowski — nauczyciel matematyki, autor serwisu Nie każ mu liczyć

Mateusz Będkowski

nauczyciel matematyki, autor „Nie każ mu liczyć”

Uczę matematyki od 13 lat, w tym 7 lat w szkole — dziś w dwóch szkołach w Kaliszu. Magister pedagogiki ze specjalnością terapia pedagogiczna, po studiach podyplomowych z matematyki. Rozwiązania na tej stronie liczę sam, krok po kroku, i zapisuję dokładnie tak, jak tłumaczę je uczniowi na kartce.

Ostatnia aktualizacja: 2026-08-01. Tekst redakcji „Nie każ mu liczyć”.