2. graf tak-berarah

2. GRAF TAK-BERARAH ( Rusmadji )

DEFINISI – DEFINISI (1)

Order n dari graf G adalah banyaknya titik yang ada di G yaitu n.

Graf yang mempunyai order terbatas dinamakan graf hingga.

Dalam suatu graf G, apabila suatu titik v dihubungkan dengan dirinya sendiri atau e = vv, maka sisi e dinamakan loop.

Jika terdapat lebih dari satu sisi yang menghubungkan dua titik, maka sisi-sisi tersebut dinamakan sisi rangkap (multiple edges).

Graf yang tidak memuat loop dan sisi rangkap dinamakan graf sederhana (simple graf).


• Jika dua titik v1 dan v2 di graf G dihubungkan oleh suatu sisi e, maka titik v1 dan v2

dikatakan adjacent (tetangga) dan sisi e insiden dengan kedua titik yang

dihubungkan.

Pada Gambar: titik-titik yang adjacent adalah v1 dan

v2, v2 dan v3, v3 dan v4, v4 dan v1, v1 dan v3.

Sedangkan sisi e1 insiden dengan v1 dan v2,

e2 insiden dengan v2 dan v3,



dan e5 insiden dengan v1 dan v3.

Derajat (degree) dari titik v adalah jumlah sisi yang berinsiden

dengan titik v, dinotasikan dengan deg (v).

Pada gambar di atas deg (v1) = deg (v3) = 3 dan deg (v2) =

deg (v4) = 2.

Jika setiap titik dalam suatu graf G mempunyai derajat yang

sama, maka graf tersebut dinamakan graf reguler. Contoh

pada gambar di samping.


• Jalan (walk) W pada graf G adalah barisan berhingga titik berhubungan dengan garis berselang-seling yang diawali dan diakhiri dengan titik, yaitu:

W = v0, e1, v1, e2, v2, e3, . . ., vn-1, en, vn (n 0)

• Lintasan (path) adalah walk yang barisan sisi-sisinya tidak ada pengulangan

Path sederhana merupakan path yang titik-titiknya tidak ada pengulangan.

