MARI BELAJAR: GRAF

BAB 4 GRAF

Graf adalah suatu diagram yg memuat informasi

Tujuan merepresentasikan obyek-obyek diskrit dan hubungan obyek2 tsb

Secara visual obyek dinyatakan dg bulatan kecil dan hubungan obyek dinyatakan dg garis, garis bisa berarah ataupun tdk berarah

Contoh

Strktur organisasi, peta rangkaian listrik dll

1. Dasar-Dasar GRAF

Definisi Graf

Suatu Graf G terdiri dari 2 himpunan yg berhingga yaitu himpunan titik tidak kosong dan himpunan garis

- Suatu grs berhubungan dg satu titik atau dua titik (titik –titik tsb dsbut titik ujung), grs yg berhub. dg satu titik ujung disebut LOOP, dua grs yg beda menghubungkan ttk yg sama disebut Garis Paralel.

- Dua titik dikatakan berhubungan jika ada garis yg menghubungkan keduanya

- Titik yg tdk memiliki garis yg berhubungan dgnya dsbut Titik Terasing

- Graf yg tidak memiliki titik (shingga tdk memiliki garis) dsbut Graf Kosong

- Panjang garis , kelengkungan garis srta letak ttk tdk berpengaruh dlm suatu graf

- Graf berarah jika semua garisnya berarah, dan sebaliknya

Contoh

1. Ada 7 kota yaitu A,B,C,D,E,F, dan G yang beberapa diantaranya dpt berhubungan langsung dg jalan darat , hubungan2 langsung yg dapat dilakukan sbb; A dg B dan D; B dg D; C dg B; E dg F . Buatlah graf nya

Jawab...

2. Diketahui graf (a) V(G)={ ..............}

E(G)={............}

v₆

Tentukan

a) Himpunan titik, himpunan garis, titik-titik ujung masing-masing garis, dan garis paralel

b) Loop dan titik terasing

Jawab.....

3. Gambarlah graf G dg titik V(G)= { v₁, v₂, v₃, v₄} dan garis E(G)= {e₁, e₂, e₃, e₄, e₅} dg titik-titik ujung berikut

garis titik ujung

e₁ { v₁, v₃}

e₂ {v₂, v₄}

e₃ {v₁}

e₄ {v₂, v₄}

e₅ {v₃ }

Jawab

Salah satu graf yg dapat dibentuk bila diketahui himpunan titik V(G)= { v₁, v₂, v₃, v₄} dan garis E(G)= {e₁, e₂, e₃, e₄, e₅} adalah sbb

( A) v₂(B)

v₁ v₃

v₄

Catatan: jika diketahui graf pasti himpunan titik, garis serta titik ujungnya adalah tunggal

4. Ada sebuah pulau yg penghuninya hanya terdiri dari dua macam yaitu pemakan orang dan pemakan sayuran dimana ada 2 orang pemakan orang dan 2 orang pemakan sayuran di sisi barat sungai. Di sisi barat sungai itu terdapat perahu kecil yg dapat menampung paling banyak 2 orang.

Pertanyaan bagaimana cara mengangkut 4 orang tsb kesisi timur sungan dg syarat jumlah pemakan manusia pada suatu sisi sungai tdk boleh lebih banyak dari pemakan sayuran ( sama boleh)

Jawab

Menggambarkan semua kemungkinan keadaan, dan kemudian menghilangkan keadaan yg tidak boleh terjadi

Misal s= pemakan sayuran

o=pemakan orang posisi berubah

p=perahu jml pemkan org timur(kanan)

/= sungi posisi tdk berubah

arah perjalanan tidak boleh pada pada satu sisi (warna sama)

Jadi didapat cara pengangkutan 0 1 2

Oossp/ ke ss/poo ke ossp/o ke

0/poss ke oop/ss ke /pssoo

jml pemakan sayur timur(kanan)

Graf Tak Berarah

Graf Bipartite

Graf sederhana adalah graf yang tidak memiliki loop ataupun garis paralel

Contoh

Ambarlah semua graf sederhanayang dibentuk dari 4 titikV(G) = {a, b, c, d) dan 2 garis

Jawab

2!.2!

Setiap garisselalu berhubungan dg 2 titik maka kemungkinan banyak garisnya adl

2!.4!

Yagn berbentuk E(G) = {a,b}, {a, c},{a, d},{b, c}, dan {c, d} dari 6 garis ini diambil = = 6

