Kalkulator Macierzy Sąsiedztwa

Konwertuj między macierzą sąsiedztwa, listą krawędzi i listą sąsiedztwa. Automatycznie wykrywa grafy skierowane/nieskierowane, oblicza ciąg stopni, gęstość, spójne składowe i potęgi macierzy — z interaktywną wizualizacją grafu SVG.

Szybkie przykłady:

Trójkąt nieskierowany + ogon Cykl skierowany K4 (lista sąsiedztwa) Macierz 4×4 Etykiety numeryczne

↔ Lista krawędzi ☰ Lista sąsiedztwa ▦ Macierz sąsiedztwa

Dane grafu

Akceptuje A-B, A->B, A B, A,B lub wiersze macierzy jak 0 1 1 0. Używaj liter, cyfr lub podkreślników dla etykiet wierzchołków.

Etykiety macierzy (opcjonalnie)

Etykiety oddzielone przecinkami lub spacjami, jedna na wiersz macierzy. Domyślnie A, B, C…, jeśli pominięto.

Typ grafu

Embed Kalkulator Macierzy Sąsiedztwa Widget

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.

A[i][j] = 1 jeśli (v_i, v_j) ∈ E , inaczej 0

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

Reprezentacja	Pamięć	Szukanie krawędzi	Lista sąsiadów	Najlepsza dla
Macierz sąsiedztwa	Θ(n²)	O(1)	Θ(n)	Grafy gęste; algebra macierzy (potęgi, wartości własne)
Lista sąsiedztwa	Θ(n + m)	O(deg v)	Θ(deg v)	Grafy rzadkie; algorytmy BFS/DFS i najkrótszej ścieżki
Lista krawędzi	Θ(m)	Θ(m)	Θ(m)	Wejście/wyjście, algorytm Kruskala, algorytmy krawędziowe

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.

Lemat o uściskach dłoni: Σ deg(v) = 2m (nieskierowany) Σ in-deg(v) = Σ out-deg(v) = m (skierowany)

Gęstość grafu

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

Nieskierowany: D = 2m / (n(n−1)) Skierowany: D = m / (n(n−1))

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ą.

A-B, B-C, C-A, C-D (nieskierowany cykl 3 z ogonem) A->B, B->C, C->D, D->A (skierowany cykl o długości 4)

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.

A: B, C, D B: A, C C: A, B, D D: A, C

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…).

0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0

Jak korzystać z tego kalkulatora

Wybierz format wejściowy za pomocą selektora zakładek: lista krawędzi, lista sąsiedztwa lub macierz sąsiedztwa.
Wklej lub wpisz swój graf w obszarze tekstowym. W przypadku macierzy dodaj opcjonalne etykiety w polu Etykiety macierzy.
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.
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.
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:

A B C D A [ 0 1 1 0 ] B [ 1 0 1 0 ] C [ 1 1 0 1 ] D [ 0 0 1 0 ]

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

Cytuj ten materiał, stronę lub narzędzie w następujący sposób:

"Kalkulator Macierzy Sąsiedztwa" na https://MiniWebtool.com/pl/kalkulator-macierzy-sasiedztwa/ z MiniWebtool, https://MiniWebtool.com/

przez zespół miniwebtool. Aktualizacja: 20 kwietnia 2026

Możesz także wypróbować nasz AI Rozwiązywacz Matematyczny GPT, aby rozwiązywać swoje problemy matematyczne poprzez pytania i odpowiedzi w języku naturalnym.

Inne powiązane narzędzia:

Kalkulator Wartości BezwzględnejNowy

Rozwiązywacz Równań Wartości Bezwzględnej

Rozwiązywacz nierówności wartości bezwzględnej

Solver Zadań o WiekuNowy

Sprawdzacz Liczb ZaprzyjaźnionychNowy

Kalkulator Antylogarytmów

Kalkulator ciągu arytmetycznego (wysoka precyzja)

📊 Kreator Wykresów SłupkowychNowy

Kalkulator funkcji beta

Konwerter binarny na dziesiętnyPolecane

Kalkulator Macierzy Sąsiedztwa

O Kalkulator Macierzy Sąsiedztwa

Co to jest macierz sąsiedztwa?

Trzy reprezentacje — wybierz dopasowaną do problemu

Obliczane kluczowe metryki

Ciąg stopni

Gęstość grafu

Spójne składowe

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

Akceptowane formaty wejściowe

1. Lista krawędzi

2. Lista sąsiedztwa

3. Macierz sąsiedztwa

Jak korzystać z tego kalkulatora

Przykład krok po kroku

Typowe zastosowania

Często zadawane pytania

Co to jest macierz sąsiedztwa?

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

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

Co to jest gęstość grafu?

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

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

Dalsza lektura

Inne powiązane narzędzia:

Zaawansowane działania matematyczne:

Polecane narzędzia: