Jaka jest różnica między K5 a K3,3?

K5 ma 5 wierzchołków, z których każda para jest połączona krawędzią, co daje łącznie 10 krawędzi. K3,3 ma 6 wierzchołków podzielonych na dwie grupy po 3, przy czym każdy wierzchołek z jednej grupy jest połączony z każdym wierzchołkiem z drugiej, co daje 9 krawędzi. Oba są najmniejszymi grafami nieplanarnymi w swoim rodzaju i razem tworzą zabronione minory dla planarności zgodnie z twierdzeniem Kuratowskiego.

Walidator Grafu Planarnego

Sprawdź, czy graf jest planarny (możliwy do narysowania bez przecinania się krawędzi) przy użyciu twierdzenia Kuratowskiego. Narzędzie wykrywa podziały K5 i K3,3, weryfikuje nierówność Eulera m ≤ 3n − 6 i wizualnie wyróżnia zakazany minor, gdy graf jest nieplanarny.

Embed Walidator Grafu Planarnego Widget

O Walidator Grafu Planarnego

Walidator Grafu Planarnego rozstrzyga, czy prosty graf nieskierowany jest planarny — czyli czy można go narysować na płaszczyźnie bez przecinania się krawędzi — a w przypadku negatywnego wyniku testu, znajduje i wizualizuje dowód Kuratowskiego: podział grafu K₅ (grafu pełnego o 5 wierzchołkach) lub K₃,₃ (pełnego grafu dwudzielnego o 3 + 3 wierzchołkach). Narzędzie to zostało stworzone do celów edukacyjnych, przygotowań do programowania konkurencyjnego oraz szybkiej weryfikacji małych konstrukcji grafowych.

Co oznacza "planarny"?

Graf G = (V, E) jest planarny, jeśli można go osadzić na płaszczyźnie w taki sposób, aby krawędzie stykały się tylko w swoich punktach końcowych — bez przecięć. Równoważnie, G można narysować na powierzchni sfery bez przecięć. Planarność jest właściwością czysto topologiczną: nie zależy od tego, jak narysujesz graf, lecz od tego, czy istnieje jakikolwiek rysunek wolny od przecięć.

Grafy planarne pojawiają się wszędzie — w sieciach drogowych i przesyłowych, projektowaniu obwodów drukowanych, grafach krawędzi wielościanów foremnych czy strukturze ścian wielościanów. Jednak wiele "naturalnych" grafów jest uporczywie nieplanarnych: za każdym razem, gdy próbujesz połączyć 3 domy z 3 mediami (wodociągi, gaz, prąd) bez przecięć, napotykasz barierę K₃,₃.

Twierdzenie Kuratowskiego — serce walidatora

Kazimierz Kuratowski udowodnił w 1930 roku, że planarność posiada czysto kombinatoryczną charakteryzację:

Graf skończony jest planarny ⇔ nie zawiera podziału K₅ ani podziału K₃,₃.

Podział grafu H uzyskuje się przez zastąpienie niektórych krawędzi H dłuższymi ścieżkami, których wewnętrzne wierzchołki są nowymi wierzchołkami stopnia 2. Twierdzenie Kuratowskiego mówi zatem, że K₅ i K₃,₃ są jedynymi przeszkodami dla planarności — każdy graf nieplanarny zawiera jeden z nich w "rozciągniętej" formie.

Zabronione grafy

Graf	Wierzchołki	Krawędzie	Struktura	Planarny?
K₅	5	10	Każda para wierzchołków jest połączona krawędzią (graf pełny).	Nie
K₃,₃	6	9	Dwie trójki A i B; każdy a ∈ A połączony z każdym b ∈ B.	Nie
K₄	4	6	Graf pełny o 4 wierzchołkach.	Tak
K₂,₃	5	6	Pełny graf dwudzielny 2 × 3.	Tak

Wzór Eulera i szybkie warunki konieczne