2 garis maka garis yg mungkin aalah sebanyak = = 15 macam graf

a b

c d Dan seterusnya cari sendiri yg 14 lainnya!!!!

Graf Lengkap dgn titik dinotasikan dg K_n

n(n-1)

Adalah graf sederhana dg n titik dimana setiap 2 titik yg beda dihubungkan dgsuatu garis

Banyaknya garis pd graf lengkap dg n titik adalah buah garis

#suatu graf disebut graf bipartite apabila V(G) merupakan gabungan 2 himpunan yg tidak kosong V₁ dan V₂ dan setiap garis dalam G menghubungkan suatu titik dalamV₁ dg titik dalam V₂

# graf bipartite lengkap (K_mn) adalah graf bipartite setiap titik dalam V₁ berhubungan dg setiap titik dalam V₂

Contoh

v₁

v₂

v₃

v₄

v₆

v₅

Tentukan mana diantara graf-graf berikut yg merupakan graf bipartite dan graf bipartite lengkap

Jawab (a) adalah graf bipartite lengkap (K₃₂) (b) adalahgraf bipartite

Catatan semua graf soal diatas titik-titiknya dapat dibagi menjadi 2 bagian

Komplemen Graf

Komplemen suatu graf G dinotasikan dg Ĝ dengan n titik adalah suatu graf sederhana dengan

1) Titik –titik Ĝ sama dg titik G jadi V(G)=V(Ĝ)

2) Garis –garis Ĝ adalah komplemen garis-garis G terhadap graf lengkapnya (K_n)

E(Ĝ)= K_n) – E(G)

berarti titi-titik yg dihubungkan dg garis dalam G tidak terhubung dalam Ĝ dan sebaliknya titik-titik yg terhubung dalam G menjadi tdk terhubung dalam Ĝ(dg kata laingaris yg ada pada G tidak ada pada Ĝ)

Contoh

Gambarlah komplemen graf G yg didefinisikan dalam gambar berikut

(a) (b) (c)

Jawab

(a) (b) (c)

Sub Graf

Misalkan G adalah suatu graf . Graf Hdikatakan subgraf G bila hanya bila

1) V(H)ÍV(G)

2) E(H)ÍE(G)

3) Setiap garis dalam H memiliki titik ujung yg sama dg garis tersebut dalam G

Contoh

v₂

diketahui graf –graf dibawah, tentukan apakah H merupakan sub graf G ?

v₂

v₃

v₁

v₃

G H

Jawab

V(H) = { v₂, v₃} dan V(G)= = { v ₁, v₂, v₃} sehingga V(H)ÍV(G)

E(H)= { e₄} dan E(G)= { e ₁, e₂, e₃, e₄} sehingga V(H)ÍV(G)

Garis e₄ di H merupakan loop pada titik v₂ dan garis e₄ juga di G merupakan loop pada ttk v₂ jadi H merupakan subgraf G

b) v1 v2 v1 v2

v3 v3

G H

Jawab

H bukan merupakan subgraf G krn meskipun V(H)=V(G)= { v ₁, v₂, v₃} dan E(H)=E(G)= { e ₁, e₂, e₃, e₄} tetapi garis e₄dalam H tdk menghubungkan ttk yg sama dg garis e₄ dalam G yaitu dalam H garisnya merupakan loop di ttk v₃ sedang dalam G garisnya merupakan loop di ttk v₂

Jawab

Karena graf H= graf G, maka H merupakan subgraf G

Derajat

Misalkan v adalah titik dalam suatu graf G. Derajat titik v yang disimbulkan d(v) = jumlah garis yg berhubungan dg titik v dan garis suatu loop dihitung dua kali. Derajat total G adalah jumlah derajat semua titik dalam G.

Contoh

Tentukan derajat tiap-tiap titik pada graf dibawah dan berapa derajat totalnya

Jawab

d(v₁) = 4 , d(v₂) = 2 , d(v₃) = 1 , d(v₄) = 1 , d(v₅) = 2 , d(v₆) = 0

i=1

Derajat total = ∑⁶ d(vi) = 10

#dalam sembarang graf, jumlah titik yg derajat ganjil adalah genap

Contoh

Gambarlah graf dg ketentuan sbb

a) Graf dg 4 titik dg derajat masing-masing 1, 1, 2, dan 3 (tdk dapat dibuat graf krn derajat total gaji)

