Grafy i drzewa: struktura, na której opierają się przeszukiwanie i sieci neuronowe

Wierzchołki i krawędzie, stopnie, macierz sąsiedztwa, ścieżki i składowe, BFS i Dijkstra, drzewa, minimalne drzewo rozpinające i graf obliczeniowy neuronu — wszystko na jednym grafie z siedmioma miastami.

14 minut Matěj Žalmánek 2026-10-15

Seria Podstawy AI Część 8 z 52

1. Mapa sztucznej inteligencji: co jest czym i jak to do siebie pasuje
2. Krótka historia sztucznej inteligencji: od Turinga do modeli językowych
3. Dane, model, trening, inferencja: podstawowe pojęcia na jednym przykładzie
4. Jak czytać zapis matematyczny: symbole, indeksy, sumy i kwantyfikatory
5. Zbiory i relacje: klocki, z których składają się definicje w AI
6. Funkcje i odwzorowania: dlaczego każdy model AI jest funkcją
7. Logika i dowody: reguły, według których rozumuje AI
8. Grafy i drzewa: struktura, na której opierają się przeszukiwanie i sieci neuronowe
9. Algebra liniowa dla uczenia maszynowego: wektory, macierze i dlaczego AI głównie mnoży
10. Pochodne, gradient i reguła łańcuchowa: jak model ustala, w którą stronę się uczyć
11. Spadek gradientu: jak uczy się model
12. Czym jest prawdopodobieństwo: od rzutu kostką do aksjomatów Kołmogorowa
13. Prawdopodobieństwo warunkowe i twierdzenie Bayesa: jak zmienić ocenę, gdy dowiesz się czegoś nowego
14. Zmienna losowa i dystrybuanta: jedna funkcja, która mówi o rozkładzie wszystko
15. Funkcja gęstości i funkcja prawdopodobieństwa: dlaczego zmienna ciągła ma w punkcie prawdopodobieństwo zero
16. Wartość oczekiwana, wariancja i kowariancja: gdzie leży rozkład, jak jest szeroki i co z czym się wiąże
17. Przegląd rozkładów prawdopodobieństwa: Bernoulliego, dwumianowy, Poissona, jednostajny, normalny i wykładniczy
18. Prawo wielkich liczb i centralne twierdzenie graniczne: dlaczego średnie zachowują się tak przewidywalnie
19. Statystyka i estymacja parametrów: największa wiarygodność, MAP i przedziały ufności
20. Teoria informacji: entropia, entropia krzyżowa i dywergencja KL — skąd się biorą funkcje straty
21. Przeszukiwanie przestrzeni stanów: BFS, DFS, UCS i A* z animacjami
22. Gry i przeciwnik: minimax, przycinanie alfa-beta i Monte Carlo tree search
23. Spełnianie ograniczeń: backtracking, propagacja ograniczeń i AC-3 na sudoku i mapie czeskich krajów
24. Logika i systemy z bazą wiedzy: wnioskowanie w przód i wstecz, rezolucja i systemy ekspertowe
25. Planowanie: STRIPS, świat klocków, heurystyki z relaksacji i planowanie w agentach AI
26. Przeszukiwanie lokalne i symulowane wyżarzanie: komiwojażer przez czeskie miasta wojewódzkie
27. Algorytmy genetyczne: populacja, krzyżowanie, mutacja i selekcja na plecaku na wycieczkę
28. Strategie ewolucyjne i programowanie genetyczne: od reguły jednej piątej do prawa Keplera
29. Optymalizacja kolonią mrówek: jak ślad feromonowy znajduje krótką drogę
30. Optymalizacja rojem cząstek: bezwładność, własne doświadczenie i doświadczenie roju
31. Neuroewolucja: ewolucja wag i kształtu sieci neuronowych oraz algorytm NEAT
32. Zbiory rozmyte i funkcje przynależności: jak zapisać „trochę ciepło”
33. Logika rozmyta a prawdopodobieństwo: dlaczego „trochę ciepło” nie znaczy „prawdopodobnie ciepło”
34. Logika rozmyta: t-normy, implikacje i reguły JEŻELI–TO
35. Sterowanie rozmyte: Mamdani i Sugeno od wentylatora po wahadło na wózku
36. Klasteryzacja rozmyta: algorytm fuzzy c-means i punkty między skupieniami
37. Systemy neuro-rozmyte (ANFIS): reguły rozmyte, które uczą się z danych
38. Łańcuchy Markowa: macierz przejścia, rozkład stacjonarny i PageRank
39. Ukryte modele Markowa: algorytm Viterbiego i nieuczciwe kasyno
40. Sieci bayesowskie: dlaczego trawa jest mokra i co z tego wynika dla zraszacza
41. Filtr Kalmana: jak z niedokładnych pomiarów oszacować, gdzie jest samochód i jak szybko jedzie
42. Rodzaje uczenia maszynowego: nadzorowane, nienadzorowane, półnadzorowane i inne
43. Prompty, kontekst i RAG: jak dać modelowi właściwe informacje
44. Wariacyjne autoenkodery (VAE): nowe obrazki z ciągłej przestrzeni latentnej
45. Generatywne sieci przeciwstawne (GAN): fałszerz kontra detektyw
46. Modele dyfuzyjne: jak z czystego szumu powstaje obraz
47. Procesy decyzyjne Markowa: stany, akcje, nagrody i równania Bellmana
48. Q-learning i DQN: uczenie się wartości akcji od tabeli po sieć neuronową
49. Policy gradient i PPO: uczenie się bezpośrednio polityki
50. Jak działa agent AI: model językowy w pętli z narzędziami
51. Programowanie z agentami AI: zadanie, testy i kontrola
52. Ocena i bezpieczeństwo systemów AI: jak mierzyć i jak pilnować