• Sirkuit / Sikel (cycle) didefinisikan sebagai suatu lintasan yang tertutup (dimulai dan diakhiri titik yang sama.

Sirkuit sederhana adalah sirkuit yang titik-titiknya berbeda.

Jalan (Walk) : v1, e1, v2, e7, v4, e6, v1, e5, v5, e4, v4, e3, v3

Lintasan (Path) : v1, e1, v2, e2, v3, e3, v4, e4, v5.

Sirkuit / Sikel : v5, e5, v1, e6, v4, e7, v2, e2, v3, e3, v4, e4, v5

Sirkuit sederhana : v5, e5, v1, e6, v4, e4, v5

SUBGRAF

Graf G1 dikatakan subgraf dari graf G jika setiap titik di G1 adalah titik di G dan setiap sisi di G1 adalah sisi di G. Dengan kata lain V(G1) V(G) dan E(G1) E(G).

Pada Gambar berikut, G1 adalah subgraf dari G tetapi G2 bukan subgraf dari G karena ada sisi v2v3 di G2 yang bukan merupakan elemen dari E(G).

GRAF TERHUBUNG dan TAK TERHUBUNG

Graf G dikatakan terhubung bila dan hanya bila setiap 2 titik dalam G terhubung.

Graf G dikatakan tak terhubung bila dan hanya bila ada 2 titik dalam G yang tidak terhubung.

Graf terhubung dan graf tak terhubung

GABUNGAN GRAF

Misalkan ada dua graf G1 dan G2, dimana himpunan titik V(G1) dan himpunan titik V(G2) saling asing, begitu juga himpunan sisi E(G1) dan himpunan sisi E(G2).

Gabungan dari G1 dan G2 dinotasikan dengan G1 G2, adalah graf dengan himpunan titik V(G1 G2) = V(G1) V(G2) dan himpunan sisi E(G1 G2) = E(G1) E(G2).

Gabungan graf

Komplemen dari Graf G, dinotasikan dengan , adalah graf sederhana dengan himpunan titik yang sama dengan himpunan titik di G, dengan kata lain , dan titik u,v di G adalah adjacent jika dan hanya jika titik u,v di G tidak adjacent.

KOMPLEMEN GRAF

KELAS-KELAS GRAF (1)

Graf terbagi dalam beberapa kelas yaitu graf path (lintasan), graf cycle (sikel), graf complete (lengkap) dan graf n-partit.

1. Graf Path (lintasan)

Graf path (lintasan) ialah graf yang terdiri dari satu lintasan. Graf

lintasan dengan n titik, dinotasikan dengan Pn .


2. Graf cycle (sikel)

Graf cycle (sikel) ialah graf yang terdiri dari satu sikel. Graf sikel dengan n titik, dinotasikan dengan Cn. Pada graf sikel, jumlah titiknya minimal 3.


3. Graf Complete (lengkap)

Graf complete (lengkap) didefinisikan sebagai graf dimana setiap dua titik berbeda di G dihubungkan dengan sisi. Graf lengkap dengan n titik dinotasikan dengan Kn.

4. Graf n – partit

Graf n - partit didefinisikan sebagai graf dimana himpunan titik V(G) dapat dipisah menjadi n himpunan titik, yaitu V1(G), V2(G), …, Vn(G). Sisi-sisi pada graf n-partit terhubung dari titik-titik pada Vi(G) ke titik-titik .

Untuk n = 2, dinamakan graf bipartit. Jika |V1| = k dan |V2| = l, maka graf bipartit tersebut dinotasikan dengan Bk,l . Sedangkan untuk n = 3, dinamakan graf tripatit, yang dinotasikan dengan Tk,l,m


Contoh :

SIRKUIT EULER

Permasalahan :

Mr. Euler akan jalan-jalan yang dimulai dari suatu kota dan singgah di setiap

kota yang ada kemudian kembali ke kota semula dengan melintasi ke tujuh

jembatan masing-masing tepat satu kali. MUNGKINKAH ?

7 jembatan Konigsberg

SIRKUIT EULER :

Definisi :

Sirkuit Euler graf G adalah sirkuit dimana

setiap titik dalam G dilewati paling sedikit

sekali dan setiap garis dalam G dilewati

tepat sekali.

Misalkan G adalah graf terhubung.

G adalah sirkuit Euler bila dan hanya

bila semua titik dalam G memiliki

derajat genap.

e3

A

B

C

D

EF

e2

e4 e5

e6

e7

e8

e9

e1

SIRKUIT HAMILTON :

Definisi :

Sirkuit Hamilton graf G adalah

sirkuit dimana setiap titik dalam G

dilewati sekali dan tidak harus

melewati semua garis.

Jika G merupakan sirkuit Hamilton, maka G memiliki subgraf H dengan

sifat-sifat sebagai berikut:

1. H terhubung

2. H memuat semua titik G

3. H memiliki jumlah garis yang sama dengan jumlah titiknya

4. Setiap titik dalam H memiliki derajat 2.

Tidak berlaku sebaliknya.

Jika salah satu dari ke-4 syarat tersebut tidak dipenuhi, maka grafnya bukan

Sirkuit Hamilton.

Contoh : Diketahui sirkuit Hamilton pada graf

G di bawah ini. Tunjukkan bahwa

graf tersebut mempunyai subgraf H

yang mempunyai empat sifat seperti

di atas !

a b

cde

f g

Contoh : Buktikan bahwa graf berikut bukan

sirkuit Hamilton !

ISOMORFISME

Definisi :

Misalkan G1 adalah suatu graf dengan himpunan titik V(G1) dan

himpunan garis E(G1). Graf G2 adalah suatu graf dengan himpunan titik

V(G2) dan himpunan garis E(G2).

G1 isomorfis dengan G2 jika dan hanya jika ada korespodensi satu-satu

g:V(G1) V(G2)

h:E(G1) E(G2)

sedemikian hingga ( u, w V(G1) dan e E(G1) u dan w adalah titik-

titik ujung e g(u) dan g(w) adalah titik-titik ujiung h(e).

Contoh :

Tunjukkan bahwa graf G1 dan G2 di bawah ini adalah isomorfis !

e1

e2

e3

e4

e5

e1

e2

e3

e4

e5

h

G1 G2

Bukti :

v1

v2

v3

v4

v5

v1

v2

v3

v4

v5

g

Pembuktian di bawah ini apakah benar ?

Hingga sekarang belum ada teori yang dapat dipakai untuk menentukan

apakah dua graf G1 dan G2 isomorfis. Akan tetapi, jika G1 dan G2 isomorfis,

maka terdapat beberapa hal yang pasti dipenuhi:

1. jumlah titik G1 = jumlah titik G2

2. jumlah garis G1 = jumlah garis G2

3. jumlah garis dengan derajat tertentu dalam G1 dan G2 sama.

Tidak berlaku sebaliknya.

Jika salah satu dari ketiga syarat tidak dipenuhi, maka G1 dan G2 tidak

isomorfis.

2. graf tak-berarah

Documents