b) Graf dg 4 titik dg derajat masing-masing 1, 1, 3, dan 3 (dapat dibuat antara lain coba sendiri)

c) Graf dg 4 titik dg derajat masing-masing 1, 1, 2, 2, 2, 4, 4, 4, dan 6 (tdk mungkin krn 3 titik derajat ganjil)

d) Graf dg 4 titik dg derajat masing-masing 1, 1, 3, dan 3 (tdk mungkin krn grafnya bentuk sederhana)

Path dan serkuit

Walk dari v kew adl barisan titik-titik yang berhubungan dan garis berselangselung diawali titik v dan diakhiri titik w

a. Walk dg panjang n dari v ke w

Ditulis sebagai :v= v₀e₁v₁e₂v₂e₃v₃..............e_nv_n= w dg v_i=1 dan v_i adl titik-titik ujung garis e_i

b. Path dg panjang n dari v ke w adl walk dari v ke w dg semua garisnya berbeda

Ditulis sebagai :v= v₀e₁v₁e₂v₂e₃v₃..............e_nv_n= w dg e_i≠e_j

c. Path sedrhana dg panjang n dari v ke w adl path dari vke w (semua garisnya berbeda), titik-titiknya berbeda

Ditulis sebagai : v=v₀e₁v₁e₂v₂e₃v₃..............e_nv_n= w dg e_i≠e_j dan v_k≠ v_m

d. Serkuit dg panjang n adl path (semua garisnya berbeda), dg titik awal dan titik akhir yang sama

Ditulis sebagai : v₀e₁v₁e₂v₂e₃v₃..............e_nv_n= v₀

e. Serkuit sederhana dg panjang n adl serkuit yg semua titik-titiknya berbeda

Ditulis sebagai : v₀e₁v₁e₂v₂e₃v₃..............e_nv_n= v₀ dg e_i≠e_j dan v_k≠ v_m

Contoh

Tentukan mana diantara baris titik dan garis pd gambar dibawah yg merupakan walk, path, path sederhana, sirkuit, dan sirkuit sederhana.

a) v₁e₁v₂e₃v₃e₄v₃e₅v₄

b) v₁e₁v₂e₃v₃e₅v₄e₅v₃e₆v₅

c)v₂e₃v₃e₅v₄e₁₀v₅e₆v₃e₇v₆e₈v₂

d) V₂e₃v₃e₅v₄e₁₀v₅e₉v₆e₈v₂e) v₁ jawab terlihat sirkuit sederhana krn .......

Jawab

a)Terlihat garisnya berbeda-beda yaitu e_1,e_3,e₄,₃e₅ sedangkan titik ada yg sama maka dsbut PATH, dg panjang 4 dari v₁ke v₄

b)Terlihat bahwa garisnya ada yg sama yaitu e₅berarti WALK dg panjang 5 dari V₁ke v₅

c) Terlihat garisnya berbada yaitu e₃e₅e₁₀e₆e₇e₈sedangkan titiknya ada yg sama letaknya di tengah , titik awal dan akhir sama berarti serkuit saja dg panjang 6

d)Terlihat garisnya berbeda-beda, barisan, di awal dan akhir dg titik sama, semua titiknya berbeda berarti merupakan SIRKUIT SEDERHANA

Sirkuit Euler

Adalah sirkuit dimana setiap titik dlm graf muncul paling sedikit sekali , dan setiap garis dlm graf muncul satu kali.

Contoh

Kota Konigsberg terletak pada pertemuan 2 cabang sungai Prigel. Kota tersebut terdiri dari sebuah pulau ditengah-tengah ditengah-tengah dan ada 7 jembatan yg mengelilinginya menghubungkan 4 daerah . Masalahnya mungkinkah seorang berjalan mengunjung 4 kota tsb yg diawali dan diakhiri pada tempat yg sama, dg melintasi 7 jembatan masing-masing tepat satu kali? Apakah termasuk sirkuit Euler?

Jawab misal 4 daerah adalah 4 titik yaitu v_{1 ,}v_{2 ,}v_{3 ,}v₄

misal 7 jembatan adlah 7 garis yaitu e₁e₂e₃e₄e₅e₆e₇

Dibuat graf sbb v₁

v₂ v₃

jadi dpt disimpulkan bahwa berjalan mgunjngi 4 kota

tidak mungkin tepat satu kali melintasi jembatan.

V₄

Graf terhubung dan tidak terhubung

- Dua titik dalam graf dikatakan terhubung bila hanya bila ada walk antara dua titik tsb

