TEORI GRAPH_GRAPH ISOMORPHIC

TEORI GRAPH_GRAPH ISOMORPHIC

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-sisi keduaya sedemikian sehingga hubungan kebersisian tetap terjaga.

Graph Isomorfik (Isomorphic Graph)

• Dengan kata lain, misalkan sisi ebersisian dengan simpul udan vdi 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.

GRAPH PLANAR & SIRKUIT HAMILTON

Kamis, 22 Desember 2011

GRAPH PLANAR & SIRKUIT HAMILTON

Graph Planar (Planar Graph) dan Graph Bidang (Plane Graph)

Graph yang dapat digambarkan pada bidang datar dengan sisi-sisi tidak saling memotong disebut sebagai graph planar, jika tidak, ia disebut graph tak-planar.

Lintasan dan Sirkuit Euler

• Lintasan Eulerialah lintasan yang melalui masing-masing sisi di dalam graph tepat satu kali. 

• Sirkuit Eulerialah sirkuit yang melewati masing-masing sisi tepat satu kali. 

• Graph yang mempunyai sirkuit Euler disebut graph Euler(Eulerian graph). Graph yang mempunyai lintasan Euler dinamakan juga graph semi-Euler(semi-Eulerian graph).

TEOREMA

• Graph tidak berarah memiliki lintasan Euler jika dan hanya jika terhubung dan memiliki dua buah simpul berderajat ganjil atau tidak ada simpul berderajat ganjil sama sekali.

•  Graph tidak berarah Gadalah graph Euler (memiliki sirkuit Euler) jika dan hanya jika setiap simpul berderajat genap.
• (Catatlah bahwa graph yang memiliki sirkuit Euler pasti mempunyai lintasan Euler, tetapi tidak sebaliknya).
•  Graph berarah G memiliki sirkuit Euler jika dan hanya jika Gterhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar sama. G memiliki lintasan Euler jika dan hanya jika G terhubung dan setiap simpul memiliki derajat-masuk dan derajat-keluar sama kecuali dua simpul, yang pertama memiliki derajat-keluar satu lebih besar derajat-masuk, dan yang kedua memiliki derajat-masuk satu lebih besar dari derajat-keluar.

 

  Lintasan dan Sirkuit Hamilton

• Lintasan Hamiltonialah lintasan yang melalui tiap simpul di dalam graph tepat satu kali. 

• Sirkuit Hamiltonialah sirkuit yang melalui tiap simpul di dalam graph tepat satu kali, kecuali simpul asal (sekaligus simpul akhir) yang dilalui dua kali.

• Graph yang memiliki sirkuit Hamilton dinamakan graph Hamilton, sedangkan graph yang hanya memiliki lintasan Hamilton disebut graph semi-Hamilton.

TEOREMA

• Syarat cukup (jadi bukan syarat perlu) supaya graph sederhana G dengan n(>=3) buah simpul adalah graph Hamilton ialah bila derajat tiap simpul paling sedikit n/2 (yaitu, d(v) n/2 untuk setiap simpul v di G).
• Setiap graph lengkap adalah graph Hamilton
• Di dalam graph lengkap Gdengan nbuah simpul (n>=3), terdapat (n-1)!/2 buah sirkuit Hamilton.
• Di dalam graph lengkap Gdengan nbuah simpul (n>=3 dan n ganjil), terdapat (n -1)/2 buah sirkuit Hamilton yang saling lepas (tidak ada sisi yang beririsan). Jika ngenap dan n4, maka di dalam G terdapat (n -2)/2 buah sirkuit Hamilton yang saling lepas.

Contoh :

(Persoalan pengaturan tempat duduk). Sembilan anggota sebuah klub bertemu tiap hari untuk makan siang pada sebuah meja bundar. Mereka memutuskan duduk sedemikian sehingga setiap anggota mempunyai tetangga duduk berbeda pada setiap makan siang. Berapa hari pengaturan tersebut dapat dilaksanakan?Jumlah pengaturan tempat duduk yang berbeda adalah (9 -1)/2 = 4.

Lintasan dan Sirkuit Hamilton/ Euler

