JENIS-JENIS GRAPH
1. Graph sederhana
Graph yang tidak mempunyai sisi rangkap dan tidak memiliki gelung disebut graph sederhana.
Graph yang tidak mempunyai sisi rangkap dan tidak memiliki gelung disebut graph sederhana.
2. Graph tidak sederhana
- Graph rangkap
Sebuah graph yang memiliki sisi rangkap tetapi tidak memiliki gelung disebut graph rangkap (multi-graph).
- Graph semu
Sebuah graph yang memilki sisi rangkap dan memiliki gelung disebut graph semu (pseudograph).
- Graph rangkap
Sebuah graph yang memiliki sisi rangkap tetapi tidak memiliki gelung disebut graph rangkap (multi-graph).
- Graph semu
Sebuah graph yang memilki sisi rangkap dan memiliki gelung disebut graph semu (pseudograph).
3. Graph komplit
Sebuah graph komplit (graph lengkap) dengan n titik, dilambangkan dengan Kn , adalah graph sederhana dengan n titik dan setiap dua titik berbeda dihubungkan dengan sebuah sisi.
Sebuah graph lengkap sering juga disebut sebagai graph universal. Kerena tiap titik dalam grap lengkap selalu dihubungkan dengan titik lain melalui satu sisi, maka derajat tiap titik dalam sebuah graph lengkap G dengan n titik adalah n-1. Dengan demikian, banyaknya sisi dalam graph lengkap G adalah .
Sebuah graph komplit (graph lengkap) dengan n titik, dilambangkan dengan Kn , adalah graph sederhana dengan n titik dan setiap dua titik berbeda dihubungkan dengan sebuah sisi.
Sebuah graph lengkap sering juga disebut sebagai graph universal. Kerena tiap titik dalam grap lengkap selalu dihubungkan dengan titik lain melalui satu sisi, maka derajat tiap titik dalam sebuah graph lengkap G dengan n titik adalah n-1. Dengan demikian, banyaknya sisi dalam graph lengkap G adalah .
4. Graph bagian (subgraph)
Sebuah graph H disebut graph bagian (subgraph) dari graph G
Sebuah graph H disebut graph bagian (subgraph) dari graph G
5. Graph teratur
Sebuah graph disebut graph teratur jika semua titiknya berderajat sama. Misal graph teratur berderajat tiga.
Sebuah graph disebut graph teratur jika semua titiknya berderajat sama. Misal graph teratur berderajat tiga.
6. Graph lingkaran
Graph sederhana yang setiap titiknya berderajat dua disebut graph lingkaran. Graph lingkaran dengan n titik dilambangkan dengan Cn. Graph lingkaran ini disebut juga graph teratur berderajat dua.
Graph sederhana yang setiap titiknya berderajat dua disebut graph lingkaran. Graph lingkaran dengan n titik dilambangkan dengan Cn. Graph lingkaran ini disebut juga graph teratur berderajat dua.
7. Graph kosong atau graph nol
Graph yang tidak memiliki sisi disebut graph kosong atau graph nol. Graph nol dengan n titik dilambangkan dengan Nn. Graph yang hanya mempunyai satu buah titik tanpa sebuah sisi dinamakan graph trivial. Misal graph kosong dengan tiga titik (N3).
Graph yang tidak memiliki sisi disebut graph kosong atau graph nol. Graph nol dengan n titik dilambangkan dengan Nn. Graph yang hanya mempunyai satu buah titik tanpa sebuah sisi dinamakan graph trivial. Misal graph kosong dengan tiga titik (N3).
8. Graph bipartisi
Sebuah graph G disebut graph bipartisi jika V(G) (himpunan titik graph G) dapat dipartisi menjadi dua himpunan bagian X dan Y sedemikian sehingga setiap sisi dari G menghubungkan sebuah titik di X dan sebuah titik di Y. Kita notasikan (X,Y) bipartisi dari G.
Apabila G sederhana dan bipartisi dengan partisi (X,Y) sedemikian sehingga setiap titik di X berhubungan langsung dengan setiap titik di Y, maka G disebut graf bipartisi lengkap, dinotasikan dengan Km,n dengan m dan n adalah banyaknya titik dikedua partisi tersebut.
Sebuah graph G disebut graph bipartisi jika V(G) (himpunan titik graph G) dapat dipartisi menjadi dua himpunan bagian X dan Y sedemikian sehingga setiap sisi dari G menghubungkan sebuah titik di X dan sebuah titik di Y. Kita notasikan (X,Y) bipartisi dari G.
Apabila G sederhana dan bipartisi dengan partisi (X,Y) sedemikian sehingga setiap titik di X berhubungan langsung dengan setiap titik di Y, maka G disebut graf bipartisi lengkap, dinotasikan dengan Km,n dengan m dan n adalah banyaknya titik dikedua partisi tersebut.
9. Graph berbobot
Sebuah graph G disebut graph berbobot jika setiap sisinya diberi sebuah harga.
Sebuah graph G disebut graph berbobot jika setiap sisinya diberi sebuah harga.