- Graf G dikatakan terhubung bila hanya bila setiap 2 titik dalam graf G terhubung.

- Graf G dikatakan TDK terhubung bila hanya bila ADA 2 titik dlm graf G tdk terhubung.

Contoh

Diketahui graf G sbb

a b c

Jawab

Teorema

Graf G terhubung dikatakan Sirkuit Euler bila hanya bila semua titik dalam G mempunyai derajat genap.

Contoh

b) # syarat graf G terhubung : tdk di penuhi krn ada 2 titik tdk terhubung

c) jawab merupakan sirkuit euler krn terhubung tiap ttk derajat genap

Contoh

Diketahui sebuah rumah beserta pintu dan ruangan-ruangannya sbb

A B C

H G D

F E

Mungkinkah seseorang keluar rumah (pintu 10) dan mengunci semua pintu dimulai dari pintu 1?, dg ketentuan pintu yg sdah dikunci sebelumnya tdk boleh dilewati

Jawab

Misal ruangan dinyatakan titik dan pintu dinyatakan dg garis dan ruangan A dg E dihubungkan

dg pintu semu sh g didapat graf sbb apakah graf tsb euler?

jawab kecuali titik A dan E , semua titik mempunyai derajat genap

dan grafnya terhubung jadi graf tsb adl graf Euler

Sirkuit Hamilton

Suatu graf terhubung disebut Sirkuit Hamilton bila ada sirkuit setiap titiknya dikunjungi sekali (kecuali titik awal yg sama dgtitik akhir) dan garisnya tdk semuanya harus dilalui.

Catatan

1)Sirkuit Euler setiap garisnya harus dilalui sekali , titiknya boleh dikunjungi lebih dari satu kali

2)Petunjuk untuk menentukan graf adl sirkuit hamilton adl memiliki sub graf H dg sifat

i) H terhubung

ii)H memuat semua titik G

iii) H memiliki jumlah garis yg sama dg jumlah titiknya

iv) setiap ttk dalam H mempunuai derajat 2

Contoh

Gambar berikut menyatakan peta beberapa kota (A.....G) beserta jalan yg menghubungkan kota-kota tsb seseorang salesmen hendak mengunjungi setiap kota masing2 sekali dimulai dr kota A . Carilah

Jalan yg dilalui jawab

F E

A D

terlihat graf H tsb sifat i) ii) iii) dan iv) dipenuhi jadi graf G tsb adlah sirkuit Hamilton

dg coba-coba didapat jalur yg mungkin adl ABFECDGA atau ABCFEDGA(buat grafnya)

Contoh

Buktikan graf berikut bukan sirkuit Hamilton

a b a c

e d c b

f g e d

Jawab

a) Syarat sirkuit hamilton bila graf G mempumyai sub graf H memiliki sifat

i) H memuat semua titik dalam dalam G

terpenuhi karena bisa diambil semua

ii) Jumlah garis dalam H sama dg jumlah titiknya tinggal menghilangkan tetapi ada kaitannya dg sarat iii)

iii) Semua titik dalam H berderajat 2 tidak terpenuhi karena titik B dan G derajat 3 salah satu garisnya harus dihilangkan padahal jml garis 8, dg menghilangkan dua maka jml garis dalam H menjadi 6 jadi tidak mungkin sub graf H memuat 7 garis

b) Ttk b derajat 4 maka 2 grs hrs dihilangkan, akan tetapi mengakibatkan titik lain derajatnya menjadi 1 jadi tidakmungkin terpenuhi terbukti bukan sirkuit hamilton

Suatu Graf berarah G terdiri dari

Himpunan titik-titik V(G) = {v₁, v₂, ....} , himpunan E(G) = {e₁,e₂} dan suatu fungsi Ψ yg mengawankan setiap garis dalam E(G) ke suatu pasangan berurutan titik (v_i, v_j)

# jika e_k = (v_i, v_j) adalah suatu garis dalamG, maka v_i disebut titik awal, dan v_j disebut titik akhir, arah garis dari v_i ke v_j

# jumlah garis yg keluar dari titik v_i disebut derajat keluar titik v_i. dinotasikan d⁺ (v_i) sedangkan garis yang masuk ke titik v_i disebut derajat masuk titik v_i. Dinotasikan d^-(v_i)

# titik terasing dalamG derajat masuk dan keluarnya adalah 0

