ANALISIS TENTANG GRAPH RANGKAP

ANALISIS TENTANG GRAPH RANGKAP

TESIS

Oleh MARSITO 077021064/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009

Marsito : Analisis Tentang Graph Rangkap, 2009 USU Repository © 2008

ANALISIS TENTANG GRAPH RANGKAP

TESIS

Diajukan Sebagai Salah Satu Syarat untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara

Oleh MARSITO 077021064/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009


Judul Tesis Nama Mahasiswa Nomor Pokok Program Studi

: : : :

ANALISIS TENTANG GRAPH RANGKAP Marsito 077021064 Matematika

Menyetujui, Komisi Pembimbing

(Dr. Saib Suwilo, M.Sc) Ketua

Ketua Program Studi

(Prof. Dr. Herman Mawengkang)

Tanggal lulus: 27 Mei 2009


(Prof. Dr. Herman Mawengkang) Anggota

Direktur

(Prof. Dr. Ir. T.Chairun Nisa. B,M.Sc)

Telah diuji pada Tanggal 27 Mei 2009

PANITIA PENGUJI TESIS Ketua

: Dr. Saib Suwilo, M.Sc

Anggota

: 1. Prof. Dr. Herman Mawengkang 2. Dr. Tulus, M.Si 3. Drs. Suwarno Ariswoyo, M.Si


ABSTRAK Suatu graph yang diperoleh dari direct product dua graph sederhana antara graph G dengan graph komplet T2 disebut sebagai graph rangkap, yang ditulis sebagai − D(G) = G × T2. Pada Penelitian ini akan dianalisis karakteristik dari graph rangkap dimaksud melalui beberapa proposisi. Karakteristik dimaksud dianalisis dengan berdasarkan pada sifat-sifat yang berlaku pada graph sederhana G(V, E)

Kata kunci: graph, direct product, graph rangkap dan karakteristik

i Marsito : Analisis Tentang Graph Rangkap, 2009 USU Repository © 2008

ABSTRACT Graph wich are the direct product of a simple graph G with the obtained by the complete graph T2 thus these graph turn out to be double graphs. In this paper will study the characteristic of double graphs. The characteristic of double graphs be analyzing with the basic property of simple graph G(V, E).

Keyword: graph, direct product, double graphs, characteristic.

ii Marsito : Analisis Tentang Graph Rangkap, 2009 USU Repository © 2008

KATA PENGANTAR Puji syukur penulis ucapkan kepada Allah SWT, yang senantiasa memberikan kekuatan, kesehatan dan kesabaran sehingga penulis mampu menyelesaikan Thesis ini sebagai tugas akhir dalam pendidikan lanjutan Program Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara (SPS USU Medan). Penulis merasakan bagaimana sulitnya melakukan penelitian ini dan sepenuhnya berserah diri kepada Allah SWT karena sesungguhnya penulis menyadari sebagai hamba yang lemah. Namun seiring ridho dan rahmat-Nya, secara perlahan penulis dapat menyelesaikan tugas ini. Penulis juga menyadari sepenuhnya bahwa banyak pihak-pihak yang turut andil dalam penyelesaian tugas ini, untuk itu melalui kesempatan ini penulis menyampaikan rasa terima kasih yang sedalam-dalamnya kepada:

1. Bapak Prof. dr. Chairuddin P. Lubis DTM&H, Sp.A(K) selaku Rektor Universitas Sumatera Utara 2. Ibu Prof. Dr. Ir. T. Chairun Nisa B., MSc selaku Direktur Sekolah Pascasarjana USU Medan 3. Bapak Prof. Dr. Herman Mawengkang, selaku Ketua Program Studi Magister Matematika pada Sekolah Pascasarjana USU Medan, yang juga sebagai Pembimbing Penulis. 4. Dr. Saib Suwilo, M.Sc selaku Sekretaris Program Magister Matematika pada Sekolah Pascasarjana USU Medan yang juga Pembimbing penulis. 5. Bapak Dr. Tulus, M.Si sebagai penguji sekaligus pembanding. iii Marsito : Analisis Tentang Graph Rangkap, 2009 USU Repository © 2008

6. Bapak Drs. Suwarno Ariswoyo, M.Si selaku penguji dan pembanding. 7. Bapak dan ibu seluruh dosen Program Studi Magister Matematika atas segala bimbingan, dorongan dan bantuannya. 8. Rekan-rekan Mahasiswa Program Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara angkatan 2007 9. Pegawai dan staf Program Studi Matematika Sekolah Pascasarjana Universitas Sumatera Utara. 10. Sri Astuti Rahayu, istri tercinta yang senantiasa memberi dorongan dan motivasi penulis dalam menyelesaikan tugas ini. 11. Yunita Deby Chintya dan Sesilia Rachma Puspita putri tercinta yang selalu mendorong penulis untuk segera menyelesaikan tugas ini. 12. Keluarga Besar SMA Negeri 1 Galang yang telah memberikan motivasi kepada penulis.

Akhirnya sembari berserah diri kehadirat Allah SWT, penulis menyadari sepenuhnya kekurangan yang dimiliki, untuk itu dengan segala kerendahan hati penulis menerima dengan senang hati kritik dan saran guna penyempurnaan penelitian ini. Penulis juga mengucapkan terimakasih

Medan, 27 Mei 2009 Penulis,

Marsito

iv Marsito : Analisis Tentang Graph Rangkap, 2009 USU Repository © 2008

RIWAYAT HIDUP

Penulis bernama Marsito, dilahirkan di Sukadamai pada tanggal 19 September 1968 anak ke tiga dari 5 bersaudara. Nama ayah Untung dan ibu Sukemi (alm). tamata dari Sekolah dasar melanjut ke SMP kemudian di SMA Tamansiswa. Pendidikan Dasar seluruhnya diselesaikan di Kisaran, kota tempat kelahiran. Pada tahun 1987 menamatkan pendidikan pada jenjang SMA kemudian melanjutkan pada jenjang berikutnya di IKIP Medan Program Studi Pendidikan Matematika selesai pada tahun 1992, dan mendapat gelar Sarjana Pendidikan. Riwayat pekerjaan dimulai sejak tahun 1990 mengajar pada sekolah swasta di Deli Tua, setelah menyelesaikan pendidikan pada program S-1, pindah ke Lhokseumawe mengajar pada SMA Swasta Pupuk Iskandar Muda, tepatnya pada tahun 1993. Setahun kemudian, tepatnya tahun 1994 diterima pada Yayasan Perguruan Tamansiswa di PT Arun Lhokseumawe, sampai pada tahun 2000 lulus sebagai CPNS di SMA Negeri 1 Galang sampai sekarang. Dalam menjalankan tugas pokok sebagai Pegawai Negeri Sipil, penulis juga aktif dalam kegiatan organisasi profesi seperti MGMP dari tingkat sekolah sampai tingkat kabupaten di Deli Serdang, anggota Tim Pengembang Kuriklum Tingkat Kabupaten Deli Serdang dan tingkat Propinsi Sumatera Utara. Dalam menjalankan tugas sebagai Pegawai Negeri Sipil, penulis juga pernah mengikuti berbagai lomba yaitu Olimpiade Guru Matematika se-Sumatera Utara pada Tahun 2005 dan terpilih sebagai juara I, Lomba Guru Berprestasi pada tahun 2006 dan terpilih sebagai juara I tingkat Propinsi Sumatera Utara dan mewakili Propinsi Sumatera Utara pada lomba yang sama di tingkat Nasional.