Pełny program serii Gotowe: 52 z 83 tematów

Mapa miast i dróg, sieć znajomych, przestrzeń stanów gry, sieć neuronowa i obliczenie, w którym liczy się gradient — to wszystko jest graf: punkty połączone liniami. Grafy to najbardziej uniwersalna struktura w informatyce, a w sztucznej inteligencji spotkasz je na każdym kroku. Drzewa są ich najprostszym i najbardziej użytecznym przypadkiem szczególnym.

Całą część zbudujemy na jednym grafie z siedmioma miastami od A do G i drogami o określonej długości. Krok po kroku pokażemy na nim stopnie, sposoby zapisu grafu, najkrótsze ścieżki i minimalne drzewo rozpinające.

1. Czym jest graf

Definicja — graf

Graf to para G = (V, E), gdzie V jest skończonym zbiorem wierzchołków, a E zbiorem krawędzi.

W grafie nieskierowanym krawędź jest zbiorem dwuelementowym {u, v}; w skierowanym parą uporządkowaną (u, v) — strzałką z u do v. Graf skierowany jest więc relacją w zbiorze V.

Graf ważony ma dodatkowo funkcję w : E → ℝ, która każdej krawędzi przypisuje wagę (długość, koszt, czas).

2. Stopień wierzchołka

Definicja — stopień i lemat o uściskach dłoni

Stopień deg(v) wierzchołka v to liczba krawędzi, które z niego wychodzą.

Twierdzenie (lemat o uściskach dłoni). W każdym grafie nieskierowanym ∑_{v ∈ V} deg(v) = 2 |E|.

Suma stopni wynosi 2 + 4 + 4 + 4 + 4 + 4 + 2 = 24, a krawędzi jest 12 — dokładnie zgodnie z twierdzeniem. Stopień ma znaczenie w praktyce: w sieci społecznościowej to liczba znajomych, w sieci WWW liczba linków, a wierzchołki o dużym stopniu bywają najważniejsze.

