Sebutkan jenis graf berdasarkan ada atau tidaknya loop dan berdasarkan orientasi arah

Academia.edu no longer supports Internet Explorer.

To browse Academia.edu and the wider internet faster and more securely, please take a few seconds to upgrade your browser.

Jawaban:

1. Secara sederhana graf didefinisikan sebagai kumpulan titik yang dihubungkan oleh garis. Secara matematis, graf adalah pasangan himpunan (V,E) dimana V adalah himpunan tak kosong yang memiliki elemen disebut simpul (vertices) dan E adalah kumpulan dari dua elemen subsets V yang disebut busur (edges).

jenis-jenis graf

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.

2. Graf tak-sederhana (unsimple-graph).

Graf yang mengandung sisi ganda atau gelang

dinamakan graf tak-sederhana (unsimple graph).

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.

2. Graf berarah (directed graph atau digraph)

Graf yang setiap sisinya diberikan orientasi arah disebut sebagai graf berarah.

4. Metode integrasi numerik adalah suatu cara untuk menghitung aproksimasi luas daerah di bawah fungsi yang dimaksud pada selang yang diberikan. Berikut ini adalah beberapa metode integrasi numerik yang lazim digunakan: Metode Euler Eksplisit. merupakan metode integrasi yang paling mudah.

5. Empat kemampuan dasar dalam computational thinking, yaitu:

Decomposition (dekomposisi)

Pattern Recognition (pengenalan pola)

Abstraction (Abstraksi)

Algorithm (Penulisan Algoritma)

- Decomposition (dekomposisi)

dekomposisi merupakan salah satu perubahan secara kimia yang membuat objek, biasanya makhluk hidup yang mati dapat mengalami perusakan susunan/struktur yang dilakukan oleh dekomposer atau media pembusukan.

- Pattern Recognition (pengenalan pola)

Pengenalan pola merupakan bidang dalam pembelajaran mesin dan dapat diartikan sebagai "tindakan mengambil data mentah dan bertindak berdasarkan klasifikasi data". ... Ilmu pengetahuan yang menitikberatkan pada deskripsi dan klasifikasi (pengenalan) dari suatu pengukuran.

- Abstraction (Abstraksi)

abstraksi adalah proses representasi data dan program dalam bentuk sama dengan pengertiannya, dengan menyembunyikan rincian / detail implementasi. Abstraksi mencoba menyembunyikan detail agar programmer dapat berfokus pada konsep tertentu saja pada satu waktu

- Algorithm (Penulisan Algoritma)

Terdapat 3 cara penulisan (notasi) algoritma yang biasanya digunakan oleh para programer dalam menuliskan algoritmanya, yaitu: Structured English (SE), Pseudocode (kode-semu), dan Flowchart (bagan alir)

Penjelasan:

maaf ya dek kakak kurang mengerti soal nomor 2 dan 3

         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

7.   Graf berlabel

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

Sebuah graf dikatakan graf regular bila derajat setiap simpulnya sama.

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

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

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.

Graf lingkaran adalah graf sederhana yang setiap simpulnya berderajat dua. Graf lingkaran dengan n simpul dilambangkan dengan 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.

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.

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

26.    Graf Cayley

27.    Graf Cartesian Product

Graf Cartesian Product

28.    Graf Claw

Graf bipartit komplit

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

33. Graf Centipede

Graf n-centipede adalah tree pada node 2n yang diperoleh dengan menggabungkan bagian dari n-copies pada path

34. Graf komposisi (compotition graph)

Komposisi terhadap

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

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

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

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

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