Do czego służy kalkulator macierzy sąsiedztwa?
W kalkulatorze macierzy sąsiedztwa grafu zamienisz listę krawędzi na tabelę 0-1, w której wiersze i kolumny odpowiadają wierzchołkom. Wartość 1 oznacza, że między dwoma wierzchołkami istnieje krawędź lub łuk, a 0 oznacza brak połączenia.
Ten kalkulator dobrze uzupełnia stopnie wierzchołków, ścieżki i cykle w grafie, drzewa w grafach oraz graf pełny. Do części logicznej pakietu pasują też tablice prawdy i działania na zbiorach.
Wzór i logika macierzy sąsiedztwa
Dla grafu o wierzchołkach v₁, v₂, ..., vₙ macierz sąsiedztwa ma rozmiar n × n. Element aᵢⱼ jest równy 1, jeśli istnieje krawędź z wierzchołka vᵢ do vⱼ, a w przeciwnym razie jest równy 0.
| Typ grafu | Co oznacza aᵢⱼ? | Cecha macierzy |
|---|---|---|
| Nieskierowany | Połączenie między vᵢ i vⱼ | Macierz symetryczna |
| Skierowany | Łuk z vᵢ do vⱼ | Macierz nie musi być symetryczna |
| Pętla | Połączenie vᵢ z samym sobą | Jedynka na przekątnej |
| Graf prosty bez pętli | Brak połączeń vᵢ-vᵢ | Przekątna z zerami |
Przykład obliczeń
Weźmy graf z wierzchołkami A, B, C, D i krawędziami A-B, A-C, B-D, C-D. W macierzy wiersz A ma jedynki w kolumnach B i C, bo A jest połączone z B oraz C. W grafie nieskierowanym pojawiają się też jedynki symetryczne: B-A i C-A.
Jeśli graf jest skierowany, zapis A-B oznacza tylko łuk z A do B. Wtedy macierz nie musi być symetryczna.
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: W kolejności A,B,C macierz to: 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 krawędź z wierzchołka do samego siebie.
Odpowiedź 4: W grafie skierowanym liczba łuków to suma wszystkich jedynek w macierzy.
Tabela porównawcza
| Reprezentacja grafu | Zaleta | Kiedy używać? |
|---|---|---|
| Lista krawędzi | Krótka przy małej liczbie połączeń | Gdy graf jest rzadki |
| Macierz sąsiedztwa | Szybkie sprawdzanie połączenia i-j | Gdy graf jest mały lub gęsty |
| Lista sąsiedztwa | Wygodna w algorytmach BFS/DFS | Gdy graf ma dużo wierzchołków |
| Rysunek grafu | Pomaga zrozumieć strukturę | Przy zadaniach szkolnych i nauce pojęć |
Najczęstsze błędy i jak zwiększyć dokładność wyniku
- Mylenie grafu skierowanego z nieskierowanym - w grafie skierowanym A-B nie dodaje automatycznie B-A.
- Zła kolejność wierzchołków - macierz zależy od kolejności etykiet wierszy i kolumn.
- Pomijanie pętli - pętla pojawia się jako jedynka na przekątnej.
- Liczenie krawędzi z macierzy nieskierowanej - zwykłe krawędzie poza przekątną są zapisane podwójnie.
Ciekawostka
Macierz sąsiedztwa można mnożyć przez samą siebie. Element macierzy A² informuje, ile jest przejść długości 2 między parami wierzchołków. To łączy teorię grafów z algebrą liniową.
Powiązane kalkulatory matematyki dyskretnej
Po zbudowaniu macierzy sąsiedztwa możesz przejść do ścieżek i cykli w grafie, drzew w grafach, stopni wierzchołków i grafu pełnego.
W szerszym pakiecie matematyki dyskretnej sprawdź także relacje i własności relacji, prawa De Morgana, kongruencje liniowe, zasadę szufladkową i modulo.
Cały pakiet: matematyka dyskretna, logika, zbiory i grafy
Ten kalkulator należy do jednego pakietu z zakresu matematyki dyskretnej. Jeżeli pracujesz z logiką i zbiorami, przejdź kolejno przez tablica prawdy, prawa De Morgana, działania na zbiorach oraz relacje i własności relacji. Te narzędzia pomagają rozumieć zapisy zdań, negacje, diagramy Venna i własności relacji.
Jeśli zadanie dotyczy reszt z dzielenia, wybierz modulo i reszty z dzielenia, kongruencje liniowe albo rozszerzony algorytm Euklidesa. Do zadań z gwarantowanym powtórzeniem pasuje zasada szufladkowa Dirichleta, szczególnie gdy szufladami są reszty modulo, kolory, miesiące lub inne klasy.
Część grafową tworzą: stopnie wierzchołków grafu, graf pełny Kₙ, drzewa w grafach, ścieżki i cykle w grafie i macierz sąsiedztwa grafu. Dzięki temu możesz przejść od listy krawędzi, przez macierz sąsiedztwa, aż po stopnie, cykle, drzewa i graf pełny.
Wskazówka od KalkulatorXXL
Przy ręcznym tworzeniu macierzy najpierw ustal kolejność wierzchołków. Dopiero potem wypełniaj komórki. Wiele błędów w zadaniach wynika nie z grafu, lecz z zamiany kolejności wierszy i kolumn.
Cały dział matematyki dyskretnej: Akademia matematyki dyskretnej – logika, zbiory i grafy łączy tablice prawdy, prawa De Morgana, zbiory, relacje, modulo, kongruencje, podzielność, kombinatorykę, prawdopodobieństwo i teorię grafów.