# titik pendan dalam G jumlah derajat masuk dan keluarnya adalah 1

# dua garis berarah disebut paralel bila keduanya memiiki titik awal dan titik akhir yg sama

Contoh

Jawab

a) V(G) = {v₁, v₂, v₃, v₄, v₅, v₆}

E(G) = { e₁, e₂, e₃, e₄, e₅, e₆, e₇, e₈, e₉}

Fungsi mengawankan garis-garis dg titik-titik adalah e₁ dengan (v₁, v₂) dst....

Path berarah dan Sirkuit berarah

Path berarah dan sirkuit berarah sama saja dg path dan sirkuit tdk berarah hanya bedanya dalam graf perjalanan yg dilakukan harus mengikuti arah garis.

Suatu graf berarah tetapi tidak memuat sirkuit berarah disebut Asiklik

Contoh

Tentukan path terpendek dari titik E ke B pd graf berarah berikut

A E

C G

B F

D H jawab ada beberapa path berarah dari E ke B yg dapat dilakukan adalah EACDB dan EAB terlihat path terpendek adalah EAB dg panjang 2

Contoh

diketahui graf AB

apakah graf tsb sirkuit

A B

terlihat graf berarah tsbt tdk ada sirkuit berarah jadi graf Asiklik

Graf berarah terhubung

Graf G berarah disebut terhubung kuat jika ada paht untuk sembarang 2 titik dalam G

Graf G berarah disebut terhubung lemah jika tidak terhubung kuat, ttp graf tak berarah yg bersesuaian dg graf G terhubung

Contoh

Tentukan apakah graf G berikut terhubung kuat atau lemah

a) b)

jawab

a) Terlihat setiap 2 titik dapat dihubungkan dg path berarah jadi graf tsb adl graf terhubung kuat

b) Tidak ada path berarah yg menghubungkan titik v₄ ke titik v₃ , akan tetapi jika arah semua garis dihilangkan maka graf tsb merupakan graf terhubung, jadi graf tsb adl graf terhubung lemah

Reprentasi Graf dalam Matriks

Matriks dapat digunakan untuk menyatakan graf, hal ini dapat membantu pembuatan program komputer yg berkaitan dg graf, sehingga memudah kan dalam perhitungan .

Kesulian graf di buat dalam bentuk matrik adalah keterbatasan bentuk matriks dalam menyerap semua informasi akibatnya ada bermacam-macam matrik dalam nenyatakan graf tertentu

a) Representasi graf tak berarah dlm matriks

1. Matrik Terhubung

adalah digunakan menyatakan graf dg cara menyatakan jumlah garis yg menghubungkan titik titiknya, jumlah baris/kolom dalam matrik sama dg jumlah titik dalam graf

Definisi

G adl matrik tak berarah dg titik-titik v₁v₂......v_n, matriks hubung yg bersesuaian dg graf G adalah A=(a_ij) dimana a_ij= jumlah garis yg menghubungkan titik v_i ke titik v_j ; i,j=1,2,.....n

Graf tak berarah bentuk matriknya adalah matriks simetris

Contoh

Nyatakan graf berikut dalam matriks hubung

a) b)

jawab

A) b)

Ada beberapa hal yg dapat digunakan dalam matriks hubung

1) Loop pada titik v₁ yg bersesuaian dg a_n = 1, graf tidak memiliki loop diagonal utamanya = 0

2) Dapat dipakai mendeteksi graf tidak terhubung secara mudah. Suatu graf tidak terhubung terdiri dari k komponen bila hanya bila matrik hubungnya berbentuk

3) Derajat titik v₁ adalah jumlah komponen matriks kolom/ baris ke i. Elemen diagonal dikalikan 2

4) Dapat dipakai untuk mendeteksi graf bipartet (K_mn), bila matriks hubung berbentuk

Dimana O = matrik yg semua elemennya nol

I_m = matriks ukuran m x n yg semua elemenya =1

I_n = matriks ukuran n x m yg semua elemennya = 1

5) Dapat dipakai untuk mendeteksi graf lengkap ini terjadi bila dan hanya bila semua elemennya diagonal utamanya nol, sedangkan elemen diluar diagonal = 1

Juga dapat menghitung banyaknya kemungkinan walk dg panjang n dari titik v_i ketitik v_j adalah elemen a_ij dari matriks hubung Aⁿ

Contoh

Diketahui graf G sbb

v₁

v₂

v₃ hitunglah jumlah walk dg panjang 2 dari titik v₂ ke v₁

