Ada banyak jenis graf yang berbeda tergantung pada jumlah simpul, jumlah sisi, interkonektivitas, dan struktur keseluruhannya, beberapa jenis graf yang umum adalah sebagai berikut:
Graf Sederhana (Simple Graph)
Graf sederhana adalah graf yang tidak memiliki lebih dari satu sisi di antara dua simpul dan tidak ada sisi yang berawal dan berakhir pada simpul yang sama. Dengan kata lain graf sederhana adalah graf tanpa loop dan sisi ganda.
Graf Multi (Multi Graph)
Graf yang memiliki banyak sisi di antara setiap pasangan simpulnya atau terdapat sisi dari suatu simpul ke dirinya sendiri (loop) disebut graf multi.
Graf Berbobot (Weighted Graph)
Graf berbobot adalah graf yang sisi-sisinya diberi label dengan beberapa bobot atau angka.
Panjang suatu lintasan pada graf berbobot adalah jumlah bobot semua sisi pada lintasan tersebut.
Graf Berarah (Directed Graph) dan Tidak Berarah (Undirected Graph)
Graf berarah adalah graf yang memiliki sisi dengan arah. Sisi menunjukkan hubungan satu arah, di mana setiap sisi hanya dapat dilalui dalam satu arah.
Sedangkan, Graf tak berarah adalah graf yang memiliki sisi yang tidak memiliki arah. Tepi menunjukkan hubungan dua arah, di mana setiap tepi dapat dilalui di kedua arah.
Graf Terhubung (Connected Graph) dan Graf Tak terhubung (Disconnected Graph)
Graf terhubung adalah graf yang memiliki lintasan atau jalur dari titik mana pun ke titik lain dalam grafik.
Graf tak terhubung adalah graf yang titik-titik terpisah menjadi dua atau lebih grup yang berbeda, di mana tidak mungkin menghubungkan simpul dalam satu grup ke simpul di grup lain dengan melakukan perjalanan sepanjang serangkaian tepi.
Graf Nol (Null Graph)
Graf nol didefinisikan sebagai graf yang hanya terdiri dari simpul-simpul yang terisolasi. Ini berarti graf nol tidak memiliki sisi yang yang menghubungkan titik simpul pada graf. Graf nol dengan n simpul dinotasikan dengan Nn.
Graf Trivial
Graf trivial adalah graf yang hanya memiliki satu simpul.
Graf Reguler (Regular Graph)
Graf Reguler adalah graf yang derajat semua simpulnya sama. Jika derajat semua simpul adalah k, maka disebut graf beraturan k.
Graph Komplit (Complete Graph)
Graf yang setiap pasang simpulnya dihubungkan oleh tepat satu sisi disebut graf lengkap. Ini berisi semua kemungkinan tepi. Graf lengkap dengan n simpul mengandung tepat nC2 sisi dan diwakili oleh Kn.
Graph Sikel (Cycle Graph)
Graf dengan 'n' simpul (di mana, n>=3) dan 'n' tepi membentuk lingkaran 'n' dengan semua sisinya dikenal sebagai graf sikel. Graf yang mengandung setidaknya satu siklus di dalamnya dikenal sebagai graf siklik. Pada graf sikel, derajat setiap simpul adalah 2. Graf siklus yang memiliki n simpul dilambangkan dengan Cn.
Graph Lintasan (Path Graph)
Graf lintasan adalah sebuah pohon dengan dua simpul yang berderajat 1 dan satu simpul lainnya. simpul derajat 2. Oleh karena itu, graf jalur adalah graf yang dapat ditarik sehingga semua simpul dan tepinya terletak pada satu garis lurus.
Graph Roda (Wheel Graph)
Graf roda diperoleh dengan menghubungkan sebuah simpul ke semua simpul dari graf siklus. Dilambangkan dengan Wn, untuk n > 3 dimana n adalah jumlah simpul pada graf. Graf roda dengan n simpul berisi graf siklus dengan orde n – 1 dan semua simpul dari siklus terhubung ke satu simpul . Banyaknya rusuk pada graf Roda, Wn adalah 2n – 2.
Graf Bintang (Star Graf)
Graf bintang adalah jenis graf khusus di mana n-1 simpul memiliki derajat 1 dan satu simpul memiliki derajat n – 1. Ini terlihat seperti n – 1 simpul terhubung ke satu simpul pusat. Graf bintang dengan total n simpul disebut sebagai Sn.
Graph Platonik (Platonic Graph)
Graf platonik muncul dari lima benda padat: tetrahedron, oktahedron, kubus, dodecahedron, dan ikosahedron, di mana titik-titik graf sama dengan titik-titik padatan, dan sisi-sisi graf sama dengan sisi-sisi padatan . Tentu saja, graf-graf ini dapat diubah dalam berbagai cara selama setiap simpul terhubung dengan tepat.
Graph Bipartisi (Bipartite Graph)
Graf bipartisi adalah graf yang himpunan simpulnya dapat dipartisi menjadi dua himpunan sehingga sisi-sisinya hanya berada di antara himpunan, bukan di dalamnya.
Suatu graf G(V,E) disebut graf bipartisi jika himpunan titiknya V(G) dapat diuraikan menjadi dua himpunan bagian tak-kosong yang saling lepas V1(G) dan V2(G) sedemikian rupa sehingga setiap sisi e∈E(G) memiliki satu sambungan terakhir di V1(G) dan titik terakhir lainnya di V2(G).
Partisi V = V1∪V2 disebut bipartisi dari G.
Graph Bipartisi Komplit (Complete Bipartite Graph)
Graf bipartisi lengkap adalah graf bipartisi yang setiap simpul pada himpunan pertama dihubungkan dengan setiap simpul pada himpunan kedua dengan tepat satu sisi. Misal banyak titik pada kedua himpunan bagian pasrtisi adalah r dan s maka banyak titik adalah r+s dan banyak sisi adalah rs.
0 komentar:
Post a Comment