PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI

DOMINASI DALAM GRAF

MAKALAH

Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika

Disusun Oleh : I Gusti Bagus Yosia Wiryakusuma 103114006

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS SANATA DHARMA YOGYAKARTA 2015

i


DOMINATION IN GRAPHS

PAPER

Presented as Partial Fulfillment of the Requirements to Obtain the Degree of Sarjana Sains in Mathematics Study Program

By : I Gusti Bagus Yosia W 103114006

MATHEMATICS STUDY PROGRAM DEPARTMENT OF MATHEMATICS FACULTY OF SCIENCE AND TECHNOLOGY SANATA DHARMA UNIVERSITY YOGYAKARTA 2015

ii


iii


iv


HALAMAN PERSEMBAHAN “Ora et labora” -Mother Teresa-

“Dan apa saja yang kamu minta dalam doa dengan penuh kepercayaan, kamu akan menerimanya” -Matius 21:22-

“Seorang prajurit yang sedang berjuang tidak memusingkan dirinya dengan soalsoal penghidupannya, supaya dengan demikian ia berkenan kepada komandannya” -2 Timotius 2:4-

“Jagalah hatimu dengan segala kewaspadaan, karena dari situlah terpancar kehidupan” -Amsal 4:23-

Tugas akhir ini kupersembahkan untuk: Tuhan Yesus Kristus, Kedua orangtua, I G. N. Wiryawan B. dan Debora Ratnawati Y., Adik-adikku, I G. A. Gracia W. dan I G. N. Yonatan W., Khusfika Stifani, Dan teman-teman Matematika 2010 USD.

v


vi


vii


ABSTRAK

I Gusti Bagus Yosia Wiryakusuma. 2015. Dominasi Dalam Graf. Makalah. Program Studi Matematika, Jurusan Matemaika, Fakultas Sains dan Teknologi, Universitas Sanata Dharma, Yogyakarta. Dominasi dalam graf merupakan salah satu cabang ilmu dalam teori graf yang mempelajari tentang himpunan yang mendominasi, atau dengan kata lain dominasi dalam graf mempelajari banyaknya titik yang dapat mendominasi graf tersebut. Himpunan yang mendominasi terdiri dari beberapa bagian, seperti himpunan yang mendominasi minimum dan himpunan yang mendominasi bebas. Dalam penerapannya, dominasi dalam graf merupakan cara untuk meletakkan titik-titik penting dalam suatu graf yang melambangkan hubungan antar kota, seperti meletakkan fasilitas-fasilitas kesehatan dalam suatu provinsi atau kabupaten. Kata kunci : graf, teori graf, dominasi, himpunan yang mendominasi

viii


ABSTRACT

I Gusti Bagus Yosia Wiryakusuma. 2015. Domination In Graphs. A Paper. Mathematics Study Program, Department of Mathematics, Faculty of Science and Technology, Sanata Dharma University, Yogyakarta. Domination in graph is one branch of graph theory that studies on the dominating set, or in other words the domination in graph learn the number of vertices that can dominate the graph. The dominating set consists of several parts, such as minimum dominating set and independent dominating set. In its application, domination in graph is a way to put the important vertices in a graph which symbolizes the relationship between the city, such as putting the health facilities in a province or district. Keywords : graph, graph theory, domination, dominating set

ix


KATA PENGANTAR Puji dan syukur kepada Tuhan Yang Maha Esa atas berkat-Nya sehingga tugas akhir ini dapat diselesaikan dengan baik. Banyak tantangan dalam penyelesaian tugas akhir ini, namun atas berkat dan rahmat-Nya, dan dukungan dari berbagai pihak, akhirnya tugas akhir ini bisa diselesaikan dengan baik. Pada kesempatan ini, penulis ingin mengucapkan terima kasih atas segala bimbingan dan dukungan kepada: 1. Ibu Maria Vianney Any Herawati, S.Si., M.Si. selaku Dosen Pembimbing Tugas Akhir. 2. Bapak Y. G. Hartono, Ph.D. selaku Ketua Program Studi Matematika Universitas Sanata Dharma dan Dosen Penguji Tugas Akhir. 3. Bapak Ir. Ig. Aris Dwiatmoko, M.Sc. selaku Dosen Pembimbing Akademik dan Dosen Penguji Tugas Akhir. 4. Ibu Paulina Heruningsih Prima Rosa, S.Si., M.Sc. selaku Dekan Fakultas Sains dan Teknologi Universitas Sanata Dharma. 5. Bapak dan Ibu Dosen Program Studi Matematika Universitas Sanata Dharma. 6. Keluarga tercinta, kedua orangtuaku, I G. N. Wiryawan B. dan Debora Ratnawati Y., kedua adikku, I G. A. Gracia W. dan I G. N. Yonatan W. 7. Khusfika Stifani yang selalu mendukung dengan kasih.

x


8. Teman-teman Matematika 2010 USD, Arga, Ayu, Celly, Tika, Agnes, Roy, Ratri, Yohan, Pandu, Sari, Leny, Astri, Marsel, Dini. 9. Kakak-kakak angkatan 2006, 2007, 2008, 2009, dan adik-adik angkatan 2011, 2012, 2013, 2014. 10. Semua pihak yang membantu penulis dalam menyelesaikan tugas akhir ini yang tidak dapat disebutkan satu per satu. Penulis menyadari masih banyak kekurangan dalam tugas akhir ini. Oleh karena itu, penulis mengharapkan kritik dan saran yang dapat membangun dan menyempurnakan tugas akhir ini. Akhirnya, penulis berharap agar tugas akhir ini dapat memberikan wawasan dan pengetahuan bagi pembaca.

Yogyakarta, 20 Januari 2015

Penulis

xi


DAFTAR ISI HALAMAN JUDUL DALAM BAHASA INDONESIA ....................................... i HALAMAN JUDUL DALAM BAHASA INGGRIS ......................................... ii HALAMAN PERSETUJUAN PEMBIMBING .................................................. iii HALAMAN PENGESAHAN .............................................................................. iv HALAMAN PERSEMBAHAN ........................................................................... v PERNYATAAN KEASLIAAN KARYA ............................................................ vi LEMBAR PERSETUJUAN PUBLIKASI KARYA ILMIAH .......................... vii ABSTRAK .......................................................................................................... viii ABSTRACT .......................................................................................................... ix KATA PENGANTAR ........................................................................................... x DAFTAR ISI ........................................................................................................ xii BAB I PENDAHULUAN ..................................................................................... 1 A. Latar Belakang ......................................................................................... 1 B. Rumusan Masalah .................................................................................... 6 C. Batasan Masalah ...................................................................................... 6 D. Tujuan Penulisan ...................................................................................... 6 E. Metode Penulisan ..................................................................................... 7 F. Manfaat .................................................................................................... 7 G. Sistematika Penulisan .............................................................................. 7 BAB II DASAR-DASAR TEORI GRAF ............................................................ 9 A. Teori Graf ................................................................................................ 9 B. Graf Bagian ............................................................................................ 16 C. Macam-macam Graf .............................................................................. 17 D. Operasi Pada Graf .................................................................................. 21

xii


E. Keterhubungan Dalam Graf ................................................................... 30 BAB III DOMINASI DALAM GRAF ............................................................... 32 A. Konsep Dominasi ................................................................................... 32 B. Himpunan Yang Mendominasi .............................................................. 33 C. Himpunan Yang Mendominasi Bebas ................................................... 35 D. Teorema Tentang Dominasi Dalam Graf ............................................... 38 E. Teorema Tentang Bilangan Dominasi Bebas Dari Suatu Graf .............. 54 F. Parameter Dominasi Lainnya ................................................................. 58 G. Aplikasi .................................................................................................. 64 BAB IV PENUTUP ............................................................................................. 68 A. Kesimpulan ............................................................................................ 68 B. Saran ...................................................................................................... 70 DAFTAR PUSTAKA .......................................................................................... 71

xiii


BAB I PENDAHULUAN

Pada bab ini akan dibahas tentang latar belakang, perumusan masalah, serta tujuan, metode dan manfaat penulisan makalah, selain itu juga akan dibahas mengenai sistematika penulisan.

