Pemeriksa Grafik Planar

Tentang Pemeriksa Grafik Planar

Pemeriksa Grafik Planar menentukan apakah suatu grafik tak berarah sederhana bersifat planar — dapat digambar pada bidang tanpa ada dua tepi yang saling berpotongan — dan, jika grafik tersebut gagal dalam pengujian, ia akan menemukan dan memvisualisasikan bukti Kuratowski: sebuah subdivisi dari K₅ (grafik lengkap pada 5 simpul) atau K₃,₃ (grafik bipartit lengkap pada 3 + 3 simpul). Alat ini dibuat untuk pengajaran, pemanasan pemrograman kompetitif, dan pemeriksaan cepat konstruksi grafik kecil.

Apa Arti "Planar"?

Sebuah grafik G = (V, E) dikatakan planar jika ia dapat disematkan dalam bidang sehingga tepi-tepinya hanya bertemu di titik ujung bersamanya — tidak ada perpotongan. Secara ekuivalen, G dapat digambar pada permukaan bola tanpa perpotongan. Planaritas adalah properti topologi murni: ia tidak bergantung pada cara Anda menggambar grafik, melainkan hanya pada apakah ada gambar yang bebas perpotongan.

Grafik planar muncul di mana-mana — jaringan jalan dan utilitas, perutean papan sirkuit cetak (PCB), grafik tepi dari padatan Platonik, dan struktur muka polihedra. Namun, banyak grafik "alami" yang tetap non-planar: setiap kali Anda mencoba menghubungkan 3 rumah ke 3 utilitas tanpa perpotongan, Anda akan menghadapi penghalang K₃,₃.

Teorema Kuratowski — Inti dari Pemeriksa

Kazimierz Kuratowski membuktikan pada tahun 1930 bahwa planaritas memiliki karakterisasi kombinatorial murni:

Sebuah subdivision dari grafik H diperoleh dengan mengganti beberapa tepi H dengan jalur yang lebih panjang yang simpul internalnya semuanya adalah simpul derajat-2 baru. Oleh karena itu, teorema Kuratowski menyatakan bahwa K₅ dan K₃,₃ adalah satu-satunya hambatan bagi planaritas — setiap grafik non-planar mengandung salah satunya dalam bentuk yang "diregangkan".

Grafik yang Terlarang

Rumus Euler dan Syarat Perlu yang Cepat

Sebelum menjalankan pencarian subdivisi (yang relatif mahal), pemeriksa menerapkan dua syarat perlu cepat yang diturunkan dari rumus Euler: untuk grafik planar terhubung apa pun yang digambar di bidang dengan V simpul, E tepi, dan F muka (menghitung muka luar yang tidak terbatas), kita memiliki

Dikombinasikan dengan pengamatan bahwa setiap muka dari grafik planar sederhana memiliki setidaknya 3 tepi pada batasnya, kita mendapatkan batas atas tepi

Setiap grafik yang melanggar pertidaksamaan ini segera dinyatakan non-planar, tanpa perlu pencarian subdivisi. K₅ memiliki m = 10, n = 5 ⇒ 3n − 6 = 9, jadi 10 > 9 — melanggar batas. K₃,₃ memiliki m = 9, n = 6 ⇒ 2n − 4 = 8, jadi 9 > 8 — melanggar batas bipartit.

Cara Kerja Pencarian Subdivisi

Setelah pemeriksaan Euler yang ringan, pemeriksa mencari subdivisi secara langsung:

1. Kemenangan cepat — deteksi K₅ atau K₃,₃ sebagai subgrafik harfiah. Jika 5 simpul saling berdekatan secara berpasangan, itu adalah K₅ secara langsung. Jika 6 simpul terbagi 3 + 3 dengan semua 9 tepi silang ada, itu adalah K₃,₃.
2. Pencarian subdivisi K₅. Untuk setiap set kandidat 5 simpul "cabang" (masing-masing dengan derajat ≥ 4 di G), coba temukan 10 jalur — satu per pasang cabang — yang bersifat internally vertex-disjoint (tidak ada simpul non-cabang yang muncul di lebih dari satu jalur) dan hindari penggunaan cabang lain sebagai simpul internal. Temuan membuktikan non-planaritas.
3. Pencarian subdivisi K₃,₃. Pilih 6 cabang (masing-masing dengan derajat ≥ 3) dan bipartisi 3 + 3. Cari 9 jalur pasangan silang dengan persyaratan internal-disjoint yang sama.
4. Tidak ada bukti ⇒ planar. Jika tidak ada subdivisi yang ditemukan dalam batas ukuran, teorema Kuratowski menjamin grafik tersebut planar.

