Berdasarkan ada tidaknya gelang atau sisi ganda pada suatu graf, maka graf digolongkan menjadi dua jenis:
1.Graf sederhana (simple graph).
Graf yang tidak mengandung gelang maupun sisi-ganda dinamakan graf sederhana. G1 pada Gambar 2 adalah contoh graf sederhana

2.Graf tak-sederhana (unsimple-graph).
 Graf yang mengandung sisi ganda atau gelang dinamakan  graf tak-sederhana (unsimple graph). G2 dan G3 pada Gambar 2 adalah contoh graf tak-sederhana

Berdasarkan jumlah simpul pada suatu graf, maka secara umum graf dapat digolongkan menjadi dua jenis:

1.Graf berhingga (limited graph)
Graf berhingga adalah graf yang jumlah simpulnya, n, berhingga.

2.Graf tak-berhingga (unlimited graph)
Graf yang jumlah simpulnya, n, tidak berhingga banyaknya disebut graf tak-berhingga.


Berdasarkan orientasi arah pada sisi, maka secara umum graf  dibedakan atas 2 jenis:
1.Graf tak-berarah (undirected graph)
Graf yang sisinya tidak mempunyai orientasi arah disebut graf tak-berarah. Tiga buah graf pada Gambar 2 adalah graf tak-berarah.

2.Graf berarah (directed graph atau digraph)
 Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah. Dua   buah graf pada Gambar 3 adalah graf berarah.

1.Graf Bidang (planar graph)
Graf bidang merupakan representasi dari graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan. Graf ini merupakan graf planar yang sudah tergambar tanpa sisi-sisi yang berpotongan.
   
2.Graf Sederhana (simple graph)
Graf sederhana merupakan graf yang tidak mengandung gelang maupun sisi-ganda. Pada graf ini sisi merupakan pasangan tak-terurut (unordered pairs) sehingga jika menuliskan sisi (u,v) sama saja dengan (v,u) dan G=(V,E) terdiri dari himpunan tidak kosong simpul-simpul dan E adalah himpunan pasangan tak-terurut yang berbeda yang disebut sisi.
                                        
3.Graf Lengkap (complete graph)
Graf lengkap ialah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya. Sebuah graf lengkap dengan n buah simpul dilambangkan dengan Kn. Setiap simpul pada Kn berderajat n – 1, sehingga jumlah sisi yang ada adalah n(n – 1)/2.

4.Graf Bipartit (bipartite graph)
Graf bipartite merupakan sebuah graf G yang himpunan simpulnya dapat dikelompokkan menjadi dua himpunan bagian V1 dan V2, sedemikian sehingga setiap sisi di dalam G menghubungkan sebuah simpul di V1 ke sebuah simpul di V2. Dengan kata lain, setiap pasang simpul di V1 (demikian pula dengan simpul-simpul di V2) tidak bertetangga.
                                       
5.Graf terhubung (connected graph) & graf tidak terhubung(disconnected graph)
Suatu graf disebut sebagai graf terhubung apabila untuk setiap pasang simpul u dan v di dalam himpunan V terdapat lintasan dari u ke v yang juga harus berarti ada lintasan dari v ke u.                             
Jika tidak, maka G disebut graph tak-terhubung (disconnected graph).

6.Sub Graf
Subgraf (Upagraf) merupakan sebuah graf   yang ada pada sebuah graf yang lain. Misalkan bilamana sebuah graf G = (V,E), maka G1 = (V1,E1)merupakan subgraf dari G jika V1 V  dan E1 E.

7.Graf berlabel
Graf berlabel/ berbobot adalah graf yang setiap ruasnya mempunyai nilai/bobot berupa bilangan non negatif.

 8.Graf Reguler
Sebuah graf dikatakan graf regular bila derajat setiap simpulnya sama.

9.Graf Planar (planar graph)
Sebuah graf dikatakan graf planar bila graf tersebut dapat disajikan (secara geometri) tanpa adanya ruas yang berpotongan. Sebuah graf yang disajikan tanpa adanya ruas yang berpotongan disebut dengan penyajian planar/map/peta.
 Graf yang termasuk planar antara lain :
· Tree / Pohon
· Kubus
· Bidang Empat
· Bidang Delapan Beraturan

10.Graf Non-Planar
Sebuah graf yang tidak dapat disajikan (secara geometri) tanpa adanya ruas yang berpotongan dikenal sebagai graf non planar.

11.Pohon(tree)
Tree atau pohon adalah graf terhubung yang tidak mengandung sirkuit.Suatu Graf  G adalah Pohon jika dan hanya jika terdapat satu dan hanya satu jalur diantara setiap pasang simpul dari Graf G.

