Stopnie wierzchołków grafu z macierzy sąsiedztwa
W kalkulatorze stopni wierzchołków grafu wpisujesz macierz sąsiedztwa, a wynik pokazuje stopień każdego wierzchołka, spójność grafu, regularność oraz prosty wykres stopni. To narzędzie odpowiada na typowe wyszukiwania: „jak policzyć stopień wierzchołka”, „czy graf jest spójny”, „czy graf jest regularny” oraz „suma stopni w grafie z macierzy”.
Ten kalkulator najlepiej łączyć z narzędziem graf pełny - liczba krawędzi, a przy szerszej powtórce z matematyką dyskretną także z kalkulatorem tablica prawdy, działania na zbiorach, modulo i rozszerzony algorytm Euklidesa.
Wzór i logika obliczeń
Dla grafu nieskierowanego macierz sąsiedztwa jest zwykle symetryczna. Stopień wierzchołka v_i to suma wartości w jego wierszu, czyli liczba krawędzi wychodzących z tego wierzchołka. Jeżeli w grafie dopuszczasz pętle, pętla w grafie nieskierowanym zwiększa stopień o 2, dlatego w zadaniach szkolnych najczęściej zostawia się zaznaczoną opcję zerowania przekątnej.
| Sytuacja | Jak liczyć | Co pokazuje kalkulator |
|---|---|---|
| Graf nieskierowany | Suma wiersza macierzy | Stopień każdego wierzchołka i sumę stopni |
| Graf skierowany | Suma wiersza i suma kolumny | Out-degree, in-degree oraz sumę |
| Graf regularny | Porównanie stopni wszystkich wierzchołków | Informację, czy graf jest regularny |
| Graf spójny | Przejście po krawędziach od pierwszego wierzchołka | Komunikat spójny albo niespójny |
Przykład obliczeń krok po kroku
Dla cyklu C5 każdy wierzchołek ma dwóch sąsiadów: poprzedni i następny. Po wybraniu szybkiego wypełnienia „Cykl Cn” oraz ustawieniu n=5 otrzymasz stopnie 2, 2, 2, 2, 2. Graf jest spójny, bo da się przejść między każdą parą wierzchołków, i jest regularny, bo wszystkie stopnie są takie same.
Zadanie 1
Graf ma stopnie 3, 3, 3, 3. Czy jest regularny?
Odpowiedź: Tak. To graf 3-regularny, bo każdy wierzchołek ma ten sam stopień.
Zadanie 2
Suma stopni w grafie nieskierowanym wynosi 14. Ile jest krawędzi?
Odpowiedź: Jest 7 krawędzi, bo suma stopni równa się 2·|E|.
Tabela referencyjna: grafy, stopnie i krawędzie
| Typ grafu | Stopnie wierzchołków | Liczba krawędzi | Wskazówka |
|---|---|---|---|
| Ścieżka P_n | Końce: 1, środek: 2 | n-1 | Dobre do nauki spójności |
| Cykl C_n | Wszystkie: 2 | n | Graf 2-regularny |
| Graf pełny K_n | Wszystkie: n-1 | n(n-1)/2 | Policzysz też w kalkulatorze grafu pełnego |
| Graf pusty | Wszystkie: 0 | 0 | Niespójny dla n>1 |
Stopnie grafu a inne działy matematyki dyskretnej
Teoria grafów często pojawia się obok logiki, zbiorów i arytmetyki modularnej. W praktyce zadanie może zaczynać się od zbioru wierzchołków, przejść do relacji sąsiedztwa, a potem wymagać sprawdzenia stopni i spójności. Dlatego po tym kalkulatorze warto przejść do działań na zbiorach, a następnie do tablic prawdy, jeśli w zadaniu pojawiają się warunki logiczne.
Przy zadaniach z liczbą możliwych połączeń przydaje się też kombinatoryka, permutacje, silnia i symbol Newtona oraz rekurencja i ciągi. To są tematy powiązane, ale nie zastępują kalkulatora stopni grafu.
Najczęstsze błędy i jak zwiększyć dokładność wyniku
- W grafie nieskierowanym macierz powinna być symetryczna. Jeśli wpiszesz tylko jedną połowę, kalkulator uzupełni ją według trybu nieskierowanego.
- Jeżeli zadanie nie mówi o pętlach, zostaw opcję „Zeruj przekątną”. Dzięki temu wartości na przekątnej nie zaburzą stopni.
- W grafie skierowanym nie myl out-degree z in-degree. Pierwszy wynika z wiersza, drugi z kolumny.
- Przy wklejaniu macierzy dopilnuj, aby liczba wierszy i kolumn była taka sama. Macierz sąsiedztwa grafu jest kwadratowa.
Lemat o uściskach dłoni mówi, że suma stopni w grafie nieskierowanym jest równa podwojonej liczbie krawędzi. To dlatego w takim grafie liczba wierzchołków o nieparzystym stopniu zawsze jest parzysta.
Wskazówka od KalkulatorXXL
Jeśli rozwiązujesz zadanie ręcznie, najpierw wypisz stopnie wierzchołków, potem sprawdź sumę stopni, a dopiero na końcu oceniaj spójność i regularność. Taka kolejność zmniejsza ryzyko pomyłki, bo szybki test Σdeg = 2·|E| od razu pokazuje, czy dane w macierzy są sensowne.
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.
Powiązane kalkulatory matematyki dyskretnej
W tym samym pakiecie sprawdź liczbę krawędzi grafu pełnego, generator tablicy prawdy, działania na zbiorach, kalkulator modulo oraz rozszerzony algorytm Euklidesa. Dzięki temu cały dział logiki, zbiorów i grafów będzie spójnie podlinkowany.
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.