Pamiętaj: Wyniki kalkulatorów mają charakter informacyjny i zależą od podanych danych oraz przyjętych założeń. W sprawach finansowych, podatkowych, prawnych lub zdrowotnych zweryfikuj wynik w aktualnym źródle lub u odpowiedniego specjalisty. Pamiętaj: Wyniki kalkulatorów mają charakter informacyjny i zależą od podanych danych oraz przyjętych założeń. W sprawach finansowych, podatkowych, prawnych lub zdrowotnych zweryfikuj wynik w aktualnym źródle lub u odpowiedniego specjalisty.
Przejdź do treści

Drzewa w grafach - kalkulator

Sprawdź, czy graf może być drzewem. Kalkulator analizuje liczbę wierzchołków i krawędzi, spójność albo ciąg stopni, a także pokazuje liczbę liści i najważniejsze własności drzewa.

Sprawdź graf lub ciąg stopni

Wybierz sposób sprawdzenia i wpisz dane z zadania.
drzewo • graf
Oddziel liczby przecinkami, średnikami albo spacjami, np. 3, 2, 2, 1, 1, 1, 2.
Dla pierwszego sposobu zakładamy prosty graf nieskierowany. Przy ciągu stopni kalkulator sprawdza, czy istnieje drzewo o podanych stopniach — nie odtwarza konkretnego rysunku grafu.

Czy to jest drzewo?

Wniosek
—
Wpisz dane grafu.
Wierzchołki
—
n
Krawędzie
—
m
Liście
—
wierzchołki stopnia 1
Warunek m = n − 1
—
—
Spójność
—
—
Podsumowanie:
Wpisz dane, aby sprawdzić warunki drzewa.

Rozwiązanie krok po kroku

Co dalej policzyć?

Po sprawdzeniu drzewa możesz przejść do stopni wierzchołków, liczby krawędzi, ścieżek albo macierzy sąsiedztwa.

Stopnie wierzchołków grafu
Policz stopnie i sprawdź spójność grafu z macierzy sąsiedztwa.
Graf pełny Kₙ
Policz liczbę krawędzi i stopień każdego wierzchołka.
Ścieżki i cykle w grafie
Sprawdź drogę, ścieżkę, szlak albo cykl.
Macierz sąsiedztwa grafu
Zamień listę krawędzi na macierz albo przeanalizuj gotową macierz.

Do czego służy kalkulator drzew w grafach?

Kalkulator pomaga sprawdzić, czy prosty graf nieskierowany jest drzewem. Drzewo jest grafem spójnym i bez cykli. Jeśli znasz liczbę wierzchołków, liczbę krawędzi i spójność, wystarczy sprawdzić warunek m = n − 1.

Możesz też podać ciąg stopni. Dla n > 1 dodatnie stopnie o sumie 2(n − 1) są ciągiem stopni pewnego drzewa. Dla pojedynczego wierzchołka poprawny ciąg to 0.

Jak sprawdzić drzewo?

m = n − 1
Drzewo z n wierzchołkami ma dokładnie n − 1 krawędzi.
Graf jest spójny
Każde dwa wierzchołki można połączyć ścieżką.
Σ deg = 2(n − 1)
To warunek używany przy sprawdzaniu ciągu stopni drzewa.
Liście
Każde drzewo z więcej niż jednym wierzchołkiem ma co najmniej dwa wierzchołki stopnia 1.

Przykład obliczeń

Graf ma n = 7 wierzchołków, m = 6 krawędzi i jest spójny. Ponieważ 6 = 7 − 1, graf spełnia warunek liczby krawędzi. Razem ze spójnością oznacza to, że jest drzewem.

Dla ciągu 3, 2, 2, 1, 1, 1, 2 suma stopni wynosi 12. Mamy 2(7 − 1) = 12, wszystkie stopnie są dodatnie, więc taki ciąg może być ciągiem stopni drzewa. Ma trzy liście, bo trzy wartości są równe 1.

Przykład drzewa

Na rysunku jest 7 wierzchołków i 6 krawędzi. Graf jest spójny i nie zawiera cyklu.

1234567 Drzewo: n = 7, m = 6, suma stopni = 12 Warunek: m = n − 1 oraz graf spójny Liście: 2, 5, 6, 7

Ćwiczenia z teorii grafów

Więcej przykładów i ćwiczeń znajdziesz w dziale zadań.

Drzewo, las, graf pełny i graf z cyklem

Drzewo
Jest spójne i nie ma cykli. Dla n wierzchołków ma n − 1 krawędzi.
Las
Nie ma cykli, ale może składać się z kilku niespójnych drzew.
Graf pełny
Każda para różnych wierzchołków jest połączona. Ma n(n − 1)/2 krawędzi.
Graf z cyklem
Zawiera zamkniętą drogę. Spójny graf z co najmniej n krawędziami na pewno ma cykl.

Najczęstsze błędy

  • Pomijanie spójności — sam warunek m = n − 1 nie wystarcza, jeśli nie wiadomo, czy graf jest spójny.
  • Mylenie drzewa z grafem pełnym — graf pełny zwykle ma znacznie więcej krawędzi.
  • Zero w ciągu stopni — dla drzewa z n > 1 każdy stopień jest dodatni.
  • Mylenie drzewa z lasem — las może być niespójny, drzewo musi być spójne.

Ciekawostka

Drzewa pojawiają się w strukturach danych, wyszukiwaniu, sieciach i wielu algorytmach. Szczególnym przykładem jest minimalne drzewo rozpinające, które łączy wszystkie wierzchołki przy minimalnym łącznym koszcie krawędzi.

Wskazówka od KalkulatorXXL

Jeśli w zadaniu pytają, czy graf jest drzewem, najpierw policz krawędzie i sprawdź spójność. Dla prostego grafu nieskierowanego warunek m = n − 1 razem ze spójnością daje jednoznaczną odpowiedź.

Cały dział matematyki dyskretnej: Akademia matematyki dyskretnej – logika, zbiory i grafy.

Aktualizacja: 29.09.2026

FAQ - drzewa w grafach

Najczęściej sprawdza się dwa warunki: graf musi być spójny i mieć dokładnie m = n - 1 krawędzi.

Każde drzewo ma dokładnie n - 1 krawędzi.

Tak. To jeden z najważniejszych testów drzewa w teorii grafów.

Nie. Drzewo jest grafem bez cykli.

Każde drzewo z więcej niż jednym wierzchołkiem ma co najmniej dwa liście.

Suma stopni musi wynosić 2(n - 1). Dla n > 1 stopnie w drzewie są dodatnie.

Las to zbiór drzew. Może być niespójny, a drzewo musi być spójne.

Zwykle nie. Graf pełny ma znacznie więcej krawędzi niż drzewo. Wyjątkiem jest K2, które jest jednocześnie drzewem.

Drzewa są podstawą struktur danych, wyszukiwania, sortowania, sieci i wielu algorytmów.

Popularne w tej kategorii

Kalkulator liczb rzymskichPopularne
Wpisz dane i zobacz wynik natychmiast.
Kalkulator wspólnego mianownika ułamkówPopularne
Wpisz dane i zobacz wynik natychmiast.
Kalkulator działań pisemnych
Wpisz dane i zobacz wynik natychmiast.
Kalkulator procentów
Wpisz dane i zobacz wynik natychmiast.