# data[].attributes.body
Kelompok 2:
1. Henry A. Mundung
2. Satrio M. Mitusala
3. Fernando Sabar
4. Meijesty Ticoalu
Siti Nur Annisa Pakaya

..::Derajat (Degree)::..

Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.
Notasi: d(v)

..::Graf Kosong(null Graph/empty Graph)::..

Graf yang himpunan sisinya merupakan Himpunan Kosong(Nn)

..::Terhubung(Connected)::..

Dua buah simpul V1 dan simpul V2 disebut terhubung jika terdapat lintasan dari V1 ke V2
G disebut graf terhubung jika untuk setiap pasangan simpul VI dan VJ dalam himpunan Vterdapat lintasan dari VI ke VJ jika tidak maka G disebut graf tak terhubung

# data[].attributes.headline
Terminologi Graf 3 (Upagraf, Upagraf Merentang, Cut-Set, Graf Berbobot)

# data[].attributes.subject
Terminologi Graf 3 (Upagraf, Upagraf Merentang, Cut-Set, Graf Berbobot)

# data[].attributes.body
Kelompok  1  :
1.Erlangga Malli
2.Marselina betah
3Hendry Nelwan
4.Braijen kahard
5.Candle rogaga
6.Natanael tampi

Upagraf (Subgraph) dan Komplemen Upagraf

Misalkan G = (V, E) adalah sebuah graf. G ₁ = (V ₁, E ₁) adalah upagraf (subgraph) dari G jika V 1  Í V dan E ₁ Í E.

Komplemen dari upagraf G ₁ terhadap graf G adalah graf G ₂ = (V ₂, E ₂) sedemikian sehingga E ₂ = E - E ₁ dan V ₂ adalah himpunan simpul yang anggota-anggota E ₂ bersisian dengannya.

Komponen graf (connected component) adalah jumlah maksimum upagraf terhubung dalam graf G.

Graf G di atas ini mempunyai 4 buah komponen.
Pada graf berarah, komponen terhubung kuat (strongly connected component) adalah jumlah maksimum upagraf yang terhubung kuat.

B. Upagraf Rentang (Spanning Subgraph)

Upagraf G 1 = (V ₁, E ₁) dari G = (V, E) dikatakan upagraf rentang jika V 1 =V (yaitu G ₁ mengandung semua simpul dari G).
dari G

C. Cut-Set

Cut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari Gmenyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen.

Pada graf di bawah, {(1,2), (1,5), (3,5), (3,4)} adalah cut-set. Terdapat banyak cut-setpada sebuah graf terhubung.

Himpunan {(1,2), (2,5)} juga adalah cut-set, {(1,3), (1,5), (1,2)} adalah cut-set, {(2,6)} juga cut-set,

tetapi {(1,2), (2,5), (4,5)} bukan cut-set sebab himpunan bagiannya, {(1,2), (2,5)} adalah cut-set.

d. Graf Berbobot (Weighted Graph)

Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot).

# data[].attributes.headline
Terminologi Graf 2 (Derajat, Graf Kosong, Terhubung

# data[].attributes.subject
Terminologi Graf 2 (Derajat, Graf Kosong, Terhubung

# data[].attributes.body
Kelompok 2   :

# data[].attributes.headline
Terminologi Graf (Bertetangga, Bersisian, Simpul Terpencil)

# data[].attributes.subject
Terminologi Graf (Bertetangga, Bersisian, Simpul Terpencil)

# data[].attributes.body
Kelompok 3  :

# data[].attributes.body
Kelompok  4  :

# data[].attributes.body
Kelompok  5  :
- Briliandro Kasenda
- Natalie Kawatu
- Injilia Rosang
- Juan Taloko
- Inzaghi Rorong

Jenis-jenis Graf

v  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

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

v  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 Regular

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

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

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

Graph adalah kumpulan simpul (nodes) yang dihubungkan satu sama lain melalui sisi/busur (edges). Suatu Graph G terdiri dari dua himpunan yaitu himpunan V dan himpunan E (Munir, 2007).
DEFINISI GRAF
Untuk mencari lintasan terpendek, algoritma Floyd Warshall memulai iteras dari awalnya kemudian memperpanjang lintasan dengan mengevaluasi titik demi titik hingga mencapai titik tujuan dengan jumlah bobot seminimum mungkin.

Menurut arah dan bobotnya, Graf dibagi menjadi empat bagian yaitu:
1. Graf berarah dan berbobot:
2. Graf tidak berarah dan berbobot
4. Graf tidak berarah dan tidak berbobot

SIKLUS HAMILTON
LINTASAN TERPENDEK
Graf digunakan sebagai alat untuk memodelkan suatu persoalan. Salah satunya adalah mencari lintasan terpendek
Graf yang digunakan yaitu graf berarah dan berbobot

Algoritma Floyd Warshall merupakan salah satu varian dari pemograman dinamis yaitu suatu metode melakukan pemecahan masalah dengan memandang solusi yang akan diperoleh oleh suatu keputusan yang terpadu. Artinya solusi-solusi tersebut dibentuk dari solusi – solusi sebelumnya dan ada kemungkinan solusinya lebih dari satu.
Algoritma ini digunakan untuk menemukan lintasan terpendek semua pasangan simpul dalam graf.

ALGORITMA FLOYD WARSHALL
3. Graf berarah dan tidak berbobot
ALgoritma Floyd Warshall