graf berarah

OLEH: RIKAYANTI, S.PD

GRAF BERARAH

PATH BERARAH DAN SIRKUIT BERARAH GRAF BERARAH TERHUBUNG ISOMORFISMA DALAM GRAF BERARAH

GRAF BERARAH

GRAF BERARAH

DEFINISIGraf berarah (directed graph): graf yang sisinya memiliki orientasi arahNotasi G(V,E) terdiri dari himpunan titik V dan himpunan garis E yang merupakan himpunan pasangan berurutan (x,y)Arah dari garis (x,y) E ditunjukkan tanda panah pada garis tersebut.

Subgraf Berarah Definisi graf g dikatakan subraf G jika seluruh titik dan garisnya berada dalam G contoh:

LINTASAN (PATH) BERARAH

DEFINISIPath dari graf berarah G(V,E) adalah suatu subgraf berarah G(V,E) yang terdiri dari barisan titik dan garis v1 – e1 – v2 – e2 – ... – vr–1 – er–1 – vr tanpa pengulangan titik CatatanUntuk setiap 1 < k < r–1, ek = (vk,vk+1)E disebut garis maju dan ek = (vk+1 ,vk )E disebut garis balik

v1 = vr : path tertutup (cycle), v1 ≠ vr : path terbuka

Path yang tidak sesuai dengan arah ruas disebut semi path

Contoh path berarah Sub Graf (a) adalah path berarah 1-

(1,2)- 2-(2,5)-5-(5,7) sedang (b) bukan path karena verteks 2 dilalui 2 kali yaitu 1-(1,2)-2-(2,4)-4-(4,5)-5-(5,2)-2-(2,3)-3-(3,1)

Sirkuit (Cycle) Berarah

Definisi:Sirkuit yang arahnya sesuai dengan arah setiap garis dalam sirkuit.Sirkuit dari graf berarah G(V,E) adalah suatu subgraf berarah G(V,E) yang terdiri dari barisan titik dan garis v1 – e1 – v2 – e2 – ... – vr–

1 – er–1 – vr tanpa pengulangan titik dengan v1 = vr

Path berarah yang dimulai dan diakhiri pada titik yang sama.

Contoh sirkuit berarah

Sirkuit berarah

OPERASI PADA GRAF BERARAH

OPERASI GABUNGAN Gabungan dari dua grup graf G1 (V1,E1) dan G2 (V2,E2) yang ditulis G3 = G1 U G2 dengan himpunan titiknya V3 = V1UV2 dan himpunan garisnya E3 = E1UE2

OPERASI IRISANIrisan dari dua grup graf G1 (V1,E1) dan G2 (V2,E2) yang ditulis G4 = G1 G2 dengan himpunan titiknya V3 = V1 V2 dan himpunan garisnya E3 = E1 E2

Contoh operasi graf berarah

SIFAT OPERASI GRAF BERARAH

GRAF BERARAH TERHUBUNG

TIGA PENGERTIAN KETERHUBUNGAN a. Terhubung lemah ,jika terdapat

semipath antara 2 simpul dari Db. Terhubung unilateral, jika antara

setiap 2 simpul u dan v dari D, terdapat jalur dari u ke v atau dari v ke u

c. Terhubung kuat, jika antara 2 simpul u dan v dari D, terdapat jalur dari u ke v dan dari v ke u

Keterhubungan

Graf terhubung kuat dan lemah

Contoh graf tak terhubung

Contoh graf terhubung lemah dan terhubung kuat

GRAF ISOMORFIK (ISOMORPHIC GRAPH)

DEFINISIDua buah graf G1 dan G2 dikatakan isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul keduanya dan antara sisi-sisi keduanya sedemikian sehingga jika sisi e bersisian dengan simpul u dan v di G1 maka sisi e’ yang berkoresponden di G2 juga harus bersisian dengan simpul u’ dan v’ di G2

Graf Isomorfik (Isomorphic Graph)

Contoh graf isomorfik tak berarah

G1 isomorfik dengan G2, tetapi G1 tidak isomorfik dengan G3

Contoh graf isomorfik

Graf berarah yang saling isomorfik

Soal latihan

Graf berarahTerangkan secara formal graf berarah berikut ini :A. B.

Graf Berarah

Gambarkan diagram untuk setiap graf berarah G berikut dimana V(G) = {A,B,C,D,E} dan:

a. E(G)={[A,B],[A,C],[B,C],[B,D],[C,C],[D,B]}

b. E(G)={[A,D],[B,C],[C,E],[D,B],[D,D],[D,E],[E,A]}

SUBGRAF BERARAH

Gambarkan subgraf yang dibangun oleh a. V’={v1,v4,v5,v8}

b. V’={v1,v2,v3,v7,v8}

v1 v2 v3 v4

v5 v6 v7 v8

Subgraf berarah

Perhatikan digraf G(V,E) dengan V={v1,v2,v3,v4,v5,v6} dan E={[v1,v3],[v2,v1],[v2,v3],[v2,v4],[v3,v2],[v3,v4], [v3,v5],[v4,v6],[v5,v5],[v5,v4],[v6,v2]}

gambarkan diagram dari subgraf yang dibangun oleh:a. V’={v1,v2,v3,v4}b. V’={v2,v3,v4,v5}

Path dan Sirkuit berarah Perhatikan graf berarah berikut ini:

v1 v2

v3 v4

v5 v6

a. Tentukan 2 path dari v1 ke v6, 2 path sederhana dari v1 ke v6

b. Tentukan sirkuit yang memuat v3, sirkuit yang memuat v4