12.Graf Berarah
Beberapa  Pengertian dalam graf berarah :
· Derajat ke luar (out degree) suatu simpul adalah banyaknya arc yang mulai / keluar dari simpul tersebut.
· Derajat ke dalam (in degree) suatu simpul adalah banyaknya arc yang berakhir / masuk ke simpul tersebut.
· Simpul berderajat ke dalam = 0 disebut sumber (source), sedangkan simpul berderajat ke luar = 0 disebut muara (sink).
· Pengertian Walk, Trail, Path (Jalur) dan Sirkuit (Cycle) berlaku pula pada graf berarah, dimana harus sesuai dengan arah arc. Kalau tidak sesuai dengan arah arc-nya, maka disebut sebagai semi walk, semi path atau semi trail. 



13.Graf Null / Hampa/ nol / kosong
Ada beberapa pengertian tentang graf null/hampa. Di sini akan dipakai pengertian bahwa suatu graf dikatakan graf null/hampa bila graf tersebut tidak mengandung ruas

14.Graf Berbobot (Weighted Graph)
Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot).

15.Graf Lengkap (Complete Graph)
Graf lengkap ialah graf sederhana yang setiap simpulnya mempunyai sisi ke semua simpul lainnya. Graf lengkap dengan n buah simpul dilambangkan dengan Kn. Jumlah sisi pada graf lengkap yang terdiri dari n buah simpul adalah n(n – 1)/2.

16.graf lingkaran (Complete Graph)
Graf lingkaran ialah graf sederhana yang setiap simpulnya berderajat Dua. Graf lingkaran dengan n symbol dilambangkan denang Cn.

17.Graf Teratur (Regular Graphs)
Graf teratur adalah graf yang setiap simpulnya mempunyai derajat yang sama. Apabila derajat setiap simpul adalah r, maka graf tersebut disebut sebagai graf teratur derajat r. Jumlah sisi pada graf teratur adalah nr/2.



18.Graf Bipartite (Bipartite Graph)
Graf G  yang himpunan simpulnya dapat dipisah menjadi dua himpunan bagian V1 dan V2,  sedemikian sehingga setiap sisi pada G menghubungkan sebuah simpul di V1 ke sebuah simpul di V2 disebut graf bipartit dan dinyatakan sebagai G(V1, V2)

19.Graf Isomorfik (Isomorphic Graph)
· Dua buah graf yang sama tetapi secara geometri berbeda disebut graf yang saling isomorfik.
· Dua buah graf, G1 dan G2 dikatakan isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul keduanya dan antara sisi-sisi keduaya sedemikian sehingga hubungan kebersisian tetap terjaga.
· Dengan kata lain, misalkan sisi e bersisian dengan simpul u dan v di G1, maka sisi e’ yang berkoresponden di G2 harus bersisian dengan simpul u’ dan v’ yang di G2.
· Dua buah graf isomorfik memenuhi ketiga syarat berikut :
1. Mempunyai jumlah simpul yang sama.
2. Mempunyai jumlah sisi yang sama
3. Mempunyai jumlah simpul yang sama berderajat tertentu

20.Graf bidang (plane graph)
Graf bidang adalah graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan.

21.Graf terhubung kuat (strongly connected graph) & terhubung lemah(weakly )
Graph berarah G disebut graph terhubung kuat (strongly connected graph) apabila untuk setiap pasang simpul sembarang u dan v di G, terhubung kuat.
Jika u dan v  tidak terhubung kuat tetapi terhubung pada graph tidak berarahnya, maka u dan v dikatakan disebut graph terhubung lemah.

22.Graf Ulat (Caterpillar graph)
Graf tree adalah suatu tree yang setiap titiknya ada disuatu central stalk atau hanya memiliki satu derajat yang lepas dari tangkainya. Suatu tree adalah graf ulat jika setiap simpul dari derajatnya ≥ 3 menegelilingi paling tidak dua simpul dari dua derajat atau lebih. Secara tak langsung grafdikatakan graf ulat jika terhubung, tidak memiliki cycle dan terdapat suatu path pada graf dimanan setiap tangkainya adalah salah satu di path atau lingkungan node di path.
Banyaknya graf ulat saat n≥3 adalah

23.Graf buku (Book Graph)
Graf buku digambarkan seperti graf Cartesian dimana salah satu graf bintang adlah path di dua tangkai(node).

24.Graf bintang (star graph)
Graf bintang adalah suatu tree pada n node dengan satu node(tangkai) yang mempunyai derajat titik n-1 dan lainnya n-1 mempunyai satu buah derajat titik. Oleh karena itu graf bintang isomorfik dengan graf bipartit lengkap .

25.Graf timbunan buku (Stacked Book Graph)
Graf timbunan buku  adalah suatu graf bintang dan suatu path pada n node. Yang digambarkan seperti graf Cartesian .


26.Graf Cayley
Suatu tree masing-masingnya bukan-daun graf titik yang memilki suatu konstanta tentang cabang n disebut dengan suatu graf n-Cayley. 2-cayley tree adalah suatu path. Unik n-cayley tree pada n+1 node adalah graf bintang.
27.Graf Cartesian Product
Graf Cartesian Product , sering disebut dengan “the” graf product pada graf  dan  dengan himpunan disjoint titik  dan  dan himpunan sisi  dan  adalah graf dengan himpunan titik  dan  dan bertetangga dengan  ketika  atau .

28.Graf Claw
Graf bipartit komplit  adalah suatu yang disebut dengan “claw”. Yang isomorfis dengan graf bintang  dan sering dikenal dengan Y-graph. Secara umum, graf bintang juga dikenal dengan graf “claw”.

29.Graf Pisang (banana tree)
Suatu (n,k)-graf pisang adalah suatu graf yang diperoleh dengan penghubungan satu leaf dari masing-masing n-copies pada suatu k-graf bintang dengan suatu akar titik yang berbeda dari semua bintang. (n,k)-Graf pisang memiliki barisan polinomial :

30.Graf Udang(Lobster)
Istilah Lobster digunakan untuk menunjukkan salah satu suatu particular polyamond atau untuk suatu kelas pada tree. Ketika menunjukkan tree, graf lobster adalah suatu tree yang mempunyai penghapusan terhadap daun-daun pada graf ulat. Banyaknya Lobster pada n=1,2,... adalah 1,1,1,2,3,6,11,23,47,105,231,532,... 

31.Graf Mercun (firecracker graph)
Suatu (n,k)-mercun adalah suaru graf yang mengandung concanetation pada nk-bintang dengan menyambung satu leaf dari masing-masingnya.

32.Graf Nauru
Graf Nauru juga merupakan graf kubik simetris , permutasi graf bintang pada order 4 dan timbulnya graf coxeter configutation.
33.Graf Centipede
Graf n-centipede adalah tree pada node 2n yang diperoleh dengan menggabungkan bagian dari n-copies pada path  yang diletakka di suatu baris pada sisi.  Barisan polinomial dari n-centipede adalah :

34.Graf komposisi (compotition graph)
Komposisi terhadap  graf  dan   dengan himpunan titik disjoint  dan  dan himpunan sisi  dan  adalah graf dengan titik  dan  bertetangga dengan  ketika  atau .

35.Graf Jumlah (sum graph)
Graf sum dari graf G dan H adalah graf dengan matriks ketetanggaan yang diberi oleh penjumlahan matriks G dan H. Graf sum didefenisikan ketika matriks G dan H adalah sama dan bisa dihitung menggunakan Graphsum.       


36.Graf Union
Union  pada graf  dan  dengan himpunan titik yang disjoint dan  dan sisi  dan  adalah graf dengan  dan .

37.Graf Domino
Graf domino adalah graf 6 titik yang diilustrasikan diatas. Yang isomorfis pada 3-ladder graf dan (2,3)-grid graf.

38.Graf Ladder
Graf Ladder dapat digambarkan dengan , dimana  adalah suatu path. Yang menyebabkan ladder graf ekivalen dengan grid graf . Graf memiliki defenisi kelihatan seperti a ladder, memilki dua rel dan n bel diantaranya.

39.Graf alat (gear graph)
Graf gear juga dikenal dengan graf bipartit roda, adalah suatu graf roda dengan suatu graf titik yang ditambahkan masing-masing pair pada ketetanggan graf titik pada cycle luarnya. Gear graf  memiliki  dan  sisi, yang menunjukkan bahwa jika dua atau lebih titik yang dimasukkan antara setiap pair pada titik cycle terluar pada roda, akhir dari graf adalah juga manis.

40.Graf Helm
Graf helm adalah graf yang terdiri dari n-graf roda yang menyatukan suatu sisi yang tergantung pada masing-masing node pada cycle. 

41.Graf Prisma(prism graph)
Graf prisma dikenal juga dengan suatu graf circular ladder, yaitu suatu graf yang berkorespodensi pada skeleton suatu n-prisma. Suatu n-prisma graf memiliki 2n-node dan 3n-sisi, dan ekivalen pada generalized Petersen graph .

42.Web graph
Web graf adalah suatu graf prisma dengan sisi-sisi pada cycle terluar dihapus.


Jenis-jenis Graf

Langganan: Postingan (Atom)