Jenis-jenis Graf

By mencoba berkarya Selasa, 08 November 2016

Share Tweet Share Pin Email

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. G₁ 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). G₂ dan G₃ 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 K_n. Setiap simpul pada K_n 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 V₁ dan V₂, sedemikian sehingga setiap sisi di dalam G menghubungkan sebuah simpul di V₁ ke sebuah simpul di V₂. Dengan kata lain, setiap pasang simpul di V₁ (demikian pula dengan simpul-simpul di V₂) 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 G₁ = (V₁,E₁)merupakan subgraf dari G jika V₁ V  dan E₁ 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 K_n. 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 C_n.

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 V₁ dan V₂,  sedemikian sehingga setiap sisi pada G menghubungkan sebuah simpul di V₁ ke sebuah simpul di V₂ disebut graf bipartit dan dinyatakan sebagai G(V₁, V₂)

19.Graf Isomorfik (Isomorphic Graph)

· Dua buah graf yang sama tetapi secara geometri berbeda disebut graf yang saling isomorfik.

· Dua buah graf, G₁ dan G₂ 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 G₁, maka sisi e’ yang berkoresponden di G₂ harus bersisian dengan simpul u’ dan v’ yang di G₂.

· 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.