Download - 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).
DEFINISI – DEFINISI (2)
• 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,
e3 insiden dengan v3 dan v4,
e4 insiden dengan v4 dan v1,
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.
DEFINISI – DEFINISI (3)
• 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 .
KELAS-KELAS GRAF (2)
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.
KELAS-KELAS GRAF (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
KELAS-KELAS GRAF (4)
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.