vi Marsito : Analisis Tentang Graph Rangkap, 2009 USU Repository © 2008

Dalam menjalani tugas sebagai guru, pada tahun 1993 penulis menikah dengan seorang wanita bernama Sri Astuti Rahayu dan dikaruniai dua orang putri. Sebagai seorang kepala rumah tangga, penulis tinggal di sebuah rumah sederhana di Komplek Perumahan Graha Deli Permai Blok A8 Nomor 11, Desa Deli Tua Kecamatan Namo Rambe Kabupaten Deli Serdang. Mambaur bersama masyarakat sekitar dan aktif pada kegiatan sosial kemasyarakatan dan kegiatan keagamaan.

vii Marsito : Analisis Tentang Graph Rangkap, 2009 USU Repository © 2008

DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

iii

RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vi

DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vii

DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ix

BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2 Rumusan Masalah . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2

1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.4 Kontribusi Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

1.5 Metodologi Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3

BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

BAB 3 LANDASAN TEORI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

3.1 Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

3.2 Direct Product Dua Graph . . . . . . . . . . . . . . . . . . . . . . . .

16

vii Marsito : Analisis Tentang Graph Rangkap, 2009 USU Repository © 2008

3.3 Graph Homomorphisme . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

BAB 4 KARAKTERISTIK DARI GRAPH RANGKAP . . . . . . . . . . . .

21

BAB 5 KESIMPULAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

31

DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

viii Marsito : Analisis Tentang Graph Rangkap, 2009 USU Repository © 2008

DAFTAR GAMBAR

Nomor

Judul

Halaman

3.1

Graph dengan 5 verteks dan 6 edge . . . . . . . . . . . . . . . . . . . .

7

3.2

Graph dengan 3 verteks dan 5 edge . . . . . . . . . . . . . . . . . . . .

7

3.3

Graph dengan adjacent edge . . . . . . . . . . . . . . . . . . . . . . . . .

8

3.4

Graph berdiameter 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

3.5

Graph dengan diameter 5 . . . . . . . . . . . . . . . . . . . . . . . . . . .

11

3.6

Graph Sederhana dengan 4 verteks dan 5 edge . . . . . . . . . . . .

12

3.7

Graph Komplit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

3.8

Graph dan sub graphnya . . . . . . . . . . . . . . . . . . . . . . . . . . . .

12

3.9

Graph terhubung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

3.10 Graph tak terhubung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

13

3.11 Graph bipartit Komplit K3,3 . . . . . . . . . . . . . . . . . . . . . . . . .

14

3.12 Graph Hamiltonian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

3.13 Graph G × H . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

17

4.1

22

a) Graph rangkap − D(P4 ) b) Graph rangkap − D(C4 ) . . . . . . . .

ix Marsito : Analisis Tentang Graph Rangkap, 2009 USU Repository © 2008

BAB 1 PENDAHULUAN

1.1 Latar Belakang Teori Graph saat ini menjadi topik yang banyak mendapat perhatian, karena bentuk dan modelnya sangat bervariasi dan cocok untuk aplikasi yang luas, seperti jaringan sosial, transportasi, komunikasi dan lain-lain. Di samping itu Teori Graph sebagai bagian dari matematika diskrit juga terus berkembang seiring dengan kebutuhan ilmu itu sendiri dalam menyahuti tantangan persoalan sehari-hari. Berbagai kajian dan penelitian terus dilakukan guna memperoleh sesuatu yang baru tentang Graph. Salah satu kajian yang saat ini sedang dilakukan dan masih jarang dilakukan adalah permasalahan Graph Rangkap. Dalam bidang aplikasi, graph rangkap digunakan peneliti, di antaranya Ruji, Huang (1994) menggunakan model graph rangkap dalam analisis dekomposisi modifikasi untuk penentuan fungsi network simbolis, dijelaskan kelebihannya adalah ekspresi simbolis yang dihasilkan tidak memuat suku pembatalan dan evaluasi tandanya sangat mudah. Selanjutnya Jin Zhipou (2003) menggunakan model graph rangkap dalam analisis stabilitas dan kinerja pada model graph rangkap formasi kendaraan. Dalam penelitiannya dijelaskan bahwa dengan menggunakan model graph rangkap dapat dibahas aliran informasi dan merumuskan stabilitas string. Dalam hal analisis, Munarini.et.al (2007) mendefinisikan Total graph Tn dengan n verteks adalah graph yang mengasosiasikan keseluruhan relasi (di mana

1 Marsito : Analisis Tentang Graph Rangkap, 2009 USU Repository © 2008

2 setiap verteks adjacent pada setiap verteks yang lain), hal itu dapat dinyatakan sebagai graph komplit Kn dengan menambahkan loop pada setiap verteks. Selanjutnya Munarini et.al juga mendefinisikan Graph Rangkap sebagai Graph − D[G] = G × T2 di mana direct product dari sebuah simple graph dengan graph yang lain adalah juga sebuah simple Graph, yang berarti graph rangkap juga adalah simple graph atau graph sederhana. Direct Product dari dua graph G dan H adalah graph G × H dengan V (G × H) = V (G) × V (H) dan dengan keterhubungannya didefinisikan oleh (v1 , w1) adj (v2, w2) jika dan hanya jika v1 adj v2 dalam G dan w1 adj w2 dalam H Dalam penelitiannya, Munarini, et.al (2007) mendefinisikan graph rangkap sebagai direct product sebuah simple graph dengan graph komplit K2 dan menjabarkan sifat-sifat dasar dari graph rangkap. Defenisi lain dari graph rangkap dijelaskan kembali oleh Marino dan Salvi (2007) yang menyatakan direct product suatu Graph sederhana dengan graph komplet Kk dengan menambahkan loop untuk setiap vertex digeneralisasikan sebagai graph rangkap. Pada penelitian ini, penulis tidak menggunakan graph rangkap dalam aplikasi sebagaimana yang dilakukan Jin dan Ruji melainkan akan mendefinisikan kembali graph rangkap, menganalisis dan menjelaskan karakteristik dari graph ragkap. 1.2 Rumusan Masalah Konstruksi untuk suatu graph seperti yang didefinisikan pada bagian latar belakang terlihat memiliki sifat-sifat menarik, terutama kemungkinannya untuk diaplikasikan atau dianalisis lebih lanjut. Oleh karena itu yang menjadi persoalan dalam tesis ini adalah bagaimana karakteristik dari graph rangkap.