3. Jak zapisać graf w komputerze

Komputer nie widzi obrazka, potrzebuje liczb. Typowe są dwie postacie:

• Macierz sąsiedztwa — tabela |V| × |V|, w komórce (u, v) jest waga krawędzi albo 0. Szybkie „czy jest tu krawędź?”, ale pamięć rośnie jak |V|².
• Lista sąsiedztwa — przy każdym wierzchołku lista jego sąsiadów. Pamięć rośnie tylko jak |V| + |E|, co dla grafów rzadkich (sieć społecznościowa, mapa) stanowi ogromną różnicę.

Macierz jest symetryczna względem przekątnej — to znak grafu nieskierowanego. W AI macierz sąsiedztwa wykorzystują grafowe sieci neuronowe, które uczą się bezpośrednio na grafach (cząsteczki, sieci społecznościowe, sieć drogowa).

4. Ścieżki, cykle i spójność

Definicja — ścieżka, cykl, spójność

Ścieżka z u do v to ciąg parami różnych wierzchołków u = v₀, v₁, …, v_k = v, w którym każde dwa kolejne łączy krawędź. Jej długość to k (liczba krawędzi), a w grafie ważonym suma wag.

Cykl to ścieżka, która wraca do wierzchołka początkowego (co najmniej trzy krawędzie).

Graf jest spójny, gdy między każdymi dwoma wierzchołkami prowadzi ścieżka. Maksymalne spójne części grafu to składowe spójności — a „leżeć w tej samej składowej” jest równoważnością, więc składowe tworzą podział V.

5. Najkrótsze ścieżki

Zadanie „jak najszybciej dostać się z A do G” to szukanie najkrótszej ścieżki — i dokładnie to robiły algorytmy z części o przeszukiwaniu przestrzeni stanów. Zależy jednak od tego, co mierzymy.

Gdy interesuje nas liczba krawędzi, wystarczy przeszukiwanie wszerz: najpierw sąsiedzi A, potem ich sąsiedzi… Liczba nad wierzchołkiem to odległość od A w krawędziach:

Do G prowadzą trzy krawędzie (na przykład A–B–E–G). Gdy jednak liczymy długość dróg, potrzebujemy algorytmu Dijkstry — zawsze kontynuuje od najbliższego jeszcze niezamkniętego wierzchołka. Liczba nad wierzchołkiem to teraz najkrótsza odległość w kilometrach, a wyróżniona jest najkrótsza ścieżka do G:

Najkrótsza ścieżka A–B–D–E–G ma cztery krawędzie, czyli więcej niż trzykrawędziowa ścieżka z BFS, ale długość tylko 12. Ścieżka A–B–E–G miałaby 4 + 7 + 3 = 14. Mniej kroków nie oznacza krótszej ścieżki — dokładnie tę różnicę między BFS a UCS widzieliśmy w labiryncie z błotem.

6. Drzewa

Definicja — drzewo i drzewo ukorzenione

Drzewo to graf spójny bez cykli. Las to graf bez cykli (każda jego składowa jest drzewem).

Twierdzenie. Dla grafu o n wierzchołkach następujące warunki są równoważne: (1) jest drzewem; (2) jest spójny i ma n − 1 krawędzi; (3) nie ma cyklu i ma n − 1 krawędzi; (4) między każdymi dwoma wierzchołkami prowadzi dokładnie jedna ścieżka.

Drzewo ukorzenione ma jeden wyróżniony wierzchołek, korzeń. Sąsiedzi wierzchołka w kierunku od korzenia to jego dzieci, wierzchołek bez dzieci to liść, a głębokość wierzchołka to długość ścieżki od korzenia.

W AI drzewa są wszędzie. Drzewo decyzyjne klasyfikuje serią pytań od korzenia do liścia. Algorytmy przeszukiwania budują drzewo przeszukiwania — drzewo BFS i DFS z części o przeszukiwaniu to właśnie to. A program szachowy przelicza drzewo gry, w którym wierzchołki to pozycje, a krawędzie to ruchy.

