Matematik gabungan

Aplikasi teori grafik

Graf satah

Graf G dikatakan datar jika dapat dilambangkan pada satah sedemikian rupa sehingga bucu-bucu itu semua titik yang berbeza, tepinya adalah lengkung sederhana, dan tidak ada dua tepi yang saling bertemu kecuali di terminal mereka. Sebagai contoh, K ₄, graf lengkap pada empat bucu, adalah satah, seperti yang ditunjukkan oleh Rajah 4A.

Dua graf dikatakan homeomorfik jika kedua-duanya dapat diperoleh dari graf yang sama dengan subdivisi tepi. Contohnya, graf dalam Rajah 4A dan Gambar 4B adalah homeomorfik.

Grafik K _{m, n} adalah grafik di mana set bucu boleh dibahagikan kepada dua subset, satu dengan bucu m dan yang lain dengan bucu n. Mana-mana dua bucu subset yang sama tidak bersebelahan, sedangkan dua bucu subset yang berlainan bersebelahan. Ahli matematik Poland Kazimierz Kuratowski pada tahun 1930 membuktikan teorema terkenal berikut:

Keadaan yang perlu dan mencukupi untuk graf G menjadi datar ialah ia tidak mengandungi homegrafik subgraf sama ada K ₅ atau K _3,3 seperti yang ditunjukkan dalam Rajah 5.

Kontraksi dasar graf G adalah transformasi G ke graf baru G ₁, sehingga dua bucu bersebelahan u dan υ G digantikan oleh bucu baru w di G ₁ dan w bersebelahan di G ₁ ke semua bucu ke yang u atau υ bersebelahan di G. Graf G * dikatakan sebagai penguncupan G jika G * dapat diperoleh dari G dengan urutan kontraksi unsur. Berikut adalah ciri lain dari graf satah kerana ahli matematik Jerman K. Wagner pada tahun 1937.

Grafik adalah satah jika dan hanya jika tidak boleh dikontrak dengan K ₅ atau K _3,3.

Masalah peta empat warna

Selama lebih dari satu abad, penyelesaian masalah peta empat warna itu menghindarkan setiap penganalisis yang mencubanya. Masalahnya mungkin menarik perhatian Möbius, tetapi rujukan bertulis pertama untuk itu sepertinya adalah surat dari seorang Francis Guthrie kepada saudaranya, seorang pelajar Augustus De Morgan, pada tahun 1852.

Masalahnya menyangkut peta satah — iaitu, pembahagian pesawat ke kawasan yang tidak bertindih dibatasi oleh lekuk tertutup sederhana. Dalam peta geografi telah diperhatikan secara empirik, dalam banyak kasus khusus yang telah dicoba, bahwa, paling banyak, empat warna diperlukan untuk mewarnai kawasan sehingga dua wilayah yang memiliki batas yang sama selalu berwarna berbeda, dan di kes tertentu yang memerlukan sekurang-kurangnya empat warna. (Kawasan yang bertemu hanya pada satu titik, seperti negara bagian Colorado dan Arizona di Amerika Syarikat, tidak dianggap memiliki batas yang sama). Formalisasi pemerhatian empirikal ini adalah apa yang disebut "teorema empat warna." Masalahnya adalah untuk membuktikan atau membantah penegasan bahawa ini berlaku untuk setiap peta satah. Ketiga warna itu tidak mencukupi ditunjukkan dengan mudah, sedangkan kecukupan lima warna dibuktikan pada tahun 1890 oleh ahli matematik Inggeris PJ Heawood.

Pada tahun 1879 AB Kempe, seorang Inggeris, mencadangkan penyelesaian masalah empat warna. Walaupun Heawood menunjukkan bahawa hujah Kempe adalah salah, dua konsepnya terbukti bermanfaat dalam penyelidikan kemudian. Salah satunya, yang disebut tidak dapat dielakkan, dengan betul menyatakan kemustahilan membina peta di mana setiap satu dari empat konfigurasi tidak ada (konfigurasi ini terdiri daripada kawasan dengan dua jiran, satu dengan tiga, satu dengan empat, dan satu dengan lima). Konsep kedua, konsep reducibility, mengambil namanya dari bukti sahih Kempe bahawa jika ada peta yang memerlukan sekurang-kurangnya lima warna dan yang mengandungi wilayah dengan empat (atau tiga atau dua) tetangga, maka mesti ada peta yang memerlukan lima warna untuk sebilangan kecil wilayah. Percubaan Kempe untuk membuktikan pengurangan peta yang mengandungi wilayah dengan lima jiran adalah salah, tetapi ia diperbaiki dalam bukti yang diterbitkan pada tahun 1976 oleh Kenneth Appel dan Wolfgang Haken dari Amerika Syarikat. Bukti mereka menarik beberapa kritikan kerana memerlukan penilaian terhadap 1,936 kes yang berbeza, masing-masing melibatkan sebanyak 500,000 operasi logik. Appel, Haken, dan kolaborator mereka merancang program yang memungkinkan komputer digital yang besar dapat menangani perincian ini. Komputer memerlukan lebih dari 1,000 jam untuk melaksanakan tugas itu, dan bukti formal yang dihasilkan panjangnya beratus-ratus halaman.

Kitaran Eulerian dan masalah jambatan Königsberg

Multigraf G terdiri daripada set simpul V (G) yang tidak kosong dan subset E (G) dari kumpulan pasangan unsur yang tidak tersusun dari V (G) dengan frekuensi f ≥ 1 yang dilampirkan pada setiap pasangan. Sekiranya pasangan (x ₁, x ₂) dengan frekuensi f tergolong dalam E (G), maka bucu x ₁ dan x ₂ disatukan oleh tepi f.

Kitaran Eulerian multigraf G adalah rantai tertutup di mana setiap pinggir muncul tepat sekali. Euler menunjukkan bahawa multigraf mempunyai kitaran Eulerian jika dan hanya jika disambungkan (selain dari titik terpencil) dan bilangan titik darjah ganjil sama ada sifar atau dua.

Masalah ini mula timbul dengan cara berikut. Sungai Pregel, dibentuk oleh pertemuan dua cabangnya, melintasi kota Königsberg dan mengalir di kedua sisi pulau Kneiphof. Terdapat tujuh jambatan, seperti yang ditunjukkan pada Gambar 6A. Penduduk bandar tertanya-tanya adakah mungkin untuk berjalan-jalan dan menyeberangi setiap jambatan sekali dan sekali sahaja. Ini sama dengan mencari kitaran Eulerian untuk multigraf dalam Rajah 6B. Euler menunjukkan ia mustahil kerana terdapat empat titik urutan ganjil.