jawab

matrik hubung A yang bersesuaian dengan graf G adalah

A = untuk menghitung walk dg panjang 2, hitung dulu A²

A² = A x A = =

Jadi walk dari v₂ ke v₁ dg panjang 2 adalah elemen a_n pada A² yaitu 6 buah cara. Walk tersebut didapat dengan coba-coba yaitu v₁e₁v₁e₁v₁, v₁e₂v₂e₂v₁,........... teruskan

2. Matriks Biner

Matriks biner yg bersesuaian dg graf G tanpa loop dg n titik dan k garis adalah matriks A ukuran nxk yg elemennya adalah

a_ij= 1 jika titik v_i berhubungan dg garis e_j .

0 jika titik v_i tidak berhubungan dg garis e_j .

Contoh

Diketahui graf G sbb

tentukan matriks binernya dan derajat totalnya

Jawab

Ada 6 titik dan 8 garis dalam graf G, maka matriks A yg bersesuaian dg graf G tersebut berukuran 6x8 ( 6 baris dan 8 kolom)yaitu

d(v₁)=1+0+0+0+0+1+0+0= 2 A=

d(v₂)= 4, d(v₃)=1, d(v₄)=4

d(v₅)=3, d(v₆)=2

Jadi derajat totalnya adalah 16

Ada beberapa yg didapat pada matriks biner sbb

1) Ada korespodensi satu satu antara graf G dan matriks biner A

2) Setiap garis berhubungan dg dua titik (krn tdk memiliki loop), shingga setiap kolom ada 2 buah elemen 1 lainnya 0.

3) Jumlah elemen baris ke i adalah derajat titik v_i , sedangkan derajat total graf G adalah jumlah semua elemen pd matriknya

4) Jika semua elemen pada baris ke-i adalah 0, maka titik v_i, adalah titik terasing

5) Dua kolom elemennya sama menyatakan garis yg paralel.

3. Matrik Sirkuit

Matriks sirkuit A= (a_ij) yg bersesuaian dg graf G yg memuat q sirkuit sederhana dan e buah garis adalah matrik yg terdidri dari q baris dan e kolom dg elemen sbb

a_ij = 1 jika sirkuit ke i memuat garis ke j

0 jika sirkuit ke i tidak memuat garis ke j

Contoh

Tentukan matriks sirkuit yg sesuai dg graf diatas.

Jawab

Graf tsb ada 8 garis (e₁ e₁ e₁e₁ e₁ e₁ e₁ e₁ ) dan 4 sirkuit ( s₁ s₁ s₁ s₁ s₁ s₁ ) sederhana masing masing s₁ =e₇ s₈ , s₂ = e₃ e₄ e₅ ; s₃ = e₁e₄ e₆ ; s₄ = e₁ e₃ e₅ e₆

Selanjutnya didapat matriks sirkuit sbb

e₁e₁e₁e₁e₁e₁e₁e₁

A = s₁

s₁

Representasi Graf Berarah Dalam Matriks

Hampis seperti graf tdk berarah , bedanya hanya terletak pada informasi tentang arah garisnya

1 Matriks hubung

Matriks hubung yg sesuai dg graf berarah G yg terdiri dari n titik tanpa garis paralel adl matriks bujur sangkar n x n , yaitu A = (a_ij )dengan

a_ij = 1 jika ada garis dari titik v_i ke titik v_j

0 jika tidak ada garis dari titik v_i ke titik v_j

Contoh

Nyatakan graf dibawah ke dalam matriks hubung

v₁v₂

v₃

v₄v₅

Jawab graf terdiri dari 5 titik sehingga matrik hubungnya v₁v₂v₃v₄v₅

adalah matriks bujur sangkar 5 x 5 A = v₁

v₂

v₃

v₄

v₅

Ada beberapa hal yg dapat digunakan pada matriks hubung untuk graf berarah

Banyaknya garis yg keluar dari v_i(derajat keluar) sama dg banyaknya elemen 1 pd baris ke i dan banyaknya garis yg mesuk dari v_i(derajat masuk) sama dg banyaknya elemen 1 pd kolom ke i .banyak totalgaris pada G adl banyaknya elemen 1 pada matriks hubungnya.
Graf tdk memiliki loop semua elemen diagonalnya nol, jika ada loop pada ttk v_ielemen a_ii=1.
Graf tdk terhubung yg terdiri dari k komponen matriks hubungnya berbentuk

