GRAF
Pengertian Graf
Sebuah graf G didefinisikan sebagai pasangan himpunan (V,E) , dengan V adalah himpunan tak kosong dari simpul-simpul (vertices) pada G. Sedangkan E adalah himpunan rusuk (edge) pada G yang menghubungkan sepasang simpul. Himpunan simpul pada G dinotasikan sebagai V, dan himpunan rusuk pada G dinotasikan sebagai E. Jadi G=(V, E).suatu graf G terdiri dari 2 himpunan yang berhingga, yaitu himpunan simpul-simpul tidak kosong (V(G)) dan himpunan garisgaris (E(G)). Jadi, suatu graf G adalah pasangan himpunan V dan E, dituliskan G = (V,E), dengan V adalah suatu himpunan berhingga dan E adalah suatu himpunan rusuk yang bersisian dengan V.
Berikut adalah beberapa istilah yang sering digunakan dalam graf.
1. Gelang (Loop) suatu rusuk dikatakan gelang apabila ujung rusuknya berawal dan berakhir pada simpul yang sama.
2. Rusuk Ganda Pada sebuah graf, terdapat kemungkinan bahwa terdapat lebih dari satu rusuk yang bersisian dengan sepasang simpul. Rusuk tersebut dinamakan rusuk ganda.
3. Bertetangga (Adjacent) Dua buah simpul pada graf tak berarah G dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah rusuk. Dengan kata lain, u bertetangga dengan v jika (u, v) adalah sebuah rusuk pada graf.
4. Bersisian (Incident) Untuk sembarang rusuk e = (u, v), rusuk e dikatakan bersisian dengan simpul u dan simpul v. Pada Gambar 2.1 rusuk e7 bersisian dengan v4 dan v5. Sedangkan e2 tidak bersisiang dengan v1 maupun v2.
5. Graf Kosong (Null Graph atau Empty Graph) Graf kosong adalah graf yang himpunan rusuknya merupakan himpunan kosong. Graf kosong dapat dinotasikan dalam Nn, dimana n adalah banyaknya simpul.
6. Perjalanan (Walk) Perjalanan u-v di G dengan u,v merupakan simpul-simpul pada graf G adalah barisan berganti-ganti antara simpul dan rusuk dari G, diawali dengan simpul u dan diakhiri dengan simpul v.
7. Lintasan (Path), lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graf D ialah barisan berselang-seling simpulsimpul dan rusuk-rusuk yang berbentuk v0, e1, v1, e2, v2, ..., vn-1, en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), ..., en = (vn-1,vn) adalah rusukrusuk dari graf D. Barisan c, cb, b, bf, f, pada Gambar 2.3 merupakan sebuah lintasan.
8. Siklus (Cycle) atau Sirkuit (Circuit) Sirkuit atau siklus adalah lintasan yang berawal dan berakhir pada simpul yang sama. Sebuah sirkuit dikatakan sirkuit sederhana (simple sirkuit) jika setiap rusuk yang dilalui berbeda.
Pengertian Graf
Sebuah graf G didefinisikan sebagai pasangan himpunan (V,E) , dengan V adalah himpunan tak kosong dari simpul-simpul (vertices) pada G. Sedangkan E adalah himpunan rusuk (edge) pada G yang menghubungkan sepasang simpul. Himpunan simpul pada G dinotasikan sebagai V, dan himpunan rusuk pada G dinotasikan sebagai E. Jadi G=(V, E).suatu graf G terdiri dari 2 himpunan yang berhingga, yaitu himpunan simpul-simpul tidak kosong (V(G)) dan himpunan garisgaris (E(G)). Jadi, suatu graf G adalah pasangan himpunan V dan E, dituliskan G = (V,E), dengan V adalah suatu himpunan berhingga dan E adalah suatu himpunan rusuk yang bersisian dengan V.
Berikut adalah beberapa istilah yang sering digunakan dalam graf.
1. Gelang (Loop) suatu rusuk dikatakan gelang apabila ujung rusuknya berawal dan berakhir pada simpul yang sama.
2. Rusuk Ganda Pada sebuah graf, terdapat kemungkinan bahwa terdapat lebih dari satu rusuk yang bersisian dengan sepasang simpul. Rusuk tersebut dinamakan rusuk ganda.
3. Bertetangga (Adjacent) Dua buah simpul pada graf tak berarah G dikatakan bertetangga bila keduanya terhubung langsung dengan sebuah rusuk. Dengan kata lain, u bertetangga dengan v jika (u, v) adalah sebuah rusuk pada graf.
4. Bersisian (Incident) Untuk sembarang rusuk e = (u, v), rusuk e dikatakan bersisian dengan simpul u dan simpul v. Pada Gambar 2.1 rusuk e7 bersisian dengan v4 dan v5. Sedangkan e2 tidak bersisiang dengan v1 maupun v2.
5. Graf Kosong (Null Graph atau Empty Graph) Graf kosong adalah graf yang himpunan rusuknya merupakan himpunan kosong. Graf kosong dapat dinotasikan dalam Nn, dimana n adalah banyaknya simpul.
6. Perjalanan (Walk) Perjalanan u-v di G dengan u,v merupakan simpul-simpul pada graf G adalah barisan berganti-ganti antara simpul dan rusuk dari G, diawali dengan simpul u dan diakhiri dengan simpul v.
7. Lintasan (Path), lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graf D ialah barisan berselang-seling simpulsimpul dan rusuk-rusuk yang berbentuk v0, e1, v1, e2, v2, ..., vn-1, en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), ..., en = (vn-1,vn) adalah rusukrusuk dari graf D. Barisan c, cb, b, bf, f, pada Gambar 2.3 merupakan sebuah lintasan.
8. Siklus (Cycle) atau Sirkuit (Circuit) Sirkuit atau siklus adalah lintasan yang berawal dan berakhir pada simpul yang sama. Sebuah sirkuit dikatakan sirkuit sederhana (simple sirkuit) jika setiap rusuk yang dilalui berbeda.
Komentar
Posting Komentar