SEMINAR TUGAS AKHIR RAINBOW CONNECTION PADA GRAF 1-CONNECTED VOENID DASTI ( )

Pendahuluan Landasan Teori Rainbow Connection pada Graf 1-Connected Kesimpulan dan Saran

SEMINAR TUGAS AKHIR RAINBOW CONNECTION PADA GRAF 1-CONNECTED

VOENID DASTI 0810432041 Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Andalas Jumu‘ah 26 APRIL 2013 VOENID DASTI (0810432041)

Seminar Tugas Akhir


VOENID DASTI (0810432041)

Seminar Tugas Akhir


List of Contents

1

Pendahuluan Latar Belakang

2

Landasan Teori Defenisi dan Terminologi Graf Terminologi Pewarnaan Graf

3

Rainbow Connection pada Graf 1-Connected

4

Kesimpulan dan Saran


Seminar Tugas Akhir


Latar Belakang

List of Contents

1

Pendahuluan

2

Landasan Teori

3


4



Seminar Tugas Akhir


Latar Belakang

Latar Belakang • 1736. Leonhard Euler (Swiss). Jembatan K¨ onigsberg, di

Rusia timur.

Figure: VOENID DASTI (0810432041)

Seminar Tugas Akhir


Latar Belakang


Rusia timur.

Figure: Masalah Jembatan K¨ onigsberg VOENID DASTI (0810432041)

Seminar Tugas Akhir


Latar Belakang


Rusia timur.

Figure: Masalah Jembatan K¨ onigsberg VOENID DASTI (0810432041)

Seminar Tugas Akhir


Latar Belakang

Latar Belakang • 2006. Chatrand dkk. Konsep rainbow connection . Dapat

digunakan untuk pengamanan pengiriman informasi rahasia antar lembaga. Selain itu, rainbow connection dimotivasi oleh interpretasi menarik di bidang jaringan. • Misalkan G diinterpretasikan sebagai suatu jaringan (misalnya, jaringan selular). Akan disampaikan rute pesan antara dua titik penerima, acceptor , dengan syarat bahwa rute antara kedua titik (atau dapat dilihat sebagai sisi pada path), diberikan suatu saluran yang berbeda (misalnya, frekuensi yang berbeda). Jelas bahwa yang ingin diminimalkan adalah banyaknya saluran berbeda yang digunakan dalam jaringan. Bilangan ini adalah rainbow connection number rc(G) [3]. Dalam skripsi ini dikaji kembali tentang rainbow connection pada graf 1-connected. VOENID DASTI (0810432041)

Seminar Tugas Akhir


Latar Belakang

Perumusan Masalah

Penentuan rainbow connection number pada graf dapat lebih mudah dilakukan setelah mengelompokkan graf berdasarkan diameter, derajat, keterhubungan (connectivity) graf atau berdasarkan parameter lain. Dalam skripsi ini akan dikaji kembali rainbow connection number graf berdasarkan keterhubungan (connectivity) dan derajat minimumnya.


Seminar Tugas Akhir


Latar Belakang

Batasan Masalah

• Pengkajian kembali rainbow connection number pada

skripsi ini dibatasi pada graf terhubung G tak trivial 1-connected dengan derajat minimum δ(G) ≥ 3.


Seminar Tugas Akhir


Latar Belakang

Tujuan

Pada penelitian yang dilakukan oleh Caro dkk [3] pada tahun 2008, Caro membuat konjektur, yaitu jika G suatu graf dengan n titik dan δ(G) ≥ 3 maka rainbow connection number rc(G) ≤ (3n) 4 . Konjektur tersebut terbukti benar untuk graf 2-connected [3]. Tujuan penulisan ini adalah untuk mengaji kembali kebenaran konjektur tersebut untuk graf 1-connected. .


Seminar Tugas Akhir


Defenisi dan Terminologi Graf Terminologi Pewarnaan Graf

List of Contents

1

Pendahuluan

2

Landasan Teori

3


4



Seminar Tugas Akhir



Defenisi Graf

