plagiat merupakan tindakan tidak terpuji - usd … · makalah. program studi matematika, jurusan...

i

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

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJIPLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

ii

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


iii


iv


v

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 soal-

soal 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.


vi


vii


viii

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


ix

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


x

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.


xi

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


xii

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


xiii

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


1

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


2

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 sehari-

hari. 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.


3

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 atau berhubungan dengan

suatu titik dalam himpunan , dimana 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


4

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 dapat memperhatikan lorong yang

menghubungkan titik dengan titik dan titik dengan titik , sedangkan

satpam di titik dapat memperhatikan lorong yang menghubungkan titik

dengan titik dan titik dengan titik , sehingga satpam di titik dapat

memperhatikan lorong yang menghubungkan titik dengan titik 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.


5

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 dan , maka kebutuhan semua kota akan dapat dipenuhi. Dari

kota , fasilitas kesehatan tersebut dapat mengirimkan bantuan ke kota itu

sendiri, ke kota , 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.


6

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.


7

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


8

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


9

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 . Bila rusuk

menghubungkan titik dan maka dapat ditulis .

Contoh 2.1

Gambar 2.1 menyatakan graf dengan:

{ }

{ }

Gambar 2.1


10

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 dan adalah himpunan titik-titik dalam graf ,

kardinalitas dari 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 , jalan

dari didefinisikan sebagai barisan titik-titik dan rusuk-rusuk yang


11

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 dan

diakhiri dengan .

Contoh 2.4

Pada gambar 2.1, jalan beberapa diantaranya adalah:

Sedangkan lintasan adalah

Siklus dari gambar 2.1 salah satunya adalah


12

Definisi 2.5

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

jika , .

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 { } dan { }, yang

didefinisikan dengan


13

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 dan berhubungan dalam

jika dan hanya jika dan berhubungan dalam . Fungsi yang

memenuhi syarat tersebut disebut isomorfisma dari ke .

Contoh 2.7

Gambar 2.2

Graf dan pada gambar 2.2 merupakan graf yang isomorfis.Dengan

, , , , dan atau ,

, , , dan .


14

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 adalah derajat

terkecil dari titik-titik dalam dan derajat maksimum dinotasikan dengan

adalah derajat terbesar dari titik-titik dalam .

Contoh 2.8

Pada gambar 2.1 didapatkan

Sehingga dan .

Definisi 2.9

Misalkan adalah suatu titik dalam graf , merupakan titik ujung jika

memiliki derajat satu. Dan merupakan titik terasing jika memiliki

derajat nol.


15

Contoh 2.9

Gambar 2.3

Dari gambar 2.3 didapatkan , maka titik adalah titik ujung

dari graf tersebut, dan , maka titik merupakan titik terasing.

Definisi 2.10

Misalkan adalah graf. Graf merupakan graf terhubung bila hanya bila

untuk setiap titik dan di , ada jalan dari titik ke titik .

Contoh 2.10

Gambar 2.4

Graf merupakan graf terhubung, sedangkan graf merupakan graf tidak

terhubung.


16

B. GRAF BAGIAN

Definisi 2.11

Misal adalah graf dengan himpunan titik dan himpunan rusuk

, suatu graf disebut graf bagian dari jika dan

dan untuk setiap , titik dan berada di .

Contoh 2.11

Gambar 2.5

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


17

Definisi 2.12

Jika , maka graf bagian yang diinduksi oleh , dinotasikan ⟨ ⟩,

adalah graf bagian yang berisi titik-titik dalam dan semua rusuk yang

berbentuk dalam , dimana dan .

Contoh 2.12

Dari gambar 2.1, misal { }, maka

⟨ ⟩ { }.

C. MACAM-MACAM GRAF

Definisi 2.13

Suatu graf disebut graf bipartit jika dapat dipartisi menjadi dua

himpunan bagian tak kosong dan , sedemikian hingga jika adalah

rusuk dalam , maka titik dan berada pada himpunan bagian yang

berbeda.

Contoh 2.13

Gambar 2.6

Gambar 2.6 merupakan graf bipartit dengan { } dan

{ }.


18

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 dan dengan kardinalitas

berturut-turut dan , sedemikian sehingga setiap titik di himpunan

berhubungan dengan setiap titik di himpunan dan tidak ada

keterhubungan lainnya.


