Powiązane obliczenia z teorii grafów
Po zbudowaniu macierzy możesz od razu sprawdzić stopnie, ścieżki, cykle i własności grafu.
Jak zrobić macierz sąsiedztwa grafu?
Najpierw ustal kolejność wierzchołków. Następnie utwórz kwadratową tabelę n × n. W komórce aᵢⱼ wpisz 1, jeśli istnieje bezpośrednie połączenie z wierzchołka vᵢ do vⱼ, a 0, jeśli go nie ma.
Dla grafu nieskierowanego macierz powinna być symetryczna. Dla grafu skierowanego wpis A → B nie wymusza wpisu B → A. Pętla, czyli połączenie wierzchołka z samym sobą, pojawia się na przekątnej macierzy.
Przykład: bezpośrednie połączenia między komputerami
Jeżeli stanowiska komputerowe oznaczysz jako A, B, C i D, a bezpośrednie połączenia zapiszesz jako A-B, A-C, B-D, C-D, kalkulator utworzy macierz 4 × 4. Jedynka w wierszu A i kolumnie B oznacza bezpośrednie połączenie A-B.
Taki zapis działa tak samo dla sieci komputerów, połączeń drogowych, relacji między punktami oraz klasycznych zadań z teorii grafów.
Macierz sąsiedztwa – graf skierowany i nieskierowany
| Typ grafu | Co oznacza aᵢⱼ? | Cecha macierzy |
|---|---|---|
| Nieskierowany | Połączenie między vᵢ i vⱼ | Macierz symetryczna |
| Skierowany | Łuk z vᵢ do vⱼ | Nie musi być symetryczna |
| Pętla | Połączenie vᵢ z samym sobą | 1 na przekątnej |
| Graf prosty bez pętli | Brak połączeń vᵢ-vᵢ | 0 na przekątnej |
Zadania przykładowe z odpowiedziami
Dla grafu A-B, B-C wpisz macierz sąsiedztwa w kolejności A,B,C.
Czy macierz grafu nieskierowanego musi być symetryczna?
Co oznacza 1 na przekątnej macierzy?
Jak z macierzy odczytać liczbę łuków w grafie skierowanym?
Odpowiedź 1: 0 1 0 / 1 0 1 / 0 1 0.
Odpowiedź 2: Tak. Dla grafu nieskierowanego macierz sąsiedztwa jest symetryczna.
Odpowiedź 3: Oznacza pętlę, czyli połączenie wierzchołka z samym sobą.
Odpowiedź 4: W grafie skierowanym liczba łuków jest równa sumie jedynek w macierzy.
Macierz sąsiedztwa a inne reprezentacje grafu
| Reprezentacja | Zaleta | Kiedy używać? |
|---|---|---|
| Lista krawędzi | Krótki zapis przy małej liczbie połączeń | Gdy graf jest rzadki |
| Macierz sąsiedztwa | Szybkie sprawdzenie, czy istnieje połączenie | Gdy graf jest mały lub gęsty |
| Lista sąsiedztwa | Wygodna w algorytmach BFS/DFS | Gdy graf ma wiele wierzchołków |
| Rysunek grafu | Pomaga zrozumieć strukturę | Przy nauce i zadaniach |
Najczęstsze błędy
- Zła kolejność wierzchołków – wiersze i kolumny muszą mieć tę samą ustaloną kolejność.
- Mylenie grafu skierowanego z nieskierowanym – w grafie skierowanym A → B nie oznacza automatycznie B → A.
- Pomijanie pętli – pętla jest zapisywana jako 1 na przekątnej.
- Podwójne liczenie krawędzi – w macierzy grafu nieskierowanego zwykła krawędź występuje w dwóch symetrycznych komórkach.
Ciekawostka
Element macierzy A² może informować o liczbie przejść długości 2 między parami wierzchołków. Dzięki temu macierze łączą teorię grafów z algebrą liniową.
Wskazówka od KalkulatorXXL
Przed ręcznym wypełnianiem macierzy zapisz kolejność wierzchołków nad kolumnami i obok wierszy. To najprostszy sposób, żeby nie zamienić miejscami komórek.
FAQ - macierz sąsiedztwa grafu
Ostatnia aktualizacja: 26.09.2026