Definisi 2.1 Suatu graf G didefinisikan sebagai pasangan himpunan (V (G), E(G)) dengan V (G) adalah himpunan titik (vertex ) tak kosong dan E(G) adalah himpunan sisi (edge) yang menghubungkan titik-titik pada G. •


Seminar Tugas Akhir



Terminologi

(cut vertex ) adalah suatu titik yang jika diambil dari suatu graf terhubung akan menyebabkan graf menjadi tak terhubung. Blok (block ) adalah suatu graf terhubung yang tidak mempunyai cut vertex. Jembatan (bridge) adalah suatu sisi pada graf yang jika diambil dari suatu graf terhubung, akan menyebabkan graf tersebut menjadi tak terhubung.


Seminar Tugas Akhir



Latar Belakang • cut vertex

Figure: c sebagai cut vertex VOENID DASTI (0810432041)

Seminar Tugas Akhir



Latar Belakang • cut edge

Figure: s sebagai jembatan (bridge) VOENID DASTI (0810432041)

Seminar Tugas Akhir



Pewarnaan

• Pewarnaan titik (vertex coloring), yaitu pemberian warna

berbeda pada setiap titik-titik yang saling bertetangga. • Pewarnaan sisi (edge coloring), yaitu pemberian warna

berbeda pada sisi yang bertetangga. • Pewarnaan bidang, yaitu pemberian warna pada bidang

sehingga tidak ada bidang yang bertetangga mempunyai warna yang sama.


Seminar Tugas Akhir




Seminar Tugas Akhir



Rainbow Connection Pada Graf Didefenisikan pewarnaan c : E(G) 7→ {1, 2, ..., k}, kN dimana dua sisi bertetangga tidak perlu berwarna berbeda.

Figure: Path


Seminar Tugas Akhir



Rainbow Connection Pada Graf Jalan (walk ) dari titik v0 ke titik vn di G adalah barisan hingga v0 , e1 , v1 , e2 , v2 , ..., vn−1 , en , vn sedemikian sehingga vi−1 vi ∈ E(G), untuk i = 1, 2, ..., n. Lintasan (path) adalah jalan yang semua titik dan sisinya berbeda. Suatu lintasan u-v path P dikatakan lintasan rainbow path jika tidak terdapat dua sisi di P yang memiliki warna sama.


Seminar Tugas Akhir



Rainbow Connection Pada Graf G dikatakan bersifat rainbow connected jika terdapat satu rainbow path yang menghubungkan setiap dua titik berbeda di G

Figure: Rainbow Connected VOENID DASTI (0810432041)

Seminar Tugas Akhir



Rainbow Connection Pada Graf Jarak u ke v, d(u,v) adalah panjang lintasan terpendek dari u ke v. Untuk dua titik u dan v di G, rainbow u-v geodesic pada G adalah rainbow u-v path yang panjangnya d(u, v) adalah jarak antara u dan v (panjang u-v path terpendek di G)

Figure: rainbow u-v geodesic VOENID DASTI (0810432041)

Seminar Tugas Akhir



Rainbow Connection Pada Graf Pewarnaan sisi yang menyebabkan G bersifat rainbow connected disebut rainbow coloring . Rainbow connection number dari graf terhubung G, ditulis rc(G), adalah banyak warna minimal yang diperlukan untuk membuat G bersifat rainbow connected. Suatu rainbow coloring yang menggunakan warna sebanyak rc(G) dikatakan minimum rainbow coloring

Figure: rc(G)=2 VOENID DASTI (0810432041)

Seminar Tugas Akhir



Rainbow Connection Pada Graf Graf G dikatakan strongly rainbow connected jika G memiliki suatu rainbow u-v geodesic untuk setiap dua titik u dan v di G. Dalam kasus ini, pewarnaan c dikatakan strong rainbow coloring di G.

Figure: rc(G) dan src(G) VOENID DASTI (0810432041)

Seminar Tugas Akhir



Keterhubungan Suatu graf G disebut terhubung jika untuk setiap dua titik dari graf terdapat lintasan yang menghubungkan kedua titik tersebut.

Figure: Konektivitas


Seminar Tugas Akhir



Graf G2 adalah graf 1-connected


Seminar Tugas Akhir