A. LATAR BELAKANG Dominasi dalam bahasa Indonesia mempunyai arti penguasaan oleh pihak yang lebih kuat terhadap yang lebih lemah, atau secara umum dapat diartikan sebagai penguasaan atas seseorang ataupun suatu hal. Demikian pula pengertian dominasi dalam kehidupan sehari-hari adalah penguasaan pihak yang kuat terhadap pihak yang lebih lemah, contohnya dominasi dalam suatu turnamen pertandingan sepak bola. Tim yang kuat akan lebih menguasai jalannya suatu pertandingan dibandingkan tim yang lemah. Konsep dominasi tersebut juga dapat ditemukan dalam ilmu matematika, yaitu dalam teori graf. Menurut catatan sejarah, pada tahun 1736, masalah jembatan Königsberg adalah masalah yang pertama kali diselesaikan dengan menggunakan graf. Di kota Königsberg yang berada di Jerman, terdapat sungai Pregal yang mengalir melalui kota tersebut. Sungai Pregal tersebut mengitari pulau Kneiphof lalu bercabang menjadi 2 buah anak sungai. Di kota Königsberg terdapat 7 buah jembatan yang menghubungkan daratan yang terbelah oleh sungai Pregal. Pada jaman itu, penduduk kota mencoba berpikir apakah mungkin melalui ketujuh jembatan

1


tersebut hanya dengan sekali jalan tanpa melalui jembatan yang sama. Sebagian penduduk berpikir bahwa tidak mungkin melalui ketujuh jembatan tersebut hanya dengan sekali jalan tanpa melalui jembatan yang sama. Namun, mereka tidak dapat menjelaskan alasannya, selain dengan cara coba-coba melalui ketujuh jembatan tersebut. Pada tahun 1736, Leonhard Euler, seorang matematikawan Swiss berhasil menyelesaikan masalah tersebut dengan menggunakan graf dan didapatkan kesimpulan bahwa tidak mungkin melalui ketujuh jembatan tersebut hanya dengan sekali jalan tanpa melalui jembatan yang sama.

Gambar 1.1

Hubungan antar titik atau dalam ilmu matematika yang sering disebut dengan teori graf sebenarnya sudah sering ditemukan dalam kehidupan seharihari. Salah satu contoh penerapan teori graf dalam kehidupan sehari-hari adalah dibangunnya suatu jalan besar (highway) yang menghubungkan beberapa kota. Penerapan ini mengaplikasikan teori graf untuk menjelaskan hubungan antar titik, misalnya tentang jalur antar kota dengan jarak terpendek, pengambilan keputusan untuk membangun pusat-pusat layanan masyarakat.

2


Teori graf memiliki beberapa bagian seperti dominasi dalam graf. Pada tahun 1958, Claude Berge memperkenalkan bilangan dominasi dalam graf. Sebuah graf

merupakan himpunan yang elemen-elemenya disebut dengan titik

(node/vertex) yang dihubungkan oleh garis-garis yang disebut rusuk (edge). Sebuah titik

dikatakan berhubungan dengan titik

jika ada suatu ruas garis

yang menghubungkan kedua titik tersebut. Dalam graf

, sebuah himpunan

adalah himpunan yang mendominasi (dominating set) jika setiap titik yang berada di himpunan

, berada di himpunan

suatu titik dalam himpunan , dimana

atau berhubungan dengan

merupakan himpunan titik-titik dari

suatu graf. Bilangan dominasi (domination number)

adalah kardinalitas

terkecil dari sebuah himpunan yang mendominasi. Dimana kardinalitas sebuah himpunan berhingga adalah banyaknya anggota dalam himpunan tersebut. Penerapan dominasi dalam graf dalam kehidupan sehari-hari sering dijumpai dalam masyarakat. Sebagai contoh adalah penempatan satpam dalam sebuah museum. Demi menjaga lukisan-lukisan yang berharga, maka pihak keamanan museum akan menempatkan satpam di ruang pameran dalam berbagai macam variasi tempat. Sebagai asumsi seorang satpam dapat mengawasi lorong yang menuju tempat lukisan dipamerkan dari tempat ia berada. Rumusan masalah yang dapat diambil dari kasus tersebut adalah berapa jumlah satpam minimal yang harus ditempatkan dalam ruang pameran lukisan namun tidak mengurangi tingkat keamanan ruangan? Dalam kasus ini, dominasi seorang satpam dalam mengawasi atau menguasai beberapa lorong dalam gedung tersebut sangat diperlukan. Pemikiran minimalisasi jumlah satpam yang digunakan dapat menekan biaya

3


operasional dari museum sehingga manfaat dari aplikasi dominasi dalam graf dapat dirasakan langsung dalam kehidupan sehari-hari.

Gambar 1.1 Misalkan titik

,

, ,

dan

adalah titik-titik dimana satpam harus

ditempatkan, dan garis-garis yang menghubungkan titik-titik tersebut merupakan lorong-lorong yang harus diperhatikan oleh satpam. Dengan menggunakan teori graf, didapatkan bahwa minimal diperlukan tiga orang satpam untuk ditempatkan pada titik-titik tersebut. Misalkan tiga orang satpam tersebut ditempatkan di titik ,

dan

, maka satpam di titik

menghubungkan titik satpam di titik dengan titik

dapat memperhatikan lorong yang

dengan titik

dan titik

dengan titik

, sedangkan

dapat memperhatikan lorong yang menghubungkan titik dan titik

dengan titik

, sehingga satpam di titik

memperhatikan lorong yang menghubungkan titik

dengan titik

dapat

dan titik

dengan titik . Contoh lain dalam penggunaan dominasi dalam graf adalah penempatan fasilitas kesehatan dalam beberapa kota. Andaikan sebuah kabupaten yang memiliki beberapa kota yang dihubungkan oleh jalan besar (highway) ingin membangun fasilitas kesehatan dengan biaya seminimal mungkin tetapi dapat memenuhi semua kebutuhan kota-kota yang terdapat dalam kabupaten tersebut.

4


Maka berapa jumlah minimal kota yang harus dibangun fasilitas kesehatan dan di kota mana saja harus di bangun fasilitas tersebut?

Gambar 1.2 Misalkan titik , , , , , ,

dan

melambangkan delapan kota besar

dalam kabupaten tersebut yang dihubungkan oleh jalan-jalan besar (highway) seperti pada gambar. Dengan menggunakan dominasi dalam graf, persoalan tersebut akan lebih mudah ditemukan solusinya. Dengan membangun fasilitas kesehatan di kota kota

dan , maka kebutuhan semua kota akan dapat dipenuhi. Dari

, fasilitas kesehatan tersebut dapat mengirimkan bantuan ke kota

sendiri, ke kota ,

itu

dan . Sedangkan dari kota , fasilitas kesehatan tersebut

dapat menjangkau kota

,

,

dan kota

itu sendiri. Sehingga banyaknya

fasilitas kesehatan yang dapat dibangun seminimal mungkin ada dua, yaitu ditempatkan di kota

dan . Praktisnya, dominasi dalam graf dalam kasus ini,

digunakan untuk meminimalkan jumlah kota yang harus dibangun fasilitas kesehatan. Berdasar uraian di atas, dalam tugas akhir ini akan dibahas tentang dominasi dalam graf beserta sifat-sifatnya dan penerapannya dalam kehidupan sehari-hari.

5


B. RUMUSAN MASALAH Pokok permasalahan yang akan dibahas dalam tulisan ini yaitu: 1. Apa yang dimaksud dengan dominasi dalam graf dan bagaimana contoh penerapan dari dominasi dalam graf? 2. Sifat-sifat apa sajakah yang berlaku dalam masalah dominasi dalam graf dan bagaimana pembuktiannya? 3. Apa saja yang menjadi parameter dominasi dan hubungan masing-masing parameter tersebut?

C. PEMBATASAN MASALAH Konsep-konsep yang akan dibahas dalam tulisan ini adalah konsep mengenai dominasi dalam graf beserta sifat-sifatnya sampai dengan penerapannya, sedangkan hal-hal di luar topik tersebut, seperti fungsi yang mendominasi, dominasi kompleks, dan frameworks of domination tidak dibahas.

D. TUJUAN PENULISAN Tujuan dari penulisan tugas akhir ini yaitu: 1. Mengetahui apa yang dimaksud dengan dominasi dalam graf beserta penerapannya. 2. Mengetahui sifat-sifat yang berlaku dalam dominasi dalam graf beserta buktinya.

6


3. Mengetahui parameter dominasi dan hubungan masing-masing parameter tersebut.

E. METODE PENULISAN Metode yang digunakan penulis adalah metode studi pustaka dengan mempelajari buku-buku yang berkaitan dengan konsep-konsep dominasi dalam graf dan penerapannya.

F. MANFAAT PENULISAN Manfaat penulisan makalah ini adalah memperoleh pengetahuan mengenai konsep-konsep dominasi dalam graf dan penerapannya dalam bidang di luar matematika.

G. SISTEMATIKA PENULISAN BAB I PENDAHULUAN H. Latar Belakang I. Rumusan Masalah J. Batasan Masalah K. Tujuan Penulisan L. Metode Penulisan M. Manfaat N. Sistematika Penulisan