3 1.3 Tujuan Penelitian Adapun tujuan dari penelitian ini adalah untuk menjelaskan karakteristik dari graph rangkap dengan membuktikan beberapa proposisi yang ada nantinya. 1.4 Kontribusi Penelitian Kontribusi dari hasil penelitian ini adalah memberikan referensi baru tentang graph rangkap, sehingga dapat dijadikan rujukan atau dalam penelitian tentang graph rangkap yang memang masih jarang dilakukan, baik dalam khasanah keilmuan maupun aplikasinya. 1.5 Metodologi Penelitian Oleh karena Penelitian ini bersifat literature, maka metodologi yang dilakukan adalah melakukan langkah-langkah kegiatan sebagai berikut :

a Menguraikan tentang Graph b Menguraikan Direct Product dua Graph c Menguraikan Graph Homomorphisme d Menjelaskan dan menguraikan karakteristik dari graph rangkap e Membuat simpulan dan rekomendasi


BAB 2 TINJAUAN PUSTAKA

Graph G(V, E) dengan V adalah himpunan tak kosong dan berhingga dari titik-titik yang selanjutnya desebut vertex dan E adalah himpunan pasangan tak berurut {vi , vj } yang merupakan sisi yang menghubungkan setiap vertex pada V yang selanjutnya disebut edge. (Brualdi, R.A 1991). Graph rangkap adalah graph yang dihasilkan dari direct product sebuah graph sederhana dengan graph komplit T2 . Kajian dan penelitian tentang graph rangkap masih jarang dilakukan. Dalam bidang aplikasi, graph rangkap juga digunakan peneliti, di antaranya Ruji, Huang (1994) menggunakan model graph rangkap dalam analisis dekomposisi modifikasi untuk penentuan fungsi network simbolis, dijelaskan kelebihannya adalah ekspresi simbolis yang dihasilkan tidak memuat suku pembatalan dan evaluasi tandanya sangat mudah. Selanjutnya Jin Zhipou (2003) menggunakan model graph rangkap dalam analisis stabilitas dan kinerga pada model graph rangkap formasi kendaraan. Dalam penelitiannya dijelaskan bahwa dengan menggunakan model graph rangkap dapat dibahas aliran informasi dan merumuskan stabilitas string. Dalam analisis tentang graph rangkap, Sclagiola, A (2006) melakukan penelitian tentang graph rangkap yang menjelaskan sifat-sifat aljabar dan struktur graph rangkap dimaksud. Selanjutnya Munarini, et.al (2007) telah melakukan kajian tentang sifat-sifat dasar dari graph rangkap. Dalam hal ini kajian yang dilakukan adalah pembuktian beberapa sifat dasar dari graph rangkap.


5 Selanjutnya, Marino and Salvi (2007) melakukan penelitian tentang direct product simple graph dengan graph komplit Kn , dengan menambahkan loop untuk setiap verteks dan menggeneralisasikannya sebagai graph rangkap. Dalam penelitian ini dikaji secara umum sifat-sifat dari direct product sebuah simple graph dengan graph komplit Tn , dan menganalisis sifat-sifatnya. Hal ini semakin memperjelas tentang kajian graph rangkap. Dalam penelitian ini, penulis tidak akan melakukan penelitian dalam bidang aplikasi graph rangkap, melainkan akan menganalisis karakteristik graph rangkap sebagaimana telah didefinisikan dalam bagian latar belakang dengan mempelajari beberapa kajian yang telah dilakukan sebelumnya.


BAB 3 LANDASAN TEORI

Dalam bab ini akan diuraikan pengertian tentang graph, direct product dua graph dan graph homomorphisme sebagai dasar teori dalam mengembangkan karakteristik dari graph rangkap. Dalam hal ini yang akan dibahas adalah graph dengan himpunan verteks dan edge yang berhingga.

3.1 Graph Brualdi, R.A, 1991 menyatakan suatu graph terdiri dari dua bagian penting yaitu titik (verteks) dan garis (edge untuk garis tak berarah) atau (arc untuk garis berarah).Graph G dengan himpunan hingga verteks V dan himpunan hingga edge E dinotasikan dengan G(V, E). Andaikan G adalah suatu graph dengan himpunan verteks V = {v1, v2, v3, . . . , vn }, dan E adalah hiompunan edge, E = {e1 , e2, e3, . . . , en } dimana e1 , e2, e3, . . . , en adalah garis tak berarah yang menghubungkan vi, vj dan dinotasikan vi − vj atau {vi, vj }. Definisi formal dari suatu graph adalah sebagai berikut :

Definisi 3.1.1. Suatu graph G adalah himpunan berhingga yang tak kosong V yang beranggotakan verteks di G yang dihubungkan oleh himpunan E yang aggotanya adalah pasangan tak berurut dari anggota V yang disebut edge atau pasangan berurutan dari anggota V atau arc. Dalam hal ini tidak semua verteks harus terhubung.


7 Graph G dengan himpunan hingga verteks V dan edge E dinotasikan dengan G(V, E) dimana V = {v1, v2, v3, . . . , vn }, dan E = {e1 , e2, e3, . . . , en } dimana e = {vi , vj } graph yang demikian disebut dengan undirect graph atau graph tak berarah. Penjelasan tenyang ini dapat diperlihatkan dalam gambar 3.1. berikut .

Gambar 3.1 Graph dengan 5 verteks dan 6 edge

Gambaran umum tentang graph dapat dinyatakan sebagai suatu diagram, dimana verteks disajikan sebagai titik-titik dan dinotasikan dengan vi , dengan i = {1, 2, 3, . . . , m} dan edge sebagai garis lurus atau lengkung yang menghubungkan dua verteks (vi, vj ) dan dinyatakan sebagai Ek dengan k = {1, 2, 3, . . . , n} dan vi dan vj sebagai verteks ujung dari edge Ek . Perhatikan himpunan verteks V = {v1, v2, v3 } dan himpunan edge E = {v1 − v2, v1 − v3, v2 − v3, v3 − v1, v2 − v2} adalah graph dengan 3 verteks dan 4 edge. Graph pada contoh ini dapat dinyatakan secara grafis sebagai berikut :

Gambar 3.2 Graph dengan 3 verteks dan 5 edge


8 Definisi 3.1.2. Sebuah edge yang menguhngkan dua verteks yang sama disebut loop, dan dua atau lebih edge mempunyai verteks-verteks ujung yang sama disebut edge paralel.

Definisi 3.1.3. Degree suatu verteks Vi dalam graph G adalah jumlah edge yang incident dengan Vi , dengan loop dihitung dua kali. Bila jumlah edge yang incident dengan Vi adalah n, maka degree dari Vi adalah n dan ditulis d(Vi ) = n.

