-
Reguler
-
Lengkap
Taman Bermain Teori Graf
Graf adalah sekumpulan noktah, yang disebut titik, yang dihubungkan oleh garis, yang disebut sisi. Gambar sebuah graf di sini dengan beberapa klik, dan taman bermain ini akan memberi tahu jenis graf apa itu: berapa bagiannya, apakah graf itu pohon, berapa warna paling sedikit yang dibutuhkannya, apakah graf itu bisa digambar dengan satu goresan, dan banyak lagi. Klik sebuah sifat untuk melihatnya pada graf Anda, ubah satu sisi, dan saksikan jawabannya ikut berubah. Klik tempat kosong untuk menambah titik. Klik sebuah titik, lalu titik lain, untuk menghubungkan keduanya dengan sisi; ulangi untuk menghapus sisi itu. Seret titik untuk memindahkannya. Ubah klik ke Menghapus, lalu klik titik atau sisi untuk menghapusnya. Saat sebuah titik dipilih, tombol Delete menghapusnya dan Escape melepaskan pilihan. Klik sebuah sifat untuk menampilkannya pada graf. Contoh memuat graf yang terkenal, Graf acak membuat graf baru, Rapikan menyebarkan titik-titik, dan Komplemen menghubungkan tepat pasangan yang tadinya tidak terhubung. Ctrl+Z membatalkan satu langkah.
Cara kerjanya
- Klik tempat kosong untuk menambah titik. Klik sebuah titik, lalu titik lain, untuk menghubungkan keduanya; ulangi untuk menghapus sisinya. Seret titik untuk memindahkannya.
- Baca sifat-sifat di bawah graf, lalu klik salah satunya untuk menampilkannya: pewarnaan, dua kelompok titik, jejak Euler, pohon merentang, siklus terpendek, atau diameter.
- Muat contoh seperti graf Petersen, buat graf acak, ambil komplemennya, atau ubah klik ke Menghapus untuk menghapus titik dan sisi.
Arti sifat-sifatnya
Derajat sebuah titik adalah banyaknya sisi yang bertemu di titik itu. Graf disebut terhubung jika setiap titik bisa mencapai titik lain mana pun melalui sisi, dan disebut pohon jika graf itu terhubung dan tidak punya siklus. Graf disebut bipartit jika titik-titiknya terbagi menjadi dua kelompok dan setiap sisi menyeberang di antara keduanya, yang terjadi tepat ketika graf itu tidak punya siklus berpanjang ganjil. Bilangan kromatik adalah banyaknya warna paling sedikit yang membuat titik-titik bertetangga selalu berbeda warna. Panjang siklus terpendek disebut girth, dan diameter adalah jarak terbesar antara dua titik, dihitung dalam banyaknya sisi.
Menggambar dengan satu goresan
Jejak Euler melewati setiap sisi tepat sekali. Pada 1736, lewat masalah tujuh jembatan Königsberg, Leonhard Euler melihat apa yang menjadi penghalangnya: setiap kali jejak melewati sebuah titik, jejak itu memakai dua sisi dari titik tersebut. Jadi, entah semua derajat genap, sehingga jejak bisa berakhir di tempat awalnya, atau tepat dua derajat ganjil, sehingga jejak harus berjalan dari salah satunya ke yang lain. Kemudian Carl Hierholzer membuktikan bahwa syarat ini, ditambah semua sisi berada dalam satu bagian, juga sudah cukup. Muat contoh rumah dan temukan dari mana goresan harus dimulai.
Pertanyaan yang sering diajukan
Apa itu graf dalam teori graf?
Sekumpulan noktah, yang disebut titik atau simpul, beserta garis di antara beberapa pasangnya, yang disebut sisi. Graf bukan grafik fungsi: graf hanya menggambarkan apa yang terhubung dengan apa. Peta jalan, jejaring sosial, molekul, dan jaringan komputer semuanya adalah graf.
Bagaimana bilangan kromatik dihitung?
Taman bermain ini mencoba mewarnai graf dengan satu warna, lalu dua, lalu tiga, dan seterusnya, dan untuk setiap jumlah warna, ia menelusuri semua cara yang relevan, dengan selalu mewarnai lebih dulu titik yang tetangganya sudah memakai warna paling banyak. Jumlah pertama yang berhasil adalah bilangan kromatiknya. Untuk graf yang bisa Anda gambar di sini, prosesnya paling lama hanya sekejap; pada graf yang sangat sulit, pencarian berhenti lebih awal dan nilainya ditampilkan sebagai batas atas.
Kapan sebuah graf memiliki lintasan Euler?
Ketika semua sisinya berada dalam satu bagian dan paling banyak dua titik berderajat ganjil. Jika tidak ada titik berderajat ganjil, ada sirkuit Euler yang berakhir di tempat awalnya; jika ada dua, setiap lintasan Euler berawal di salah satunya dan berakhir di yang lain. Banyaknya titik berderajat ganjil selalu genap, jadi tidak pernah tepat satu.
Apa itu komplemen graf?
Graf dengan titik-titik yang sama, yang sisi-sisinya tepat pasangan-pasangan yang sebelumnya tidak terhubung. Komplemen dari komplemen adalah graf semula. Misalnya, komplemen graf Petersen adalah graf 6-reguler, karena setiap titik semula terhubung ke 3 dari 9 titik lainnya.
Mengapa graf Petersen terkenal?
Graf Petersen adalah graf kecil dengan 10 titik dan 15 sisi yang menjadi contoh penyangkal bagi banyak dugaan yang terlalu optimistis. Setiap titiknya berderajat 3, siklus terpendeknya berpanjang 5, setiap dua titik berjarak paling banyak 2 sisi, dan graf ini tidak bisa digambar tanpa ada sisi yang bersilangan. Taman bermain ini dibuka dengan graf tersebut.
Siap mencobanya?
Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.
Ke Editor