tugas1teorigraf

8/18/2019 Tugas1TEORIGRAF

1/6

Nama : Jonathan Hans S.NIM : H13114320 TUGAS 1 TEORI GRAF


2/6

1. Definisi Isomorfis Graf

Dua graf disebut isomorfis jika keduanya menunjukkan "bentuk" yang sama,

kedua graph tersebut hanya berbeda dalam hal pemberian label titik dan garisnya saja.

Dua 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’ .

Syarat dua buah graph dikatakan isomorfik, yaitu :

1. Memiliki jumlah titik yang sama

2. umlah sisi yang sama

!. Memiliki derajat yang sama dari titik-titiknya

atatan : apabila dua graph yang berbeda tidak memiliki salah satu dari syarat

diatas sudah pasti kedua graph tersebut tidak isomorfis, tetapi #alaupun kedua graph

tersebut memiliki seluruh syarat diatas belum tentu juga keduanya isomorfis.

$ntuk itu ada beberapa syarat tambahan yang #ajib kita penuhi apabila ingin

menunjukkan apakah kedua graph tersebut isomorfik atau tidak, yaitu :

1. %raf sederhana %1 & '(1, )1* dan %2 & '(2, )2* adalah isomorfis jika ada sebuah

fungsi bijektif 'fungsi satu-ke-satu dan on to* dari (1 ke (2 dengan sifat

kepemilikan bah#a jika a dan b adalah tetangga pada %1 jika dan hanya jika f'a*

dan f'b* adalah tetangga di %2, untuk seluruh a dan b di (1.

2. Misalkan sisi e bersisian dengan simpul u dan + di % 1, maka sisi e yang

berkoresponden di %2 harus bersisian dengan simpul u dan + yang di %2.

!. %1 dan %2 adalah isomorfis jika simpul-simpulnya dapat diurut dengan ara

sedemikian rupa sehingga matriks ketetanggan M%1 dan M%2 adalah identik.

gar lebih mudah memahami apakah dua graf isomorfik atau tidak, berikut

adalah ontoh ara menunjukan dua graf yang isomorfik.

2. Contoh Graf Isomorfis


3/6

/edua graf tersebut adalah isomorfik. 0erlihat graf tersebut memuat simpul

dimana setiap simpulnya masing-masing berderajat dua.

3. Contoh Graf Tidak Isomorfis

da 2 graf yang memenuhi ketiga syarat tersebut, tetapi keduanya tidak isomorfis.

Sebagai ontoh adalah graf % dan % pada %ambar di ba#ah ini :

Dalam %, satu-satunya titik yang berderajat ! adalah titik . 0itik

dihubungkan dengan 2 titik lain yang berderajat 1 'titik y dan 3*. Sebaliknya, dalam

%, satu-satunya titik yang berderajat ! adalah . Satu-satunya titik berderajat 1 yang

dihubungkan dengan hanyalah titik d, sehingga % tidak mungkin isomorfis dengan

%.

4. Definisi Matriks Ketetanggaan


4/6

Matriks ketetangaaan A'G* & 'aij* dari suatu graf berlabel G dengan n titik

adalah matriks berukuran nn, dengan

14 jikaυ

i bertetangga denganυ

j

ai , j

54 untuk lainnya

ontoh ! :

% &

Matriks ketetanggaan dari % adalah :

1

2

3

4

5

1

[

0

1

0

0

0

2

1

0

1

0

0

3

0

1

0

1

1

4

0

0

1

0

1

5

0

0

1

1

0

]5. Definisi Matriks KeterkaitanMatriks keterkaitan 6 & ' bi , j * dari suatu graf berlabel dengan p titik simpul

dan 7 sisi, adalah matriks berukuran 7p, dengan

14 jika sisi ei bertetangga dengan υ j

bi , j

54 untuk lainnya

ontoh 8 :


5/6

% &

Matriks keterkaitan dari % adalah :

e1

e2

e3

e4

e5

1

[1

0

0

0

0

2

1

1

0

0

0

3

0

1

1

1

0

4

0

0

1

0

1

5

0

0

0

1

1

]6. Analisis Matriks

9ada ontoh graf isomof telah dijelaskan bah#a graf pada ontoh tersebut

adalah isomorfis. 6erdasarkan syarat khusus yang telah disebutkan diatas salah satu

syarat mengatakan bah#a graf yang isomorfis adalah graf yang titik-titiknya dapat

disusun sedemikian rupa sehingga dapat membentuk matriks ketetanggan yang

identik antar 1 dan 2.6erikut adalah pembuktian bah#a matriks ketetanggan dari 1 dan 2 dapat

dibuat menjadi identik.

1 2

simpul u1 dengan simpul v1







6/6

Matriks /etetanggan dari 1 dan 2

Y 1=

u1

u2u3

u4

u5

u6

u1

[0

0

0

1

1

1

u2

0

0

0

1

1

1

u3

0

0

0

1

1

1

u4

1

1

1

0

0

0

u5

1

1

1

0

0

0

u6

1

1

1

0

0

0]Y 2=

v1

v2v3

v4

v5

v6

v1

[0

1

0

1

0

1

v2

1

0

1

0

1

0

v3

0

1

0

1

0

1

v4

1

0

1

0

1

0

v5

0

1

0

1

0

1

v6

1

0

1

0

1

0]

9erhatikan perbedaan bentuk kedua matriks ketetanggan antara 1 dan 2.

ika bentuk kedua matriks tersebut seperti itu maka graf 1 dan 2 belum dapat

dikatakan isomorfis sehingga harus dilakukan sedikit perubahan pada susunan titiknya

sehingga matriks ketetanggan 1 dan 2 dapat identik. 6erikut adalah bentuk dari

matriks ketetanggan 2 setelah dilakukan perubahan.

Y 1=

v1

v2

v3

v4

v5

v6

v1

[0

1

0

1

0

1

v2

0

10

1

0

1

v3

0

10

1

0

1

v4

1

01

0

1

0

v5

1

01

0

1

0

v6

1

0

1

0

1

0 ]Y

2=

v1

v2

v3

v4

v5

v6

v1

[0

0

0

1

1

1

v2

0

00

1

1

1

v3

0

00

1

1

1

v4

1

11

0

0

0

v5

1

11

0

0

0

v6

1

1

1

0

0

0]/arena matriks ketetanggan dari 2 dapat disusun menjadi identik dengan

matriks ketetanggan 1 maka terbukti bah#a graf 1 dan 2 adalah isomorfis.

tugas1teorigraf

Documents