Aplikasi teori grafik
Grafik planar
Grafik G dikatakan planar jika dapat direpresentasikan pada bidang sedemikian rupa sehingga semua simpul adalah titik yang berbeda, ujungnya adalah kurva sederhana, dan tidak ada dua sisi yang saling bertemu kecuali di terminalnya. Sebagai contoh, K 4, grafik lengkap pada empat simpul, adalah planar, seperti yang ditunjukkan Gambar 4A.
Dua grafik dikatakan homeomorfik jika keduanya dapat diperoleh dari grafik yang sama dengan subdivisi sisi. Sebagai contoh, grafik pada Gambar 4A dan Gambar 4B adalah homeomorfik.
K m, n grafik adalah grafik yang himpunan titik dapat dibagi menjadi dua himpunan bagian, satu dengan simpul m dan yang lainnya dengan n simpul. Setiap dua simpul dari himpunan bagian yang sama adalah tidak berdekatan, sedangkan dua simpul dari himpunan bagian yang berbeda berdekatan. Ahli matematika Polandia Kazimierz Kuratowski pada tahun 1930 membuktikan teorema terkenal berikut ini:
Kondisi yang diperlukan dan cukup untuk grafik G menjadi planar adalah bahwa grafik itu tidak mengandung homeomorfik subgraph ke K 5 atau K 3,3 yang ditunjukkan pada Gambar 5.
Kontraksi SD dari graf G adalah transformasi G untuk grafik baru G 1, sehingga dua simpul yang berdekatan u dan υ dari G digantikan oleh titik baru w di G 1 dan w berdekatan di G 1 untuk semua simpul untuk yang salah satu dari kita atau kita berbatasan dalam G. Sebuah grafik G * dikatakan sebagai kontraksi G jika G * dapat diperoleh dari G dengan urutan kontraksi elementer. Berikut ini adalah karakterisasi lain dari grafik planar karena ahli matematika Jerman K. Wagner pada tahun 1937.
Grafik planar jika dan hanya jika tidak dapat dikontrak ke K 5 atau K 3,3.
Masalah peta empat warna
Selama lebih dari seabad solusi dari masalah peta empat warna luput dari setiap analis yang mencobanya. Masalahnya mungkin telah menarik perhatian Möbius, tetapi referensi tertulis pertama tampaknya adalah surat dari satu Francis Guthrie kepada saudaranya, seorang mahasiswa Augustus De Morgan, pada tahun 1852.
Masalahnya menyangkut peta planar — yaitu, subdivisi pesawat ke daerah yang tidak tumpang tindih yang dibatasi oleh kurva tertutup sederhana. Dalam peta geografis telah diamati secara empiris, dalam banyak kasus khusus seperti yang telah dicoba, bahwa, paling banyak, empat warna diperlukan untuk mewarnai daerah sehingga dua daerah yang memiliki batas yang sama selalu berwarna berbeda, dan dalam kasus-kasus tertentu yang setidaknya diperlukan empat warna. (Wilayah yang hanya bertemu pada suatu titik, seperti negara bagian Colorado dan Arizona di Amerika Serikat, tidak dianggap memiliki batas bersama). Formalisasi dari pengamatan empiris ini membentuk apa yang disebut “teorema empat warna.” Masalahnya adalah untuk membuktikan atau membantah pernyataan bahwa ini adalah kasus untuk setiap peta planar. Tiga warna tidak akan cukup mudah ditunjukkan, sedangkan kecukupan lima warna dibuktikan pada tahun 1890 oleh ahli matematika Inggris PJ Heawood.
Pada 1879 AB Kempe, seorang Inggris, mengusulkan solusi untuk masalah empat warna. Meskipun Heawood menunjukkan bahwa argumen Kempe cacat, dua konsepnya terbukti berhasil dalam penyelidikan selanjutnya. Salah satunya, yang disebut tidak terhindarkan, dengan tepat menyatakan ketidakmungkinan membangun peta di mana setiap satu dari empat konfigurasi tidak ada (konfigurasi ini terdiri dari wilayah dengan dua tetangga, satu dengan tiga, satu dengan empat, dan satu dengan lima). Konsep kedua, yaitu reducibilitas, mengambil namanya dari bukti sah Kempe bahwa jika ada peta yang membutuhkan setidaknya lima warna dan yang berisi wilayah dengan empat (atau tiga atau dua) tetangga, maka harus ada peta yang membutuhkan lima warna untuk sejumlah kecil wilayah. Upaya Kempe untuk membuktikan reducibilitas peta yang berisi wilayah dengan lima tetangga itu keliru, tetapi diperbaiki dalam bukti yang diterbitkan pada tahun 1976 oleh Kenneth Appel dan Wolfgang Haken dari Amerika Serikat. Bukti mereka menarik beberapa kritik karena mengharuskan evaluasi 1.936 kasus yang berbeda, masing-masing melibatkan sebanyak 500.000 operasi logis. Appel, Haken, dan kolaborator mereka merancang program yang memungkinkan komputer digital besar untuk menangani detail ini. Komputer membutuhkan lebih dari 1.000 jam untuk melakukan tugas, dan bukti formal yang dihasilkan adalah beberapa ratus halaman.
Siklus Euler dan masalah jembatan Königsberg
Multigraf G terdiri dari set V (G) simpul yang tidak kosong dan subset E (G) dari himpunan pasangan elemen V (G) yang tidak berurutan dengan frekuensi f ≥ 1 yang melekat pada setiap pasangan. Jika pasangan (x 1, x 2) dengan frekuensi f milik E (G), maka simpul x 1 dan x 2 bergabung dengan f tepi.
Siklus Euler dari multigraf G adalah rantai tertutup di mana setiap sisi muncul tepat satu kali. Euler menunjukkan bahwa multigraf memiliki siklus Euler jika dan hanya jika terhubung (terpisah dari titik-titik yang terisolasi) dan jumlah simpul derajat ganjil adalah nol atau dua.
Masalah ini pertama kali muncul dengan cara berikut. Sungai Pregel, dibentuk oleh pertemuan dua cabangnya, mengalir melalui kota Königsberg dan mengalir di kedua sisi pulau Kneiphof. Ada tujuh jembatan, seperti yang ditunjukkan pada Gambar 6A. Warga kota bertanya-tanya apakah mungkin berjalan-jalan dan menyeberangi setiap jembatan hanya sekali dan sekali saja. Ini sama dengan menemukan siklus Euler untuk multigraf pada Gambar 6B. Euler menunjukkan itu mustahil karena ada empat simpul urutan aneh.
