Pertemuan_9_REPRESENTASI_GRAF_Isomorfik_planar_bidang[1].pdf

math disk

1. MATEMATIKA DISKRIT
PERTEMUAN 9
1.REPRESENTASI GRAF
2.GRAF ISOMORFIK
3.GRAF PLANAR DAN GRAF BIDANG

2. REPRESENTASI GRAF
1. MatriksKetetanggaan(adjacency matrix)
A = [aij],
1, jikasimpulidan j bertetangga
aij= {
0, jikasimpulidan j tidakbertetangga

3. REPRESENTASI GRAF

4. REPRESENTASI GRAF
2. MatriksBersisian(incidencymatrix)
A = [aij],
1, jikasimpulibersisiandengansisij
aij= {
0, jikasimpulitidakbersisiandengansisij

5. REPRESENTASI GRAF
3. SenaraiKetetanggaan(adjacency list)

6. GRAF ISOMORFIK
Diketahuimatriksketetanggaan(adjacency matrices) darisebuahgraftidakberarah.
Gambarkandua buahgrafyang yangbersesuaiandenganmatrikstersebut.

7. REPRESENTASI GRAF
Jawaban:
Dua buahgrafyang sama(hanyapenggambaransecarageometriberbeda) →isomorfik!

8. GRAF ISOMORFIK
•Dua buahgrafyang samatetapisecarageometriberbedadisebutgrafyang salingisomorfik.
• Dua buahgraf, G1 dan G2 dikatakanisomorfikjikaterdapatkorespondensisatu-satuantara
simpul-simpulkeduanyadan antarasisi-sisikeduayasedemikiansehinggahubungankebersisian
tetapterjaga.
• Dengankata lain, misalkansisie bersisiandengansimpulu dan v di G1, makasisie’ yang
berkorespondendi G2 harusbersisiandengansimpulu’ dan v’ yang di G2.
• Dua buahgrafyang isomorfikadalahgrafyang sama, kecualipenamaansimpuldan sisinyasaja
yang berbeda. Ini benarkarenasebuahgrafdapatdigambarkandalambanyakcara
G1 isomorfikdenganG2, tetatiG1 tidakisomorfikdenganG3

9. GRAF ISOMORFIK

10. GRAF ISOMORFIK

11. GRAF ISOMORFIK
Dari definisigrafisomorfikdapatdikemukakanbahwadua buahgrafisomorfikmemenuhiketigasyarat
berikut:
1. Mempunyaijumlahsimpulyang sama.
2. Mempunyaijumlahsisiyang sama
3. Mempunyaijumlahsimpulyang samaberderajattertentu
Namun, ketigasyaratiniternyatabelumcukupmenjamin. Pemeriksaansecaravisual perludilakukan.

12. LATIHAN
1. Apakahpasangangrafdi bawahiniisomorfik?

13. LATIHAN
2. Apakahpasangangrafdi bawahiniisomorfik?
3. Gambarkan2 buahgrafyang isomorfikdengangrafteraturberderajat3 yang mempunyai8 buah
simpul

14. GRAF PLANAR DAN GRAF BIDANG
Graf yang dapatdigambarkanpada bidangdatardengansisi-sisitidaksalingmemotong
(bersilangan) disebutgrafplanar, jikatidak, makaiadisebutgraftak-planar.
K4 adalahgrafplanar:

15. GRAF PLANAR DAN GRAF BIDANG
K5 adalahgraftidakplanar:

16. GRAF BIDANG
Graf planar yang digambarkandengansisi-sisiyang tidaksalingberpotongandisebutgrafbidang
(plane graph).
Tiga buahgrafplanar. Graf (b) dan (c) adalahgrafbidang

17. LATIHAN
Gambarkan graf di bawah ini sehingga tidak ada sisi-sisi yang berpotongan (menjadi
graf bidang).

18. TERIMAKASIH