Definisi 3.1.4. Suatu edge ek dimana k = 1, 2, 3, . . . , n. Dikatakan incident dengan suatu verteks Vi dimana i = 1, 2, 3, . . . , m, yaitu jika dan hanya jika ek adalah penghubung antara Vi dengan suatu verteks lain. Definisi tersebut menjelaskan bahwa suatu edge harus incident dengan dua buah verteks yang sama atau tidak. Dua buah verteks disebut adjecent jika kedua verteks tersebut merupakan ujung dari sebua edge yang sama dan sering disebut sebagai adjecent verteks. Jika dua buah edge incident terhadap suatu verteks terkait, maka kedua edge yang demikian disebut adjecent edge, lebih jelas perhatikan gambar berikut

Gambar 3.3 Graph dengan adjacent edge


9 Definisi 3.1.5 Walk dari u ke v dinotasikan dengan uv - walk atau wuv adalah barisan verteks-verteks u = u0 , u1, u2, . . . , uj−1 = v dan edge yang berhubungan u−v1, u1 −v2, . . . , un−1 yang disusun sedemikian sehingga satu sama lain berselang seling yang diawali dengan verteks u dan diakhiri dengan verteks v. Secara umum dinyatakan sebagai berikut : u = u0 − v1 − u1 − v2 − . . . − uj−1 − vj = v Panjang suatu walk uv adalah banyaknya edge yang terdapat pada walk tersebut dan dinotasikan sebagai l(wuv ). Suatu walk dikatakan terbuka jika verteks u 6= v dan dikatakan tertutup jika u = v. Selanjutnya jika suatu walk terdiri dari verteks yang berbeda-beda disebut trail dan path adalah walk tanpa pengulangan verteks kecuali verteks awal dan akhir. Path yang menghubungkan verteks u dan v dinotasikan dengan puv dan panjangnya adalah l(puv ). Dalam teori graph path tertutup disebut dengan cycle, yaitu path yang verteks awal sama dengan verteks akhir. Contoh gambar 3.2. menjelaskan tentang walk, path cycle dan loop. Walk yang dapat dibentk pada graph tersebut adalah v1 − v2 − v3 − v1, yang juga merupakan suatu cycle dengan panjang 3, sedangkan v2 − v2 merupakan loop. Perlu diperhatikan bahwa suatu uv − walk dapat melalui satu verteks beberapa kali, sedangkan uv − path tidak ada pengulangan di dalamnya dengan kata lain tidak dibenarkan adanya loop, hal ini juga menjelaskan bahwa dalam setiap walk selalu ada paling sedikit satu path. Berikut adalah teorema yang menjelaskan bahwa terdapat path pada setiap walk.

Teorema 3.1.1. Andaikan G adalah suatu graph. Setiap walk wuv di G mengandung suatu path puv .


10 Bukti : Andaikan W adalah suatu walk wuv dalam bentuk u = u0 − v1, . . . , ui − vi+1 , . . . , uj − vj+1 , . . . , uk − vk+1 , . . . − vm = v

Jika walk W tidak menggunakan suatu verteks lebih dari satu kali maka walk ini adalah suatu path. Andaikan ada verteks yang digunakan lebih dari satu kali oleh walk W , hal ini berarti terdapat indeks i dan j dengan i < j sehingga ui = uj . Dengan membuang path dari ui ke vj , kecuali verteks ui maka diperoleh suatu walk W1. Dari sini dapat kita lihat walk W1 lebih pendek dari walk W dan merupakan suatu path jika tidak terdapat penggunaan verteks yang berulang di dalamnya. Andaikan masih ada verteks yang digunakan walk W1 lebih dari satu kali, misalkan verteks uk , maka dengan membuang path dari uk ke vk kecuali verteks uk , diperoleh walk W2, jelas bahwa W2 lebih pendek dari W1 . Andaikan masih ada juga verteks yang digunakan lebih dari satu kali oleh walk W2 , karena edge dan verteks pada walk W berhingga, maka dengan meneruskan proses di atas, akan diperoleh walk Wt. Walk Wt adalah walk dari u ke v yang merupakan suatu path. Jadi setiap walk di G mengandung suatu path.

Andaikan verteks u dan v adalah dua verteks yang berbeda dalam graph G. Jarak antara dua verteks u dan v adalah panjang dari sisi path puv yang terpendek di G dan disebut diameter dari graph G dan dinotasikan dengan d(u, v) atau dapat dinyatakan dengan diam(G) yang merupakan jarak maksimum antara dua verteks u dan v di G: Diam(G) = maks{d(u, v)} u,v∈G


11 Contoh graph dengan diameter 3 diperlihatkan oleh gambar berikut :

Gambar 3.4 Graph berdiameter 3

Contoh graph berdiameter 5 :

Gambar 3.5 Graph dengan diameter 5

Dari gambar 3.4 dapat dilihat bahwa jarak maksimum antar dua verteks ke verteks lainnya adalah 3, sedangkan pada gambar 3.5, jarak antara dua verteks adalah 5.

Definisi 3.1.6 Suatu graph yang tidak memiliki loop dan edge-edge paralel di dalamnya disebut graph simple (graph sederhana). Contoh Grap Sederhana :


12

Gambar 3.6 Graph Sederhana dengan 4 verteks dan 5 edge Definisi 3.1.7. Graph komplit adalah graph yang memiliki edge atau arc pada setiap pasangan verteksnya. Perhatikan contoh graph komplit pada gambar 3.7 berikut :

Gambar 3.7 Graph Komplit

Definisi 3.1.8. Suatu graph g disebut sub graph dari graph G, jika semua verteks dan edge dalam g termuat dalam G, dan setiap edge yang mempunyai verteksverteks ujung yang sama dalam g juga akan mempunyai verteks-verteks ujung yang sama dalam G. Perhatikan gambar berikut :

Gambar 3.8 Graph dan sub graphnya


13 Definisi 3.1.9. Suatu graph G dikatakan terhubung jika untuk setiap pasangan verteks u dan v di G terdapat uv− walk di G yang menghubungkan verteks u dan v. Berikut adalah contoh graph terhubung dan graph tak terhubung.

Gambar 3.9 Graph terhubung

Gambar 3.10 Graph tak terhubung

Definisi 3.1.10. Matriks Adjacency dari suatu graph G(V, E) dengan n verteks adalah matriks bujur sangkar berukuran n × n yang didefinisikan sebagai : aij =

1, bila ada edge yang menghubungkan verteks vi kevj 0, untuk yang lainnya

Matriks adjacency bersifat simetris. Suatu contoh untuk matriks adjacency dapat dilihat pada graph yang direpresentasikan dalam gambar 3.9, matriks adjacen-


14 cynya adalah :



0 1 1 A= 0 0 0

1 0 1 1 0 0

1 1 0 0 0 0

0 1 0 0 1 1

0 0 0 1 0 1

 0 0 0  1 1 0