7


BAB II DASAR-DASAR TEORI GRAF F. Teori Graf G. Graf Bagian H. Macam-macam Graf I. Operasi Pada Graf J. Keterhubungan Dalam Graf BAB III DOMINASI DALAM GRAF H. Konsep Dominasi I. Himpunan Yang Mendominasi J. Himpunan Yang Mendominasi Bebas K. Teorema Tentang Dominasi Dalam Graf L. Teorema Tentang Bilangan Dominasi Bebas Dari Suatu Graf M. Parameter Dominasi Lainnya N. Aplikasi BAB IV PENUTUP C. Kesimpulan D. Saran

8


BAB II DASAR-DASAR TEORI GRAF

A. TEORI GRAF Definisi 2.1 Graf

didefinisikan sebagai pasangan himpunan

, yang dalam hal

ini

adalah himpunan tidak kosong dari titik-titik, yaitu {

dan

adalah himpunan rusuk yang menghubungkan sepasang titik, yaitu

{

}, atau dapat ditulis dengan notasi

menghubungkan titik

dan

maka dapat ditulis

Contoh 2.1 Gambar 2.1 menyatakan graf {

dengan:

}

{

}

Gambar 2.1

9

}

. Bila rusuk .


Definisi 2.2 Dua buah titik pada graf

dikatakan berhubungan bila keduanya

terhubung langsung oleh suatu rusuk. Untuk sebarang rusuk

, rusuk

dikatakan bersisian dengan titik

dan titik .

Contoh 2.2 Pada gambar 2.1, titik

berhubungan dengan titik , tetapi titik

tidak

berhubungan dengan titik .

Definisi 2.3 Misalkan kardinalitas dari

dan

adalah himpunan titik-titik dalam graf

didefinisikan sebagai banyaknya titik dalam

,

, dan

dinotasikan dengan | |.

Contoh 2.3 Pada gambar 2.1 kardinalitas dari

adalah 8 atau | |

.

Definisi 2.4 Misal

adalah graf,

dan

adalah titik-titik dalam graf

dari

didefinisikan sebagai barisan titik-titik dan rusuk-rusuk yang

10

, jalan


dimulai dari

dan diakhiri dengan

sedemikian sehingga titik-titik dan

rusuk-rusuk yang berurutan saling bersisian. Sebuah jalan tanpa titik yang berulang disebut lintasan dan lintasan yang menghubungkan titik

dan

disebut lintasan

.

Lintasan tertutup atau siklus adalah lintasan yang dimulai dari diakhiri dengan .

Contoh 2.4 Pada gambar 2.1, jalan

Sedangkan lintasan

beberapa diantaranya adalah:

adalah

Siklus dari gambar 2.1 salah satunya adalah

11

dan


Definisi 2.5 Suatu fungsi jika

disebut fungsi one-to-one (satu-satu) jika hanya ,

.

Contoh 2.5 Misal

dengan

{

} dan

{

}, yang

didefinisikan dengan

maka fungsi

merupakan fungsi yang one-to-one.

Definisi 2.6 Suatu fungsi ,

disebut fungsi onto jika hanya jika

,

.

Contoh 2.6 Misal

dengan

{

didefinisikan dengan

12

} dan

{

}, yang


maka fungsi

merupakan fungsi yang onto.

Definisi 2.7 Graf

dan

dikatakan isomorfis, dinotasikan dengan

, jika

terdapat fungsi satu-satu (one-to-one) dan onto sedemikian hingga setiap pasangan titik jika dan hanya jika

dan

dan

berhubungan dalam

berhubungan dalam

memenuhi syarat tersebut disebut isomorfisma dari

ke

. Fungsi

yang

.

Contoh 2.7

Gambar 2.2 Graf

dan

pada gambar 2.2 merupakan graf yang isomorfis.Dengan

,

,

,

, dan

,

,

, dan

13

.

atau

,


Definisi 2.8 Misalkan

adalah suatu titik dalam graf

, derajat dari titik

atau

adalah banyaknya rusuk yang bersisian dengan titik . Sedangkan derajat minimum dinotasikan dengan terkecil dari titik-titik dalam

adalah derajat

dan derajat maksimum dinotasikan dengan

adalah derajat terbesar dari titik-titik dalam .

Contoh 2.8 Pada gambar 2.1 didapatkan

Sehingga

dan

.


adalah suatu titik dalam graf ,

memiliki derajat satu. Dan

merupakan titik ujung jika

merupakan titik terasing jika

derajat nol.

14

memiliki


Contoh 2.9

Gambar 2.3 Dari gambar 2.3 didapatkan dari graf tersebut, dan

, maka titik , maka titik

adalah titik ujung

merupakan titik terasing.


adalah graf. Graf

untuk setiap titik

dan

merupakan graf terhubung bila hanya bila

di , ada jalan dari titik

ke titik .

Contoh 2.10

Gambar 2.4 Graf

merupakan graf terhubung, sedangkan graf

terhubung.

15

merupakan graf tidak


B. GRAF BAGIAN Definisi 2.11 Misal

adalah graf dengan himpunan titik

, suatu graf

disebut graf bagian dari

dan untuk setiap

, titik

dan himpunan rusuk jika dan

dan berada di

.

Contoh 2.11

Gambar 2.5 Gambar 2.5 merupakan beberapa graf bagian dari graf dalam gambar 2.1.

16


Definisi 2.12 , maka graf bagian yang diinduksi oleh , dinotasikan 〈 〉,

Jika

adalah graf bagian yang berisi titik-titik dalam berbentuk

dalam , dimana

dan

dan semua rusuk yang

.

Contoh 2.12 Dari 〈 〉

gambar

2.1,

{

{

misal

},

maka

}.

C. MACAM-MACAM GRAF Definisi 2.13 Suatu graf

disebut graf bipartit jika

himpunan bagian tak kosong rusuk dalam

, maka titik

dan dan

dapat dipartisi menjadi dua

, sedemikian hingga jika

adalah

berada pada himpunan bagian yang

berbeda.

Contoh 2.13

Gambar 2.6 Gambar 2.6 merupakan graf bipartit dengan {

}.

17

{

} dan


Definisi 2.14 Graf lengkap

adalah graf yang memiliki

titik dan setiap setiap titik

dihubungkan satu sama lain oleh sebuah rusuk. Graf lengkap

disebut

juga graf trivial.

Contoh 2.14

Gambar 2.7 Gambar 2.7 merupakan beberapa contoh graf lengkap.

Definisi 2.15 Graf bipartit lengkap

adalah graf yang himpunan titiknya dapat

dipartisi menjadi himpunan tak kosong berturut-turut

dan

dan

dengan kardinalitas

, sedemikian sehingga setiap titik di himpunan

berhubungan dengan setiap titik di himpunan keterhubungan lainnya.

18

dan tidak ada


Contoh 2.15

Gambar 2.8

Definisi 2.16 Graf bintang

adalah graf bipartit lengkap yang memuat satu titik

dengan derajat , dan titik lainnya berderajat satu yang berarti merupakan titik ujung.

Contoh 2.16

Gambar 2.9

Definisi 2.17 Untuk

, graf siklus yang dinotasikan

titik.

19

adalah suatu siklus dengan


Contoh 2.17

Gambar 2.10 Gambar 2.10 merupakan beberapa contoh dari graf siklus.

Definisi 2.18 Graf lintasan dengan

titik, dinotasikan

adalah lintasan dengan

titik.

disebut graf bebas-F jika graf

tidak

Contoh 2.18

Gambar 2.11

Definisi 2.19 Misal

adalah graf. Suatu graf

memuat graf bagian yang diinduksi secara isomorfis oleh .

20


Contoh 2.19

Gambar 2.12 Dalam gambar 2.12, graf

bukan graf bebas- . Sedangkan graf

merupakan graf bebas- . Graf bebas-

disebut juga graf bebas-cakar. Graf

dan graf

merupakan beberapa contoh graf bebas-cakar.

D. OPERASI PADA GRAF 1. GABUNGAN DAN PENGGABUNGAN Definisi 2.20 Jika

dan

adalah dua graf yang tidak terhubung, gabungan

adalah graf dengan . Maka, salinan dari

dan memuat salinan dari

.

21

bersama dengan


Contoh 2.20

Gambar 2.13

Definisi 2.21 Jika

dan

adalah dua graf yang tidak terhubung, penggabungan

terbentuk dengan menambahkan rusuk pada setiap titik sedemikian hingga setiap titik . Jika ditambahkan

dan

memiliki

