EKSPONEN VERTEX DARI DIGRAPH DWI-WARNA DENGAN DUA LOOP SKRIPSI NURUL HIDAYATI

EKSPONEN VERTEX DARI DIGRAPH DWI-WARNA DENGAN DUA LOOP

SKRIPSI

NURUL HIDAYATI 060803032

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2011

Universitas Sumatera Utara


SKRIPSI

Diajukan untuk melengkapi tugas dan memenuhi syarat mencapai gelar Sarjana Sains


DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2011


i PERSETUJUAN

Judul

: EKSPONEN VERTEX DARI DIGRAPH DWIWARNA DENGAN DUA LOOP

Kategori

: SKRIPSI

Nama

: NURUL HIDAYATI

Nomor Induk Mahasiswa

: 060803032

Program Studi

: SARJANA (S1) MATEMATIKA

Departemen

: MATEMATIKA

Fakultas

: MATEMATIKA DAN ILMU PENGETAHUAN ALAM (FMIPA) UNIVERSITAS SUMATERA UTARA

Medan, Nopember 2011

Komisi Pembimbing : Pembimbing 2

Pembimbing 1

Dra. Mardiningsih, M.Si

Dr. Saib Suwilo, M.Sc.

NIP.19630405 198811 2 001

NIP. 19640109 198803 1 004

Diketahui oleh Departemen Matematika FMIPA USU Ketua,

Prof. Dr. Tulus, M.Si NIP. l9620901 198803 1 002


ii PERNYATAAN


SKRIPSI

Saya mengakui bahwa skripsi ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.

Medan,

Nopember 2011



iii PENGHARGAAN

Alhamdulillahirabbil’alamiin, penulis panjatkan ke hadirat ALLAH Subhanahu Wa Ta’ala dengan tidak putus-putusnya, yang telah mencurahkan rahmat dan hidayah-Nya kepada penulis sehingga penulis dapat menyelesaikan skripsi yang berjudul ”EKSPONEN VERTEX DARI DIGRAPH DWI-WARNA DENGAN DUA LOOP” ini dengan baik. Tak lupa juga Sholawat beriring salam kepada junjungan Nabi Muhammad Shallallahu ’Alaihi Wassalam beserta keluarga dan para sahabat. Pada kesempatan ini penulis mengucapkan terima kasih yang sebesar-besarnya kepada semua pihak yang banyak membantu, memotivasi dan mendo’akan penulis dari awal penulis memulai sampai menyelesaikan skripsi ini, yaitu kepada: 1. Bapak Dr. Sutarman, M.Sc, selaku Dekan Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Sumatera Utara. 2. Bapak Prof. Dr. Tulus, M.Si dan Ibu Dra. Mardiningsih, M.Si, selaku Ketua dan Sekretaris Departemen Matematika F-MIPA USU Medan. 3. Bapak Dr. Saib Suwilo, M.Sc, selaku dosen pembimbing I dan Ibu Dra. Mardiningsih, M.Si, selaku dosen pembimbing II, yang telah banyak membantu dan memberi dukungan baik berupa nasehat maupun ilmu pengetahuan, serta dukungan moril dan motivasi bagi penulis dalam menyelesaikan penelitian ini. 4. Seluruh staf pengajar dan staf administrasi Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Sumatera Utara. 5. Guru-guru yang telah sabar mendidik penulis di SD Negeri 101896 Kiri Hulu khususnya ibu kami Buk Ros yang telah meninggalkan dunia ini, di SLTP Swasta Tanjungmorawa Bersubsidi khususnya Ibu Lindawati Pakpahan, serta di SMA Negeri 5 Medan khususnya Ibu Farawiati Adrianti. 6. Ibunda Sunariyah, S.Pd dan Ayahanda Djumianto Wardhana yang telah begitu sabar dan penuh cinta mendo’akan penulis, memberikan dukungan moril dan materiil serta motivasi kepada penulis untuk segera menyelesaikan tulisan ini. Dan juga kepada abangda Fitrayadi Eka Wardhana, S.E beserta kakanda Sunarseh, abangda Dwiyanto Setiawan, S.T beserta kakanda Yani Farahdina Nasution, S.P, yang juga telah menyemangati dan mendo’akan penulis serta kepada keponakan-keponakan penulis Halwa Aulia Wardhana, Wardah Annisa Wardhana dan Muhammad Luthfi Setiawan yang telah memberikan rona ceria di hari-hari penulis pada saat menyelesaikan penelitian ini. 7. Nurlinda Sari Butarbutar dan Tuti Larasati yang senantiasa bersama penulis dalam suka dan duka, bersama-sama dalam menyelesaikan skripsi serta saling mendo’akan, saling memotivasi dan saling membantu. Universitas Sumatera Utara