Definisi 3.1.11. Graph bipartit adalah graph G yang himpunan verteks-nya dapat dipartisi menjadi dua himpunan bagian V1 dan V2 sedemikian sehingga setiap edge pada G menghubungkan sebuah verteks pada V1 ke sebuah verteks pada V2 . Graph bipartit dilambangkan dengan Km,n dengan m adalah jumlah verteks pada V1 dan n melambangkan jumlah verteks pada V2 . Perhatikan gambar graph bipartit K3,3 berikut :

Gambar 3.11 Graph bipartit Komplit K3,3

Lintasan Euler adalah lintasan yang melalui masing-masing edge dalam graph G tepat satu kali. Bila lintasan tersebut kembali ke verteks asal membentuk barisan tertutup, lintasan tersebut disebut sebagai Sirkuit Euler. Sirkuit Euler adalah sirkuit yang melalui masing-masing verteks tepat satu kali. Definisi 3.1.12. Graph yang memiliki sirkuit Euler disebut graph Euler (Eulerian Graph) Graph yang memiliki lintasan Euler disebut graph semi Euler ( Semi Eulerian Graph).


15 Berikut adalah teorema yang menjamin bahwa setiap graph Eulerian memiliki jumlah verteks genap. Teorema 3.1.2. Suatu graph G(V, E) adalah Eulerian jika dan hanya jika G terhubung dan derajad dari verteks dalam G adalah genap.

Bukti : Graph G harus terhubung, yang lainnya tidak dapat melalui seluruh edge, untuk degree verteks yang genap. ⇒ Asumsikan G adalah sirkuit Eulerian. Setiap saat walk memasuki sebuah verteks, lalu meninggalkannya sesudah itu, selanjutnya G haruslah memiliki degree genap atau akan memberikan lintasan lurus. Untuk verteks pertama, meninggalkannya dan masuk sesudahnya, hal itu juga harus memilikidegree genap.

⇐ asumsikan semua vertex dalam G memiliki degree genap. Pilih sebarang vertex v ∈ V dan mulai berjalan menuju edge dari graph. Diberikan bahwa semua degree dari edge dalam G adalah genap, itu hanya akan memberikan satu lintasan lurus pada v. Hapus kunjungan edge dari G. Jika tidak ada edge yang diberikan, tentu tidak ada. Yang lainnya pilih sebarang vertex yang lain dengan degree tidak nol dan ulangi perdalanan. Ulangi proses sampai setiap edge dihapus. Sekarang diperoleh koleksi dari sirkuit c1 , c2, . . . , ck . Kesemuanya dapat digabung dalam sirkuit besar oleh perjalanan c1 sampai vertex pertama v yang merupakan bagian dari path cj . Selanjutnya lanjutkan perjalanan cj dengan aturan yang sama. Dapat diresume perjalanan c1 ke cj telah selesai. Perhatikan bahwa oleh karena itu G terhubung.


16 Definisi 3.1.13. Graph Hamilton adalah graph yang memiliki sirkuit Hamilton. Sirkuit Hamilton adalah sirkuit yang melewati setiap edge tepat satu kali tanpa menyentuh sirkuit lainnya lebih dari satu kali. Perhatikan gambar graph Hamiltonian berikut :

Gambar 3.12 Graph Hamiltonian

3.2 Direct Product Dua Graph Dalam bagian ini, akan dibahas operasi graph yaitu direct product dua graph. Hasil kali kartesius dari graph G1 dan G2 adalah graph yang dinotasikan G1 × G2 dan mempunyai himpunan verteks V = {v1, v2|v1 ∈ V (G1 ), v2 ∈ V (G2 )} di mana vertex (u1 , u2) dan (v1, v2 ) adjacent di G1 × G2 jika : [ u1 = v1 dan u2 adjacent v2 ] atau [u2 = v2 dan u1 adjacent v1] (Hagauer,1996). Direct product dua graph G dan H didefinisikan sebagai product Kartesius G × H. Untuk menjelaskan pengertian direct product dua graph sederhana, perhatikan gambar berikut


17

Gambar 3.13 Graph G × H

Pada direct product dua graph berlaku sifat assosistif dan distributif. Dalam pembahasan selanjutnya, direct product graph G dengan graph komplet dengan dua verteks dinyatakan sebagai graph rangkap.

3.3 Graph Homomorphisme Suatu homomorphisme dari graph G ke graph H adalah suatu fungsi f dari V G ke V H dimana jika u ≈ v dalam G, maka uf ≈ vf dalam H. Selanjutnya isomorphisme adalah homomorphisme bijektif yang inversnya juga homomorphisme. Suatu homomorphisme merupakan generelisasi dari graph koloring. Suatu homomorphisme dari graph G ke graph komplet Kγ (r = 1, 2, 3, r yang merupakan kumpulan verteks) selanjutnya dinyatakan sebagai r - koloring dari G, yang mana adjecent verteks dipetakan ke distink verteks pada graph komplet. Selanjutnya homomorphisme digeneralisasikan sebagai koloring. Oleh karena homomorphisme memetakan edge ke edge, kita dapat melihat homomorphic bayangan dari graph terhubung harus terhubung.


18 Perhatikan kasus berikut: Bagaimana menjadwalkan ujian dalam jumlah periode terkecil ? Dua ujian yang diikuti oleh siswa yang sama tidak dapat dijadwalkan dalam waktu yang sama. Sehingga, buatlah sebuah graph G yang verteksnya adalah ujian, dua vertik yang diapdukan oleh sebuah edge jika siswa sedang mengikuti dua ujian. Sehingga, jadwal ujian dalam periode k ada jika dan hanya jika graphnya dapat diwarnai dengan warna k-periode, ada homomorfisme dari G ke graph komplit Kk . Sekarang misalkan bahwa seorang siswa tidak diizinkan untuk mengikuti ujian dalam periode berturut-turut. Misalkan Hk adalah graph komplit pada k verteks dengan edge ujung k1 dari jalur yang dilewati. Sehingga, ujian dapat dijadwalkan dalam periode k jika dan hanya jika ada homomorfisme dari G ke Hk . Kelihatan bahwa ada hubungan erat antara homomorfisme dengan masalah masalah kepuasan tertentu Selanjutnya ditemukan G → H jika ada homomorfisme dari G ke H, dan G ≡ H jika G ≡ H dan H → G. sehingga, tanda → adalah sebuah pra-order ( yang bersifat refleksif karena peta identitasnya adalah homomorfisme, dan bersifat transitif karena komposisi homomorfisme adalah homomorfisme ) dan ≡ adalah hubungan ekivalensi yang dihasilkan ( yang disebut ekivalensi homomorfisme). Kelas-kelas ekivalensi ini sebagian dinotasikan dengan tanda →, inilah yang disebut ordo homomorfisme. Terkadang, kita menyalahgunakan notasi dengan merujuk ordo pada graph masing - masing. Karena homomorfisme memetakan edge ujung ke edge ujung, maka akan terlihat bahwa bayangan homomorfik dari sebuah graph ,harus dihubungkan.