19

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 adalah suatu siklus dengan

titik.


20

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.

Contoh 2.18

Gambar 2.11

Definisi 2.19

Misal adalah graf. Suatu graf disebut graf bebas-F jika graf tidak

memuat graf bagian yang diinduksi secara isomorfis oleh .


21

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 dan

. Maka, memuat salinan dari bersama dengan

salinan dari .


22

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 berhubungan dengan setiap titik

. Jika dan memiliki dan titik, maka graf harus

ditambahkan rusuk.

Contoh 2.21

Gambar 2.14


23

Definisi 2.22

Untuk , roda adalah penggabungan dari dengan ,

yang berarti .

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 , untuk .

Contoh 2.23

Gambar 2.16


24

2. KOMPLEMEN

Definisi 2.24

Komplemen dari suatu graf memiliki dan

jika hanya jika .

Contoh 2.24

Gambar 2.17

3. FAKTORISASI

Definisi 2.25

Suatu graf dapat difaktorkan dengan jika

sepasang-sepasang saling asing dan

⋃ . Jika dapat difaktorkan atas , maka

hal tersebut dinotasikan dengan , yang disebut

faktorisasi dari


25

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 , dimana dan . Dua titik dan

berhubungan dalam jika

1. dan berhubungan dengan dalam graf , atau

2. dan berhubungan dengan dalam graf .

Setiap titik dari dapat dipandang memiliki dua “orang

tua” , yaitu dalam dan dalam . Untuk setiap , graf bagian

yang diinduksi oleh { | } disebut tiruan ke- dari .

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

oleh { | } disebut tiruan ke- dari . Gambar 2.19


26

memperlihatkan graf , dan produk kartesius

.

Gambar 2.19

Graf dalam gambar 2.19 dapat dilihat sebagai tiga graf tiruan

dari graf yang berkorespondensi dengan tiga titik dalam graf . Kira-

kira seperti meletakan titik-titik dari pada tiruan graf . Setiap tiruan

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

tiruan yang pertama berhubungan dengan titik-titik yang

berkorespondensi dari graf tiruan yang kedua, karena berhubungan

dengan dalam . Dengan cara yang mirip, titik-titik dalam tiruan

yang kedua berhubungan dengan titik-titik yang berkorespondensi dari

graf tiruan yang ketiga, karena berhubungan dengan dalam .

Selain itu, titik-titik yang berkorespondensi dalam tiruan yang pertama

dan ketiga tidak saling berhubungan karena dan tidak berhubungan

dalam .

Paragraf sebelumnya dapat ditulis ulang dengan sedikit penyesuaian

jika pandangan terhadap graf tersebut diubah dengan mulai dengan empat


27

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 untuk setiap

tiga graf , 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 dengan , yang berarti

. Graf sama dengan produk kartesius dari

dengan dan . Sehingga ,

karena produk kartesius bersifat asosiatif. Graf ini dapat diperluas menjadi

. Graf adalah produk kartesius dari

lintasan dengan urutan , dan

. Graf jala diperlihatkan pada gambar 2.20, dengan empat

titik yang berderajat 2 diberi label.


28

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 berhubungan jika


29

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 adalah graf yang terbentuk dari

dengan menghapus titik dan semua rusuk yang bersisian dengan .

Contoh 2.27

Gambar 2.23


30

Definisi 2.28

Jika adalah rusuk dalam , graf adalah graf yang terbentuk

dari dengan menghapus rusuk .

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 menjadi graf

trivial.


31

Contoh 2.29

Gambar 2.25

Dari gambar 2.25, didapatkan . Karena cukup hanya dengan

menghapus satu titik 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 atau .


32

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 jika dapat

memakan bidak catur dalam posisi . Yang berarti, posisi berada tepat

pada suatu garis lurus terhadap posisi dari , 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.


33

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


34

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

{ }, { }, { }, { }, { }, { }. dan himpunan

yang mendominasi minimum { }, { }, { }. Sedangkan himpunan

yang mendominasi minimal tapi tidak minimum adalah { },

{ }, { }.


35

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 ratu-

ratu 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.


36

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 yang saling

berhubungan. Bilangan bebas dari sebuah graf , 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 .


37

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 .


38

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 , dimana | | .

Sehingga adalah himpunan bebas dengan kardinalitas terbesar. Untuk