berhubungan dengan setiap titik dan

titik, maka graf

rusuk.

Contoh 2.21

Gambar 2.14

22

harus


Definisi 2.22 Untuk

, roda

yang berarti

adalah penggabungan dari

dengan

,

.

Contoh 2.22

Gambar 2.15

Definisi 2.23 Misal

adalah graf, barisan penggabungan adalah graf yang terbentuk dengan mengambil satu tiruan dari

setiap graf

dan menambahkan rusuk dari setiap titik pada

dihubungkan pada setiap titik pada

Contoh 2.23

Gambar 2.16 23

, untuk

.


2. KOMPLEMEN Definisi 2.24 Komplemen

̅ dari suatu graf

̅ jika hanya jika

̅

memiliki

dan

.

Contoh 2.24

̅ Gambar 2.17

3. FAKTORISASI Definisi 2.25 Suatu

graf

dapat

difaktorkan

dengan

sepasang-sepasang ⋃

. Jika

jika saling

dapat difaktorkan atas

hal tersebut dinotasikan dengan faktorisasi dari

24

asing

dan , maka

, yang disebut


Contoh 2.25

Gambar 2.18 Gambar 2.18 merupakan contoh dari

.

4. PRODUK KARTESIUS Misal

dan

{

adalah graf dengan himpunan titik-titik

} dan {

}, produk kartesius

adalah

graf dengan himpunan titik yang memuat

titik-titik yang diberi

label

. Dua titik

, dimana

dan

berhubungan dalam

jika

1.

dan

berhubungan dengan

dalam graf

2.

dan

berhubungan dengan

dalam graf .

Setiap titik tua” , yaitu

yang diinduksi oleh {

, atau

dapat dipandang memiliki dua “orang

dari dalam

dan

dan |

dalam

. Untuk setiap , graf bagian } disebut tiruan ke- dari

.

Dengan cara yang sama, untuk setiap , graf bagian yang diinduksi oleh {

|

} disebut tiruan ke- dari

25

. Gambar 2.19


memperlihatkan graf

,

dan produk kartesius

.

Gambar 2.19 Graf dari graf

dalam gambar 2.19 dapat dilihat sebagai tiga graf tiruan yang berkorespondensi dengan tiga titik dalam graf

kira seperti meletakan titik-titik dari

. Kira-

pada tiruan graf . Setiap tiruan

memiliki koordinat tetap kedua (lihat gambar 2.19). Titik-titik dalam tiruan

yang

pertama

berhubungan

berkorespondensi dari graf tiruan dengan

dalam

dengan

titik-titik

yang kedua, karena

yang

berhubungan

. Dengan cara yang mirip, titik-titik dalam tiruan

yang kedua berhubungan dengan titik-titik yang berkorespondensi dari graf tiruan

yang ketiga, karena

berhubungan dengan

Selain itu, titik-titik yang berkorespondensi dalam tiruan dan ketiga tidak saling berhubungan karena dalam

dan

dalam

.

yang pertama

tidak berhubungan

.

Paragraf sebelumnya dapat ditulis ulang dengan sedikit penyesuaian jika pandangan terhadap graf tersebut diubah dengan mulai dengan empat

26


graf tiruan

. Terdapat empat graf

, yang setiap graf tersebut

dikarakterisasi oleh koordinat tetap yang pertama. Dalam faktanya, dan

adalah isomorfis untuk setiap dua graf

dan

, perbedaannya

hanya pada penamaannya. Dapat dilihat juga bahwa produk kartesius memiliki sifat asosiatif, yaitu tiga graf ,

untuk setiap

dan .

5. JALA Salah satu graf yang dapat dibentuk menggunakan produk kartesius adalah jala, yang juga disebut jaringan atau kisi. Graf sama dengan produk kartesius dari . Graf dengan

dan

dengan

, yang berarti

sama dengan produk kartesius dari . Sehingga

,

karena produk kartesius bersifat asosiatif. Graf ini dapat diperluas menjadi . Graf

adalah produk kartesius dari

lintasan dengan urutan . Graf jala

, dan diperlihatkan pada gambar 2.20, dengan empat

titik yang berderajat 2 diberi label.

27


Gambar 2.20 Graf 3-jala

diperlihatkan pada gambar 2.21 dengan

beberapa titik berlabel. Graf 3-jala

yang umum dapat dilihat

sebagai garasi dengan beberapa lantai, tepatnya c lantai. Koordinat ketiga mengidentifikasi banyaknya lantai. Setiap lantai adalah graf 2-jala dengan baris dan

kolom.

Gambar 2.21

6. GRAF RUSUK Definisi 2.26 Untuk suatu graf

, graf rusuk

memiliki himpunan titik yang

terdiri atas rusuk-rusuk dari . Dua titik dalam

28

berhubungan jika


rusuk-rusuk yang berkorespondensi di

bersisian dengan titik yang

sama dalam .

Contoh 2.26

Gambar 2.22

7. PENGHAPUSAN RUSUK ATAU TITIK Definisi 2.27 Jika

adalah titik dalam , graf

dengan menghapus titik

adalah graf yang terbentuk dari

dan semua rusuk yang bersisian dengan .

Contoh 2.27

Gambar 2.23

29


Definisi 2.28 Jika

adalah rusuk dalam

, graf

dari

dengan menghapus rusuk .

adalah graf yang terbentuk

Contoh 2.28

Gambar 2.24

E. KETERHUBUNGAN DALAM GRAF Definisi 2.29 Misal graf

terhubung. Keterhubungan titik dalam suatu graf

,

dinotasikan

, adalah jumlah minimum titik yang bila dihapus

akan membuat

menjadi tak terhubung atau membuat

trivial.

30

menjadi graf


Contoh 2.29

Gambar 2.25 Dari gambar 2.25, didapatkan menghapus satu titik

. Karena cukup hanya dengan

akan membuat graf tersebut menjadi tak

terhubung.

Definisi 2.30 Misal graf

terhubung. Keterhubungan rusuk dalam suatu graf

,

dinotasikan

, adalah jumlah minimum rusuk yang bila dihapus

akan membuat

menjadi tak terhubung atau membuat

menjadi graf

trivial.

Contoh 2.30 Dari gambar 2.25, didapatkan

. Karena cukup hanya dengan

menghapus satu rusuk akan membuat graf tersebut menjadi tak terhubung, yaitu dengan menghapus rusuk

31

atau

.


BAB III DOMINASI DALAM GRAF

A. KONSEP DOMINASI Contoh dominasi dalam matematika muncul pada tahun 1850 dalam permainan yang disebut masalah n ratu. Dalam permainan catur, sebuah ratu

pada papan catur, diperbolehkan untuk bergerak secara horisontal,

vertikal, maupun diagonal.

dikatakan menyerang

memakan bidak catur dalam posisi . Yang berarti, posisi pada suatu garis lurus terhadap posisi dari

jika

dapat

berada tepat

, baik secara horisontal,

vertikal, maupun diagonal. dalam masalah n ratu, tantangannya adalah meletakan n ratu pada papan catur yang kosong, sehingga masing-masing kotak dari 64 kotak tersebut dapat diserang oleh paling sedikit satu ratu. Ratu-ratu tersebut dikatakan mendominasi semua kotak jika ratu-ratu tersebut dapat menduduki atau menyerang semua kotak, himpunan ratu tersebut adalah himpunan yang mendominasi kotak catur tersebut. Masalahnya adalah untuk menentukan jumlah minimum ratu yang merupakan himpunan yang mendominasi. Jawaban tersebut adalah 5; salah satunya ditunjukan pada gambar 3.1.

32


Gambar 3.1 B. HIMPUNAN YANG MENDOMINASI Konsep dari himpunan yang mendominasi dalam graf tidak didefinisikan secara formal hingga 1958, ketika Berge dalam bukunya yang berjudul “Théorie des Graphes et ses Applications” menulis buku teori graf yang kedua; buku teori graf yang pertama ditulis oleh König dalam bukunya yang berjudul “Theorie der endlichen und unendlichen Graphen” pada tahun 1936.

Definisi 3.1 Sebuah himpunan

yang terdiri dari titik-titik dalam sebuah graf

disebut himpunan yang mendominasi jika setiap titik merupakan anggota dari

atau berhubungan dengan anggota dari

33


Selanjutnya, semua titik di

atau yang berhubungan dengan anggota dari

dikatakan “didominasi” oleh titik-titik di .

Contoh 3.1 Dari gambar 2.1 didapatkan himpunan yang mendominasi beberapa {

diantaranya adalah {

}, {

}, { }, {

}, {

},

}

Definisi 3.2 Himpunan yang mendominasi