7. Minimalne drzewo rozpinające

Definicja — drzewo rozpinające i algorytm Kruskala

Drzewo rozpinające grafu spójnego G to podgraf, który zawiera wszystkie wierzchołki G i jest drzewem. Minimalne drzewo rozpinające ma najmniejszą sumę wag krawędzi.

Algorytm Kruskala: posortuj krawędzie rosnąco według wagi i po kolei dodawaj każdą, która nie tworzy cyklu. To algorytm zachłanny, a mimo to zawsze znajduje optimum.

Drzewo rozpinające ma 6 krawędzi dla 7 wierzchołków — dokładnie n − 1, jak mówi twierdzenie o drzewach — i łączną długość 18. Sześć pozostałych dróg algorytm odrzucił, bo utworzyłyby cykl.

8. Grafy acykliczne i obliczenia sieci neuronowej

Definicja — DAG i porządek topologiczny

Skierowany graf acykliczny (DAG) to graf skierowany bez cyklu skierowanego.

Porządek topologiczny to takie ułożenie wierzchołków, w którym każda krawędź (u, v) prowadzi od lewej do prawej — u jest przed v. Twierdzenie. Graf skierowany ma porządek topologiczny wtedy i tylko wtedy, gdy jest acykliczny.

Tak liczy każda sieć neuronowa. Oto obliczenie jednego neuronu ŷ = σ(w · x + b) i jego błędu L(ŷ, y) jako graf obliczeniowy: wejścia po lewej, operacje jako wierzchołki, strzałki pokazują, co od czego zależy. Liczby to porządek topologiczny:

Sieć liczy do przodu w porządku topologicznym — najpierw iloczyn, potem sumę, sigmoidę i błąd. A gdy potem się uczy, przechodzi tym samym grafem wstecz: propagacja wsteczna błędu (backpropagation) odwiedza wierzchołki w odwróconym porządku topologicznym i w każdym stosuje regułę łańcuchową. Biblioteki takie jak PyTorch budują sobie ten graf same przy każdym obliczeniu. Nawiasem mówiąc, graf zależności modułów w programie tej serii też jest DAG-iem.

9. Grafy w sztucznej inteligencji

• Przestrzeń stanów to graf: stany są wierzchołkami, akcje krawędziami z kosztem. Przeszukiwanie to szukanie ścieżki w grafie.
• Grafy obliczeniowe sieci neuronowych to DAG-i; trening to przejście tam i z powrotem.
• Grafy wiedzy przechowują fakty jako krawędzie w rodzaju „Praga — jest stolicą — Czech”, a wyszukiwarki składają z nich odpowiedzi.
• Sieci bayesowskie to DAG-i zależności probabilistycznych — dojdziemy do nich w module o modelach probabilistycznych.
• Grafowe sieci neuronowe uczą się bezpośrednio na grafach: przewidują właściwości cząsteczek, ruch drogowy albo rekomendacje.

10. Podsumowanie

• Graf to zbiór wierzchołków i krawędzi; krawędzie mogą mieć kierunek i wagę. Suma stopni jest dwa razy większa niż liczba krawędzi.
• Graf zapisuje się macierzą sąsiedztwa albo listą sąsiedztwa — ta druga jest dla grafów rzadkich znacznie oszczędniejsza.
• BFS znajduje ścieżkę o najmniejszej liczbie krawędzi, Dijkstra najkrótszą według wag — i nie musi to być to samo.
• Drzewo to graf spójny bez cykli z n − 1 krawędziami; minimalne drzewo rozpinające znajduje zachłanny algorytm Kruskala.
• Sieć neuronowa to obliczeniowy DAG: do przodu liczy się w porządku topologicznym, gradient wstecz.

Masz inne zdanie? Napisz na support@coden-app.com.