, harus berhubungan dengan suatu titik dalam . Dengan

kata lain, { } akan menjadi himpunan bebas yang lebih besar, terjadi

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 sedemikian

sehingga setiap rusuk dalam berisisian dengan paling sedikit satu titik

dalam . Kardinalitas terkecil dari penutup titik dalam dinotasikan

dengan .


39

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 bukan himpunan bebas. Maka ada pasangan titik

dan dari yang berhubungan. Maka bukan penutup titik,

terjadi kontradiksi bahwa adalah penutup

titik.

Dengan menggunakan teorema 3.2, kardinalitas terkecil penutup

titik dan bilangan bebas , didapatkan akibat 3.2.


40

Akibat 3.2

Untuk semua graf dengan titik, .

Bukti

Misalkan adalah penutup titik dengan kardinalitas terkecil. Maka

| | . Dengan teorema 3.2, adalah sebuah himpunan

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 yang bersisian dengan ,

sehingga adalah penutup titik. Dan mengakibatkan bahwa

atau, secara ekuivalen . Sehingga

didapatkan dan . Sehingga

.

Teorema 3.3

Untuk setiap graf lengkap dengan . Bilangan dominasi dari

graf lengkap adalah 1, atau .

Bukti

Menurut definisi 2.14, graf lengkap adalah graf yang terdiri dari titik

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


41

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 dengan dan adalah bilangan

asli, maka ( ) .

Bukti

Menurut definisi 2.15, graf bipartit lengkap adalah graf yang himpunan

titiknya dapat dipartisi menjadi himpunan tak kosong dan dengan

kardinalitas berturut-turut dan , sedemikian sehingga setiap titik di

himpunan berhubungan dengan setiap titik di himpunan dan tidak ada

keterhubungan lainnya. Ada tiga kemungkinan, yaitu , ,

. Misal , maka ada titik yang mendominasi titik, dan ada

titik yang mendominasi 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 . Untuk , maka

didapatkan titik yang mendominasi. Sehingga didapatkan

kesimpulan ( )


42

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 adalah bilangan bulat dan . Maka

⌈ ⌉ jika , dan ⌈ ⌉ ketika .

Contoh 3.8

⌈ ⌉

⌈ ⌉

Teorema 3.6

Untuk setiap bilangan asli, ⌈

⌉.


43

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 , maka

.

Teorema 3.7

Untuk , dan adalah bilangan asli, .


44

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


⌉.

Bukti

Dengan teorema 3.7 , maka ada tiga kemungkinan yaitu ,

, dan .

Akan dibuktikan untuk ruas kanan.

Untuk ,

⌈

⌉ ⌈

⌉ ⌈ ⌉

⌈

⌉ ⌈

⌉ ⌈

⌉

⌈

⌉ ⌈

⌉ ⌈

⌉

Akan dibuktikan untuk ruas kiri.


45

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 adalah himpunan yang memuat titik-titik

yang berhubungan dengan , dimana { | }.

Sedangkan kitar tertutup { }.

Untuk , kitar terbuka didefinisikan ⋃ dan kitar

tertutup .

Contoh 3.9

Pada gambar 2.1 didapatkan { } dan { }.

Sedangkan misal { } pada gambar 2.1, maka { }

dan { }.


46

Teorema 3.9

Sebuah himpunan yang mendominasi dari graf adalah himpunan yang

mendominasi minimal dari graf 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 maka

untuk setiap titik , { } bukan himpunan yang mendominasi. Ini

berarti terdapat titik { } tidak didominasi oleh semua

titik di { }. Yang berarti , yang dalam hal ini adalah titik

terasing dari , atau . Jika tidak didominasi oleh { },

tapi didominasi oleh , maka titik hanya berhubungan dengan titik di

, { }.

Andaikan adalah himpunan yang mendominasi dan setiap titik

, memenuhi salah satu dari dua syarat. Kita tunjukan bahwa adalah

himpunan yang mendominasi minimal. Andaikan bukan himpunan yang

mendominasi minimal, misal titik , maka ada dua kemungkinan,

yaitu { } adalah himpunan yang mendominasi. Akibatnya

berhubungan dengan paling sedikit satu titik di { }, sehingga syarat (i)

tidak terpenuhi. Jika { } adalah himpunan yang mendominasi, maka