disebut himpunan yang mendominasi

minimal jika tidak ada himpunan bagian sejati

yang merupakan

himpunan yang mendominasi. Himpunan yang mendominasi minimum adalah himpunan yang mendominasi yang memiliki kardinalitas terkecil.

Contoh 3.2 Pada gambar 2.1, didapatkan himpunan yang mendominasi minimal {

}, {

}, {

yang mendominasi minimum {

}, {

}, {

}, {

}. dan himpunan

}, {

}, {

}. Sedangkan himpunan

yang mendominasi minimal tapi tidak minimum adalah { {

}, {

}.

34

},


Definisi 3.3 Bilangan dominasi

dalam sebuah graf

adalah kardinalitas dari

himpunan yang mendominasi minimum. Sedangkan bilangan dominasi atas

adalah kardinalitas terbesar dari himpunan-himpunan yang

mendominasi minimal.

Contoh 3.3 Pada gambar 2.1, didapatkan bilangan dominasi

dan

.

C. HIMPUNAN YANG MENDOMINASI BEBAS Dalam subbab sebelumnya dua ratu dalam papan catur dapat saling menyerang jika posisi ratu tersebut dapat dicapai oleh ratu lainnya dalam sekali jalan, sebaliknya jika ratu tersebut tidak berada pada posisi yang dapat dicapai oleh ratu lainnya dalam sekali jalan. Dalam gambar 3.1 dapat dilihat secara jelas bahwa ratu-ratu tersebut dapat saling menyerang satu sama lain. Muncul masalah baru, yaitu untuk menempatkan posisi raturatu tersebut yang tidak dapat saling menyerang satu sama lain dan mendominasi papan catur tersebut. Penempatan posisi ratu yang mungkin dibuat, ditunjukan pada gambar 3.2.

35


Gambar 3.2 Definisi 3.4 Sebuah himpunan bagian

yang berisi titik-titik dalam sebuah graf

disebut himpunan bebas jika tidak ada titik-titik dalam berhubungan. Bilangan bebas dari sebuah graf

yang saling

, dinotasikan

,

adalah kardinalitas terbesar dari himpunan-himpunan bebas dalam graf tersebut.

Contoh 3.4 Dari gambar 2.1, himpunan bebas dari graf tersebut ada 37 himpunan, yaitu { }{ }{ }{ }{ }{ }{ }{ }{ { { {

}{

}{

}{ } {

}{ }{

}{

}{

}{

}{ }{

}{

}, dengan

36

}{ }{ }{ .

}{ }{ }{

}{ |{

}{ }{ }{

}{ }{

} }

}


Dari definisi himpunan yang mendominasi dan himpunan bebas, dapat dibentuk suatu definisi baru dengan menggabungkan kedua definisi tersebut.

Definisi 3.5 Himpunan yang mendominasi

disebut himpunan yang mendominasi

bebas jika titik-titik dalam himpunan yang mendominasi

tidak

berhubungan satu sama lain.

Contoh 3.5 Pada gambar 2.1, didapatkan himpunan yang mendominasi bebas {

}, {

}, {

}, {

}.

Definisi 3.6 Bilangan dominasi bebas

adalah kardinalitas terkecil dari semua

himpunan yang mendominasi bebas.

Contoh 3.6 Pada contoh 3.5 didapatkan

.

37


D. TEOREMA TENTANG DOMINASI DALAM GRAF Berikut ini merupakan hubungan antara bilangan dominasi dengan bilangan bebas

.

Teorema 3.1 Untuk setiap graf ,

.

Bukti Misal

adalah himpunan bebas dari titik dalam

Sehingga

, dimana | |

.

adalah himpunan bebas dengan kardinalitas terbesar. Untuk ,

harus berhubungan dengan suatu titik dalam . Dengan

{ } akan menjadi himpunan bebas yang lebih besar, terjadi

kata lain,

kontradiksi. Sehingga

mendominasi semua titik dalam

. Sehingga

.

Konsep yang berhubungan dengan dominasi adalah penutup titik.

Definisi 3.7 Sebuah penutup titik adalah sebuah himpunan titik-titik di sehingga setiap rusuk dalam dalam dengan

sedemikian

berisisian dengan paling sedikit satu titik

. Kardinalitas terkecil dari penutup titik dalam .

38

dinotasikan


Contoh 3.7

Gambar 3.3 Pada gambar 3.3, didapatkan penutup titiknya adalah {

},

{

},

{

}, { }, {

}, {

}, {

} dengan

}, {

}, {

.

Teorema 3.2 Jika

adalah penutup titik dari , maka

adalah himpunan bebas.

Bukti Misalkan dan terjadi

bukan himpunan bebas. Maka ada pasangan titik

dari

yang berhubungan. Maka kontradiksi

bahwa

bukan penutup titik, adalah

penutup

titik.

Dengan menggunakan teorema 3.2, kardinalitas terkecil penutup titik

dan bilangan bebas

, didapatkan akibat 3.2.

39


Akibat 3.2 Untuk semua graf

dengan

titik,

.

Bukti Misalkan

adalah penutup titik dengan kardinalitas terkecil. Maka

| |

. Dengan teorema 3.2,

bebas. Jadi

, yang berarti bahwa

Selain itu, jika | |

.

adalah sebuah himpunan bebas sedemikian sehingga

, maka

adalah penutup titik. Untuk memahaminya,

ingat bahwa hanya rusuk-rusuk dalam sehingga

adalah sebuah himpunan

yang bersisian dengan

,

adalah penutup titik. Dan mengakibatkan bahwa atau, secara ekuivalen

didapatkan

dan

. Sehingga . Sehingga

.

Teorema 3.3 Untuk setiap graf lengkap graf lengkap

dengan

adalah 1, atau

. Bilangan dominasi dari .

Bukti Menurut definisi 2.14, graf lengkap

adalah graf yang terdiri dari

titik

dan setiap titik dihubungkan satu sama lain oleh sebuah rusuk. Sehingga,

40


semua titik dalam graf tersebut saling berhubungan satu sama lain, sehingga hanya dibutuhkan 1 titik saja untuk mendominasi graf tersebut.

Teorema 3.4 Untuk setiap graf bipartit lengkap asli, maka (

)

dengan

dan

adalah bilangan

.

Bukti Menurut definisi 2.15, graf bipartit lengkap adalah graf yang himpunan titiknya dapat dipartisi menjadi himpunan tak kosong kardinalitas berturut-turut himpunan

dan

keterhubungan lainnya. Ada tiga kemungkinan, yaitu , maka ada

titik yang mendominasi

dengan

, sedemikian sehingga setiap titik di

berhubungan dengan setiap titik di himpunan

. Misal

dan

titik yang mendominasi

dan tidak ada ,

,

titik, dan ada

titik. Karena bilangan dominasi adalah

kardinalitas terkecil dari himpunan yang mendominasi, maka didapatkan bilangan dominasinya

. Dengan cara yang serupa dibuktikan juga untuk

, sehingga bilangan dominasinya adalah didapatkan kesimpulan (

. Untuk

, maka

titik yang mendominasi. Sehingga didapatkan )

41


Teorema 3.5 Untuk

, dan

adalah bilangan asli,

.

Bukti Dalam suatu lintasan, derajat maksimal dari suatu titik dalam lintasan adalah 2, yang berarti bahwa setiap titik dapat mendominasi tidak lebih dari 3 titik, termasuk dirinya sendiri. Sehingga jika lintasan tersebut memiliki

titik,

maka

.

Definisi 3.8 Misal

, dimana

⌈ ⌉

jika

adalah bilangan bulat dan

, dan ⌈ ⌉

ketika

Contoh 3.8 ⌈

⌉

⌈ ⌉

Teorema 3.6 ⌈ ⌉.

Untuk setiap bilangan asli,

42

.

. Maka


Bukti Dengan teorema 3.5 , maka ada tiga kemungkinan yaitu , dan

,

.

Akan dibuktikan untuk ruas kanan. Untuk

, ⌈ ⌉

⌈ ⌉

⌈ ⌉

⌈ ⌉

⌈

⌉

⌈

⌉

⌈ ⌉

⌈

⌉

⌈

⌉

Akan dibuktikan untuk ruas kiri. Dalam graf lintasan, jika graf tersebut bertambah 1 atau 2 titik, maka bilangan dominasi dari graf tersebut akan bertambah 1. Sehingga kalau atau

,

.

Teorema 3.7 Untuk

, dan

adalah bilangan asli,

43

.

maka


Bukti Dalam suatu siklus, derajat maksimal dari suatu titik dalam siklus adalah 2, yang berarti bahwa setiap titik dapat mendominasi tidak lebih dari 3 titik, termasuk dirinya sendiri. Sehingga jika siklus tersebut memiliki titik, maka

.

Teorema 3.8 ⌈ ⌉.

Untuk setiap bilangan asli,

Bukti Dengan teorema 3.7 , maka ada tiga kemungkinan yaitu , dan

.

Akan dibuktikan untuk ruas kanan. Untuk

, ⌈ ⌉

⌈ ⌉

⌈ ⌉

⌈ ⌉

⌈

⌉

⌈

⌉

⌈ ⌉

⌈

⌉

⌈

⌉

Akan dibuktikan untuk ruas kiri.

44

,


Dalam graf siklus, jika graf tersebut bertambah 1 atau 2 titik, maka bilangan dominasi dari graf tersebut akan bertambah 1. Sehingga kalau atau

, maka

.

Definisi 3.9 Kitar terbuka

dari titik

yang berhubungan dengan

adalah himpunan yang memuat titik-titik }.

