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

 

TEORI GRAF V

Derajat (Degree)
Derajatsuatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.
Notasi: d(v)
Tinjau graph G1:
d(1) = d(4) = 2
d(2) = d(3) = 3

Derajat (Degree)
Tinjau graph G3:
d(5) = 0 = simpul terpencil
d(4) = 1 = simpul anting-anting (pendant vertex)
Tinjau graph G2:
d(1) = 3 = bersisian dengan sisi ganda
d(2) = 4 = bersisian dengan sisi gelang (loop)





Derajat (Degree)
Pada graph berarah,
d in(v) = derajat-masuk (in-degree) = jumlah busur yang masuk ke simpul v
d out(v) = derajat-keluar (out-degree) = jumlah busur yang keluar dari simpul v
d(v) = d in(v) + d out(v)

Derajat (Degree)
Tinjau graph :
d in(1) = 2; d out(1) = 1
d in(2) = 2; d out(2) = 3
d in(3) = 2; d out(3) = 1
d in(4) = 1; d out(4) = 2





Lemma Jabat Tangan
Jumlah derajat semua simpul pada suatu graph adalah genap, yaitu dua kali jumlah sisi pada graph tersebut.
Dengan kata lain, jika G= (V, E), maka

Lemma Jabat Tangan
Tinjau graph G1:
d(1) + d(2) + d(3) + d(4) =
2 + 3 + 3 + 2 = 10 =
2 jumlah sisi = 2 x 5
Tinjau graph G2:
d(1) +d(2) + d(3)
= 3 + 3 + 4 = 10
= 2 jumlah sisi = 2 x 5




Lemma Jabat Tangan
Tinjau graph G3:
d(1) + d(2) + d(3) + d(4) + d(5)
= 2 + 2 + 3 + 1 + 0
= 8
= 2 jumlah sisi
= 2 x 4

Lemma Jabat Tangan
Contoh.
Diketahui graph dengan lima buah simpul. Dapatkah kita menggambar graph tersebut jika derajat masing-masing simpul adalah:
(a) 2, 3, 1, 1, 2
(b) 2, 3, 3, 4, 4
Penyelesaian:
(a) tidak dapat, karena jumlah derajat semua simpulnya
ganjil
(2 + 3 + 1 + 1 + 2 = 9).
(b) dapat, karena jumlah derajat semua simpulnya
genap
(2 + 3 + 3 + 4 + 4 = 16).

TEORI GRAF IV

Contoh Terapan Graph

Contoh Terapan Graph

• Transaksi konkuren pada basis data terpusat

• Transaksi T0menunggu transaksi T1dan T2

• Transaksi T2menunggu transaksi T1

• Transaksi T1menunggu transaksi T3

• Transaksi T3menunggu transaksi T2

Contoh Terapan Graph
. Pengujian program
read(x);
whilex <> 9999 do
begin
ifx < 0 then
writeln(‘Masukan tidak boleh negatif’)
else
x:=x+10;
read(x);
end;
writeln(x);


Contoh Terapan Graph

Ketetanggaan (Adjacent)
Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.
Tinjau graph :
simpul 1 bertetangga dengan simpul 2 dan 3, simpul 1 tidak bertetangga dengan simpul 4.

Bersisian (Incidency)
Untuk sembarang sisi e= (vj, vk) dikatakan e bersisian dengan simpul vj, atau e bersisian dengan simpul vk
Tinjau graph :
sisi (2, 3) bersisian dengan simpul 2 dan simpul 3,
sisi (2, 4) bersisian dengan simpul 2 dan simpul 4,
tetapi sisi (1, 2) tidak bersisian dengan simpul 4.

Simpul Terpencil (Isolated Vertex)
Simpul terpencilialah simpul yang tidak mempunyai sisi yang bersisian dengannya.
Tinjau graph : simpul 5 adalah simpul terpencil

Graph Kosong (null graphatau empty graph)
Graph yang himpunan sisinya merupakan himpunan kosong (Nn).