47

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 adalah himpunan yang mendominasi minimal dari tanpa titik

terasing, maka 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 adalah titik terasing dari graf bagian

⟨ ⟩. Karena tidak terasing di , titik berhubungan dengan suatu titik di

.

Andaikan memenuhi sifat (ii), bahwa terdapat titik

sedemikian hingga { }. Karena berhubungan dengan suatu

titik di . Sehingga adalah himpunan yang

mendominasi .


48

Akibat 3.10

Jika adalah graf dengan titik tanpa titik terasing, maka

.

Bukti

Misal adalah himpunan yang mendominasi minimal dari . Dengan

teorema 3.10, adalah himpunan yang mendominasi . Maka

{| | | |}

.

Teorema 3.11

Setiap graf tanpa titik terasing memuat sebuah himpunan yang

mendominasi minimum sedemikian hingga untuk setiap titik di ,

terdapat di sedemikian hingga { }.

Bukti

Diantara semua himpunan yang mendominasi minimum dari , misal

adalah salah satu dari himpunan yang mendominasi minimum dari

sedemikian hingga ⟨ ⟩ memiliki ukuran maksimum. Diandaikan

sebaliknya , bahwa memuat titik yang tidak memenuhi syarat. Maka

dengan teorema 3.9, adalah titik terasing dari ⟨ ⟩. Selain itu, setiap titik

di yang berhubungan dengan juga berhubungan dengan titik-

titik lainnya di . Karena tidak memuat titik terasing, berhubungan


49

dengan di . Sebagai konsekwensinya, { } { } adalah

himpunan yang mendominasi minimum dari 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 akan membuat graf

