Izin menjawab Zakcyudin, tidak semua graf bisa digambar tanpa ada sisi yang saling berpotongan. Graf yang dapat digambar tanpa ada sisi yang saling berpotongan disebut graf planar.
Syarat Graf Planar
1. Definisi Planar: Graf planar adalah graf yang bisa digambar di bidang 2 dimensi tanpa ada sisi yang saling berpotongan (kecuali pada titik simpulnya).
2. Teorema Kuratowski: Sebuah graf tidak planar jika mengandung subgraf yang isomorfik dengan K5 (graf lengkap dengan 5 simpul) atau K3,3 (graf bipartit lengkap dengan 6 simpul, 3 di setiap partisi).
Contoh:
• Planar:
• Graf dengan simpul sedikit, seperti segitiga atau persegi, jelas planar.
• Graf Kubus juga bisa digambar sebagai planar.
• Tidak Planar:
• Graf K5: Semua simpul terhubung dengan semua simpul lainnya.
• Graf K3,3 : Terhubung antara dua set (misalnya 3 kota dan 3 jembatan) sehingga tidak ada cara menggambarnya tanpa garis yang saling berpotongan.
Jadi, graf planar bergantung pada struktur dan jumlah simpul serta sisi.
Syarat Graf Planar
1. Definisi Planar: Graf planar adalah graf yang bisa digambar di bidang 2 dimensi tanpa ada sisi yang saling berpotongan (kecuali pada titik simpulnya).
2. Teorema Kuratowski: Sebuah graf tidak planar jika mengandung subgraf yang isomorfik dengan K5 (graf lengkap dengan 5 simpul) atau K3,3 (graf bipartit lengkap dengan 6 simpul, 3 di setiap partisi).
Contoh:
• Planar:
• Graf dengan simpul sedikit, seperti segitiga atau persegi, jelas planar.
• Graf Kubus juga bisa digambar sebagai planar.
• Tidak Planar:
• Graf K5: Semua simpul terhubung dengan semua simpul lainnya.
• Graf K3,3 : Terhubung antara dua set (misalnya 3 kota dan 3 jembatan) sehingga tidak ada cara menggambarnya tanpa garis yang saling berpotongan.
Jadi, graf planar bergantung pada struktur dan jumlah simpul serta sisi.