19 Misalkan ω(G) dan χ(G) menunjukkan bilangan klik dan bilangan kromatik dari graph G. sekarang, nomor klik G adalah nilai k terbesar dimana Kk → G, karena bayangan sebuah graph lengkap di bawah homomorfisme adalah graph lengkap dari ukuran yang sama, dan juga, graph adalah berwarna k jika dan hanya jika memilki homomorfisme terhadap graph lengkap Kk, sehingga χ(G) adalah k terkecil di mana ketentuan ini berlaku.

Proposisi 3.3.1. jika G ⇒ H, maka ω(G) < ω(H) dan χ(G) < χ(H)

Bukti. Jika ∅ : G → H adalah homomorfisme, maka dengan menguraikannya dengan homomorfisme dari atau ke Kk akan memungkinkan kita untuk melihat bahwa ; - Kk → G mengimplikasian Kk → H: - H → Kk mengimplikasian G → H: Sebagai akibat proposisi 3.3.1. adalah Jika G ≡ H maka ω(W ) = ω(H) dan χ(G) = χ(H)

Definisi 3.3.1. Dua graph sederhana dengan himpunan vertex V dan U adalah isomorphic jika keduanya dipetakan oleh fungsi bijektif f dari V pada U sehingga dua vertex v dan u adjacent dalam V dan bayangan f (v) dan f (u) adjacent dalam U. Dalam kasus ini fungsi f disebut isomorphism antara dua graph. Definisi lain tentang isomorphism dua graph adalah :


20 Definisi 3.3.2. Dua graph A dan B adalah isomorphic jika dan hanya jika untuk setiap graph G bilangan homomorphisme dari G ke dalam A sama dengan bilangan homomorphisme dari G ke dalam B.


BAB 4 KARAKTERISTIK DARI GRAPH RANGKAP

Pada bagian ini akan dijelaskan definisi dan karakteristik dari graph rangkap dengan menggunakan dasar teori yang telah diuraikan pada bagian sebelumnya. Beberapa pengertian perlu diuraikan kembali untuk memudahkan dalam pembahasan selanjutnya. Dalam tesis ini hanya akan dibahas graph sederhana terhingga, yaitu graph tanpa loop dan multiple edge, sebagaimana biasanya V (G) dan E(G) mendefinisikan himpunan vertex dan edge dalam G. Untuk seluruh definisi telah diuraikan dalam bab III. Direct Progduct dua graph G dan H adalah graph G×H dengan V (G×H) = V (G) × V (H) dan dengan adjacency didefinisikan sebagai (v1, w1 ) adj (v2, w2 ) jika dan hanya jika v1 adj v2 dalam G dan w1 adc w2 dalam H. Total graph Tn pada n verteks adalah graph yang mengasosiasikan seluruh relasi (setiap verteks adj dengan setiap vertex). Definisi 4.1.1. Graph rangkap dari graph G ( ditulis − D(G) ) didefinisikan sebagai − D(G) = G × T2 dimana T2 adalah graph komplit dengan dua vertex. Oleh karena direct product dua graph sederhana, maka rangkap dari graph sederhana adalah juga graph sederhana. Dalam graph rangkap − D(G) dapat dilihat bahwa (v, h) adj (w, k) jika dan hanya jika u dan w dalam G. Jika V (T2) = {0, 1} diperoleh G0 = {(v, 0) : v ∈ V (G)} dan G1 = {(v, 1) : v ∈ V (G)} adalah dua subgraph dari − D(G) yang keduanya isomorphik pada G dimana


22 D(G). Selanjutnya G0 ∩ G1 = ∅ dan G0 ∪ G1 adlaah spanning subgraph dari − terdapat sebuah edge di antara (v, 0) dan (w, 0) demikian pula terdapat sebuah edge di antara (v, 1) dan (w, 0) dimana v adj w dalam G. Dikatakan {G0 , G1 } suatu dekomposisi kanonikal dari − D(G), dapat dilihat pada gambar 14.

Gambar 4.1 a) Graph rangkap − D(P4 ) b) Graph rangkap − D(C4 )

Dari penjelasan di atas dapat dilihat bahwa jika G memiliki n vertex dan m edge, maka − D(G) memiliki 2n vertex dan 4m edge. Sehingga dapat dinyatakan degree dari graph rangkap − D(G) dengan n vertex dan m edge atau deg (v, k) = D −(G)

2 deg G (v). Leksikograpfik atau komposisi dua graph G dan H adalah graph G ◦ H dengan V (G) × V (H) dimana himpunan vertex dan adjacency didefinisikan sebagai (v1 , w1) adj (v2 , w2) jika dan hanya jika v1 = v2 dan w1 adj w2 dalam H atau v1 adj v2 dalam G. Graph G ◦ H dapat diperoleh dengan mensubstitusi G pada tiap vertex V pada G sebuah turunan Hv pada H dan menggabungkan tiap vertex pada Hv dengan tiap vertex pada Hw dimana v dan w adj dalam G. Selanjutnya pada bagian ini akan dijelaskan karakteristik dari graph rangkap sebagai berikut:


23 Proposisi 4.1.1. Suatu graph rangkap − D(G) dari graph G pada n vertex mempunyai paling sedikit 2n subgraph isomorphik pada G itu sendiri.

Bukti. Misalkan {G0 , G1 } sebagai dekomposisi dari graph rangkap − D(G). Asumsikan S0 sebagai subset V (G0 ) dan ambil S1 sebagai subset V (G1 ) yang berkorespondensi dengan komplemen himpunan dari S0 . Maka graph yang diperoleh dari S0 ∪ S1 isomorphik ke graph G.

Proposisi 4.1.2. Untuk setiap graph G, maka G merupakan bipartite jika dan hanya jika − D[G] bipartite. D[G]. Jika G merupakan bipartite Bukti : Misal {G0 , G1 } sebagai dekomposisi − maka G0 dan G1 juga bipartite. Asumsikan [V, W ] sebagai bipartisi dari G dan berturut-turut {V0 , W0}, {V1 , W1 } sebagai hasil bipartisi dari G0 dan G1 . Tiap edge − D[G] mempunyai satu nilai ekstrim pada V0 ∪V1 dan yang lain pada W0 ∪W1 , sehingga − D[G] juga bipartite. Sebaliknya, jika − D[G] merupakan bipartit maka ia tidak mengandung cycle ganjil . Jadi subgraph G0 ≈ G tidak mengandung cycle ganjil dan karena itu ia merupakan bipartite.

Sebuah irisan vertex pada suatu graph G adalah suatu subset S dari V (G) dimana G\S tidak terhubung. Koneksi K(G) pada G adalah ukuran terkecil dari suatu irisan vertex G. Suatu artikulasi adalah suatu vertex yang mengalami pemotongan penambahan jumlah pada komponen yang berhubungan. Suatu blok adalah suatu graph terhubung tanpa titik artikulasi.


24 Proposisi 4.1.3: Untuk setiap graph G 6= K1 berlaku sifat-sifat :