tersebut tidak terhubung ( 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 yang

sesuai dengan titik hasil yang dipilih dari rusuk di dan oleh karena itu,

menghasilkan graf yang tidak terhubung. (Mungkin saja ada himpunan

titik pemisah yang lebih kecil di ). Maka .


50

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 dengan

. Maka adalah himpunan yang mendominasi dengan

kardinalitas , sehingga .

Akibat 3.13

Jika adalah sebuah graf dengan titik, maka .


51

Bukti

Dengan teorema 3.13 didapatkan dan karena

.

Teorema 3.14

Jika adalah graf dengan banyak titik , maka

(i) ,

(ii) .

Bukti

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

maka dan bila maka .

Untuk batas atas dari (i), jika memiliki sebuah titik terasing, maka

dan ; sedangkan jika memiliki sebuah titik terasing,

maka dan . Dalam kasus ini, .

Jika maupun memiliki titik terasing, maka

dan

menurut akibat 3.10, sehingga .

Untuk batas atas dari (ii), jika maka jelas bahwa

. Maka diasumsikan . Misal

{ } adalah himpunan yang mendominasi minimum dari dan


52

partisi menjadi himpunan bagian dengan

syarat :

(a) untuk dan semua titik di 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 dengan

adalah himpunan yang mendominasi dari . Andaikan

himpunan bukan himpunan yang mendominasi dari , maka terdapat

titik yang berhubungan di tapi tidak berhubungan dengan

untuk bilangan bulat dan yang berbeda dengan , . Maka

berhubungan dalam dengan setiap titik dari . Jika , maka

{ } adalah himpunan yang mendominasi dari yang memiliki

kardinalitas kurang dari , yang berarti tidak mungkin. Sebagai

konsekwensinya, { }. Jika berhubungan di dalam untuk

setiap titik lainnya dari , maka { } { } adalah himpunan

yang mendominasi dari yang memiliki kardinalitas kurang dari ,

yang berarti tidak mungkin. Oleh karena itu, berhubungan dalam ke

semua titik dari tapi tidak ke semua titik di .


53

Didefinisikan { } dan

{ }. Untuk ,

didefinisikan . Sekarang kita memiliki partisi dari ke dalam

himpunan bagian

sedemikian hingga

untuk

dan semua titik dalam didominasi oleh . Bagaimanapun, jumlah

semua himpunan bagian dengan dari titik dalam

yang

berhubungan dengan semua titik dari melebihi penjumlahan yang

berkorespondensi untuk partisi , 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

.


54

Teorema 3.15

Jika adalah suatu graf dengan titik sebanyak sedemikian hingga

dan keduanya tidak memiliki titik terasing, maka

.

Bukti

Karena dan keduanya tidak memiliki titik terasing, menurut akibat

3.10 maka

dan

. Karena itu jika salah satu

atau , maka bukti selesai. Jika dan , maka

menurut batas atas (ii) pada teorema 3.14,

dan

, sehingga

. Karena itu diasumsikan

atau . Karena

, maka . Dengan teorema 3.14,

. Maka

.

E. TEOREMA TENTANG BILANGAN DOMINASI BEBAS DARI

SUATU GRAF

Tidak sulit untuk melihat bahwa setiap himpunan bebas yang

memiliki kardinalitas maksimal dari suatu graf adalah himpunan yang

mendominasi dari . Maka , dimana adalah bilangan

dominasi bebas minimum dari . Bagaimanapun juga tidak semua

himpunan yang mendominasi adalah himpunan bebas.


55

Teorema 3.16

Setiap himpunan bebas yang memiliki kardinalitas maksimal dari suatu

graf adalah himpunan yang mendominasi dari .

Bukti

Misal adalah himpunan bebas dari dan memiliki kardinalitas

terbesar dari semua himpunan bebas di . 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 dalam adalah himpunan yang mendominasi

bebas jika dan hanya jika adalah himpunan bebas yang memiliki

kardinalitas maksimal.

Bukti

Setiap himpunan bebas maksimal adalah himpunan yang mendominasi

berdasarkan teorema 3.16. Sebaliknya, misal adalah himpunan yang

mendominasi bebas, maka adalah himpunan bebas dan setiap titik diluar

berhubungan dengan titik dalam , yang berarti adalah himpunan

bebas maksimal.


56

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 tidak berhubungan dengan titik

dalam . Maka, setiap titik dalam memenuhi sifat (i) dari teorema 3.9.

Menurut 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 dan misal

adalah himpunan bebas maksimal di . Maka, | | dan | | .

Misal adalah himpunan semua titik dalam yang tidak

berhubungan dengan titik dalam , dan misal adalah himpunan bebas

maksimal di . Maka adalah himpunan bebas dari . Karena setiap

titik dalam berhubungan dengan suatu titik dalam dan


57

setiap titik dalam berhubungan ke suatu titik dalam , yang

mengakibatkan adalah himpunan bebas maksimal. Maka menurut

teorema 3.16, adalah himpunan yang mendominasi bebas.

Setiap titik dalam berhubungan dengan paling banyak

titik dalam , jika tidak, maka titik dalam berhubungan dengan

paling sedikit titik dalam dan juga paling sedikit satu titik dalam ,

yang menyebabkan kontradiksi dengan hipotesa bahwa tidak memuat

graf bagian yang diinduksi oleh . Juga, setiap titik dari

berhubungan ke suatu titik dalam . Maka, | | | |

| | | | | | .

Akibatnya,

| | | | | |

| | | |

| |

Akibat 3.18.a

Jika adalah graf bebas cakar, maka .


58

Akibat 3.18.b

Untuk setiap graf , ( ) ( ).

Definisi 3.10

Suatu graf disebut dominasi sempurna jika untuk setiap

graf bagian yang diinduksi oleh .

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.


59

Definisi 3.11

Himpunan dari titik-titik dalam disebut himpunan irredundant dari

jika untuk setiap titik , terdapat titik sedemikian hingga

{ } . Setiap titik yang memenuhi sifat ini disebut titik

irredundant. Himpunan yang bukan himpunan irredundant disebut

himpunan redundant. Setiap titik dalam himpunan redundant disebut

titik redundant.

Dengan kata lain, adalah himpunan irredundant dari jika { }

untuk setiap titik . Dan himpunan adalah himpunan redundant

jika hanya jika terdapat titik dimana { } .

Contoh 3.11

Pada gambar 2.1, misal { }, maka adalah himpunan irredundant,

karena tapi { } dan tapi { }

Teorema 3.19

Himpunan dari titik-titik dalam adalah himpunan irredundant jika

hanya jika setiap titik dalam memenuhi paling sedikit satu dari dua

sifat berikut:


60

(i) terasing dari ,

(ii) Terdapat titik sedemikian sehingga

{ }.

Bukti

Misal adalah himpunan dari titik-titik dalam sedemikian sehingga

untuk setiap titik , 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 adalah himpunan yang irredundant di ,

dan misal . Karena adalah himpunan yang irredundant, terdapat

sedemikian sehingga { } . Jika , maka (ii)

terpenuhi, sedangkan jika , 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.


61

Definisi 3.12

Jika adalah himpunan yang irredundant di , dan , maka setiap

titik di { } disebut kitar pribadi dari .

Titik merupakan kitar pribadi bagi dirinya sendiri. Jika adalah

himpunan yang irredundant di , maka untuk setiap , himpunan

{ } tak kosong.

Contoh 3.12

Pada gambar 2.1, misal { }, titik merupakan kitar pribadi bagi

karena tetapi { } , begitu juga dengan titik dan .

Definisi 3.13

Bilangan irredundance dari suatu graf adalah kardinalitas

minimum dari himpunan yang irredundant di . Sedangkan bilangan

irredundance atas adalah kardinalitas maksimum dari himpunan

yang irredundant di .


62

Contoh 3.13

Dari gambar 2.1 didapatkan dan .

Teorema 3.20


Bukti

Untuk sudah pernah diperlihatkan. Untuk ketidaksamaan

merupakan akibat dari fakta bahwa setiap himpunan yang

mendominasi minimal di adalah himpunan yang irredundant.

Teorema 3.21


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 .


63

Teorema 3.22

Untuk setiap graf bipartit , .

Bukti

Misal adalah graf bipartit dengan himpunan partisi dan . Misal

adalah himpunan irredundant maksimum dari 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 adalah himpunan yang

irredundant, adalah kitar pribadi dari suatu titik di . Karena itu,

untuk , terdapat titik sedemikian sehingga

{ }. Selain itu, karena , menyebabkan .

Misal { | }. Maka | | | | dan .

Selanjutnya tidak ada titik di yang berhubungan dengan titik di .

Akibatnya merupakan himpunan bebas di . Karena

itu, | | | | | | | | | | .


64

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


65

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 , , dan , fasilitas kesehatan

tersebut harus diletakkan di kota . Dengan demikian, harus ada

fasilitas kesehatan di kota dan .

b. Unit kebakaran di kota 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.


66

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 , setiap titik dapat

mendominasi paling banyak 5 titik, sehingga

.

Bagaimanapun, batas yang lebih kecil tidak dapat diterima. Untuk

mendominasi titik ujung seperti , kita harus memasukan titik

atau tetangga dari dalam himpunan yang mendominasi. Titik hanya

mendominasi 3 titik dan tetangganya hanya mendominasi 4 titik. Sehingga

batasnya bertambah menjadi jika menggunakan tetangga setiap

waktu ( , 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


67

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 . Titik juga didominasi. Untuk

mendominasi , harus digunakan titik , karena jika menggunakan

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

ekuivalen dengan menggunakan 2 titik ujung (dimana tidak

diperbolehkan). Sehingga . Sekarang, tidak didominasi.

Titik adalah satu-satunya titik yang mendominasi , yang juga

mendominasi lima titik baru. Jadi . Sekarang terdapat tiga titik

yang tidak didominasi: , , dan . Paling sedikit dibutuhkan

dua titik untuk mendominasi mereka. Jadi . Karena

{ } adalah himpunan yang

mendominasi untuk , maka didapatkan . Sehingga jumlah

minimum dari wadah pembuangan yang diperlukan adalah enam.


68

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 fasilitas-

fasilitas 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


⌉.

Teorema 3.16

Setiap himpunan bebas yang memiliki kardinalitas maksimal

dari suatu graf adalah himpunan yang mendominasi dari .

Teorema 3.9

Sebuah himpunan yang mendominasi dari graf adalah

himpunan yang mendominasi minimal dari graf jika dan


69

hanya jika setiap titik di memenuhi paling sedikit salah

satu dari dua sifat berikut:

(iii) adalah titik terasing dari ,

(iv) Terdapat titik sedemikian sehingga

{ }.

Teorema 3.19

Himpunan dari titik-titik dalam adalah himpunan

irredundant jika hanya jika setiap titik dalam memenuhi

paling sedikit satu dari dua sifat berikut:

(iii) terasing dari ,

(iv) 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 , ”.


70

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.


71

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.


plagiat merupakan tindakan tidak terpuji - usd … · makalah. program studi matematika, jurusan...

Documents