Teori graf
Noktah-noktah dan garis di antaranya: hanya itulah graf. Namun gambar yang sama bisa melukiskan peta jalan, jaringan pertemanan, molekul, dan internet, dan pertanyaan-pertanyaan yang bisa diajukan tentangnya, mulai dari berapa warna yang dibutuhkan sampai apakah ia bisa digambar dengan satu goresan, telah menyibukkan para matematikawan sejak 1736.
Titik dan sisi
Sebuah graf memiliki titik, yang juga disebut simpul, dan sisi, yang masing-masing menghubungkan dua titik. Letak titik saat digambar tidak penting; yang penting hanyalah pasangan mana yang terhubung, sehingga graf yang sama bisa tampak sangat berbeda di atas kertas. Graf di taman bermain ini adalah graf sederhana: tidak ada sisi dari sebuah titik ke dirinya sendiri, dan paling banyak ada satu sisi di antara dua titik. Dengan n titik, paling banyak ada n(n − 1) / 2 sisi; graf yang memiliki semuanya disebut graf lengkap, dan K5 adalah graf lengkap dengan lima titik.
Derajat dan lema jabat tangan
Derajat sebuah titik adalah banyaknya sisi yang bertemu di titik itu. Jumlahkan semua derajat, dan hasilnya tepat dua kali banyaknya sisi, karena setiap sisi punya dua ujung dan dihitung sekali di masing-masing ujung. Inilah lema jabat tangan: dalam kelompok mana pun, jabat tangan yang dihitung per orang jumlahnya dua kali banyaknya jabat tangan. Artinya juga, banyaknya titik berderajat ganjil selalu genap. Graf yang setiap titiknya memiliki derajat yang sama, yaitu k, disebut graf k-reguler.
Graf terhubung, pohon, dan siklus
Graf disebut terhubung jika Anda bisa berpindah dari setiap titik ke titik lain mana pun melalui sisi; jika tidak, graf itu terpecah menjadi beberapa bagian yang disebut komponen. Siklus adalah perjalanan keliling yang kembali ke titik awalnya tanpa melewati titik yang sama dua kali, dan panjang siklus terpendek disebut girth. Graf terhubung tanpa siklus disebut pohon, dan pohon dengan n titik selalu memiliki tepat n − 1 sisi: kurang satu, graf itu terpecah; lebih satu, muncul siklus. Setiap graf terhubung memuat pohon merentang, yaitu pohon yang menjangkau semua titik dengan hanya memakai sebagian sisi.
Graf bipartit dan pewarnaan
Warnai titik-titiknya sehingga tidak ada sisi yang menghubungkan dua titik berwarna sama. Banyaknya warna paling sedikit yang bisa melakukannya disebut bilangan kromatik. Satu warna hanya cukup jika tidak ada sisi sama sekali. Dua warna cukup tepat ketika graf itu bipartit: titik-titiknya terbagi menjadi dua kelompok dan setiap sisi menyeberang di antara keduanya. Pada 1936 Dénes Kőnig menunjukkan bahwa hal ini sama dengan tidak memiliki siklus berpanjang ganjil, karena siklus ganjil tidak bisa diwarnai berselang-seling dengan dua warna. Untuk tiga warna atau lebih, belum diketahui uji sederhana semacam itu: menentukan apakah tiga warna sudah cukup adalah masalah NP-lengkap, jadi program harus melakukan pencarian, seperti yang dilakukan taman bermain ini.
Contoh: graf Petersen
Ambil segi lima A–B–C–D–E dan bintang bersudut lima F–H–J–G–I di dalamnya, lalu hubungkan setiap sudut segi lima ke satu ujung bintang: A–F, B–G, C–H, D–I, dan E–J. Itulah graf Petersen, dengan 10 titik dan 15 sisi. Setiap titik berderajat 3, jadi jumlah derajatnya 30, dua kali 15. Siklus terpendeknya berpanjang 5, jadi graf ini tidak punya segitiga, tetapi segi lima adalah siklus ganjil, jadi graf ini tidak bipartit dan membutuhkan 3 warna. Setiap dua titik berjarak paling banyak 2 sisi, jadi diameternya 2. Kesepuluh derajatnya ganjil, jadi graf ini tidak punya jejak Euler, dan graf ini tidak bisa digambar tanpa persilangan.
Lintasan Euler dan jembatan Königsberg
Kota Königsberg memiliki tujuh jembatan yang menghubungkan empat daratan, dan orang-orang bertanya-tanya apakah mungkin berjalan melintasi setiap jembatan tepat sekali. Pada 1736 Leonhard Euler menunjukkan bahwa hal itu mustahil, dan lahirlah teori graf. Setiap kali perjalanan melewati sebuah daratan, perjalanan itu memakai dua jembatan, jadi hanya daratan awal dan akhir yang boleh memiliki jembatan berjumlah ganjil, padahal keempat daratan di Königsberg semuanya memiliki jembatan berjumlah ganjil. Jejak yang melewati setiap sisi tepat sekali kini disebut lintasan Euler, atau sirkuit Euler jika berakhir di tempat awalnya. Pada 1873 Carl Hierholzer membuktikan bahwa syarat itu juga sudah cukup: jika semua sisi berada dalam satu bagian dan paling banyak dua derajat ganjil, jejak itu ada, dan metodenya, yaitu menyambungkan perjalanan-perjalanan keliling, masih dipakai untuk menemukannya.
Jarak, diameter, dan komplemen
Jarak antara dua titik adalah banyaknya sisi paling sedikit pada lintasan di antara keduanya, dan diameter adalah jarak terbesar dalam graf; pada graf yang tidak terhubung, diameternya tak hingga. Jejaring sosial memiliki diameter kecil, gagasan di balik teori enam derajat keterpisahan (six degrees of separation). Komplemen sebuah graf memiliki titik-titik yang sama dan menghubungkan tepat pasangan-pasangan yang sebelumnya tidak terhubung. Dari sebuah graf dan komplemennya, setidaknya salah satunya selalu terhubung.
Jelajahi sendiri
Taman bermain ini dibuka dengan graf Petersen yang diwarnai tiga warna. Klik Derajat dan periksa lema jabat tangan, klik Bipartit untuk melihat siklus ganjil, lalu muat kubus dan lihat dua kelompoknya muncul. Muat rumah dan klik Jejak Euler untuk melihat dari mana satu goresan itu harus dimulai. Gambar graf Anda sendiri dan tambahkan sisi satu per satu: saksikan siklus terpendek memendek, diameter mengecil, dan bilangan kromatik naik ketika sisi terakhir K4 dipasang.
Pertanyaan yang sering diajukan
Apa perbedaan lintasan, jejak, dan jalan?
Jalan (walk) adalah barisan titik apa pun yang dihubungkan oleh sisi, dan boleh mengulang titik maupun sisi. Jejak (trail) boleh mengulang titik tetapi tidak boleh mengulang sisi, itulah sebabnya jejak Euler bisa melewati sebuah titik beberapa kali. Lintasan (path) tidak mengulang keduanya.
Apa itu teorema empat warna?
Teorema ini menyatakan bahwa setiap graf yang bisa digambar di atas kertas tanpa sisi yang bersilangan dapat diwarnai dengan paling banyak empat warna, sehingga peta apa pun tidak memerlukan lebih dari empat warna. Teorema ini dibuktikan pada 1976 oleh Kenneth Appel dan Wolfgang Haken dengan bantuan komputer, dan menjadi teorema besar pertama yang dibuktikan dengan cara itu.
Apa itu siklus Hamilton?
Siklus yang mengunjungi setiap titik tepat sekali, bukan setiap sisi. Kedengarannya mirip pertanyaan Euler, tetapi belum diketahui uji sederhana untuknya: menentukan apakah sebuah graf memilikinya adalah masalah NP-lengkap. Graf Petersen memiliki lintasan Hamilton tetapi tidak memiliki siklus Hamilton.
Di mana teori graf digunakan?
Perencana rute menelusuri graf jalan raya, mesin pencari memeringkat halaman web berdasarkan tautannya, kompilator mewarnai graf untuk berbagi register prosesor, penyusunan jadwal menghindari bentrokan dengan mewarnai graf konflik, ahli kimia menghitung molekul sebagai graf, dan jaringan komputer, jaringan listrik, serta jaringan pertemanan dipelajari sebagai graf.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Buka Taman Bermain Teori Graf