Podstawy teorii grafów

Wprowadzenie

Teoria grafów to dziedzina matematyki i informatyki zajmująca się badaniem grafów - struktur składających się z wierzchołków (węzłów) połączonych krawędziami. Grafy są jedną z najważniejszych struktur danych w informatyce, wykorzystywaną do modelowania:

Sieci społecznościowych (użytkownicy i znajomości)
Map i nawigacji (miasta i drogi)
Internetu (strony i linki)
Sieci komputerowych (komputery i połączenia)
Zależności w projektach (zadania i ich kolejność)
Systemów rekomendacji (użytkownicy i produkty)

Definicja grafu

Graf nieskierowany

Graf nieskierowany G = (V, E) składa się z: - V (Vertices) - zbiór wierzchołków - E (Edges) - zbiór krawędzi, gdzie każda krawędź to para wierzchołków {u, v}

Przykład:

V = {A, B, C, D}
E = {{A,B}, {A,C}, {B,C}, {C,D}}

Wizualizacja:
    A --- B
    |   / |
    | /   |
    C --- D

Własności: - Krawędzie są symetryczne: jeśli {A,B} ∈ E, to można iść z A do B i z B do A - Kolejność wierzchołków w krawędzi nie ma znaczenia: {A,B} = {B,A}

Graf skierowany (digraf)

Graf skierowany G = (V, E) składa się z: - V - zbiór wierzchołków - E - zbiór krawędzi skierowanych (strzałek), gdzie każda krawędź to uporządkowana para (u, v)

Przykład:

V = {A, B, C, D}
E = {(A,B), (A,C), (B,C), (C,D), (D,A)}

Wizualizacja:
    A → B
    ↓   ↓
    C → D
    ↑___|

Własności: - Krawędzie są asymetryczne: (A,B) ≠ (B,A) - (A,B) oznacza krawędź z A do B (nie na odwrót)

Podstawowe pojęcia

1. Stopień wierzchołka

Graf nieskierowany: - Stopień wierzchołka v (oznaczany deg(v)) = liczba krawędzi incydentnych z v

Przykład:

    A --- B
    |     |
    C --- D

deg(A) = 2 (krawędzie: {A,B}, {A,C})
deg(B) = 2 (krawędzie: {A,B}, {B,D})
deg(C) = 2 (krawędzie: {A,C}, {C,D})
deg(D) = 2 (krawędzie: {B,D}, {C,D})

Twierdzenie o sumie stopni:

Σ deg(v) = 2|E|

(Suma stopni wszystkich wierzchołków = 2 × liczba krawędzi)

Graf skierowany: - Stopień wejściowy deg⁻(v) = liczba krawędzi wchodzących do v - Stopień wyjściowy deg⁺(v) = liczba krawędzi wychodzących z v

Przykład:

    A → B
    ↓   ↓
    C → D

deg⁻(A) = 0, deg⁺(A) = 2
deg⁻(B) = 1, deg⁺(B) = 1
deg⁻(C) = 1, deg⁺(C) = 1
deg⁻(D) = 2, deg⁺(D) = 0

2. Ścieżka (Path)

Ścieżka to ciąg wierzchołków v₁, v₂, ..., vₖ, gdzie każda para kolejnych wierzchołków jest połączona krawędzią.

Ścieżka prosta (simple path) - nie powtarza wierzchołków.

Przykład:

Graf:
    A --- B --- C
    |           |
    D --- E --- F

Ścieżka z A do F:
- A → B → C → F (długość 3)
- A → D → E → F (długość 3)
- A → B → C → F → E → D → A (to NIE jest ścieżka prosta - wraca do A)

Długość ścieżki = liczba krawędzi w ścieżce.

3. Cykl (Cycle)

Cykl to ścieżka, która zaczyna się i kończy w tym samym wierzchołku.

Cykl prosty - nie powtarza wierzchołków (oprócz pierwszego/ostatniego).

Przykład:

Graf:
    A --- B
    |     |
    D --- C