Menemukan jalur vertex-disjoint secara umum adalah NP-hard, sehingga pemeriksa menggunakan pencarian serakah acak terbatas: setiap iterasi mengurutkan pasangan yang diperlukan berdasarkan tingkat kesulitan, memilih jalur untuk pasangan tersulit terlebih dahulu menggunakan BFS acak, menghapus simpul internal tersebut, dan melanjutkan. Jika urutan tertentu gagal, ia mencoba lagi dengan urutan acak — hingga 40 upaya per konfigurasi cabang. Pada setiap grafik kecil yang diuji (hingga 16 simpul), ini cukup untuk menemukan bukti kapan pun bukti tersebut ada.

Cara Menggunakan Kalkulator Ini

1. Pilih format input menggunakan tab di bagian atas: daftar tepi atau daftar kedekatan. Keduanya mengodekan grafik yang sama.
2. Masukkan grafik Anda. Grafik diperlakukan sebagai tak berarah, jadi A-B dan B-A adalah tepi yang sama.
3. Klik Periksa Planaritas. Alat ini melaporkan keputusan, menunjukkan penalaran langkah-demi-langkah (Euler, bipartit, Kuratowski), dan merender grafik.
4. Untuk grafik non-planar visualisasi mewarnai subdivisi K₅ atau K₃,₃ dan mencantumkan 10 (atau 9) jalur vertex-disjoint. Klik baris jalur untuk mengisolasinya.
5. Untuk grafik planar jumlah muka F = m − n + 1 + c dilaporkan bersama dengan struktur grafik.

Contoh Pengerjaan 1 — K₄ adalah planar

K₄ memiliki n = 4, m = 6. Setiap grafik dengan ≤ 4 simpul adalah planar, dan memang K₄ tersemat sebagai segitiga dengan satu simpul di dalamnya yang terhubung ke ketiga sudutnya. Euler menyatakan F = 6 − 4 + 2 = 4 muka: tiga muka segitiga dalam ditambah muka luar.

Contoh Pengerjaan 2 — K₃,₃ adalah non-planar

K₃,₃ memiliki n = 6, m = 9. Karena bersifat bipartit, batas bipartit berlaku: m = 9 > 2n − 4 = 8. Ini saja sudah membuktikan non-planaritas. Buktinya bersifat trivial — K₃,₃ itu sendiri adalah subgrafik terlarang. Alat ini kemudian menyoroti partisi 3 + 3 dan 9 tepi langsung.

Contoh Pengerjaan 3 — Grafik Petersen

Grafik Petersen memiliki n = 10, m = 15, sehingga m ≤ 3n − 6 = 24 dan pemeriksaan Euler cepat lolos. Namun, ia terkenal non-planar. Pemeriksa menemukan subdivisi K₃,₃: pilih enam simpul dari pentagon luar dan pentagram dalam sehingga setiap pasangan silang dapat dirutekan melalui empat simpul sisanya dengan jalur vertex-disjoint. Alat ini menggambar buktinya, membuat geometri tahun 1930-an terasa nyata.

Aplikasi Planaritas