iv Penulis juga berterima kasih kepada Mohammad Amin yang begitu banyak memberikan semangat dan mendo’akan kebaikan penulis, abangda Heri Risdianto, pak Agustin, serta sahabat-sahabat Reza, Cory, Jo, Ulfa, Tanti, Eko, Satria, Tantri, Rani, Agung, Rini, Ayu, Sari, Tika dan Andi dan sepupu-sepupu yang tergabung dalam Wagiran’s Club khususnya Mbak Tia, Puput, Anis, Dita, Dini dan Nanda. Juga kepada Aghni, Bayu, bang Zuhri, kak Nenna, bang Deni, kak Masnah, kak Rima, kak Diana, bang Budi, kak Nana, Putri, Rina, bang Nanang yang telah membantu dan menyemangati penulis. Teman-teman seperjuangan anak-anak Murni 2006, serta teman-teman stambuk 2006, abangda dan kakanda stambuk 2002, 2003, 2004 dan 2005, serta adinda stambuk 2007, 2008 dan 2009, anggota IM-KUBIK, ukhti-ukhti di musholah UKMI AL-FALAK dan semua teman-teman penulis baik dirumah, SD, SMP maupun SMA dan di lingkungan USU yang telah mendukung dan menyemangati penulis yang tidak dapat disebutkan satu persatu, terimakasih semuanya. Penulis menyadari masih ada kekurangan dalam penelitian ini, penulis mengharapkan kritik dan saran yang membangun dari pembaca sekalian. Akhir kata penulis mengucapkan terima kasih atas perhatiannya, semoga tulisan ini dapat bermanfaat bagi semua dan di dunia pendidikan.

Medan, 01 Oktober 2011 Penulis,

Nurul Hidayati


v ABSTRAK

Suatu digraph D yang setiap arc-nya berwarna merah atau biru disebut digraph dwi-warna. Suatu digraph dwi-warna terhubung kuat dikatakan primitif jika terdapat bilangan bulat tak negatif m dan b sehingga untuk setiap pasangan vertex u dan v di D terdapat walk dari u ke v dengan panjang m + b, dimana banyaknya arc merah adalah m dan banyaknya arc biru adalah b. Misalkan D adalah digraph dwi-warna dengan V (D) = {v1, v2 , · · · , vn } untuk setiap vk ∈ V (D), maka eksponen vertex dari D adalah bilangan bulat positif terkecil m + b sedemikian hingga terdapat walk dengan panjang m + b dari vk ke masing-masing vertex di D. Andaikan D adalah suatu digraph dwi - warna yang terdiri dari n vertex dengan n ≥ 3 dan memiliki 2 loop, dan jika vk , k = 1, 2, ..., n adalah vertex di D, tulisan ini akan memperlihatkan pola dari eksponen vertex di D tepat 2n−2 untuk k = 1, 2, 3 dan tepat 2n − 5 + k untuk 4 ≤ k ≤ n.


vi VERTEX EXPONENT OF A TWO-COLOURED DIGRAPH WITH 2 LOOPS

ABSTRACT

A digraph D in which each of its arcs is coloured by either red or blue is called two-coloured digraph. A strongly connected of two-coloured digraph is primitive provided there are nonnegative integers m and b such that for each pair of vertices u and v in D there is a walk with length m + b, in which m arcs coloured by red and b arcs coloured by blue. Let D is a two-coloured digraph with V (D) = {v1, v2, · · · , vn } for each vk ∈ V (D), the vertex exponent of D is the smallest nonnegative integer m + b such that there is a walk with length m + b from vk to each vertex in D. Let D is a two-coloured digraph on n vertex with n ≥ 3 and 2 loops, if vk , k = 1, 2, ..., n is vertex of D, this paper will give the general of vertex exponent of D exactly 2n − 2 for k = 1, 2, 3 and exactly 2n − 5 + k for 4 ≤ k ≤ n.


vii DAFTAR ISI

Halaman PERSETUJUAN

i

PERNYATAAN

ii

PENGHARGAAN

iii

ABSTRAK

v

ABSTRACT

vi

DAFTAR ISI

vii

DAFTAR GAMBAR

ix

BAB 1. PENDAHULUAN 1.1. 1.2. 1.3. 1.4. 1.5.

1

Latar Belakang Perumusan Masalah Tujuan Penelitian Manfaat Penelitian Metodologi Penelitian

1 4 4 4 4

2. DIGRAPH DAN 2-DIGRAPH 2.1. 2.2. 2.3. 2.4. 2.5.

6

Definisi Matriks Adjacency Primitifitas dari Digraph dan 2-Digraph Terhubung Kuat Eksponen Digraph dan 2-Digraph Eksponen Vertex Digraph dan 2-Digraph

3. DIGRAPH DWI-WARNA DENGAN 2 LOOP

29

3.1. Eksponen 2-Digraph dengan 2 Loop 3.2. Eksponen Vertex 2-Digraph dengan 2 Loop 4. KESIMPULAN DAN SARAN 4.1. Kesimpulan 4.2. Saran DAFTAR PUSTAKA

6 11 12 16 24

29 32 41 41 41 42


viii LAMPIRAN A. FUNGSI MATLAB ”VERT 2EXP LOOPS”

43

B. OUTPUT DARI FUNGSI MATLAB ”VERT 2EXP LOOPS”

47


ix DAFTAR GAMBAR

Gambar

Halaman

1.1

Digraph dengan 2 Loop

3

2.1

Digraph dengan 6 vertex dan 9 arc

7

2.2

Digraph dengan walk, path, cycle dan loop

8

2.3

2-Digraph dengan 6 vertex dan 9 arc

9

2.4

2-Digraph dengan walk, path, cycle dan loop

2.5

(a) Digraph terhubung kuat

2.6

Digraph terhubung kuat dan primitif

2.7

(a) 2-digraph terhubung kuat

2.8

2-Digraph terhubung kuat dan primitif

16

2.9

Digraph Wielandt Wn dengan n vertex

27

3.1

2-Digraph dengan 2 Loop

36

10

(b) Digraph tidak terhubung kuat 13 14

(b) 2-digraph tidak terhubung kuat 15


EKSPONEN VERTEX DARI DIGRAPH DWI-WARNA DENGAN DUA LOOP SKRIPSI NURUL HIDAYATI

Recommend Documents