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
Contoh :
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
Contoh :
3. Senarai Ketetanggaan (adjacency list)
GRAF
A. Graf
Isomorfik
Diketahui
matriks ketetanggaan ( adjacency matrices ) dari sebuah graf tidak berarah.
Gambarkan dua buah graf yang yang bersesuaian dengan matriks tersebut.
Penyelesaian :
Dua buah graf yang
sama (hanya penggambaran secara geometri berbeda) isomorfik
Graf Isomorfik
mempunyai ciri sebagai berikut :
a.
Dua buah graf yang
sama tetapi secara geometri berbeda disebut graf yang saling isomorfik.
b.
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.
c.
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.
d.
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.
Gambar G1 isomorfik dengan G2, tetapi G1 tidak isomorfik dengan G3.
Gambar Graf (a) dan graf (b) isomorfik [DEO74]
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.
Materi Lainnya :
1. Definisi Graf-graf Bipartite :
http://maysarahhmay.blogspot.com/2018/12/matdis-graf.html
2. Graf Planar - Lintasan Euler
https://cucusulaiman.blogspot.com/2018/12/graf-planar-planar-graph-dan-grafbidang.html
3. Lintasan Hamilton - Pewarnaan Graf
https://yayadidiyadi.blogspot.com/2018/12/ti-politala-matdis-1c_11.html
SUMBER :
Tidak ada komentar:
Posting Komentar