• Perutean VLSI dan PCB. Sirkuit satu lapis hanya layak jika grafik koneksinya planar; jaringan non-planar memaksa penggunaan via atau lapisan tambahan.
• Gambar dan visualisasi grafik. Grafik planar memungkinkan tata letak yang jelas dan bebas perpotongan — berguna untuk peta metro, grafik panggilan, dan diagram skema.
• Desain algoritma. Banyak masalah NP-hard (maximum cut, vertex cover, isomorfisme grafik) menjadi waktu-polinomial jika dibatasi pada grafik planar.
• Pewarnaan grafik. Teorema Empat Warna menjamin setiap grafik planar dapat diwarnai dengan 4 warna — hasil klasik yang pernyataannya bergantung pada planaritas.
• Optimasi kombinatorial. Jalur terpendek planar, max-flow, dan min-cut semuanya memiliki algoritma cepat khusus.
• Kimia molekuler. Grafik hidrokarbon aromatik cincin benzena bersifat planar; molekul sangkar tertentu tidak.

Pertanyaan yang Sering Diajukan

Apa arti planar bagi sebuah grafik?

Sebuah grafik dikatakan planar jika Anda dapat menggambarnya pada bidang sehingga tidak ada dua tepi yang saling berpotongan kecuali pada simpul yang sama. Secara ekuivalen, sebuah grafik adalah planar jika dan hanya jika dapat digambar pada permukaan bola tanpa perpotongan. Pohon, siklus, grafik kubus, dan padatan Platonik semuanya bersifat planar, sementara K₅ dan K₃,₃ adalah contoh kanonik non-planar.

Apa itu teorema Kuratowski?

Teorema Kuratowski menyatakan bahwa grafik hingga adalah planar jika dan hanya jika tidak mengandung subgrafik yang merupakan subdivisi dari K₅ atau K₃,₃. Sebuah subdivisi diperoleh dengan mengganti beberapa tepi dengan jalur yang lebih panjang, masing-masing melalui simpul derajat-2 yang baru. Ini memberikan sertifikat kombinatorial konkret dari non-planaritas.

Apa perbedaan antara K₅ dan K₃,₃?

K₅ memiliki 5 simpul, setiap pasangannya dihubungkan oleh sebuah tepi, sehingga totalnya ada 10 tepi. K₃,₃ memiliki 6 simpul yang dibagi menjadi dua kelompok berisi 3 simpul, dengan setiap simpul di satu kelompok terhubung ke setiap simpul di kelompok lainnya, sehingga totalnya ada 9 tepi. Keduanya adalah grafik non-planar terkecil di jenisnya, dan bersama-sama mereka membentuk minor terlarang untuk planaritas.

Bagaimana pertidaksamaan Euler membantu?

Rumus Euler V − E + F = 2 untuk grafik terhubung planar dikombinasikan dengan fakta bahwa setiap muka grafik planar sederhana memiliki setidaknya 3 tepi menghasilkan m ≤ 3n − 6. Grafik sederhana apa pun yang melanggar batas ini segera dinyatakan non-planar. Untuk grafik planar bipartit, setiap muka memiliki setidaknya 4 tepi, memberikan batas yang lebih ketat m ≤ 2n − 4. Pemeriksa menerapkan keduanya sebagai aturan penolakan cepat.

Berapa batas ukurannya?

Pemeriksa ini menangani hingga 16 simpul dan 60 tepi. Ini mencakup grafik gaya pengajaran dan kompetisi yang umum termasuk grafik Petersen, grafik Möbius-Kantor, hypercube kecil, dan grafik lengkap K₇. Grafik yang lebih besar memerlukan pengujian planaritas khusus waktu-linear seperti Hopcroft-Tarjan atau planaritas kiri-kanan.

Bagaimana subdivisi bukti digambar?

Ketika grafik bersifat non-planar, 5 simpul cabang dari K₅ yang ditemukan — atau 6 simpul cabang dari K₃,₃ yang dibagi menjadi dua tigaan A dan B — akan disorot pada cincin bagian dalam. 10 (atau 9) jalur vertex-disjoint internal yang diperlukan masing-masing digambar dalam warna berbeda sehingga Anda dapat melacak topologi K₅ atau K₃,₃ secara visual. Simpul dan tepi yang bukan bagian dari subdivisi akan diredupkan.

Bacaan Lebih Lanjut

• Planar graph — Wikipedia
• Kuratowski's theorem — Wikipedia
• Euler characteristic — Wikipedia
• Petersen graph — Wikipedia
• Wagner's theorem (minor version) — Wikipedia