Cykl: A → B → C → D → A (długość 4)

Graf acykliczny - graf bez cykli.

4. Spójność (Connectivity)

Graf nieskierowany: - Graf jest spójny, jeśli istnieje ścieżka między każdą parą wierzchołków - Składowa spójna (connected component) - maksymalny spójny podgraf

Przykład:

Graf niespójny (2 składowe):

    A --- B       E --- F
    |     |       |
    C --- D       G

Składowa 1: {A, B, C, D}
Składowa 2: {E, F, G}

Graf skierowany: - Silnie spójny (strongly connected) - istnieje ścieżka skierowana między każdą parą wierzchołków - Słabo spójny (weakly connected) - graf jest spójny po zignorowaniu kierunków krawędzi

5. Graf ważony

Graf ważony - każda krawędź ma przypisaną wagę (koszt, odległość, czas).

Przykład:

    A --5-- B
    |       |
    3       2
    |       |
    C --4-- D

Waga ścieżki A → B → D = 5 + 2 = 7
Waga ścieżki A → C → D = 3 + 4 = 7

Typy grafów

1. Graf pełny (Complete Graph)

Graf pełny Kₙ - każda para wierzchołków jest połączona krawędzią.

K₃ (trójkąt):        K₄:
    A                 A --- B
   / \               /|   / |
  B---C             / | /   |
                   D--+/----C
                     |/
                     (wszystkie połączone)

Liczba krawędzi w Kₙ = n(n-1)/2

2. Graf dwudzielny (Bipartite Graph)

Graf dwudzielny - wierzchołki można podzielić na dwa zbiory, gdzie krawędzie łączą tylko wierzchołki z różnych zbiorów.

Przykład:

Zbiór A: {1, 2, 3}
Zbiór B: {a, b, c}

    1 --- a
    |  \  |
    2   \ b
    |     |
    3 --- c

Krawędzie: {1,a}, {1,b}, {2,a}, {3,c}

Zastosowania: - Dopasowanie zadań do pracowników - Systemy rekomendacji (użytkownicy ↔ produkty)

3. Drzewo (Tree)

Drzewo to spójny graf acykliczny.

Własności drzewa: - Ma dokładnie n-1 krawędzi (gdzie n = liczba wierzchołków) - Istnieje dokładnie jedna ścieżka między każdą parą wierzchołków - Usunięcie dowolnej krawędzi powoduje niespójność

Przykład:

        A
       / \
      B   C
     / \   \
    D   E   F

|V| = 6, |E| = 5 (6-1 = 5 ✓)

4. DAG (Directed Acyclic Graph)

DAG - graf skierowany bez cykli.

Zastosowania: - Zależności między zadaniami (scheduling) - Genealogia (drzewa genealogiczne) - Systemy kompilacji (zależności plików)

Przykład:

    A → B → D
    ↓   ↓
    C → E

Brak cykli (nie można wrócić do wierzchołka startowego)

Implementacja grafu w Pythonie

Klasa podstawowa

Wyjście:

Graf: V={'A', 'B', 'C', 'D'}, E={('A', 'B'), ('A', 'C'), ('B', 'C'), ('C', 'D')}
Sąsiedzi A: ['B', 'C']
Stopień B: 2
Czy A-D połączone? False

Graf skierowany

Wyjście:

Następniki A: ['B', 'C']
Poprzedniki A: ['D']
Stopień wejściowy D: 1
Stopień wyjściowy A: 2
Czy A → D? False

Graf ważony

Wyjście:

Waga A-B: 5
Sąsiedzi A: [('B', 5), ('C', 3)]

Przykłady zastosowań grafów

1. Sieć społecznościowa

Wyjście:

Przyjaciele Alice: ['bob', 'charlie']
Wspólni przyjaciele Alice i Boba: {'charlie'}
Sugestie dla Alice: ['diana', 'eve']

2. Mapa drogowa

Wyjście:

Odległość Warszawa-Kraków: 290 km
Miasta połączone z Warszawą: [('Kraków', 290), ('Poznań', 310)]

Własności matematyczne grafów

Twierdzenie 1: Suma stopni

W grafie nieskierowanym:

Σ deg(v) = 2|E|

Dowód:
Każda krawędź {u,v} zwiększa stopień u i v o 1,
więc każda krawędź jest liczona 2 razy w sumie stopni.

Wniosek: Liczba wierzchołków o nieparzystym stopniu jest parzysta.

Twierdzenie 2: Liczba krawędzi w grafie pełnym

Graf pełny Kₙ ma:

|E| = n(n-1)/2 krawędzi

Dowód:
Każdy z n wierzchołków łączy się z (n-1) innymi.
Daje to n(n-1) par, ale każda krawędź jest liczona 2 razy.
Zatem |E| = n(n-1)/2.

Twierdzenie 3: Własności drzewa

Graf G = (V, E) jest drzewem ⟺ spełnia DOWOLNE DWA z warunków: 1. G jest spójny 2. G jest acykliczny 3. |E| = |V| - 1

Złożoność operacji

Operacja	Lista krawędzi	Macierz sąsiedztwa	Lista sąsiedztwa
Dodanie wierzchołka	O(1)	O(V²)	O(1)
Dodanie krawędzi	O(1)	O(1)	O(1)
Usunięcie wierzchołka	O(E)	O(V²)	O(V+E)
Usunięcie krawędzi	O(E)	O(1)	O(V)
Sprawdzenie krawędzi	O(E)	O(1)	O(V)
Sąsiedzi wierzchołka	O(E)	O(V)	O(deg(v))
Pamięć	O(V+E)	O(V²)	O(V+E)

(Szczegóły reprezentacji grafów w następnej lekcji!)

Podsumowanie

Kluczowe pojęcia

Pojęcie	Definicja
Graf	Struktura G = (V, E) składająca się z wierzchołków i krawędzi
Wierzchołek	Węzeł grafu
Krawędź	Połączenie między wierzchołkami
Stopień	Liczba krawędzi incydentnych z wierzchołkiem
Ścieżka	Ciąg wierzchołków połączonych krawędziami
Cykl	Ścieżka zaczynająca się i kończąca w tym samym wierzchołku
Spójność	Graf jest spójny, jeśli istnieje ścieżka między każdą parą wierzchołków
Drzewo	Spójny graf acykliczny
DAG	Graf skierowany bez cykli

Co dalej?

Po zrozumieniu podstaw teorii grafów, następne kroki to:

Lekcja 55: Reprezentacje grafów
Macierz sąsiedztwa
Lista sąsiedztwa
Lista krawędzi
Porównanie wydajności
Lekcja 56: Przeszukiwanie wszerz (BFS)
Algorytm BFS
Najkrótsza ścieżka w grafie nieważonym
Zastosowania
Lekcja 57: Przeszukiwanie w głąb (DFS)
Algorytm DFS
Wykrywanie cykli
Sortowanie topologiczne

Zadania praktyczne

Zadanie 1: Walidacja grafu

Napisz funkcję, która sprawdza, czy dany graf jest: - Spójny - Acykliczny - Drzewem

Zadanie 2: Stopnie wierzchołków

Dla danego grafu, znajdź: - Wierzchołek o największym stopniu - Rozkład stopni (ile wierzchołków ma stopień 0, 1, 2, ...)

Zadanie 3: Graf dwudzielny

Napisz funkcję sprawdzającą, czy graf jest dwudzielny (kolorowanie 2 kolorami).

Zadanie 4: Statystyki sieci społecznościowej

Dla sieci społecznościowej, oblicz: - Średnią liczbę przyjaciół - Maksymalną liczbę wspólnych przyjaciół między dwoma osobami - "Najpopularniejszego" użytkownika (najwyższy stopień)

Następna lekcja: Reprezentacje grafów - macierz sąsiedztwa i lista sąsiedztwa