Nurlaela Jumadil _ STT-PLN

v GRAF (2) ·        Graf Planar ( Planar Graph ) dan Graf Bidang ( Plane Graph )        Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak saling memotong (bersilangan) disebut graf planar, jika tidak, maka ia disebut graf tak-planar. K4 adalah graf planar:        K5 adalah graf tidak planar: Graf planar yang digambarkan dengan sisi-sisi yangtidak saling berpotongan disebut graf bidang ( plane graph ). Tiga buah graf planar. Graf (b) dan (c) adalah graf bidang. Persoalan utilitas ( utility problem ) a)      Graf persoalan utilitas ( K 3,3), b)     graf persoalan utilitas bukan graf planar. Perancangan IC ( Integrated Circuit )   Tidak boleh ada kawat-kawat di dalam ICboard yang saling bersilangan -> dapat men...

v GRAF Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Sejarah graf terjadi pada tahun 1736, pada masalah Königsberg seperti gambar dibawah ini Graf yang merepresentasikan jembatan Königsberg:   Simpul (vertex) à menyatakan daratan  Sisi (edge) à menyatakan jembatan Graf G = (V, E), yang dalam hal ini:     V  = himpunan tidak-kosong dari simpul-simpul (vertices)  = { v1 , v2 , ... , vn }       E = himpunan sisi  (edges) yang menghubungkan sepasang  simpul  = {e1 , e2 , ... , en } ð Pada Gambar diatas: ·         G1 adalah graf dengan: V = { 1, 2, 3, 4 }     E =  { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) } ·         G2 adalah graf dengan  V = { 1, 2, 3, ...