dimana O=matrik semua elemennya 0

A= matriks hubung komponen ke i bent bjr sangkar

Pohon (Tree)

Pohon merupakan salah satu kasus husus graf, dan ini banyak dipakai dalam struktur data

Definisi

Pohon adalah graf sederhana G bila G terhubung dan tdk memuat sirkuit

Pohon semu adalah pohon yg terdiri dari satu titik

Hutan adalah graf sederhana G bila tdk terhubung dan tidak memuat sirkuit

Contoh

Tentukan apakah graf G berikut poho atau hutan

a) c)

jawab merupakan hutan krn graft dk trhubung

Jawab merupakan pohon krn grafnya terhubung dan tdk ada sirkuit

Jawab bukan merupakan pohon karena ada sirkuit

Definisi

Daun (terminal vertex)adalah pohon T yg mempunyai derajat 1

Cabang (interval vertek) adalah pohon T yg mempunyai derajat lebih besar 1

Contoh

Tentukan daun dan cabang pada pohon T berikut

jawab mencari derajat masing masing titik dalam pohon T

d(v₁)=2; d(v₃)=2 ; d(v₃)=3

d(v₄)=1; d(v₅)=1; d(v₆)=1; d(v₇)=1 ; d(v₈)=1 d(v₁)=2

berarti daunnya adalah v_4,v_5,v₆ v₇v₈

titik cabangnya adalah v₁ ,v₂ ,v₃

Teorema : Pohon T dg n titik akan memiliki (n-1) garis

Misal T’ adalah pohon sprti T tetapi titik dan garisnya masing2 dikurangi 1

P(k) adalah pohon dg k titik berarti ada k-1 garis

Jumlah garis dalam T = jumlah garis dalam T’ + 1

= (k-1) + 1 = k

Jadi terbukti pohon Tadl pohon dg (k+1) titik memiliki k garis

Pohon Berakar dan Pohon Biner

Definisi

Pohon Berakar adalah suatu pohon dimana ada suatu titik dihususkan dari yg lain, titik husus itu disebut akar.

Tingkat suatu titik adalah banyaknya grs antara titik tersebut dg akar

Tinggi pohon adalah tingkat maksimum yg dimiliki titik-titik pada pohon

Anak dari titik v adalah semua titik yg berhubungan langsung dg titik v ttp yg memiliki tingkat yg lebih tinggi dari v, sedangkan v disebut orang tua

Dua titik memiliki orang tua yg sama disebut saudara(sibling).

Contoh

Perhatikan graf G berikut jawab

Dg v₂ sbg akar a) tingkat v₄adl jml grs antara v₄dg akar =1

Tentukan tingkat v₁=tingkat v₆=tingkat v₅=1

tingkat v₃= 2, tingkat v₇=tingkat v₈=3

a) Tingkat tiap-tiap titik b)tinggi pohon(ttk terjauh dari akar) adl 3

b) Tinggi pohon

c) Anak, orang tua, saudara v₁. c)anak v₁ adalah v₃, orang tua v₁adl v₂

d) Pertanyaan a,b, c untuk akarnya v₁saudara v₁adl v₄, v₅,dan v₆

Definisi Pohon Biner

Pohon biner adl pohon berakar yg setiap titiknya memiliki paling banyak 2 anak

Pohon biner penuh adl pohon biner yg setiap titiknya memiliki 2 anak

Dapat digunakan untuk menyatakan ekspresi aljabar dal pohon biner dg cara sbb

Contoh

Ekspresi aljabar x/y kalau dibuat bentuk pohon biner adalah

Contoh

Nyatakan ekspresi aljabar berikut dalam pohon biner

Pohon Rentang
merupakan salah satu bentuk husus dari pohon

Definisi

Pohon rentang suatu graf terhubung G adl subgraf G yg merupakan pohon dan memuat semua titik dalam G

Dari definisi dapat dijelaskan bahwa garisnya bisa ada yg dihapus agar menjadi pohon, tetapi jika tidak ada sirkuit berarti graf G itu sendiri langsung menjadi pohon rentang

Suatu graf bisa memiliki pohon rentang yg berbeda tetapi yg jelas dari pohon rentang tsb memiliki jumlah garis yg sama yaitu (k-1) dimana k adalah jumlah titik pada graf.

Contoh diketahui graf berikut , buatlah pohon rentangnya

Jawab