• Beberapa graph dapat mengandung sirkuit Euler dan sirkuit Hamilton sekaligus, mengandung sirkuit Euler tetapi tidak mengandung sirkuit Hamilton, mengandung sirkuit Euler dan lintasan Hamilton, mengandung lintsan Euler maupun lintasan Hamilton, tidak mengandung lintasan Euler namun mengandung sirkuit Hamilton, dan sebagainya!).

TEORI GRAF

Materi Teori Graf sebelum UTS :

 TEORI GRAPH 

Graph digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menuyatakan objek dinyatakan sebagai noktah, bulatan, atau titik, sedangkan hubungan antara objek dinyatakan dengan garis.

*

Gambar perkotaan

I. SEJARAH GRAPH

Teori graf pertama kali dikembangkan oleh Leonhard Euler dalam memecahkan masalah jembatan Königsberg (tahun 1736). Permasalahannya adalah " Apakah bisa seseorang  melalui  sekali setiap jembatan yang menghubungkan kota-kota tersebut, dan kembali lagi ke kota dari mana ia berjalan".

*

Gambar1.1  (a) Jembatan Königsberg [ROS99], dan (b) graf yang merepresentasikan jembatan Königsberg

Jawaban yang dikemukakan oleh Euler adalah: orang tidak mungkin melalui ketujuh jembatan itu masingmasing satu kali dan kembali lagi ke tempat asal keberangkatan jika derajat setiap simpul tidak seluruhnyagenap. Yang dimaksud dengan derajat adalah banyaknya garis yang bersisian dengan noktah. Sebagai contoh,simpul C memiliki derajat 3 karena ada tiga buah garis yang bersisian dengannya, simpul B dan D juga berderajat dua, sedangkan simpul A berderajat 5. Karena tidak semua simpul berderajat genap, maka tidak mungkin dilakuk an perjalananan berupa sirkuit (yang dinamakan dengan sirkuit Euler) pada graf tersebut.
II. DEFINISI GRAPH

Graf G didefinisikan sebagai pasangan himpunan (V, E), yang dalam hal ini:
V = himpunan tidak-kosong dari simpul-simpul (vertices atau node) = { v1 , v2 , ... , vn }
dan
E = himpunan sisi (edges atau arcs) yang menghubungkan sepasang simpul = {e1 , e2 , ... , en }
atau dapat ditulis singkat notasi G = (V, E).

CATATAN : menyatakan bahwa V tidak boleh kosong, sedangkan E boleh kosong. Jadi, sebuah graf
dimungkinkan tidak mempunyai sisi satu buah pun, tetapi simpulnya harus ada, minimal satu. Graf yang
hanya mempunyai satu buah simpul tanpa sebuah sisi pun dinamakan graf trivial.

Simpul pada graf dapat dinomori dengan huruf, seperti a, b, c, …, v, w, ..., dengan bilangan asli 1, 2, 3, ...,
atau gabungan keduanya. Sedangkan sisi yang menghubungkan simpul vi dengan simpul vj dinyatakan
dengan pasangan (vi, vj) atau dengan lambang e1, e2, …. Dengan kata lain, jika e adalah sisi yang
menghubungkan simpul vi dengan simpul vj , maka e dapat ditulis sebagai
e = (vi , vj)
Secara geometri graf digambarkan sebagai sekumpulan noktah (simpul) di dalam bidang dwimatra yang
dihubungkan dengan sekumpulan garis (sisi).

*

Gambar2.1

G1 adalah graf dengan

V = { 1, 2, 3, 4 }

E = { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) }

G2 adalah graf dengan

V = { 1, 2, 3, 4 }

E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) }

= { e1, e2, e3, e4, e5, e6, e7}

G3 adalah graf dengan

V = { 1, 2, 3, 4 }

E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) }

= { e1, e2, e3, e4, e5, e6, e7, e8}

Pada G2, sisi e3 = (1, 3) dan sisi e4 = (1, 3) dinamakan sisi-ganda (multiple edges atau paralel edges) karena

kedua sisi ini menghubungi dua buah simpul yang sama, yaitu simpul 1 dan simpul 3. Pada G3, sisi e8 = (3, 3)

dinamakan gelang atau kalang (loop) karena ia berawal dan berakhir pada simpul yang sama.

Semoga Bermanfaat Bagi Anda-anda Semua nya

Materi Teori Graf

Materi Teori Graf dari pertemuan pertama sampai dengan terakhir :

Di sini anda tinggal meng-unduh file nya saja














UNDUH FILE