1. G terhubung jika dan hanya jika − D[G] terhubung 2. Jika G terhubung maka setiap pasangan vertex dari − D[G] termasuk suatu cycle 3. Setiap edge dari − D[G] termasuk pada 4 -cycle 4. Pada graph rangkap tidak terdapat jembatan maupun titik artikulasi 5. Jika G terhubung maka − D[G] adalah suatiu blok. 6. Koneksi pada − D[G] adalah K(− D[G]) = 2k(G)

Bukti : Misal {G0 , G1 } merupakan dekomposisi dari − D[G]

1. Jika G terhubung maka G0 dan G1 juga terhubung sehingga kita hanya perlu membuktikan bahwa semua vertex (v, 0) pada G0 terhubung dengan semua vertex pada G1 . misal v adalah vertex adjacent ke v, maka (v, 0) adjacent dengan (v, I) karena G1 terhubung, maka ada path yang menghubungkan (v, 1), dan sehingga (v, 0) pada setiap vertex dari G1 , sebaliknya jika G tidak terhubung maka − D[G] tidak terhubung. 2. Misal (v, 0) dan (w, 0) sebagai dua vertex berbeda pada G0 .asumsikan γ0 path yang menghubungkan kedua vertex tersebut dan asumsikan γ1 sebagai hasil dari hubungan path pada vertex (v, 1) dan (w, 1) dalam G1 . Misal (v, 1) sebagai vertex berikutnya (v, 1) pada γ1 , (W , I) sebagai vertex pendahulu (W, I) pada γ1 dan misalkan γ 1 sebagai sub -path dari γ1 dari (w, 1) ke (v, 1). Maka γ0 U {(w, 0), (w, 1)}U γ, ∪{(v, 1), (v, 0)} adalah suatu cycle


25 yang mengandung (v, 0) dan (w, 0). Sebuah argumen yang sama berperan pada saat akan menyelesaikan dua vertex berbeda pada G1 atau dua vertex (v, 0) dan (w, 1) dengan v 6 w akhirnya, pada permasalahan dua vertex (v, 0) dan (v, 1), pilihan sebarang vertex v adjecent ke v, kita memiliki (v, 0), (v, 1), (v, 1), (v, 0), (v, 0), (v, 0) sebagai suatu cycle yang mengandung kedua verteks. 3. Tiap edge vw pada G menghasilkan 4-cycle (v, 0), (w, 0), (v, 1), (w, 1), (v, 0) dalam − D(G) dan setiap edge pada − D[G] termasuk ke dalam satu cycle. 4. Suatu edge vw pada graph terhubung H adalah suatu jembatan jika dan hanya jika tidak ada suatu cycle pada H yang terkandung pada v dan w . Di sini tanpa ada sifat umum yang hilang, dapat diasumsikan G terhubung. Oleh karena setiap edge pada − D[G] termasuk ke dalam satu cycle maka berarti − D[G] tidak mempunyai suatu jembatan. Singkatnya oleh sifat 2, G tidak mempunyai titik artikulasi. 5. Mengikuti sifat 1 dan 4 6. Misal S adalah irisan verteks pada − D[G] dengan ukuran minimum. Himpunan S0 = S ∩ V (G1 ) dan S1 = S ∩ V (G1 ) adalah irisan-irisan vertex dari G0 dan G1 , berturut-turut. Maka |S0 |, |S1| ≥ k(G) dan selanjutnya k(− D[G]) ≥ 2k(G). Sebaliknya, misal S sebagai irisan verteks dari G dan S0 dan S1 sebagai himpunan hasil pada G0 dan G1 , berturut-turut. D[G] dan akhirnya Maka S0 dan S1 adalah suatu potongan verteks dari − k(− D[G]) ≤ 2k(G).


26 Graph terhubung G adalah Eulerian jika mempunyai suatu percobaan tertutup yang mengandung seluruh edge pada G. Graph Eulerian dikategorikan sebagai graph terhubung genap, dimana suatu graph genap adalah suatu graph di mana setiap vertexnya mempunyai derajat genap. Suatu graph G adalah Hamiltonian jika mempunyai spanning cycle. Proposisi 4.1.4 : Untuk setiap graph G 6= k1 mempunyai sifat-sifat :

1. Jika G terhubung maka − D[G] adalah Eulerian 2. Jika G Hamiltonian maka − D[G] juga Hamiltonian

Bukti :

1. Rangkap dari suatu graph terhubung adalah dan graph rangkap terhubung yang selalu genap 2. Misal {G0 , G1 } adalah dekomposisi pada − D[G] asumsikan γ sebagai spanning cycle dari G, vw sebagai suatu edge dari γ dan γ sebagai hasil dari path dari γ dengan memindahkan edge vw. Misal γ sebagai hasil path pada G1 , untuk I = 0,1 maka γ 0 ∪ {(w, 0), (v, 1)} ∪ γ 1 ∪ {(w, 1), (v, 0)} adalah spanning cycle pada − D[G]

Proposisi 4.1.5 : Untuk setiap graph G1 dan G2 mempunyai sifat-sifat :

1. − D[G1 × G2 ] = G1 × − D[G2 ] = − D[G1 ] × G2 2. − D[G1 ◦ G1 ] = G1 ◦ − D[G2 ]


27 Bukti : Identitas berikut adalah konsekuensi dari sifat asosiatif pada direct produk dua graph dan pada lexikograhikal produk, berturut-turut. Dari definisi graph rangkap didapat bahwa :

Proposisi 4.1.6. : Misal A adalah matrix adjacency pada G. Maka matriks A A 1 1 adjacency − D[G] adalah − D[A] = A A = A × 1 1 . Rank pada graph G ditulis r(G) adalah rank matriks adjacency itu sendiri, maka dari proposisi di atas diperolah :

Proposisi 4.1.6.: Untuk setiap graph G, r(− D[G]) = r(G) Pada bagian ini akan digunakan sifat bahwa dua graph adalah isomorphik jika dan hanya jika matriks adjecencynya identik dengan pengertian dari matriks permutasi. Misalkan G1 dan G2 adalah dua graph. Penjumlahan G1 G2 pada G1 dan G2 adalah disjoin gabungan dari dua graph. Penjumlahan seluruhnya G1 + G2 dari G1 dan G2 adalah graph yang diperoleh dari G1 + G2 dengan menggabungkan setiap vertex dari G1 ke setiap vertex dari G2 .Suatu graph adalah dekompos/tidak digunakan jika dapat dinyatakan sebagai penjumlahan dan penjumlahan seluruhnya pada vertex terisolasi.

Proposisi 4.1.7. : Untuk setiap graph G1 dan G2 mempunyai sifat-sifat : 1. − D[G1 + G2 ] = − D[G1 ] + − D[G2 ] 2. − D[G1 G2 ] = − D[G1 ] + − D[G2 ]


28 3. Rangkap pada graph dekomposible adalah dekomposible.