Rainbow Connection

Proposisi 2.4.1 [2] Misalkan G suatu graf terhubung (connected) berukuran m. Maka (a) src(G) = 1 jika dan hanya jika G suatu graf lengkap, (b) rc(G) = 2 jika dan hanya jika src(G) = 2, (c) rc(G) = m jika dan hanya jika G merupakan suatu graf pohon. zUkuran graf G adalah banyak sisi di graf G.X


Seminar Tugas Akhir



Rainbow Connection

Proposisi 2.4.2 [2] Untuk setiap bilangan n ≥ 4, rc(Cn ) = src(Cn ) = dn/2e Graf lingkaran dengan banyak titik n, dinotasikan dengan Cn , adalah graf sederhana (tidak memuat loop atau sisi ganda) yang memiliki derajat 2 pada setiap titiknya. X


Seminar Tugas Akhir


List of Contents

1

Pendahuluan

2

Landasan Teori

3


4



Seminar Tugas Akhir


Graf dengan konektivitas 1 Pada graf G dengan konektivitas κ(G) = 1, konsep rainbow connection diperluas dengan menambahkan syarat, yaitu ........................................ .. . untuk sebarang dua sisi di G, sisi-sisi tersebut memiliki warna . berbeda bilamana berada pada blok yang berbeda di G. .. . Rainbow connection number yang bersesuaian dengan penambahan syarat ini dinotasikan dengan rc∗ (G). Dari defenisinya, jelas bahwa rc(G) ≤ rc∗ (G) untuk setiap graf G dan rc(G) = rc∗ (G) untuk setiap graf 2-connected G.


Seminar Tugas Akhir


Rainbow Connection Number rc∗ (G)

Pada graf dengan κ(G) = 1, akan dibuktikan teorema berikut: Teorema 3.3.1 Jika G suatu graf terhubung dengan n banyaknya titik, κ(G) = 1 dan δ(G) ≥ 3 maka rc∗ (G) ≤ 3n−10 4 . Batas 3n−10 tidak dapat dikurangkan karena terdapat graf 4 terhubung 3 − regular dengan rc(G) = rc∗ (G) = diam(G) = 3n−10 4 .


Seminar Tugas Akhir


Graf terhubung 3-regular G dengan rc∗ (G) =

3n−10 4

Suatu graf terhubung 3 − regular dapat dikonstruksi dengan langkah-langkah berikut : 1 Ambil dua vertex disjoint pada graf hasil penggandaan graf K5 − (P3 ∪ P2 ) dan beri label dua titik berderajat 2 dengan w1 dan w2k+2 dengan k ≥ 1, k bilangan bulat. 2 Hubungkan w1 dan w2k+2 melalui suatu lintasan dengan panjang 2k + 1 dan beri label titik-titik pada lintasan tersebut dengan w1 , w2 , ..., w2k+2 . 3 Untuk 1 ≤ i ≤ k, setiap sisi w2i w2i+1 diganti dengan suatu graf K4 − e dan tandai dua titik yang berderajat 2 di K4 − e dengan w2i dan w2i+1 . 4 Graf yang diperoleh dari proses di atas adalah graf G4k+10 yang merupakan graf terhubung 3 − regular dengan n = 4k + 10 dan rc∗ (G4k+10 ) = rc(G4k+10 ) = diam(G4k+10 ) = 3k+5 = 3n−10 4 VOENID DASTI (0810432041)

Seminar Tugas Akhir


Graf terhubung 3-regular contoh : untuk k = 1, diperolah G14 yang merupakan graf terhubung 3 − regular :

rc∗ (G14 ) = rc(G14 ) = diam(G14 ) = VOENID DASTI (0810432041)

3(14)−10 4

=8

Seminar Tugas Akhir