didefinisikan ⋃

, kitar terbuka

tertutup

|

{ }.

Sedangkan kitar tertutup Untuk

{

, dimana

dan kitar

.

Contoh 3.9 {

Pada gambar 2.1 didapatkan Sedangkan misal dan

{

{

} dan

} pada gambar 2.1, maka }.

45

{

}. {

}


Teorema 3.9 Sebuah himpunan yang mendominasi mendominasi minimal dari graf

dari graf

adalah himpunan yang

jika dan hanya jika setiap titik

di

memenuhi paling sedikit salah satu dari dua sifat berikut: (i)

terasing dari ,

(ii)

Terdapat titik

{ }.

sedemikian sehingga

Bukti Asumsikan

adalah himpunan yang mendominasi minimal dari

untuk setiap titik

,

{ } bukan himpunan yang mendominasi. Ini { } tidak didominasi oleh semua

berarti terdapat titik titik di

{ }. Yang berarti

, yang dalam hal ini

terasing dari , atau

. Jika

tapi didominasi oleh , maka titik ,

adalah titik { },

tidak didominasi oleh

hanya berhubungan dengan titik

di

{ }. Andaikan

adalah himpunan yang mendominasi dan setiap titik

, memenuhi salah satu dari dua syarat. Kita tunjukan bahwa himpunan yang mendominasi minimal. Andaikan mendominasi minimal, misal titik yaitu

maka

adalah

bukan himpunan yang

, maka ada dua kemungkinan,

{ } adalah himpunan yang mendominasi. Akibatnya

berhubungan dengan paling sedikit satu titik di tidak terpenuhi. Jika

{ }, sehingga syarat (i)

{ } adalah himpunan yang mendominasi, maka

46


setiap titik di

berhubungan dengan paling sedikit satu titik di

{ }, sehingga syarat (ii) juga tidak terpenuhi. Kedua syarat (i) dan (ii) tidak terpenuhi, sehingga akan menimbulkan kontradiksi dengan asumsi kita

bahwa

paling

sedikit

satu

syarat

yang

terpenuhi.

Teorema 3.10 Jika


terasing, maka

tanpa titik

adalah himpunan yang mendominasi dari .

Bukti Misal

. Maka

paling sedikit memenuhi salah satu dari dua sifat (i)

dan (ii) diberikan pada teorema 3.9. Andaikan memenuhi sifat (i), bahwa adalah titik terasing dari . Maka 〈 〉. Karena

adalah titik terasing dari graf bagian

tidak terasing di , titik

berhubungan dengan suatu titik di

. Andaikan memenuhi sifat (ii), bahwa terdapat titik { }. Karena

sedemikian hingga titik

di

.

Sehingga

mendominasi .

47

berhubungan dengan suatu adalah

himpunan

yang


Akibat 3.10 Jika

adalah graf dengan

titik tanpa titik terasing, maka

.

Bukti Misal


teorema 3.10,

. Dengan

adalah himpunan yang mendominasi . Maka

{| | |

|}

.

Teorema 3.11 Setiap graf

tanpa titik terasing memuat sebuah himpunan yang

mendominasi minimum terdapat

di

sedemikian hingga untuk setiap titik

sedemikian hingga

di ,

{ }.

Bukti Diantara semua himpunan yang mendominasi minimum dari

, misal

adalah salah satu dari himpunan yang mendominasi minimum dari sedemikian hingga

〈 〉

sebaliknya , bahwa

memuat titik

dengan teorema 3.9, di

memiliki ukuran maksimum. Diandaikan yang tidak memenuhi syarat. Maka

adalah titik terasing dari 〈 〉. Selain itu, setiap titik

yang berhubungan dengan

titik lainnya di . Karena

juga berhubungan dengan titik-

tidak memuat titik terasing,

48

berhubungan


dengan

di

{ }

. Sebagai konsekwensinya,

himpunan yang mendominasi minimum dari

{ } adalah

dimana graf bagian yang

diinduksi memuat paling sedikit satu rusuk yang bersisian dengan

dan

karena itu memiliki ukuran yang lebih besar dari 〈 〉. Terjadi kontradiksi.

Teorema 3.12 Diberikan suatu graf terhubung , maka

Bukti Perhatikan bahwa jika

adalah titik dengan derajat minimum, maka

penghapusan semua rusuk yang bersisian dengan tersebut tidak terhubung (

akan membuat graf

adalah salah satu komponennya). Tentu saja

akan ada himpunan rusuk pemisah, di lain graf yang memuat rusuk yang lebih sedikit. Maka

. Selanjutnya, jika

adalah himpunan

rusuk pemisah yang memuat rusuk sebanyak , maka penghapusan sesuai dengan titik hasil yang dipilih dari rusuk di

yang

dan oleh karena itu,

menghasilkan graf yang tidak terhubung. (Mungkin saja ada himpunan titik pemisah yang lebih kecil di ). Maka

49

.


Teorema 3.13

Jika

adalah sebuah graf dengan

titik, maka ⌈

⌉

. Bukti Misal

adalah himpunan yang mendominasi minimum dari . ⋃

Maka

, menyebabkan |

|

| |

.

Oleh karena itu,

( ⌈

) ⌉.

Selanjutnya akan dibuktikan batas atasnya. Misal . Maka kardinalitas

dengan

adalah himpunan yang mendominasi dengan , sehingga

.

Akibat 3.13 Jika

adalah sebuah graf dengan

50

titik, maka

.


Bukti Dengan teorema 3.13 didapatkan

dan karena

.

Teorema 3.14 Jika

adalah graf dengan banyak titik ̅

(i)

,

̅

(ii)

, maka

.

Bukti Batas bawah dari (i) dan (ii) didapatkan dari pengamatan bahwa jika ̅

maka

dan bila

Untuk batas atas dari (i), jika ̅

dan maka Jika

̅

̅

memiliki sebuah titik terasing, maka

̅

. Dalam kasus ini,

̅ memiliki titik terasing, maka

maupun

̅

menurut akibat 3.10, sehingga Untuk batas atas dari (ii), jika

{

.

; sedangkan jika ̅ memiliki sebuah titik terasing,

dan

̅

maka

.

Maka

diasumsikan

dan

̅

. maka jelas bahwa .

Misal

} adalah himpunan yang mendominasi minimum dari

51

.

dan


partisi

menjadi

himpunan bagian

untuk

dan semua titik di

dengan

syarat : (a)

didominasi oleh

dan (b)

Penjumlahan semua bilangan bulat yang menyatakan banyaknya titik dalam

yang berhubungan dengan semua titik lain dalam

adalah maksimum. Sekarang diperlihatkan bahwa untuk setiap himpunan adalah himpunan yang mendominasi dari himpunan titik

dengan

̅ . Andaikan

bukan himpunan yang mendominasi dari ̅ , maka terdapat yang berhubungan di

untuk bilangan bulat

dan

berhubungan dalam

̅ tapi tidak berhubungan dengan

yang berbeda dengan

dengan setiap titik dari

, . Jika

{ } adalah himpunan yang mendominasi dari kardinalitas kurang dari

. Maka , maka yang memiliki

, yang berarti tidak mungkin. Sebagai

konsekwensinya,

{ }. Jika

berhubungan di dalam

setiap titik lainnya dari

, maka

{

yang mendominasi dari

yang memiliki kardinalitas kurang dari

}

yang berarti tidak mungkin. Oleh karena itu, semua titik dari

tapi tidak ke semua titik di

52

{ } adalah himpunan

berhubungan dalam .

untuk

, ke


{ } dan

Didefinisikan didefinisikan

{ }. Untuk

. Sekarang kita memiliki partisi dari

himpunan bagian

sedemikian hingga

dan semua titik dalam

didominasi oleh

semua himpunan bagian

dengan

, ke dalam

untuk

. Bagaimanapun, jumlah dari titik dalam

berhubungan dengan semua titik dari berkorespondensi untuk partisi

yang

melebihi penjumlahan yang , yang berarti kontradiksi.

Kemudian, seperti yang telah dinyatakan, setiap himpunan bagian adalah himpunan yang mendominasi dalam

̅ , sehingga

untuk setiap . Karena itu ∑

̅ .

| |

Akibat 3.14 Jika

dapat difaktorkan menjadi

,

, dan

, maka

. Bukti Karena

̅̅̅, didapatkan dari teorema 3.14 bahwa .

53

̅

| |


Teorema 3.15 Jika

adalah suatu graf dengan titik sebanyak

sedemikian hingga

dan ̅ keduanya tidak memiliki titik terasing, maka

̅

.

Bukti Karena

̅ keduanya tidak memiliki titik terasing, menurut akibat

dan

3.10 maka ̅

atau

̅

dan

. Karena itu jika salah satu

, maka bukti selesai. Jika

dan

menurut batas atas (ii) pada teorema 3.14, ̅

, sehingga atau ̅

̅

, maka dan

̅

. Karena itu diasumsikan

. Karena

, maka ̅

. Maka

̅

̅

. Dengan teorema 3.14, .

E. TEOREMA TENTANG BILANGAN DOMINASI BEBAS DARI SUATU GRAF Tidak sulit untuk melihat bahwa setiap himpunan bebas yang memiliki kardinalitas maksimal dari suatu graf mendominasi dari

. Maka


, dimana

dominasi bebas minimum dari

. Bagaimanapun juga tidak semua

himpunan yang mendominasi adalah himpunan bebas.

54

adalah bilangan


Teorema 3.16 Setiap himpunan bebas yang memiliki kardinalitas maksimal dari suatu graf


Bukti Misal

adalah himpunan bebas dari

terbesar dari semua himpunan bebas di

dan

memiliki kardinalitas

. Maka untuk setiap titik

akan berhubungan dengan paling sedikit satu titik di . Sehingga menurut definisi 3.1,

merupakan himpunan yang mendominasi dari

.

Teorema 3.17 Suatu himpunan titik-titik bebas jika dan hanya jika

dalam

adalah himpunan yang mendominasi

adalah himpunan bebas yang memiliki

kardinalitas maksimal. Bukti Setiap himpunan bebas maksimal adalah himpunan yang mendominasi berdasarkan teorema 3.16. Sebaliknya, misal mendominasi bebas, maka


adalah himpunan bebas dan setiap titik diluar

berhubungan dengan titik dalam bebas maksimal.

55

, yang berarti

adalah himpunan


Akibat 3.17 Setiap himpunan bebas maksimal suatu graf adalah himpunan yang mendominasi minimal. Bukti Misal

adalah himpunan bebas maksimal dari graf

. Dengan teorema

3.16,

adalah himpunan yang mendominasi. Karena

adalah himpunan

bebas, maka pasti setiap titik dalam dalam . Maka, setiap titik dalam Menurut teorema 3.9,

tidak berhubungan dengan titik

memenuhi sifat (i) dari teorema 3.9.

adalah himpunan yang mendominasi minimal.

Teorema 3.18 Jika

adalah graf bebas-

, dimana

, maka

. Bukti Misal

adalah himpunan yang mendominasi minimum dari

adalah himpunan bebas maksimal di Misal

. Maka, | |

adalah himpunan semua titik dalam

berhubungan dengan titik dalam

, dan misal

dan misal dan | |

.

yang tidak adalah himpunan bebas

maksimal di . Maka

adalah himpunan bebas dari . Karena setiap

titik dalam

berhubungan dengan suatu titik dalam

56

dan


setiap titik dalam mengakibatkan

berhubungan ke suatu titik dalam

adalah himpunan bebas maksimal. Maka menurut

teorema 3.16,

adalah himpunan yang mendominasi bebas.

Setiap titik dalam titik dalam

berhubungan dengan paling banyak

, jika tidak, maka titik

paling sedikit

titik dalam

dalam

berhubungan dengan

dan juga paling sedikit satu titik dalam

yang menyebabkan kontradiksi dengan hipotesa bahwa graf bagian yang diinduksi oleh berhubungan ke suatu titik dalam | |

| |

| | |

|

. Maka, | | | | .

| |

| | | | | |

Akibat 3.18.a adalah graf bebas cakar, maka

57

,

tidak memuat

. Juga, setiap titik dari

Akibatnya,

Jika

, yang

.

|

|


Akibat 3.18.b Untuk setiap graf , (

)

(

).

Definisi 3.10 Suatu graf

disebut dominasi sempurna jika

graf bagian

yang diinduksi oleh .

untuk setiap

Contoh 3.10 Graf

dan graf

merupakan dominasi sempurna.

Akibat 3.18.c Setiap graf bebas cakar adalah dominasi sempurna.

F. PARAMETER DOMINASI LAINNYA Pada subbab sebelumnya telah diperkenalkan variasi dari bilangan dominasi, yaitu bilangan dominasi bebas. Sedangkan pada bagian ini, akan diperlihatkan beberapa parameter dominasi lainnya.

58


Definisi 3.11 Himpunan

dari titik-titik dalam

jika untuk setiap titik

disebut himpunan irredundant dari

, terdapat titik

{ } . Setiap titik irredundant. Himpunan

sedemikian hingga

yang memenuhi sifat ini disebut titik

yang bukan himpunan irredundant disebut

himpunan redundant. Setiap titik

dalam himpunan redundant disebut

titik redundant.

Dengan kata lain,

adalah himpunan irredundant dari

untuk setiap titik

. Dan himpunan

jika hanya jika terdapat titik

dimana

{ }

jika

adalah himpunan redundant { }

.

Contoh 3.11 Pada gambar 2.1, misal karena

{

}, maka { } dan

tapi

adalah himpunan irredundant, tapi

{ }

Teorema 3.19 Himpunan


hanya jika setiap titik

dalam

adalah himpunan irredundant jika

memenuhi paling sedikit satu dari dua

sifat berikut:

59


(i) (ii)

terasing dari , Terdapat titik

sedemikian sehingga

{ }. Bukti Misal

adalah himpunan dari titik-titik dalam

untuk setiap titik

sedemikian sehingga

, paling sedikit memenuhi salah satu sifat (i) dan

(ii). Jika (ii) terpenuhi, maka terdapat titik

sedemikian hingga

{ } . Jika (i) dipenuhi, maka

{ } . Dalam kasus ini

adalah himpunan irredundant. Secara konvers, misal dan misal

. Karena

adalah himpunan yang irredundant di

adalah himpunan yang irredundant, terdapat { } . Jika

sedemikian sehingga terpenuhi, sedangkan jika

,

, maka (ii)

, maka (i) terpenuhi.

Dengan teorema 3.9, maka himpunan yang mendominasi minimal dalam suatu graf adalah himpunan irredundant. Karena itu, setiap graf memiliki himpunan yang irredundant.

60


Definisi 3.12 Jika

adalah himpunan yang irredundant di

, maka setiap

{ } disebut kitar pribadi dari .

titik di

Titik

, dan

merupakan kitar pribadi bagi dirinya sendiri. Jika

himpunan yang irredundant di

, maka untuk setiap

adalah

, himpunan

{ } tak kosong.

Contoh 3.12 Pada gambar 2.1, misal karena

{

}, titik

merupakan kitar pribadi bagi

{ } , begitu juga dengan titik

tetapi

dan .

Definisi 3.13 Bilangan irredundance

dari suatu graf

minimum dari himpunan yang irredundant di irredundance atas

adalah kardinalitas . Sedangkan bilangan

adalah kardinalitas maksimum dari himpunan

yang irredundant di .

61


Contoh 3.13 Dari gambar 2.1 didapatkan

dan

.


.

Bukti Untuk

sudah pernah diperlihatkan. Untuk ketidaksamaan merupakan akibat dari fakta bahwa setiap himpunan yang

mendominasi minimal di

adalah himpunan yang irredundant.


.

Bukti Karena semua himpunan yang mendominasi minimal adalah himpunan yang irredundant, maka menyebabkan

. Selain itu, setiap

himpunan bebas maksimum adalah himpunan yang mendominasi, sehingga

. Karena himpunan yang mendominasi bebas

merupakan himpunan bebas, maka

62

.


Teorema 3.22 Untuk setiap graf bipartit ,

.

Bukti Misal

adalah graf bipartit dengan himpunan partisi

adalah himpunan irredundant maksimum dari

dan

. Misal

dan misal

adalah

himpunan dari titik terasing dari 〈 〉. Selanjutnya misal ,

,

,

, dimana salah satu

atau lebih dari himpunan ini merupakan himpunan kosong. Setiap titik adalah irredundant di . Karena

tidak terisolasi di 〈 〉, titik

bukan kitar pribadi. Bagaimanapun, karena


irredundant,

adalah kitar pribadi dari suatu titik di

untuk

, terdapat titik

sedemikian sehingga

{ }. Selain itu, karena { |

Misal

}.

Selanjutnya tidak ada titik di Akibatnya itu,

. Karena itu,

, menyebabkan Maka

| |

|

|

. dan

yang berhubungan dengan titik di merupakan himpunan bebas di

|

|

|

|

|

.

|

| |

63

| |

.

.

. Karena


G. APLIKASI Contoh 3.14 Misalkan sebuah provinsi terdiri dari delapan kota yang dihubungkan oleh jalan besar seperti yang diperlihatkan pada gambar 3.4. Pengawas provinsi tersebut ingin memperbesar fasilitas kesehatan yang mereka miliki sehingga setiap kota memiliki unit kebakaran atau berhubungan dengan kota yang memilikinya. Karena keterbatasan dana, jumlah fasilitas kesehatan yang akan diperbesar tersebut harus diminimumkan. a. Di kota mana harus diletakkan unit kebakaran jika di kota

juga harus

dibangun? b. Di kota mana harus diletakkan unit kebakaran jika sudah ada satu unit yang diletakkan pada kota , kota yang paling besar dalam kabupaten tersebut?

Gambar 3.4

64


Solusi Untuk menyelesaikan masalah tersebut dibutuhkan himpunan yang mendominasi minimum. a. Fasilitas dengan pusat

akan mendominasi , ,

, , dan . Yang

berarti, setiap kota tersebut memiliki unit kebakaran di sekitarnya. Untuk mendominasi kota lainnya

,

tersebut harus diletakkan di kota

. Dengan demikian, harus ada

fasilitas kesehatan di kota b. Unit kebakaran di kota

, dan

, fasilitas kesehatan

dan .

melayani kota , , , dan . Untuk melayani

kota-kota lainnya, hanya dengan menambahkan fasilitas pada kota . Sehingga hanya akan dibangun fasilitas di kota

dan

. Inilah

himpunan yang mendominasi minimum kedua.

Contoh 3.15 Seorang perancang kota dari kota Mesh telah menemukan masalah bahwa kota mereka sangat kotor. Untuk menyelesaikan masalah tersebut, mereka memutuskan untuk meletakan wadah pembuangan di setiap persimpangan. Tentukan jumlah minimum dari wadah pembuangan yang dapat mereka gunakan sehingga untuk setiap persimpangan, terdapat wadah pembuangan atau terdapat pada perpotongan blok lain. Bentuk rangkaian jalan mereka adalah

dan diperlihatkan pada gambar 3.5.

65


Gambar 3.5 Solusi Masalah tersebut ekuivalen dengan mencari

dalam graf

pada

gambar 3.5. terdapat 20 titik dan masing-masing titik mendominasi tetangganya dan dirinya sendiri. Karena mendominasi

paling

banyak

5

, setiap titik dapat

titik,

sehingga

.

Bagaimanapun, batas yang lebih kecil tidak dapat diterima. Untuk mendominasi titik ujung seperti atau tetangga dari

, kita harus memasukan titik

dalam himpunan yang mendominasi. Titik

hanya

mendominasi 3 titik dan tetangganya hanya mendominasi 4 titik. Sehingga batasnya bertambah menjadi waktu (

jika menggunakan tetangga setiap

, sehingga paling sedikit dibutuhkan 1 titik lagi

untuk mendominasi titik-titik yang tersisa). Untuk mendapatkan

,

tidak dapat menggunakan lebih dari satu titik ujung (dimana hanya

66


mendominasi 3 titik). Sebagai contoh, jika menggunakan 2 titik ujung dan 2 tetangga dari titik ujung, mereka paling banyak dapat mendominasi titik. Paling sedikit diperlukan 2 titik tambahan dalam himpunan yang mendominasi untuk mendominasi 6 titik yang tersisa. Sekarang ditunjukan bahwa

. Karena paling sedikit ada 3

tetangga dari titik ujung dalam himpunan yang mendominasi minimum, dan berhubungan dengan mereka akan memperbanyak titik yang mendominasi, paling tidak harus terdapat 2 titik dalam kolom yang berurutan dari

. Tanpa mengurangi bentuk secara umum, dapat

diasumsikan bahwa

dan

berada dalam himpunan yang

mendominasi minimum . Sehingga semua titik dalam dua kolom yang pertama didominasi kecuali mendominasi

. Titik

juga didominasi. Untuk

, harus digunakan titik

, karena jika menggunakan

titik lain, hanya akan mendominasi paling banyak 2 titik baru, yang juga ekuivalen

dengan

menggunakan

diperbolehkan). Sehingga Titik