Bukti : dua sifat pertama dapat dibuktikan sebagai berikut. Misalkan A1 dan A2 merupakan matriks adjacency pada graph G1 dan G2 beturut-turut, maka. Maka A1 X X A adalah matriks adjacency dari G1 +G2, dimana X adalah matriks nol O 2

dan dari G1 + G2 dimana X adalah matriks J yang mana entri seluruh elemennya adalah 1. Maka matrik adjacency dari graph rangkap adalah : 

A1 X A 1 X

X A2 X A2

A1 X A1 X

 X A2 X A2

Perubahan pertama terjadi pada kolom kedua dan ketiga lalu baris kedua dan ketiga, pada matriks :



A1 A1 X X

A1 A1 X X

X X A2 A2

 X X A2 A2

D[G2 ] dimana X = 0 dan − D[G1] + Yang merupakan matrix adjecency − D[G1 ] + − − D[G2] dimana X = J. Sifat-sifat ini juga secara langsung oleh hokum distributif pada lexikographik produk Akhirnya ketiga sifat tersebut menunjukkan bahwa − D menghasilkan penjumlahan dan penjumlahan seluruhnya dan − D[K1 ] = N2 = K1 + K2 .

Contoh 1. Jika Nn adalah graph dengan vertexnya tanpa edge maka − D[Nn ] = N2n Contoh 2. Misalkan Km,n adalah graph bipartit, maka − D[Km,n ] = − D[Nm + Nn ] = D[Nn ] = N2m +N2n = K2m,2n , Singkatnya, jika Km1 ,m2 ,...,mn adalah − D[Nm ]+− graph komplet n -partisi, terdapat − D[Km1 ,m2 ,...,mn . Dalam keadaan khusus,


29 D[Km(n) ] = jika Km(n) adalah graph komplet m - partisi Kn,...,n , maka − Km(2n) . Oleh karena Kn = Kn(1) hal itu mengakibatkan bahwa rangkap dari graph Kn adalah graph Hyperoctahedral Hn = Kn(2) Contoh 3. Untuk n ≥ 2, misal Kn− graph yang dihasilkan oleh pengurangan tiap edge D[Kn− ] = − D[N2 ] + − D[Kn−2 ] = graph Kn , maka Kn− = N2 + Kn−1 dan − D[Kn− ] = K4,2,...,2. N4 + Hn−2 yang bahwa − Contoh 4. Misal G adalah suatu grup dan misal Ω adalah himpunan dari pembangkit untuk G saat (i) jika x ∈ Ω maka x−1 ∈ Ω, dan (ii) 1 6∈ Ω. Graph Cayley Cay (G, Ω) adalah graph sederhana yang vertexnya adalah elemen-elemen dari G dan dimana x adj y jika dan hanya jika x−1 y ∈ Ω sekarang asumsikan C2 sebagai suatu grup siklik pada orde 2, maka Cay (G × C2, Ω × C2 ) = − D[(Cay(G, Ω)]

Suatu graph adalah bersirkulasi dimana batasan matriks A itu sendiri bersirkulasi, misalnya disaat setiap barisan berbeda dari pertama, yang diperoleh terlebih dahulu dengan merubah setiap barisan berbeda dari yang pertama, yang diperoleh terlebih dahulu dengan merubah setiap elemen satu posisi ke kanan. Ambil C(a1, . . . , an ) sebagai graph bersikulasi dimana (a1, . . . , an ) adalah baris pertama dari matrix Adjecency (untuk vertex yang sesuai).

Proposisi 4.1.8. Suatu graph G adalah sirkulan jika dan hanya jka − D(G) juga D(G) = sirkulan. Dalam keadaan khusus − D[Ca1,...,n ) = C(a1,...,n,a1,...,n ). MIsal − G × K2 sebagai rangkap canonical dari G


30 Proposisi 4.1.9. − D dan R komutatif − D[R(G)] = − D[R(G)] = R[R(G)] untuk setiap graph G. Bukti. Sifat assisiatif dan kumutatif dari direct produk mengakibatkan bahwa D[R(G)] = R(G) × T2 = G × K2 × T2 = G × T2 × K2 = D(G) × K2 = R[D(G)] Mi¯ adalah komplemen dari G. sal γ(G)G×T2 yang rangkap strong dari G, dan misal G

Proposisi 4.1.10. Untuk setiap graph G, D(G) = γ(G). Bukti. Jika A adalah matriks adjacency dari graph G, matriks adjacency dari γ(G) adalah

A I+A A(γ(G)) = I + A A , maka : " J − I − A J − I − A# ¯ A(G) ¯ A( G) A I+A ¯ A(D(G) = = J −I − I + A ¯ A(G) ¯ = A , A(G) J −I −A J −I −A

¯ = J − I − A(γ(G)) = AD(G) Jadi proposisi benar. maka : A(DG)


BAB 5 KESIMPULAN

Berdasarkan hasil penelitian, dapat ditarik beberapa kesimpulan sebagai berikut :

a Graph merupakan cabang matematika yang bentuk dan modelnya sangat bervariasi dan cocok untuk aplikasi yang luas, b Graph rangkap diperoleh dari direct produk dua graph sederhana dimana salah satunya adalah graph komplit dengan 2 verteks. c Graph rangkap tidak saja menarik untuk dianalisis lebih jauh, namun juga sangat memungkinkan untuk diaplikasikan pada bidang-bidang lain.


DAFTAR PUSTAKA

Brualdi, R.A dan Ryser, HJ.1991. Combinatorial Matrices Theory. Cambridge. Cambridge University Press Cameron, J Peter, 2006, Graph Homomorphisms, Combinatorics Study Group Notes. Gravier, S and Kheladi, A. 1995. On The Dominating Number of Cross Products of Graphs, Discrete Math, 145 (273 -277). Hagauer, Johann. 1996. On Independence Number of the Cartesian Product Graphs. ARS Combinatorial 43, pp 149 -157. Maria Corinna Marino and Norma Zagaglia Salvi, 2007. Generalizing Double Graphs. Atti dellAccademia Peloritana dei Pericolanti Classe di Scienze Fisiche, Matemamatiche e Naturali Vol. LXXXV, CIA0702002 (2007). Munarini, E., Claudio Perelli Cippo, Andre Scagiola, Norma Zagaglia Salvi, 2007. Double Graphs, Discrete Math. 308(2008) 242 - 254 . Murray, M. Richard and Jin, Zhipu, 2003. Stability and performence Analysis with Duoble-Graph Model of Vehicle Formations. Division of Enginering and Apl. Sci. California Institute of Technology Pasadena, CA. 91125. Ruji, Huang. 1994. Modified Double - Graph Decomposition Analysis for Finding Symbolic Network Function. Beijing University of Science and Technology, Beijing 100085. Scagliola, A. 2006. On Double Graph. Dip. Matematica Politecnico di Milano P.zzal L da Vinci, 32 20133 Milano.


ANALISIS TENTANG GRAPH RANGKAP

Recommend Documents