Teorema 3.3.1 Sebelum membuktikan teorema 3.3.1 diatas, terlebih dulu dibuktikan proposisi 3.3.1 dan akibat 3.3.1 berikut : Proposisi 3.3.1 Misalkan G suatu graf 2-connected dengan n banyak titik dan barisan derajatnya 2 ≤ d1 ≤ d2 ≤ ... ≤ dn . Jika d3 ≥ 3 maka rc(G) ≤ 2n−2 untuk 4 ≤ n ≤ 7 dan rc(G) ≤ 2n−1 untuk n ≥ 8. 3 3 Akibat 3.3.1 Misalkan G suatu graf 2-connected dengan n banyaknya titik dan barisan derajat 2 ≤ d1 ≤ d2 ≤ ... ≤ dn . Jika d3 ≥ 3, maka rc(G) ≤ 3n−4 4 .


Seminar Tugas Akhir


Proposisi 3.3.1

Bukti Proposisi 3.3.1 Misalkan H suatu subgraf terhubung maksimal dari G dan rc(H) ≤ 2h 3 − 1 dengan h adalah banyak titik di H. Klaim H tersebut ada. Karena G suatu graf 2-connected dan d3 ≥ 3, maka n ≥ 4. Berdasarkan teorema Dirac [6], circumference c(G) pada G memenuhi c(G) ≥ min{n, 2δ(G)} ≥ 4. Selanjutnya, pandang beberapa kasus: z Circumference G, dinotasikan dengan c(G), merupakan panjang dari lingkaran terpanjang di G.


Seminar Tugas Akhir


Bukti Proposisi 3.3.1 (2)

Kasus 1. Jika n=4, maka rc(G) ≤ 2 ≤ 2.4−2 3 . ∼ Jika c(G) = 4 maka G = K2,n−2 , yang kontradiksi dengan d3 ≥ 3 untuk n ≥ 5. Jadi dapat diasumsikan bahwa c(G) ≥ 5 Kasus 2. Jika n = 5 = c(G) maka G memuat C5 + e sebagai subgraf dan rc(G) ≤ 2 ≤ 2.5−2 3 .


Seminar Tugas Akhir



Kasus 3. Jika n = 6. Subkasus 1 Jika c(G) = 5, maka dengan menjadikan H sebagai C5 dengan satu sisi yang ditambahkan, diperoleh rc(G) = 3 = 2.6 3 − 1. Subkasus 2 Jika c(G) = 6, maka dengan menjadikan C6 sebagai H, didapat rc(C6 ) = 3 [2]. look, it is possbl to K6 to be frmed


Seminar Tugas Akhir



Kasus 4. Jika n > 5 Subkasus 1 Jika c(G) ∈ {6, 8} maka rc(Ck ) = untuk k = 6, 8.

k 2

≤

Subkasus 2 Jika c(G) = 7 = n maka rc(C7 ) = 4 =

2k 3

−1

2.7−2 3 .

Subkasus 3 Jika c(G) = 7 < n maka dengan menjadikan H sebagai suatu C7 dengan suatu sisi yang ditambahkan, didapat rc(H) = 4 < 2.8 3 − 1. Subkasus 4 Jika c(G) = k ≥ 9 maka 2k rc(Ck ) = d k2 e ≤ k+1 2 ≤ 3 − 1.


Seminar Tugas Akhir



Kemudian, klaim h ≥ n − 2. Bukti Klaim • Asumsikan bahwa h < n − 2, ini berarti terdapat tiga titik

berbeda yang terletak diluar H,yaitu w1 , w2 , w3 yang masing-masing memiliki dua tetangga yang berada di dalam H (tetangga-tetangga dari titik wi tidak perlu berbeda dengan tetangga-tetangga dari titik wj ). • Titik-titik w1 , w2 , w3 dapat ditambahkan ke graf H

sehinggaa terbentuk suatu subgraf yang lebih besar, H 0 , dengan h + 3 titik.


Seminar Tugas Akhir


Bukti Proposisi 3.3.1 (4) Kemudian, klaim h ≥ n − 2. Bukti Klaim • Anggap ei , fi adalah dua sisi yang menghubungkan wi dengan H. Dua warna dapat digunakan untuk mewarnai keenam sisi, yaitu e1 , e2 , e3 diwarnai dengan warna yang sama dan f1 , f2 , f3 memiliki warna lain yang sama pula.


Seminar Tugas Akhir



Sehingga diperoleh: rc(H 0 ) ≤ rc(H) + 2 ≤

