Graph Lintasan dan Sirkuit

Graph Planar

 

Teori Graph Isomorfik

Graph Isomorfik (Isomorphic Graph)

• Dua buah graph yang sama tetapi secara geometri berbeda disebut graph yang saling isomorfik.

• Dua buah graph, G1 dan G2 dikatakan isomorfik jika terdapat korespondensi satu-satu antara simpul-simpul keduanya dan antara sisi-sisikeduaya sedemikian sehingga hubungan kebersisian tetap terjaga.

Graph Isomorfik (Isomorphic Graph)

• 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 graph yang isomorfik adalah graph yang sama, kecuali penamaan simpul dan sisinya saja yang berbeda. Ini benar karena sebuah graph dapat digambarkan dalam banyak cara.

Graph Isomorfik (Isomorphic Graph)
Dari definisi graph isomorfik dapat dikemukakan bahwa dua buah graph 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

PENDAHULUAN

Pendahuluan 

Permasalahan yang muncul di dunia nyata sering terkait dengan objek diskrit dan relasi antarobjek tersebut. Sebagai contoh: ada beberapa kota dalam suatu propinsi, dan ada jalan yangmenghubungkan dar suatu kota ke kota lain. Hal ini kota merupakan objek diskrit, sedangkan jalan merelasikan antar satu objek ke objek lainnya. Contoh lainnya, dalam sistem jaringankomputer terdiri dari objek-objek computer baik sebagai

server 

maupun

workstation.

Disini kitabisa mencari apakah satu komputer dapat terhubung ke komputer lainnya.Permasalahan-permasalahan seperti ini dapat dimodelkan secara baik dengan menggunakankonsep, graf, graf berarah, pohon, maupun pohon biner. Dalam bab ini kita akan membahastentang konsep dasar graf, contoh-contoh pemakaian dalam kehidupan sehari-hari, danbagaimana mengimplementasikan graf dalam pemrograman komputer.

Tujuan Instruksional Umum 

Mahasiswa mengerti konsep graf, macam-macam graf, dan dapat menerapkan dalam kehidupansehari-hari.

Tujuan Instruksional Khusus 

Mahasiswa diharapkan dapat: 

 

1.Memahami definisi graf tak berarah dan graf berarah, dan dapat mengaitkannya dalampermasalahan sehari-hari.

 

2.Memahami pengertian lintasan dan sirkuit dalam graf tak berarah dan graf berarah.

 

3.Memahami pengertian Sikuit Euler Dan Hamilton dan penerapannya.

 

4.Mampu menyelesaikan Permasalahan Perjalanan Penjual.

 

5.Memahami definisi dan dapat mengenali Graf Isomophic

 

http://www.scribd.com/doc/25489300/Teori-Graf

Pengertian Teori Graph

Dalam matematika dan ilmu komputer, teori graf adalah cabang kajian yang mempelajari sifat-sifat graf. Secara informal, suatu graf adalah himpunan benda-benda yang disebut simpul (vertex atau node) yang terhubung oleh sisi (edge) atau busur (arc). Biasanya graf digambarkan sebagai kumpulan titik-titik (melambangkan simpul) yang dihubungkan oleh garis-garis (melambangkan sisi) atau garis berpanah (melambangkan busur). Suatu sisi dapat menghubungkan suatu simpul dengan simpul yang sama. Sisi yang demikian dinamakan gelang (loop).
Banyak sekali struktur yang bisa direpresentasikan dengan graf, dan banyak masalah yang bisa diselesaikan dengan bantuan graf. Jaringan persahabatan pada Friendster bisa direpresentasikan dengan graf: simpul-simpulnya adalah para pemakai Friendster dan ada sisi antara A dan B jika dan hanya jika A berteman (berkoinsidensi) dengan B. Perkembangan algoritma untuk menangani graf akan berdampak besar bagi ilmu komputer.
Sebuah struktur graf bisa dikembangkan dengan memberi bobot pada tiap sisi. Graf berbobot dapat digunakan untuk melambangkan banyak konsep berbeda. Sebagai contoh jika suatu graf melambangkan jaringan jalan maka bobotnya bisa berarti panjang jalan maupun batas kecepatan tertinggi pada jalan tertentu. Ekstensi lain pada graf adalah dengan membuat sisinya berarah, yang secara teknis disebut graf berarah atau digraf (directed graph). Digraf dengan sisi berbobot disebut jaringan.
Jaringan banyak digunakan pada cabang praktis teori graf yaitu analisis jaringan. Perlu dicatat bahwa pada analisis jaringan, definisi kata "jaringan" bisa berbeda, dan sering berarti graf sederhana (tanpa bobot dan arah).

http://id.wikipedia.org/wiki/Teori_graf

TEORI GRAF VII

TEORI GRAF VI

Representasi Graph 

1. Matriks Ketetanggaan (adjacency matrix)
2. Matriks Bersisian (incidency matrix)
3. Senarai Ketetanggaan (adjacency list)

Matriks Ketetanggaan (adjacency matrix)
A= [aij],
1, jika simpul idan jbertetangga
a ij= {
0, jika simpul idan jtidak bertetangga