2

titik

ujung

. Sekarang,

(dimana

tidak didominasi.

adalah satu-satunya titik yang mendominasi

mendominasi lima titik baru. Jadi yang tidak didominasi:

,

. Paling sedikit dibutuhkan

dua titik untuk mendominasi mereka. Jadi

mendominasi untuk

, yang juga

. Sekarang terdapat tiga titik , dan

{

}

adalah

, maka didapatkan

. Karena himpunan

yang

. Sehingga jumlah

minimum dari wadah pembuangan yang diperlukan adalah enam.

67

tidak


BAB IV PENUTUP Pada bab ini dituliskan kesimpulan dari pembahasan bab-bab sebelumnya, serta saran bagi penelitian selanjutnya. A. KESIMPULAN Dominasi dalam graf merupakan cara untuk meletakan titik-titik penting dalam suatu graf yang melambangkan hubungan antar kota. Dominasi dalam graf biasanya digunakan untuk meletakan fasilitasfasilitas kesehatan dalam suatu provinsi atau kabupaten. Dalam tulisan ini telah dibuktikan beberapa teorema yang berlaku dalam masalah dominasi dalam graf antara lain: 

Teorema 3.6 Untuk setiap bilangan asli,



⌈ ⌉.

Teorema 3.16 Setiap himpunan bebas yang memiliki kardinalitas maksimal dari suatu graf




Teorema 3.9 Sebuah himpunan yang mendominasi

dari graf

himpunan yang mendominasi minimal dari graf

68

adalah jika dan


hanya jika setiap titik

di

memenuhi paling sedikit salah

satu dari dua sifat berikut: (iii) (iv)

adalah titik terasing dari , Terdapat titik

sedemikian sehingga

{ }. 

Teorema 3.19 Himpunan


adalah himpunan

irredundant jika hanya jika setiap titik

dalam

memenuhi

paling sedikit satu dari dua sifat berikut: (iii) (iv)

terasing dari , Terdapat titik

sedemikian sehingga

{ }. 

Hubungan antara himpunan yang mendominasi minimal dengan

himpunan

irredundant

yaitu,

himpunan

yang

mendominasi minimal adalah himpunan irredundant. Selain itu, telah dibahas pula tentang parameter-parameter dominasi, yaitu bilangan dominasi, dan bilangan dominasi bebas dan hubungan antara masing-masing parameter tersebut dengan bilangan irredundant seperti yang diperlihatkan dalam teorema 3.20 yang berbunyi, “Untuk ”.

setiap graf ,

69


B. SARAN Hingga saat makalah ini ditulis, masih belum ditemukan algoritma untuk mencari himpunan yang mendominasi maupun bilangan dominasi untuk suatu graf secara umum, sehingga masih terbuka untuk diteliti lebih lanjut tentang algoritma untuk mencari himpunan yang mendominasi maupun bilangan dominasi dan parameter-parameter dominasi lainnya.

70


DAFTAR PUSTAKA

Buckley, F., and Lewinter, M. 2003. A Friendly Introduction to Graph Theory. New Jersey: Pearson Education Inc. Chartrand, G., Lesniak, L. 2005. Graphs & Digraphs Fourth Edition. Florida: CRC Press Company. Haynes, T. W., Hedetnemi S. T., and Slater P. J. 1998. Fundamentals of Domination in Graphs. New York: Marcel Dekker Inc. Ross, K. A., Wright, C. R. B. 1992. Discrete Mathematics, 3rd ed. New Jersey: Prentice-Hall, Inc. West, D. B. 2001. Introduction To Graph Theory Second Edition. New Jersey: Prentice-Hall, Inc.

71

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

Recommend Documents