2h 3

−1+2=

2(h+3) 3

−1

kontradiksi dengan pernyataan bahwa H merupakan subgraf maksimal


Seminar Tugas Akhir



• Ini berarti bahwa, jika terdapat tiga titik diluar H maka

sekurang-kurangnya salah satu dari titik-titik tersebut, katakanlah w, memiliki sifat bahwa untuk suatu lintasan terpendek dari H ke H yang melewati w, memiliki panjang tidak kurang dari 3 ( perhatikan bahwa pasti terdapat suatu path karena G adalah graf 2-connected ). • Misalkan uw1 w2 ...wt v suatu lintasan dengan u, vV (H),

w1 , ..., wt ∈ / V (H) dan t ≥ 2. Titik-titik w1 , ..., wt ditambahkan ke H sehingga membentuk suatu subgraf H 0 yang lebih besar dengan h + t banyaknya titik.


Seminar Tugas Akhir



• Misalkan uw1 w2 ...wt v suatu lintasan dengan u, vV (H),

w1 , ..., wt ∈ / V (H) dan t ≥ 2. Titik-titik w1 , ..., wt ditambahkan ke H sehingga membentuk suatu subgraf H 0 yang lebih besar dengan h + t banyaknya titik.


Seminar Tugas Akhir


Bukti Proposisi 3.3.1 (7) • Jika t ganjil maka t + 1 sisi lintasan diberi t+1 2 warna baru.

Paruh pertama beri warna berbeda pada sisi-sisi nya, dan urutan warna yang sama diwarnakan pada paruh kedua. Hal ini menunjukkan bahwa H 0 bersifat rainbow connected


Seminar Tugas Akhir


Bukti Proposisi 3.3.1 (7) • t genap, maka t + 1 sisi lintasan diwarnai dengan 2t warna.

Sisi tengah, wt/2 wt/2+1 , diberi warna yang sudah muncul di H. 2t sisi pertama pada lint diberi warna menggunakan warna baru yang berbeda dan pada 2t sisi terakhir, warna-warna tersebut diulang dengan urutan sama.


Seminar Tugas Akhir



Proses ini menunjukkan bahwa H 0 bersifat rainbow connected dan diperoleh : rc(H 0 ) ≤ rc(H) + d 2t e ≤

2h 3

− 1 + d 2t e ≤

2(h+t) 3

−1

kontradiksi dengan pernyataan bahwa H subgraf maksimal. Jadi, haruslah h ≥ n − 2


Seminar Tugas Akhir


• Setelah membuktikan bahwa h ≥ n − 2, • jelaslah bahwa rc(G) ≤ 2(n−2) − 1 + 2 = 2n−1 3 3 • Bukti Proposisi 3.3.1 selesai | {z }


Seminar Tugas Akhir


Proposisi 3.3.1 dan Akibat 3.3.1

Proposisi 3.3.1 X Misalkan G suatu graf 2-connected dengan n banyak titik dan barisan derajatnya 2 ≤ d1 ≤ d2 ≤ ... ≤ dn . Jika d3 ≥ 3 maka untuk 4 ≤ n ≤ 7 dan rc(G) ≤ 2n−1 untuk n ≥ 8. rc(G) ≤ 2n−2 3 3 Akibat 3.3.1 X Misalkan G suatu graf 2-connected dengan n banyaknya titik dan barisan derajat 2 ≤ d1 ≤ d2 ≤ ... ≤ dn . Jika d3 ≥ 3, maka rc(G) ≤ 3n−4 4 .


Seminar Tugas Akhir


Endblock

Berikut akan ditentukan struktur endblocks. Endblock adalah block yang mempunyai tepat satu cut vertex. Misalkan B={K4 , K5 , K5 − e, K5 − P3 , K5 − 2P2 , K5 − (P3 ∪ P2 )}. Diperoleh: rc(K4 ) = rc(K5 ) = 1 dan rc(K5 −e) = rc(K5 −P3 ) = rc(K5 −2P2 ) = rc(K5 −(P2 ∪P3 )) = 2.


Seminar Tugas Akhir


Endblock

Figure: rc(G)=1


