ASAL USUL DAN PENJELASAN MUDAH DIPAHAMI REPRESENTASI GRAF PPT \ REPRESENTASI GRAF PPT

SILAHKAN DOWNLOAD DISINI FILE PPT ASLINYA

Rinaldi M/IF2091 Strukdis 1
Representasi Graf
1. Matriks Ketetanggaan (adjacency matrix)
A = [aij],
1, jika simpul i dan j bertetangga
aij = {
0, jika simpul i dan j tidak bertetangga
Rinaldi M/IF2091 Strukdis 2
Contoh:
1 2 3 4
1 2 3 4 5
1 2 3 4
4
3
2
1






ASAL USUL DAN PENJELASAN MUDAH DIPAHAMI REPREDENTASI GRAF PPT \ REPRESENTASI GRAF PPT








0 1 1 0
1 1 0 1
1 0 1 1
0 1 1 0
















0 0 0 0 0
0 0 1 0 0
1 1 0 1 0
1 0 1 0 0
0 1 1 0 0
5
4
3
2
1
4
3
2
1




ASAL USUL DAN PENJELASAN MUDAH DIPAHAMI REPREDENTASI GRAF PPT \ REPRESENTASI GRAF PPT










0 1 1 0
1 0 0 0
1 0 1 1
0 1 0 0
(a) (b) (c)

1 2 3 4

4
3
2
1












0 1 2 0
2 1 1 2
1 0 1 1
0 1 2 0
1
3
2
4
1
2
3
4
5
1
2 3
4
1
2
4
3
e1
e2
e3
e4
e5
e6
e7
e8
Rinaldi M/IF2091 Strukdis 3
Derajat tiap simpul i:
(a) Untuk graf tak-berarah
d(vi
) = =
n
j
aij
1
(b) Untuk graf berarah,
din (vj
) = jumlah nilai pada kolom j = =
n
i
aij
1

dout (vi
) = jumlah nilai pada baris i = =
n
j
aij
1
Rinaldi M/IF2091 Strukdis 4


ASAL USUL DAN PENJELASAN MUDAH DIPAHAMI REPREDENTASI GRAF PPT \ REPRESENTASI GRAF PPT


a b c d e
















 
 
  

  
10 8 15
11 14 15
9 14
12 9 11 8
12 10
e
d
c
b
a
a
b
d c
e
10 12
8
15 9
11
14
Rinaldi M/IF2091 Strukdis 5
2. Matriks Bersisian (incidency matrix)
A = [aij],
1, jika simpul i bersisian dengan sisi j
aij = {
0, jika simpul i tidak bersisian dengan sisi j
e1 e2 e3 e4 e5
4
3
2
1












0 0 0 0 1
0 0 1 1 1
1 1 1 0 0
1 1 0 1 0
1 2
3
4
e1
e2
e3
e4
e5
Rinaldi M/IF2091 Strukdis 6
3. Senarai Ketetanggaan (adjacency list)
Simpul Simpul Tetangga Simpul Simpul Tetangga Simpul Simpul Terminal
1 2, 3 1 2, 3 1 2
2 1, 3, 4 2 1, 3 2 1, 3, 4
3 1, 2, 4 3 1, 2, 4 3 1
4 2, 3 4 3 4 2, 3

ASAL USUL DAN PENJELASAN MUDAH DIPAHAMI REPREDENTASI GRAF PPT \ REPRESENTASI GRAF PPT

5 -
(a) (b) (c)
1
3
2
4
1
2
3
4
5
1
2 3
4
Rinaldi M/IF2091 Strukdis 7
Graf Isomorfik
Diketahui matriks ketetanggaan (adjacency
matrices) dari sebuah graf tidak berarah.
Gambarkan dua buah graf yang yang
bersesuaian dengan matriks tersebut.
















1 1 0 1 0
0 1 1 0 1
0 1 1 1 0
1 0 1 1 1
0 1 0 0 1
Rinaldi M/IF2091 Strukdis 8
Jawaban:
Dua buah graf yang sama (hanya
penggambaran secara geometri berbeda)
→ isomorfik!
1
1
2 3
3
5 4
5 4
2
Rinaldi M/IF2091 Strukdis 9
Graf Isomorfik
• Dua buah graf yang sama tetapi secara geometri berbeda disebut graf
yang saling isomorfik.
• Dua buah graf, G1 dan G2 dikatakan isomorfik jika terdapat
korespondensi satu-satu antara simpul-simpul keduanya dan antara sisisisi keduaya sedemikian sehingga hubungan kebersisian tetap terjaga.
• Dengan kata lain, misalkan sisi e bersisian dengan simpul u dan v di G1,
maka sisi e’ yang berkoresponden di G2 harus bersisian dengan simpul u’
dan v’ yang di G2.
• Dua buah graf yang isomorfik adalah graf yang sama, kecuali penamaan
simpul dan sisinya saja yang berbeda. Ini benar karena sebuah graf dapat
digambarkan dalam banyak cara.
Rinaldi M/IF2091 Strukdis 10 (a) G1 (b) G2 (c) G3
Gambar 6.35 G1 isomorfik dengan G2, tetapi G1 tidak isomorfik dengan G3
3
4
1 2
d c
a b
v w
x y
Rinaldi M/IF2091 Strukdis 11
(a) G1 (b) G2
Gambar 6.36 Graf (a) dan graf (b) isomorfik [DEO74]

a b c d e

x y w v z
AG1 =
e
d
c
b

ASAL USUL DAN PENJELASAN MUDAH DIPAHAMI REPREDENTASI GRAF PPT \ REPRESENTASI GRAF PPT

a
















0 0 0 1 0
1 0 1 0 1
1 1 0 1 0
1 0 1 0 0
0 1 1 1 0
AG2 =
z
v
w
y
x
















0 0 0 1 0
1 0 1 0 1
1 1 0 1 0
1 0 1 0 0
0 1 1 1 0
z
d
c
a
b
e
x
v w
y
Rinaldi M/IF2091 Strukdis 12
(a)
(b)
Gambar 6.38 (a) Dua buah graf isomorfik, (b) tiga buah graf isomorfik
Rinaldi M/IF2091 Strukdis 13
Dari definisi graf isomorfik dapat dikemukakan bahwa dua buah graf
isomorfik memenuhi ketiga syarat berikut [DEO74]:
1. Mempunyai jumlah simpul yang sama.
2. Mempunyai jumlah sisi yang sama
3. Mempunyai jumlah simpul yang sama berderajat tertentu
Namun, ketiga syarat ini ternyata belum cukup menjamin. Pemeriksaan
secara visual perlu dilakukan.
(a) (b)
x
u
v
w
y
Rinaldi M/IF2091 Strukdis 14
Latihan
Apakah pasangan graf di bawah ini

ASAL USUL DAN PENJELASAN MUDAH DIPAHAMI REPREDENTASI GRAF PPT \ REPRESENTASI GRAF PPT

isomorfik?
a
b
c
d
e
f
g
h u
v
w
t
p
q
r
s
Rinaldi M/IF2091 Strukdis 15
Latihan
Apakah pasangan graf di bawah ini
isomorfik?
a b
d c
e f
p q
s r
t
u
Rinaldi M/IF2091 Strukdis 16

ASAL USUL DAN PENJELASAN MUDAH DIPAHAMI REPREDENTASI GRAF PPT \ REPRESENTASI GRAF PPT

Latihan
Gambarkan 2 buah graf yang isomorfik
dengan graf teratur berderajat 3 yang
mempunyai 8 buah simpul
Rinaldi M/IF2091 Strukdis 17
Jawaban:

Tweet

Postingan terkait:

— Sunday, May 31, 2020 — Add Comment — matematika