Przed uruchomieniem (stosunkowo kosztownego) wyszukiwania podziału, walidator stosuje dwa szybkie warunki konieczne wywodzące się ze wzoru Eulera: dla każdego spójnego grafu planarnego narysowanego na płaszczyźnie z V wierzchołkami, E krawędziami i F ścianami (wliczając zewnętrzną), mamy:

V − E + F = 2 (Wzór Eulera dla spójnych grafów planarnych) V − E + F = 1 + c (dla grafu planarnego o c składowych spójnych)

W połączeniu z obserwacją, że każda ściana prostego grafu planarnego ma co najmniej 3 krawędzie na brzegu, otrzymujemy górne ograniczenie liczby krawędzi:

m ≤ 3n − 6 (prosty planarny, n ≥ 3) m ≤ 2n − 4 (dwudzielny prosty planarny, n ≥ 3)

Każdy graf naruszający te nierówności jest natychmiast uznawany za nieplanarny, bez potrzeby szukania podziału. K₅ ma m = 10, n = 5 ⇒ 3n − 6 = 9, więc 10 > 9 — narusza ograniczenie. K₃,₃ ma m = 9, n = 6 ⇒ 2n − 4 = 8, więc 9 > 8 — narusza ograniczenie dla grafów dwudzielnych.

Jak działa wyszukiwanie podziału

Po wykonaniu szybkich testów Eulera, walidator bezpośrednio wyszukuje podział:

Szybka wygrana — wykrycie K₅ lub K₃,₃ jako dosłownego podgrafu. Jeśli 5 wierzchołków jest połączonych każdy z każdym, to jest to bezpośrednio K₅. Jeśli 6 wierzchołków dzieli się na 3 + 3 ze wszystkimi 9 krawędziami międzygrupowymi, to jest to K₃,₃.
Wyszukiwanie podziału K₅. Dla każdego zestawu kandydatów na 5 wierzchołków "głównych" (o stopniu ≥ 4), próbuje znaleźć 10 ścieżek — po jednej na każdą parę — które są wewnętrznie rozłączne wierzchołkowo. Znalezienie takiego zestawu dowodzi nieplanarności.
Wyszukiwanie podziału K₃,₃. Wybiera 6 wierzchołków głównych (o stopniu ≥ 3) i dwupodział 3 + 3. Szuka 9 ścieżek międzygrupowych przy zachowaniu warunku rozłączności.
Brak dowodu ⇒ planarny. Jeśli w granicach rozmiaru nie zostanie znaleziony żaden podział, twierdzenie Kuratowskiego gwarantuje, że graf jest planarny.

Znajdowanie wierzchołkowo rozłącznych ścieżek jest ogólnie problemem NP-trudnym, dlatego walidator używa ograniczonego losowego przeszukiwania zachłannego. Dla każdego przetestowanego małego grafu (do 16 wierzchołków) metoda ta jest wystarczająca do znalezienia dowodu.

Jak korzystać z tego kalkulatora

Wybierz format wejściowy za pomocą kart u góry: lista krawędzi lub lista sąsiedztwa.
Wprowadź swój graf. Jest on traktowany jako nieskierowany, więc A-B i B-A to ta sama krawędź.
Kliknij Sprawdź planarność. Narzędzie wyświetli werdykt, rozumowanie krok po kroku i wygeneruje rysunek.
Dla grafu nieplanarnego wizualizacja pokoloruje podział K₅ lub K₃,₃ i wymieni ścieżki rozłączne.
Dla grafu planarnego podana zostanie liczba ścian F = m − n + 1 + c.

Przykład 1 — K₄ jest planarny

K₄ ma n = 4, m = 6. Każdy graf o ≤ 4 wierzchołkach jest planarny; K₄ osadza się jako trójkąt z jednym wierzchołkiem wewnątrz połączonym ze wszystkimi narożnikami. Euler mówi o F = 6 − 4 + 2 = 4 ścianach: trzy trójkątne ściany wewnętrzne plus zewnętrzna.

Przykład 2 — K₃,₃ jest nieplanarny

K₃,₃ ma n = 6, m = 9. Jest dwudzielny, więc stosuje się ograniczenie: m = 9 > 2n − 4 = 8. To samo w sobie dowodzi nieplanarności. Dowód jest trywialny — K₃,₃ sam w sobie jest zabronionym podgrafem.