Caranya menghilangkan garisnya satu persatu agar tidak ada sirkutnya ..

GRAF BERLABEL

Adalah graf yg setiap sisinya diberi bobot, Misal: bobot sisinya tentang jarak, biaya, waktu antar 2 kota, waktu tempuh pesan antar simpul komunikasi (dlm jaringan komputer) dsb.

contoh

Dalam suatu propinsi ada 8 kota (A,B,C,D,E,F,G,H)yg akan dihubungkan dg jaringan listrik yg mungkin dibuat antar dua kota sbb

garis	Kota yang dihubungkan	Biaya per satuan
e₄ e₄ e₄ e₄ e₄ e₄ e₄ e₄ e₄ e₄ e₄	B ke C D ke F A ke G C ke D C ke E A ke B A ke D F ke H G ke H E ke F F ke G	3 4 5 5 5 15 15 15 15 15 18

a) Nyatan masalah tsb dalam graf berlabel

b) Buatlah matriks hubungnya

LINTASAN MINIMUM

Lintasa minimum dipilih dari simpul tertentu kesemua simpul yg lain.

Algoritma Dijktra

Misal: ada n buah simpul

dg matrik ketetanggan M = [ m _ij] dimana m _ij= bobot sisi (i,j) pd graf tak berarah m _ij= m_ji,,m_ii=0, dan m _ij= θ

Larik S = [si ] dimana si=1 temasuk lintasan terpendek

si=0 tdk masuk lin. Terpendek

larik/tabel D=[di] dimana di=panjang lin dr awal s ke simp. i

Langkah-langkah mencari lintasan terpendek

#Langkah 0 (inisialisasi)

-Inisialisasi s_i=0 dan d_i=m_ai,unt. i=1,2,…..n nilai a sdh ada, untu mengisi baris selanjutnya

# langkah 1:

- isikan s_a=1(krn simpul a adl simpul asal jadi sdh pasti terpilih)

- isikan d_a=∞(tdk ada path terpendek dari a ke a )

Langkah 2,3,…(n-1)

- cari j sedemikian hingga s_j=0 dan d_j=min{ d₁,……d_n} didapat kolom yg diinginkan

- isi s_j dgn 1 untuk mengisi baris selanjutnya

- perbarui d_i, unt. i=1,2,3,….n dgn ketentuan sbb

d_i(baru)=min{d_i(lama),d_j+m_ji} nilai j sudah tertentu(ada)

contoh

Diketahui graf berarah yg menyatakan jarak antar kota di pulau jawa sbb

B C

A G Tentukan path minimumnya

A B C D E F G H

jawab .

matriks hubungnya sbb

Simpul awal E, dengan tabulasi berikut

pilih lintasan S D

Simpul 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8

- - 0 0 0 0 0 0 0 0 - - - 1500 0 250 - -

5 5 0 0 0 0 1 0 0 0 - - - 1500 - 250 - -

6 5, 6, 0 0 0 0 1 1 0 0 - - - 250+1000 - 250 250+900 250+1400

7 5, 6, 7 0 0 0 0 1 1 1 0 - - - 1250 - 250 1150 1650

4 5, 6, 4 0 0 0 1 1 1 1 0 - - 1250+1200 1250 - 250 1150 1650

8 5, 6, 8 0 0 0 1 1 1 1 1 1650+1700 - 2450 1250 - 250 1150 1650

3 5, 6, 4, 3 0 0 1 1 1 1 1 1 3350 2450+800 2450 1250 - 250 1150 1650

2 5, 6, 4, 3, 2 0 1 1 1 1 1 1 1 3350 3250 2450 1250 - 250 1150 1650

1 5, 6, 8 , 1 1 1 1 1 1 1 1 1 3350 3250 2450 1250 - 250 1150 1650

Jadi path minimum dari

5 ke 6 adalah 5, 6 dengan panjang 250

5 ke 7 adalah 5, 6, 7 dengan panjang 1150

5 ke 4 adalah 5, 6, 4 dengan panjang 1250

5 ke 8 adalah 5, 6, 8 dengan panjang 1650

5 ke 3 adalah 5, 6, 4, 3 dengan panjang 2450

5 ke 2 adalah 5, 6, 4, 3, 2 dengan panjang 3250

5 ke 1 adalah 5, 6, 8, 1 dengan panjang 3350

MARI BELAJAR

Senin, 19 November 2012

GRAF

Tidak ada komentar:

Posting Komentar

Mengenai Saya