Kalkulator Macierzy Sąsiedztwa

O Kalkulator Macierzy Sąsiedztwa

Kalkulator Macierzy Sąsiedztwa to narzędzie z dziedziny teorii grafów, które konwertuje między trzema kanonicznymi reprezentacjami grafu — macierzą sąsiedztwa, listą krawędzi i listą sąsiedztwa — oraz wzbogaca wynik o analizę strukturalną: ciąg stopni, gęstość grafu, spójne składowe i potęgi macierzy. Automatycznie wykrywa, czy dane wejściowe opisują graf skierowany czy nieskierowany, i generuje interaktywną wizualizację SVG przy każdym wyniku.

Co to jest macierz sąsiedztwa?

Dla grafu G = (V, E) o n wierzchołkach, jego macierz sąsiedztwa to macierz kwadratowa A o wymiarach n × n, w której wpis A[i][j] wynosi 1, jeśli istnieje krawędź z wierzchołka i do wierzchołka j, a 0 w przeciwnym razie.

Dla grafu nieskierowanego macierz sąsiedztwa jest zawsze symetryczna: każda krawędź {u, v} skutkuje wpisami A[u][v] = 1 oraz A[v][u] = 1. Dla grafu skierowanego (digrafu) macierz może być asymetryczna, odzwierciedlając kierunek każdego łuku.

Trzy reprezentacje — wybierz dopasowaną do problemu

Obliczane kluczowe metryki

Ciąg stopni

Dla grafów nieskierowanych stopień wierzchołka to liczba krawędzi z nim incydentnych (pętle własne liczone podwójnie). Dla grafów skierowanych każdy wierzchołek ma stopień wejściowy (łuki wchodzące) i stopień wyjściowy (łuki wychodzące). Posortowana lista stopni to klasyczny niezmiennik grafu używany w testowaniu izomorfizmu i twierdzeniu Erdősa-Gallai.

Gęstość grafu

Gęstość mierzy, jak "pełny" jest graf w stosunku do maksymalnej możliwej liczby krawędzi na n wierzchołkach.

Gęstość 0 oznacza brak krawędzi, 1 oznacza graf pełny, a wartości poniżej 0.1 zazwyczaj wskazują na graf rzadki, gdzie lista sąsiedztwa jest bardziej efektywna pamięciowo niż macierz.

Spójne składowe

Spójna składowa to maksymalny podzbiór wierzchołków taki, że każda para jest połączona ścieżką. Dla grafów skierowanych kalkulator podaje słabo spójne składowe (ignorując kierunki strzałek) — te same podzbiory, które uzyskałoby się, traktując każdy łuk jako krawędź nieskierowaną.

Potęgi macierzy (A², A³ ... )

Podstawowe twierdzenie algebraicznej teorii grafów mówi, że wpis (i, j) w macierzy A^k jest równy liczbie dróg o długości dokładnie k z wierzchołka i do wierzchołka j. W rezultacie:

• A²[i][i] jest równe stopniowi wierzchołka i (nieskierowany), ponieważ droga długości 2 z i do samego siebie to "pójście do sąsiada i z powrotem".
• Ślad macierzy A³ podzielony przez 6 zlicza trójkąty w grafie nieskierowanym.
• Informacja o tym, czy Aⁿ⁻¹ zawiera jakiekolwiek zerowe wpisy, mówi o tym, czy graf jest spójny.

Akceptowane formaty wejściowe

1. Lista krawędzi

Jedna krawędź na linię lub oddzielona przecinkami. Dowolny z tych separatorów działa: A-B, A B, A,B, A->B, A--B. Użyj ->, jeśli chcesz wymusić interpretację skierowaną.

2. Lista sąsiedztwa

Jedna linia na wierzchołek, w formacie wierzchołek: sąsiad1, sąsiad2, .... Kolejność nie ma znaczenia; brakujące wierzchołki są dodawane automatycznie z list sąsiadów.

3. Macierz sąsiedztwa

Jeden wiersz na linię z wartościami 0/1 oddzielonymi spacjami lub przecinkami. Macierz musi być kwadratowa. Opcjonalnie podaj własne etykiety w polu Etykiety macierzy (w przeciwnym razie zostaną użyte A, B, C…).

Jak korzystać z tego kalkulatora

1. Wybierz format wejściowy za pomocą selektora zakładek: lista krawędzi, lista sąsiedztwa lub macierz sąsiedztwa.
2. Wklej lub wpisz swój graf w obszarze tekstowym. W przypadku macierzy dodaj opcjonalne etykiety w polu Etykiety macierzy.
3. Wybierz typ grafu — pozostaw Auto-wykrywanie, a kalkulator rozpozna skierowanie na podstawie strzałek (->) lub symetrii macierzy. Wymuś tryb Skierowany lub Nieskierowany, jeśli chcesz nadpisać wykrywanie.
4. Kliknij Konwertuj i analizuj graf. Strona wynikowa pokaże macierz sąsiedztwa, interaktywny rendering SVG, pozostałe dwie reprezentacje tekstowe, statystyki stopni, spójne składowe oraz macierze dróg A² i A³, gdy graf jest wystarczająco mały.
5. Najedź na wiersz macierzy lub węzeł grafu, aby podświetlić pasujący wiersz/kolumnę i incydentne krawędzie — to natychmiastowy dowód wizualny, że każdy format koduje te same informacje.