Przykład 3 — Graf Petersena

Graf Petersena ma n = 10, m = 15, więc m ≤ 3n − 6 = 24 i testy Eulera przechodzą pomyślnie. Mimo to jest on słynnym przykładem grafu nieplanarnego. Walidator lokalizuje podział K₃,₃, czyniąc geometrię z lat 30. XX wieku namacalną.

Zastosowania planarności

Projektowanie VLSI i PCB. Obwód jednowarstwowy jest możliwy do zrealizowania tylko wtedy, gdy graf połączeń jest planarny.
Wizualizacja grafów. Grafy planarne pozwalają na czytelne układy bez przecięć — przydatne w mapach metra i schematach.
Projektowanie algorytmów. Wiele problemów NP-trudnych staje się rozwiązywalnych w czasie wielomianowym dla grafów planarnych.
Kolorowanie grafów. Twierdzenie o czterech barwach gwarantuje, że każdy graf planarny jest 4-kolorowalny.
Chemia molekularna. Grafy węglowodorów aromatycznych są planarne; niektóre cząsteczki klatkowe nie.

Często zadawane pytania

Co oznacza, że graf jest planarny?

Graf jest planarny, jeśli można go narysować na płaszczyźnie tak, aby żadne dwie krawędzie nie przecinały się poza wspólnymi wierzchołkami. Drzewa, cykle i bryły platońskie są planarne, podczas gdy K₅ i K₃,₃ to klasyczne przykłady nieplanarne.

Co to jest twierdzenie Kuratowskiego?

Mówi ono, że graf jest planarny wtedy i tylko wtedy, gdy nie zawiera podgrafu będącego podziałem K₅ lub K₃,₃. Daje to konkretny dowód kombinatoryczny na brak planarności.

Jaka jest różnica między K₅ a K₃,₃?

K₅ ma 5 wierzchołków połączonych każdy z każdym (10 krawędzi). K₃,₃ ma 6 wierzchołków podzielonych na dwie grupy po 3 (9 krawędzi). Oba są najmniejszymi grafami nieplanarnymi.

Jak pomaga nierówność Eulera?

Wzór V − E + F = 2 prowadzi do nierówności m ≤ 3n − 6. Każdy graf prosty naruszający ten warunek musi być nieplanarny. Walidator stosuje to jako szybką regułę odrzucania.

Jaki jest limit wielkości?

Narzędzie obsługuje do 16 wierzchołków i 60 krawędzi, co wystarcza dla większości grafów dydaktycznych i małych hipersześcianów.

Jak rysowany jest dowód podziału?

Wierzchołki główne K₅ lub K₃,₃ są podświetlone na wewnętrznym pierścieniu, a ścieżki je łączące są rysowane w różnych kolorach. Pozostałe elementy grafu są przyciemnione.

Dalsza lektura

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

"Walidator Grafu Planarnego" na https://MiniWebtool.com/pl/walidator-grafu-planarnego/ z MiniWebtool, https://MiniWebtool.com/

przez zespół miniwebtool. Aktualizacja: 22 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.

Walidator Grafu Planarnego

O Walidator Grafu Planarnego

Co oznacza "planarny"?

Twierdzenie Kuratowskiego — serce walidatora

Zabronione grafy

Wzór Eulera i szybkie warunki konieczne

Jak działa wyszukiwanie podziału

Jak korzystać z tego kalkulatora

Przykład 1 — K₄ jest planarny

Przykład 2 — K₃,₃ jest nieplanarny

Przykład 3 — Graf Petersena

Zastosowania planarności

Często zadawane pytania

Co oznacza, że graf jest planarny?

Co to jest twierdzenie Kuratowskiego?

Jaka jest różnica między K₅ a K₃,₃?

Jak pomaga nierówność Eulera?

Jaki jest limit wielkości?

Jak rysowany jest dowód podziału?

Dalsza lektura

Zaawansowane działania matematyczne:

Polecane narzędzia: