Jenis-jenis Graf PDF

Preview

Summary

Jenis-jenis Graf 1. Graf Null (𝑁𝑛 ) Graf Kosong adalah graf yang tidak memiliki sisi. Contoh: Graf kosong 𝑁1 dan 𝑁2 𝑁1 : 𝑁2 : 2. Graf Sederhana (Simple Graph) Graf sederhana merupakan graf tak berarah yang tidak mengandung gelang maupun sisi-ganda. Contoh: 3. Graf Ganda (Multigraph) Graf ganda merup...

Description

Jenis-jenis Graf 1. Graf Null (� )

Graf Kosong adalah graf yang tidak memiliki sisi. Contoh: Graf kosong � dan � �: �:

2. Graf Sederhana (Simple Graph) Graf sederhana merupakan graf tak berarah yang tidak mengandung gelang maupun sisi-ganda. Contoh:

3. Graf Ganda (Multigraph) Graf ganda merupakan graf tak berarah yang tidak mengandung gelang(loop). Contoh:

4. Graf Semu (Pseudo Graph) Graf semu merupakan graf yang boleh mengandung gelang(loop).

Contoh:

5. Graf Berarah (Digraph) Graf berarah adalah graf yang setiap sisinya mempunyai arah dan tidak mempunyai dua sisi yang berlawanan antara dua buah simpul(tidak mempunyai sisi ganda). Contoh:

6. Graf Ganda Berarah (Directed Multigraph) Graf ganda berarah merupakan graf berarah yang membolehkan adanya sisi ganda pada graf tersebut (boleh mempunyai dua sisi yang berlawanan antara dua buah simpul). Contoh:

