Path: TopS2-ThesesMathematics-FMIPA2014

BILANGAN TERHUBUNG PELANGI PADA GRAF LINGKARAN, PERTEMANAN, KIPAS, DAN RODA DENGAN BEBERAPA OPERASINYA

Master Theses from JBPTITBPP / 2017-09-27 14:41:47
Oleh : ANTIK ESTIKA HADER (NIM:20112001) ; Pembimbing Tesis Prof. Dr. M. Salman A.N., S2 - Mathematics
Dibuat : 2014, dengan 6 file

Keyword : bilangan terhubung pelangi, pewarnaan sisi, lingkaran, pertemanan, kipas, roda, lintasan.

Graf yang dibahas di dalam tesis ini adalah graf hingga, sederhana, dan tak berarah. Misalkan G = (V (G);E(G)) adalah graf terhubung tak trivial dan m adalah suatu bilangan bulat positif. Didefinisikan c : E(G) ->(1,2,...,m) sebagai suatu pewarnaan-m sisi dari G: Lintasan P di G dikatakan lintasan pelangi, jika tidak terdapat sisi di P yang mempunyai warna yang sama. Misalkan u dan v adalah titik di G, suatu lintasan pelangi dikatakan lintasan pelangi u - v jika lintasan tersebut mempunyai titik ujung u dan v: Bilangan terhubung pelangi dari G dinotasikan dengan rc(G) adalah m terkecil sehingga G mempunyai pewarnaan-m sisi sedemikian sehingga setiap dua titik u,v di G terhubung




dengan lintasan pelangi u - v: Jarak antara dua titik u dan v di G dinotasikan dengan d(u; v), adalah panjang dari lintasan terpendek yang menghubungkan kedua titik tersebut. Diameter dari G dino- tasikan oleh diam(G); didefinisikan oleh diam(G) := max d(u; v) untuk setiap u dan v di V (G): Misalkan ukuran dari G dinotasikan dengan l; Chartrand, Johns, McKeon and Zhang memperlihatkan diam(G)< rc(G) < l: Chakraborty, Fischer, Matsilah dan Yuster membuktikan bahwa menghitung bilangan terhubung pelangi dari suatu graf adalah NP-




Hard dan jika diberikan suatu pewarnaan sisi graf G, untuk mengecek apakah pewarnaan yang diberikan membuat G terhubung pelangi adalah NP-complete. Dalam tesis ini kami akan memperlihatkan bilangan terhubung pelangi dari graf lingkaran, pertemanan, kipas, dan roda yang dioperasikan dengan operasi korona, Cartesian product, weak product dan strong product dengan lintasan, serta bilangan terhubung pelangi dari graf belenggu yang




dikonstruksi dari graf-graf tersebut, selain itu kami juga memperlihatkan batas atas bila- ngan terhubung pelangi dari graf belenggu yang dikonstruksi dari sebarang graf terhubung.

Beri Komentar ?#(0) | Bookmark

PropertiNilai Properti
ID PublisherJBPTITBPP
OrganisasiS
Nama KontakUPT Perpustakaan ITB
AlamatJl. Ganesha 10
KotaBandung
DaerahJawa Barat
NegaraIndonesia
Telepon62-22-2509118, 2500089
Fax62-22-2500089
E-mail Administratordigilib@lib.itb.ac.id
E-mail CKOinfo@lib.itb.ac.id

Print ...

Kontributor...

  • Pembimbing Tesis :Prof. Dr. M. Salman A.N., Editor: Alice Diniarti

File PDF...