Przykład krok po kroku

Rozważmy graf nieskierowany na wierzchołkach {A, B, C, D} z krawędziami AB, BC, CA, CD. Macierz sąsiedztwa to:

Kluczowe fakty wyliczone przez kalkulator:

• Symetryczna? Tak — potwierdza charakter nieskierowany.
• Ciąg stopni: (3, 2, 2, 1) — wierzchołek C jest centrum.
• Gęstość: 2·4 / (4·3) = 0.667 — graf umiarkowanie gęsty.
• Spójny? Tak, pojedyncza składowa.
• Trójkąty: dokładnie jeden (A–B–C), co potwierdza tr(A³) = 6.

Typowe zastosowania

• Analiza sieci społecznościowych — grafy przyjaźni / obserwujących, centralność.
• Grafy sieciowe i cytowań — algorytmy PageRank i HITS działają bezpośrednio na A i A^T.
• Routing i sieci — najkrótsza ścieżka, minimalne cięcie, maksymalny przepływ.
• Chemia — grafy molekularne, gdzie atomy są wierzchołkami, a wiązania krawędziami.
• Harmonogramowanie i rozwiązywanie zależności — skierowane grafy acykliczne (DAG) w systemach budowania.
• Łańcuchy Markowa — macierze stochastyczne wyprowadzone z grafów kodują prawdopodobieństwa przejść.

Często zadawane pytania

Co to jest macierz sąsiedztwa?

Macierz sąsiedztwa to macierz kwadratowa n × n służąca do reprezentacji skończonego grafu. Każda komórka A[i][j] wynosi 1, jeśli istnieje krawędź z wierzchołka i do wierzchołka j, a 0 w przeciwnym razie. Dla grafów nieskierowanych macierz jest symetryczna, więc A[i][j] = A[j][i]. Macierz ułatwia sprawdzanie połączenia w czasie stałym, a jej potęgi kodują liczbę dróg między wierzchołkami.

Jak stwierdzić, czy graf jest skierowany na podstawie macierzy?

Jeśli macierz sąsiedztwa jest symetryczna (A[i][j] = A[j][i] dla każdej pary indeksów), graf jest nieskierowany. Jeśli istnieje choć jedna para, gdzie A[i][j] różni się od A[j][i], graf jest skierowany. Kalkulator wykonuje to sprawdzenie automatycznie w opcji Auto-wykrywanie.

Co reprezentuje k-ta potęga macierzy sąsiedztwa?

Wpis (i, j) w A^k zlicza liczbę dróg o długości dokładnie k z wierzchołka i do wierzchołka j. Na przykład A²[i][j] to liczba ścieżek 2-krokowych, czyli liczba wspólnych sąsiadów między i oraz j w grafach nieskierowanych. Własność ta służy do zliczania trójkątów i obliczeń osiągalności.

Co to jest gęstość grafu?

Gęstość grafu to stosunek liczby istniejących krawędzi do maksymalnej możliwej liczby krawędzi. Dla nieskierowanego grafu prostego o n wierzchołkach, gęstość = 2m / (n(n-1)). Dla grafu skierowanego, gęstość = m / (n(n-1)). Gęstość bliska 0 oznacza graf rzadki, a gęstość 1 oznacza graf pełny.

Czym różni się macierz sąsiedztwa od listy sąsiedztwa?

Macierz sąsiedztwa przechowuje połączenia dla każdej pary wierzchołków przy użyciu n² bitów (szybki dostęp O(1), ale duża pamięć O(n²)). Lista sąsiedztwa przechowuje tylko faktycznych sąsiadów (mniejsza pamięć O(n + m), wolniejszy dostęp). Macierze są lepsze dla grafów gęstych i operacji macierzowych; listy dla grafów rzadkich i algorytmów przeszukiwania (BFS/DFS).

Czy to narzędzie obsługuje grafy ważone?

Kalkulator skupia się na nieważonych macierzach 0/1. Wklejenie wag numerycznych spowoduje, że każda wartość niezerowa zostanie potraktowana jako 1. Do obliczeń na grafach ważonych (np. algorytm Dijkstry) zalecamy dedykowane narzędzia do grafów ważonych.

Dalsza lektura

• Macierz sąsiedztwa — Wikipedia
• Stopień wierzchołka — Wikipedia
• Gęstość grafu — Wikipedia (EN)
• Składowa spójna grafu — Wikipedia