Walidator Grafu Planarnego

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ę:

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

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:

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:

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ł:

1. 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₃,₃.
2. 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.
3. 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.
4. 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

1. Wybierz format wejściowy za pomocą kart u góry: lista krawędzi lub lista sąsiedztwa.
2. Wprowadź swój graf. Jest on traktowany jako nieskierowany, więc A-B i B-A to ta sama krawędź.
3. Kliknij Sprawdź planarność. Narzędzie wyświetli werdykt, rozumowanie krok po kroku i wygeneruje rysunek.
4. Dla grafu nieplanarnego wizualizacja pokoloruje podział K₅ lub K₃,₃ i wymieni ścieżki rozłączne.
5. 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

• Graf planarny — Wikipedia
• Twierdzenie Kuratowskiego — Wikipedia
• Charakterystyka Eulera — Wikipedia
• Graf Petersena — Wikipedia