7. Graf Lintasan ( Misalkan adalah graf dengan himpunan titik = { , , … , , … , }, dan himpunan sisi � = {� : � = � � , }. Jalan pada graf dengan panjang adalah barisan titik dan sisi : , � , , � , , � , … , � − , dengan � = ≠ untuk setiap , ∈ + , = , , , … , − . Jika { , , , … , }maka disebut lintasan. Graf yang hanya terdiri atas satu lintasan disebut graf lintasan. Contoh: }. Graf Lintasan pada Misalkan = { , } dan � ={ graf adalah : , . Graf adalah graf lintasan berorde 2 ( :

8. Graf Siklus ( Misalkan : , � , , � , , � , … , � − , adalah Lintasan orde dengan panjang − pada graf . Siklus pada dengan panjang adalah subgraf dengan himpunan titik = dan himpunan sisi � =� ⋃{ , }. Graf yang hanya terdiri dari satu siklus disebut graf siklus. Contoh: Misalkan = { , , , , , , } dan � ={ = , = , = , , , }. Siklus pada graf adalah , , , , .

9. Graf Lengkap ( Graf lengkap merupakan graf sederhana yang setiap simpulnya terhubung (oleh satu sisi) ke semua simpul lainnya. Dengan kata lain, setiap simpulnya bertetangga. Contoh:

10. Graf Roda ( Graf roda adalah graf yang diperoleh dengan cara menambahkan satu simpul pada graf lingkaran , dan menghubungkan simpul baru tersebut dengan semua simpul pada graf lingkaran tersebut. Contoh:g

11. Graf Teratur (Regular Graph) Graf teratur merupakan graf yang setiap simpulnya mempunyai derajat yang sama. Apabila derajat setiap simpul pada graf teratur adalah r, maka graf tersebut dinamakan graf teratur berderajat r. Contoh: Graf reguler dengan empat simpul berderajat 2

12. Graf Planar (Planar Graph) Graf yang dapat digambarkan pada bidang datar dengan sisi-sisi yang tidak saling berpotongan dinamakan graf planar. Jika tidak, maka graf tersebut dinamakan graf tak-planar. Contoh: - Semua graf lingkaran merupakan graf planar - Graf lengkap K1, K2, K3, K4 merupakan graf planar

13. Graf Bidang (Plane Graph) Graf planar yang digambarkan dengan sisi-sisi yang tidak saling berpotongan dinamakan graf bidang (plane graph). Contoh:

, ) Sebuah graf sederhana G dikatakan graf bipartit jika himpunan simpul pada graf tersebut dapat dipisah menjadi dua himpunan tak kosong

14. Graf Bipartit (

yang disjoint, misalkan dan , sedemikian sehingga setiap sisi pada menghubungkan sebuah simpul pada dan sebuah simpul pada . Dengan demikian, pada graf bipartit tidak ada sisi yang menghubungkan dua simpul pada atau . Contoh:

15. Graf Berbobot (Weighted Graph) Graf berbobot(label) adalah graf yang setiap sisinya diberi sebuah harga (bobot). Contoh:

16. Graf Multipartit (

,

,.., �

Misalkan , , … , adalah beberapa himpunan bagian dari himpunan titik pada suatu graf . Untuk setiap , himpunan disebut partisi dari jika ≠ ∅ dan = ⋃ = serta ∩ = ∅ dengan ≠ . Graf disebut -partit jika dapat dipartisi ke dalam partisi , , … , sehingga setiap sisi � = �� , berlaku � dan � untuk suatu dan , , �{ , , … , }. Graf -partit untuk dengan | | = � disebut graf Multipartit. Contoh:

17. Graf Pohon ( Graf pohon adalah graf terhubung yang tidak mengandung sirkuit(siklus). Suatu Graf adalah Pohon jika dan hanya jika terdapat satu dan hanya satu jalur diantara setiap pasang simpul dari Graf . Contoh:

18. Graf Interval (Interval Graph) Misalkan suatu interval (0, 3), (2, 7), (-1, 1), (2, 3), (1, 4), (6, 8) yang diilustrasikan sebagai

Kita bisa mengkonstruksi hasil grafik interval ini kedalam graf dengan menganggap interval tersebut sebagai simpul yang dihubungkan oleh suatu sisi yang setidaknya interval yang berkorespondensi memiliki paling sedikit satu titik yang sama. Contoh:

19. Graf Kubik ( Graf kubik adalah graf bipartit yang dikonstruksi dengan menganggap setiap simpul sebagai biner. Contoh:

20. Graf Petersen (Petersen Graph) Graf Petersen adalah graf kubik dengan sepuluh titik. Contoh:

21. Graf Isomorfik . Dua buah graf yang sama tetapi secara geometri berbeda disebut graf yang saling isomorfik. · Dua buah graf, dan dikatakan isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul keduanya dan antara sisi-sisi keduanya sedemikian sehingga hubungan kebersisian tetap terjaga. · Dengan kata lain, misalkan sisi � bersisian dengan simpul dan di , maka sisi �′ yang berkoresponden di harus bersisian dengan simpul ′ dan ′ yang di . · 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 Contoh:

Dua buah graf diatas, terdiri dari empat buah simpul dimana setiap simpul adalah berderajat tiga. Walaupun secara geometri kedua tersebut berbeda tetapi pada prinsipnya kedua graf tersebut adalah sama.

22. Graf Bintang ( ) Graf bintang adalah suatu tree pada � node dengan satu node(tangkai) yang mempunyai derajat titik � − dan lainnya � − mempunyai satu buah derajat titik. Oleh karena itu graf bintang isomorfik dengan graf bipartit lengkap , − . Contoh:

23. Graf Pohon Pisang (

,

Graf pohon pisang adalah suatu graf yang diperoleh dengan menghubungkan satu daun pada setiap � kopian dari suatu -graf bintang dengan akar simpul tunggal yang dibedakan dari semua graf bintang yang ada. Contoh:

�, Graf perluasan petersen untuk � dan �− ⁄ adalah graf kubik terhubung yang berisi suatu poligon bintang dalam {�, }(circulant graph dan poligon regular luar {�}(cycle graph }, dengan simpul yang berkorespondensi antara dalam dan luar poligon yang terhubung lewat sisi. Contoh:

24. Graf Perluasan Petersen (

25. Graf Caterpillar Graf caterpillar adalah suatu pohon yang mana setiap simpul graf terletak pada pusat tangkai atau hanya satu sisi graf yang terletak jauh dari pusat tangkai. Contoh:

26. Graf Lobster Graf lobster adalah suatu pohon yang memiliki aturan jika dihapuskan satu simpul daun maka akan menjadi graf caterpillar. Contoh:

27. Graf Cakar (Claw Graph) Graf cakar adalah graf bipartit lengkap graf bintang . Contoh:

,

yang isomorfik dengan

28. Graf Anti-Prisma Graf anti-prisma adalah suatu graf yang berkorespondensi dengan skeleton dari suatu anti-prisma. Contoh:

29. Graf Barbel Graf barbel adalah suatu graf sederhana yang diperoleh dengan menghubungkan dua kopian graf lengkap dengan suatu jembatan(sisi). Contoh:

30. Graf Pesta Koktail (Cocktail Party Graph) Graf pesta koktail(Graf Robert) adalah graf yang berisi dua baris pasangan simpul dimana setiap simpul terkecuali satu pasangan dipasangkan dengan sisi graf. Contoh:

31. Graf de Bruijn Graf de Bruijn adalah suatu graf yang simpulnya terdiri atas barisan simbol-simbol dari suatu alfabet dan sisinya adalah barisan yang bisa saja overlap. Contoh:

32. Graf Hanoi ( Graf Hanoi adalah suatu graf yang didasarkan oleh masalah puncak menara Hanoi. Contoh:

33. Graf Anak Tangga (Ladder Rung Graph) Graf anak tangga adalah suatu graf � . Contoh:

34. Graf Hasil Kali Kartesius (Cartesian Product Graph) Graf hasil kali kartesius adalah suatu graf dengan himpunan titik × dan = , yang bertetangga dengan = , dimana [ = adj ] atau [ = adj ]. Contoh:

35. Graf Garis ( Graf garis adalah suatu graf sederhana yang diperoleh dengan mengasosiasikan suatu simpul dengan setiap sisi pada graf dan menghubungkan dua simpul dengan sisi jika dan hanya jika korespondensi sisi dari punya simpul yang sama. Contoh:

36. Graf Benteng (Rook Graph) Graf benteng adalah graf hasil kali kartesius × dari suatu graf lengkap, yang mana ekuivalen dengan graf garis dari suatu graf bipartit lengkap , . Contoh:

37. Graf Lolipop Graf lolipop adalah graf yang diperoleh dengan cara menghubungkan graf lengkap dengan graf lintasan dengan suatu jembatan(sisi). Contoh:

38. Graf Segitiga Sierpinski Graf segitiga Sierpinski adalah suatu graf yang didasarkan pada masalah segitiga Sierpinski. Contoh:

39. Graf Triangular ( Graf triangular adalah graf garis dari graf lengkap Contoh:

.

40. Graf Johnson Graf Johnson adalah graf yang simpulnya diperoleh dari -Subset { , … , �} dengan dua simpul terhubung jika dan hanya jika masing-masing irisannya punya ukuran − . Contoh:

41. Graf Terhubung dan Graf Tidak Terhubung Suatu graf disebut sebagai graf terhubung apabila untuk setiap pasang simpul dan di dalam himpunan terdapat lintasan dari ke yang juga harus berarti ada lintasan dari ke . Jika tidak, maka disebut graf tak-terhubung. Contoh:

42. Sub Graf Subgraf (Upagraf) merupakan sebuah graf yang ada pada sebuah graf yang lain. Contoh:

43. Graf Euler Sirkuit Euler merupakan sirkuit yang melewati masing-masing sisi tepat satu kali. Graf yang memuat sirkuit Euler dinamakan graf Euler (Eulerian graph). Contoh:

44. Graf Semi-Euler Graf yang memuat suatu jalur Euler dinamakan graf semi Euler (semiEulerian graph).

Contoh:

45. Graf Hamilton Sirkuit Hamilton merupakan sirkuit yang melewati masing-masing sisi tepat satu kali. Graf yang memuat sirkuit Hamilton dinamakan graf Hamilton (Hamiltonian graph). Contoh:

46. Graf Semi-Hamilton Graf yang memuat lintasan Hamilton dinamakan graf semi Hamilton (semi- Hamiltonian graph). Contoh:

47. Graf Integral Graf integral adalah suatu graf yang spektrum grafnya berisikan bilangan bulat. Contoh:

48. Graf Coxeter Graf Coxeter adalah graf kubik simetris nonhamiltonian dengan 28 titik dan 42 sisi. Contoh:

49. Graf Ikan Graf Ikan adalah graf dengan 6 simpul. Contoh:

50. Graf Domino Graf domino adalah graf dengan 6 titik yang juga isomorfik dengan 3graf anak tangga dan (2,3)-graf grid. Contoh:...