Seminar Tugas Akhir


Endblock

Figure: rc(G)=2


Seminar Tugas Akhir


Endblock Untuk BB, misalkan B ∪ K2 suatu endblock dengan penambahan K2 . • Jika B{K4 , K5 , K5 − e, K5 − 2P2 } maka K2 dapat ditambahkan ke sebarang titik di B.


Seminar Tugas Akhir


Endblock Untuk BB, misalkan B ∪ K2 suatu endblock dengan penambahan K2 . • Jika B{K4 , K5 , K5 − e, K5 − 2P2 } maka K2 dapat ditambahkan ke sebarang titik di B.


Seminar Tugas Akhir


Endblock • Jika B{K5 − P3 , K5 − (P3 ∪ P2 )} maka K2 dapat

ditambahkan pada titik berderajat 2 dalam K5 − P3 atau K5 − (P3 ∪ P2 ).


Seminar Tugas Akhir


Endblock

Sekarang, klaim berikut dapat dibuktikan. Klaim 1. Misalkan G suatu graf terhubung dengan δ(G) ≥ 3. Jika G = G1 ∪ G2 dengan V (G1 ) ∩ V (G2 ) = w untuk w suatu cut vertex dan |V (G1 )| ≤ 6 maka G1 ∼ = B atau G1 ∼ = B ∪ K2 untuk beberapa BB Klaim 2. Jika BB suatu endblock maka rc(B) ≤ rc(B ∪ K2 ) ≤ 3n−6 4 .


Seminar Tugas Akhir

3n−7 4

dan


Teorema 3.3.1 Klaim 3. Misalkan G suatu graf terhubung dengan suatu cut vertex w. Jika G = G1 ∪ G2 dan V (G1 ) ∩ (V (G2 )) = w, dG1 (w) ≥ 2, dG2 (w) ≥ 1, V |(G1 )| ≥ 6 dan V |(G2 )| ≥ 7. Maka dengan induksi didapat rc∗ (G) ≤ 3n−10 4 . Bukti Klaim 3. Konstruksi dua graf, yaitu H1 dan H2 : H1 = (K5 − P3 ) ∪ G2 . Identifikasi titik berderajat 2 dalam K5 − P3 dengan w dari G2 . H2 = G1 ∪ K2 ∪ (K5 − P3 ), identifikasi satu titik di K2 dengan w di G1 dan titik lain dari K2 dengan titik berderajat 2 dalam K5 − P3 .


Seminar Tugas Akhir


Teorema 3.3.1

Diperoleh : ...(bukti klaim) |V (H1 )| = |V (K5 − P3 )| + |V (G2 )| − 1 < |V (G1 )| + |V (G2 )| − 1 = |V (G)| dan |V (H2 )| = |V (K5 −P3 )∪K2 )|+|V (G1 )|−1 < |V (G2 )|+|V (G1 )|− 1 = |V (G)|.


Seminar Tugas Akhir



Seminar Tugas Akhir



Seminar Tugas Akhir


Teorema 3.3.1 ...(bukti klaim) dengan induksi didapat rc∗ (H1 ) ≤ 3n(H41 )−10 dan rc∗ (H2 ) ≤ yang mengakibatkan

3n(H2 )−10 4

rc∗ (G2 ) ≤

3(n(G2 )+4)−10 4

−2=

3n(G2 )−6 4

rc∗ (G1 ) ≤

3(n(G1 )+5)−10 4

−3=

3n(G1 )−7 . 4

dan

Hasil ini memberi persamaan rc∗ (G) = rc∗ (G1 ) + rc∗ (G2 ) ≤ =

3(n(G1 )+n(G2 )−1)−10 4

=

3n(G1 )−7 4

+

3n(G2 )−6 4

3n−10 4 .


Seminar Tugas Akhir


block graf pohon T dari G. Misalkan V (T ) = {w1 , w2 , ..., b1 , b2 , ...}, dimana wi adalah suatu cut vertex pada G dan bi merupakan blok Bi dari G. wi bj E(T ) jika dan hanya jika wi insiden dengan Bj di dalam G. Amati pengamatan berikut : • 1 Jika Bi suatu endblock dari G (bi merupakan daun dari

(T )) maka |V (Bi | ≥ 4, karena δ ≥ 3. • 2 Jika dT (w) ≥ 4 untuk suatu cut vertex w dari G maka

G = G1 ∪ G2 dengan G1 ∩ G2 = w serta kedua graf G1 dan G2 memuat paling sedikit dua block nontrivial. Kemudian |V (Gi )| ≥ 2.4 − 1 = 7 untuk i = 1, 2 Jadi dapat diasumsikan bahwa 2 ≤ dT (w) ≤ 3 untuk setiap cut vertex w.


Seminar Tugas Akhir


block graf pohon T dari G. • 3 Jika suatu cut vertex w berderajat 3, maka

G = G1 ∪ G2 ∪ G3 . Dari argumen pada observasi kedua di atas, masing-masing Gi memuat tepat satu block nontrivial yang merupakan endblock. |V (Gi )| ≤ 6 untuk 1 ≤ i ≤ 3, untuk nilai i yang lain dapatkan dengan induksi. Dari |V (G)| = |V (G1 )| + |V (G2 )| + |V (G3 )| − 2 didapatkan ≤ 3n−10 rc∗ (G) ≤ 3n(G41 )−6 + 3n(G42 )−6 + 3n(G43 )−6 = 3n−12 4 4 . • 4 Jika suatu titik b berderajat p ≥ 3 maka B berinsiden

dengan p cut vertices w1 , w2 , ..., wp . Sehingga G = B ∪ G1 ∪ G2 ∪ ... ∪ Gp . Maka rc∗ (G) ≤ 2n(B) + Σp i=1 3n(G4i )−6 ≤ 3 3n(B)−1 + 3(n+p−n(B))−6p = 3n−1−3p ≤ 3n−10 4 4 4 4 . VOENID DASTI (0810432041)

Seminar Tugas Akhir


graf pohon blok T dari G. Jadi dapat diasumsikan bahwa M (T ) = 2 dan dengan demikian T adalah suatu path. G memuat paling banyak satu inner block nontrivial B. Jadi untuk path T , struktur-struktur block berikut dapat terbentuk : 1 B1 , B2 . Sehingga < 3n−10 rc∗ (G) ≤ 3n(B41 )−7 + 3n(B42 −7) = 3n−11 4 4 . 2 B1 , K2 , B2 . Sehingga 2 )−6 rc∗ ≤ 3n(B1 ∪K + 3n(B42 )−7 = 3n−10 4 4 . 3 B1 , B, B2 . Sehingga rc∗ (G) ≤ 3n(B41 )−7 + 3n(B)−4 + 3n(B42 )−7 = 3n−12 < 3n−10 4 4 4 . 4 B1 , K2 , B, B2 . Sehingga 2 )−4 rc∗ ≤ 3n(B1 ∪K + 3n(B)−6 + 3n(B42 )−7 = 3n−11 < 3n−10 4 4 4 4 . 5 B1 , K2 , B, K2 , B2 . Sehingga 2 )−6 2 )−6 rc∗ (G) ≤ 3n(B1 ∪K + 3n(B)−4 + 3n(B2 ∪K = 3n−10 4 4 4 4 . VOENID DASTI (0810432041)

Seminar Tugas Akhir


List of Contents

1

Pendahuluan

2

Landasan Teori

3


4



Seminar Tugas Akhir


Kesimpulan

Jika graf terhubung G dengan κ(G) = 1 dan δ(G) ≥ 3, maka pada pembahasan skripsi ini telah diperoleh bahwa < 3n rc∗ (G) ≤ 3n−10 4 4 , dengan n adalah banyak titik di G. Dengan rc(G) adalah rainbow connection number pada graf terhubung tak trivial G dan rc∗ (G) adalah rainbow connection number pada graf 1-connected tak trivial..


Seminar Tugas Akhir


Terima Kasih


Seminar Tugas Akhir

SEMINAR TUGAS AKHIR RAINBOW CONNECTION PADA GRAF 1-CONNECTED VOENID DASTI ( )

Recommend Documents