š Eksplorasi & Komparasi Topik Dokumen
Pencarian topik
Hasil Dokumen
Ditemukan: 14 dokumenHIMPUNAN-[1, 2] PADA GRAF HASIL OPERASI SISIR TITIK
Misalkan G adalah graf sederhana sembarang yang terhubung dan tak berarah. Himpunan S ? V disebut sebagai himpunan-[1, 2] dari G jika setiap titik v ? V \ S bertetangga dengan setidaknya satu dan paling banyak dua titik dalam S. Kardinalitas minimum dari suatu himpunan-[1, 2] disebut sebagai bilangan dominasi-[1, 2] dari G, dinotasikan dengan ?[1,2](G). Misalkan terdapat dua graf sederhana terhubung G dan H. Graf kali sisir titik antara G dan H (dinotasikan dengan G ?o H) merupakan graf hasil operasi yang dibentuk dengan mengambil satu salinan G dan sebanyak |V (G)| salinan H, kemudian menempelkan titik o di salinan ke?i dari graf H dengan titik ke-i dari graf G, untuk setiap i = 1, 2, . . . , |V (G)|. Pada tugas akhir ini, akan dibahas mengenai bilangan dominasi-[1, 2] pada graf G ?o H untuk sebarang graf sederhana terhubung G dan H.
DOMINASI LOKASI PADA HASIL KALI KARTESIUS GRAF DENGAN GRAF LENGKAP
Misalkan G graf sederhana. Himpunan D ? V (G) disebut himpunan dominasi lokasi dari graf G jika untuk setiap dua titik berbeda u, v ? V (G) \ D berlaku ? ?= N(u) ? D ?= N(v) ? D ?= ?. Kardinalitas minimum dari semua himpunan dominasi lokasi di G disebut bilangan dominasi lokasi dari G dan dinotasikan dengan ?L(G). Hasil kali Kartesius dari G1 dan G2, dinotasikan dengan G1?G2, didefinisikan sebagai graf dengan himpunan titik V = V1 Ć V2 = {(u, v) | u ? V1, v ? V2} dan himpunan sisi E = ((u1, v1), (u2, v2)) ???? u1 = u2 dan (v1, v2) ? E2 atau ???? v1 = v2 dan (u1, u2) ? E1 . Pada tesis ini, ditentukan batas atas dan batas bawah bilangan dominasi lokasi dari G?Kn untuk G adalah sebarang graf dan Kn adalah graf lengkap dengan n ? 3. Selain itu, ditentukan juga bilangan dominasi lokasi dari G?Kn dengan G merupakan graf bintang, graf lengkap, dan graf bipartit lengkap dengan orde masing-masing partisi adalah 2.
GARIS EQUIANGULAR : BATAS ATAS KARDINALITAS TERBESAR GARIS EQUIANGULAR DAN KONSTRUKSI GARIS EQUIANGULAR DENGAN GRAF TERATUR KUAT
Garis equiangular didefinisikan sebagai himpunan garis di dimensi d yang melalui titik awal, yang sudut dari sembarang dua garis dalam himpunan tersebut bernilai konstan. Masalah utama dalam topik ini adalah menentukan kardinalitas terbesar himpunan garis equiangular yang ada di dimensi d, yang dinotasikan sebagai N(d). Hingga saat ini, nilai N(d) belum sepenuhnya diketahui, terutama untuk nilai d sangat besar. Untuk nilai d yang cukup kecil, yakni d ? 23, beberapa penelitian telah dilakukan untuk mendapatkan batas atas N(d), utamanya dengan memanfaatkan konsep matriks Gram dan Seidel beserta sifat-sifat yang dimilikinya. Selain itu, konsep garis equiangular juga memiliki keterkaitan yang erat dengan konsep graf, terutama graf teratur kuat (strongly regular graph). Hubungan sudut antar garis dalam himpunan garis equiangular dapat dinyatakan dalam bentuk matriks Gram dan Seidel, sedangkan hubungan ketetanggaan antar simpul dalam suatu graf dapat dinyatakan dalam bentuk matriks ketetanggaan. Adapun dalam aljabar, matriks ketetanggaan dan matriks Seidel dapat saling bersesuaian di bawah operasi tertentu. Hal ini memungkinkan dilakukannya konstruksi garis equiangular dari suatu graf teratur kuat, dan sebaliknya. Tugas akhir kali ini dilakukan untuk meninjau bagaimana cara merumuskan batas atas nilai N(d) dan bagaimana cara mengonstruksi himpunan garis equiangular dengan kardinalitas terbesar yang ada di dimensi d, untuk beberapa nilai d tertentu, berdasarkan literatur-literatur lain yang sudah ada. Perumusan batas atas menggunakan konsep matriks Gram dan matriks Seidel, sedangkan konstruksi garis equiangular menggunakan konsep graf teratur kuat maupun graf secara umum.
ALGORITMA EMBEDDINGPADA PELABELAN GRAF GRACEFUL ANTIMAGIC
Pelabelan graceful dan antimagic merupakan dua jenis pelabelan graf yang banyak dikaji dalam teori graf. Sebuah graf G dengan q sisi dikatakan graceful apabila terdapat fungsi injektif f : V (G) ? {0, 1, . . . , q} sedemikian sehingga himpunan label sisi { |f(u) ? f(v)| : uv ? E(G) } tepat sama dengan {1, 2, . . . , q}. Suatu pelabelan sisi dikatakan antimagic apabila bobot setiap simpul, yaitu jumlah label sisi yang berinsiden dengan simpul tersebut, bernilai berbeda untuk setiap simpul. Penelitian ini memperkenalkan konsep graceful antimagic embedding, yaitu mengonstruksi supergraf H ? G dari sebuah graf terhubung G sehingga H memenuhi syarat pelabelan graceful dan antimagic secara bersamaan. Untuk mengonstruksi H, dirancang algoritma berbasis stochastic heuristic yang bekerja melalui dua strategi, yaitu internal filling (menambahkan sisi antar simpul yang telah ada) dan external filling (menyematkan simpul baru), dengan evaluasi antimagic secara look-ahead pada setiap langkah. Eksperimen dilakukan terhadap seluruh kelas isomorfisme graf terhubung dengan banyak sisi q = 3 hingga q = 12, dengan total 40.962 tipe graf. Algoritma yang diusulkan berhasil menyelesaikan seluruh kasus uji dengan tingkat keberhasilan 100%, dengan waktu komputasi meningkat seiring bertambahnya q, dari 0,002 detik pada q = 3 hingga 131,587 detik pada q = 12. Berdasarkan hasil tersebut, diajukan konjektur bahwa setiap graf terhubung G dapat di-embed ke dalam suatu supergraf H ? G yang memenuhi pelabelan graceful dan antimagic secara bersamaan.
KAITAN ANTARA BILANGAN ISTIMEWA DAN DIMENSI PARTISI GRAF
Suatu pelabelan titik pada graf dikatakan istimewa jika satu-satunya automorfisma yang mengawetkan pelabelan tersebut hanyalah identitas. Bilangan istimewa (distinguishing number) dari graf G adalah nilai terkecil m sedemikian hingga G memiliki pelabelan?m istimewa, dilambangkan dengan D(G). Untuk suatu partisi?k berurutan ? = {S1, S2, ..., Sk} dari V (G), representasi r(v|?) dari titik v terhadap ? adalah (d(v, S1), ..., d(v, Sk)), di mana d(v, S) = min{d(v, x)|x ? S}. Partisi ? tersebut merupakan partisi pembeda dari G bila semua vektor r(v|?) berbeda untuk semua v ? G. Nilai terkecil k di mana terdapat partisi pembeda dengan k kelas partisi dari graf G dinamakan dimensi partisi G, dilambangkan dengan pd(G). Partisi V (G) menjadi k kelas partisi dapat dipandang sebagai pelabelan setiap titik di V (G) ke {1, 2, ..., k}. Pelabelan istimewa yang ditemukan pada tahun 1996 dan partisi pembeda yang ditemukan pada tahun 2000 merupakan dua aturan pelabelan titik yang menarik minat para peneliti di bidang teori graf selama lebih dari 2 dekade. Berdasarkan definisinya, pelabelan istimewa didasarkan atas automorfisma titik, yang mana sifat automorfisma adalah mempertahankan ketetanggaan dari setiap titik yang dipetakan. Diperhatikan bahwa ketetanggaan titik berkaitan erat dengan jarak antar titik pada graf yang merupakan parameter dasar dalam menentukan partisi pembeda suatu graf. Oleh karena itu, cukup masuk akal bila kita menduga terdapat kaitan erat antara dua aturan pelabelan titik tersebut, sesuatu yang belum pernah diteliti hingga saat ini. Baik bilangan istimewa maupun dimensi partisi untuk beberapa kelas graf telah ditemukan. Di antaranya, graf siklus, graf lintasan, graf lengkap, graf Petersen, graf hypercube, graf bintang, graf bipartit lengkap, graf roda (batas atas dan bawah) , graf pohon ulat, pohon firecrackers, subdivisi pohon, dan beberapa struktur pohon lainnya. Namun demikian, hingga saat ini belum ada penelitian yang mengkaji kaitan antara kedua parameter tersebut. Bila kaitan tersebut diketahui, maka pengetahuan mengenai dimensi partisi suatu kelas graf dapat digunakan untuk mencari nilai bilangan istimewa dari kelas graf tersebut, dan sebaliknya. Penelitian disertasi ini akan memberi fokus perhatian pada kaitan dari kedua parameter graf tersebut. Secara lebih spesifik, penelitian disertasi ini berfokus pada kaitan umum dan kaitan khusus antara bilangan istimewa dan dimensi partisi graf sederhana terhubung. Kami berhasil menunjukkan bahwa untuk setiap graf G dimensi partisi merupakan batas atas bagi bilangan istimewa, yaitu D(G) ? pd(G). Kami juga menemukan beberapa kelas graf yang memenuhi D(G) = pd(G), di antaranya Pn, K1,n, Kn, Kn,n, graf bintang ganda Sm,n, dan Cn. Dengan menggunakan pengetahuan mengenai karakterisasi graf berorde n dan dimensi partisi n ? 1 atau n ? 2, kami berhasil mendapatkan beberapa kelas graf yang memenuhi pd(G) ? D(G) = 1 dan pd(G) ? D(G) = 2. Selisih antara dimensi partisi dan bilangan istimewa ini bisa menjadi sangat jauh, yang dapat dilihat contohnya pada graf theta umum dan juga graf roda. Sifat dimensi partisi terkait banyaknya titik kembar ternyata juga dimiliki oleh bilangan istimewa. Selain relasi umum antara dua pelabelan itu, dalam disertasi ini kami juga membahas pelabelan istimewa untuk kelas graf terhubung yang tidak memuat cycle, yaitu graf pohon. Bilangan istimewa maupun dimensi partisi untuk sebarang pohon hingga saat ini belum diketahui. Dalam penelitian ini kami mengkaji pohon berjari-jari 1 dan 2 dengan memperkenalkan notasi tuple. Dengan menggunakan notasi tersebut, dapat ditentukan bilangan istimewa setiap pohon dengan radius tidak melebihi 2. Kami menunjukkan bahwa untuk setiap bilangan bulat positif d, dapat dilakukan karakterisasi semua graf pohon T dengan rad(T) ? 2 dan bilangan istimewa d.
BILANGAN TERHUBUNG SISI PELANGI LOKASI GRAF UNISIKLIK
Misalkan G suatu graf tidak trivial, sederhana, berhingga, dan terhubung. Suatu pewarnaan sisi pelangi-k dari G adalah pewarnaan c : E(G) ? {1, 2, . . . , k} sedemikian sehingga untuk setiap pasangan titik u, v ? V (G) terdapat lintasan uāv yang semua sisinya memiliki warna berbeda. Jarak antara dua sisi e1 = u1v1 dan e2 = u2v2 didefinisikan sebagai d(e1, e2) = ( min{d(u1, u2), d(u1, v2), d(v1, u2), d(v1, v2)} + 1, jika e1 ?= e2, 0, jika e1 = e2. Untuk setiap i ? {1, 2, . . . , k}, misalkan Ri menyatakan himpunan sisi berwarna i dan ? = {R1,R2, . . . ,Rk} merupakan partisi terurut dari E(G). Kode pelangi dari suatu sisi e terhadap ? didefinisikan sebagai rc?(e) = (d(e,R1), d(e,R2), . . . , d(e,Rk)) dengan d(e,Ri) = min{d(e, f) : f ? Ri}. Jika setiap sisi pada G memiliki kode pelangi yang unik, maka pewarnaan c disebut pewarnaan sisi pelangi lokasik, dan nilai k minimum yang memenuhi sifat tersebut disebut bilangan terhubung sisi pelangi lokasi dari G, dilambangkan dengan recl(G). Pada penelitian ini, ditentukan batas atas dan batas bawah yang ketat untuk bilangan terhubung sisi pelangi lokasi graf unisiklik, yaitu graf yang memuat tepat satu subgraf siklus, dan mengkarakterisasi kelas-kelas graf unisiklik yang bilangan terhubung sisi pelangi lokasinya tertentu. Selain itu, ditentukan bilangan terhubung sisi pelangi lokasi dari beberapa kelas graf unisiklik tertentu.
DEKOMPOSISI REGULAR KUAT DARI GRAF LENGKAP
Untuk sembarang bilangan prima ganjil p, graf lengkap dengan p2(p+2) titik, dapat didekomposisi menjadi sebanyak p + 1 graf regular kuat. Sebanyak p graf regular kuat memiliki parameter (p2(p+2), p2+p, p, p) dan sebanyak satu graf regular kuat memiliki parameter (p2(p+2), p2?1, p2?2, 0). Kemudian, akan diberikan metode untuk mengontruksi matriks ketetanggaan dari setiap kelas graf.
BILANGAN TERHUBUNG SISI PELANGI LOKASI HASIL OPERASI SISIR DUA GRAF
MisalkanGdanH merupakan dua graf tak trivial, sederhana, hingga, dan terhubung. Untuk suatu k ? N, didefinisikan suatu pewarnaan c : E(G) ? [1, k] merupakan pewarnaan-k pelangi jika untuk setiap titik u ? V(G) dan v ? V(G) terdapat lintasan u?v sedemikian sehingga sisi-sisi dalamnya memiliki warna yang berbeda. Misalkan a = uv dan b = xy merupakan anggota sisi di G. Jarak antara dua sisi a dan b, dinotasikan dengan d(a, b) yang didefinisikan sebagai d(a, b) = ??????? min{d(u, x), d(u, y), d(v, x), d(v, y)} + 1, jika a , b; 0, jika a = b. Untuk setiap i ? {1, 2, . . . , k}, misalkan Ri adalah himpunan sisi dengan warna i dan ? = {R1,R2, . . . ,Rk} merupakan partisi terurut dari E(G). Kode pelangi dari sisi e ? E(G) terkait ? dinotasikan dengan rc?(e) = (d(e,R1), d(e,R2), . . . , d(e,Rk)) dengan d(e,Ri) = min{d(e, y) : y ? Ri} untuk setiap i ? {1, 2, . . . , k}. Jika setiap sisi di G memiliki kode pelangi berbeda, maka pewarnaan c disebut pewarnaan-k sisi pelangi lokasi pada G. Bilangan bulat positif terkecil k sehingga G memiliki pewarnaan-k sisi pelangi lokasi adalah bilangan terhubung sisi pelangi lokasi dari G, dinotasikan dengan recl(G). Untuk suatu u ? V(H), operasi sisir G dengan H, dinotasikan dengan G ?u H, adalah graf yang diperoleh dengan mengambil satu duplikasi G dan |V(G)| duplikat dari H dan mengidentifikasi duplikat ke-i dari H pada titik u terhadap titik ke-i dari G. Pada penelitian ini, diberikan batas bawah dan batas atas yang ketat untuk bilangan terhubung sisi pelangi lokasi hasil operasi sisir dua graf. Selanjutnya ditentukan bilangan terhubung sisi pelangi lokasi hasil operasi sisir dua graf untuk beberapa kelas graf G dan H, yaitu operasi sisir graf pohon dengan graf pohon, graf payung dengan graf pohon, graf siklus dengan graf pohon, graf pohon dengan graf siklus dan graf siklus dengan graf siklus.
PEWARNAAN PELANGI-3 KAKU BEBERAPA KELAS GRAF
Misalkan ???? adalah suatu graf sederhana, terhubung, dan berhingga berorde ?????3 dan ???? memiliki suatu pewarnaan sisi. Suatu lintasan ???? di ???? disebut lintasan pelangi jika setiap sisi di ???? memiliki warna yang berbeda. Untuk ?????????(????), lintasan Steiner dari ???? adalah lintasan terpendek yang mengandung titik-titik di himpunan ????. Pewarnaan pelangi-3 kaku adalah suatu pewarnaan sisi graf ???? dengan properti untuk setiap himpunan ?????????(????) dengan |????|=3, terdapat suatu lintasan Steiner pelangi dari ????. Graf ???? dikatakan terhubung pelangi-3 kaku jika pada ???? dapat didefinisikan suatu pewarnaan pelangi-3 kaku. Minimum banyaknya warna yang dibutuhkan untuk membuat ???? memiliki pewarnaan pelangi-3 kaku disebut sebagai indeks pewarnaan pelangi-3 kaku dari ???? dan dinotasikan degan sebagai ????????????????3(????). Jelas bahwa tidak semua graf dapat memiliki pewarnaan pelangi-3 kaku. Oleh karena itu, pada Tugas Akhir ini ditentukan karakteristik dari graf yang terhubung pelangi-3 kaku dan dikaji batas atas dan batas bawah dari indeks pewarnaan pelangi-3 kaku dari graf, serta ditentukan ????????????????3(????) untuk beberapa kelas graf sederhana ????. Selain itu, juga dikaji ????????????????3 graf hasil operasi sisir sisi lintasan ???????? dengan suatu graf terhubung ????, dinotasikan dengan ?????????????????? ????. Diberikan pula syarat-syarat dari graf ???? agar graf ?????????????????? ???? terhubung pelangi-3 kaku. Kemudian dikaji batas atas dan batas bawah untuk ????????????????3(?????????????????? ????). Pada Tugas Akhir ini juga diberikan nilai ????????????????3(?????????????????? ????) untuk graf ???? berupa graf kipas ???????? berorde ????+1 dan graf siklik ???????? berorde ????.
BILANGAN TERHUBUNG SISI PELANGI LOKASI PADA BEBERAPA KELAS GRAF
Misalkan k adalah suatu bilangan bulat positif dan G = (V,E) adalah graf berhingga dan terhubung. Pewarnaan-k pelangi pada G adalah suatu pemetaan c : E(G) ? {1, 2, ..., k} sehingga untuk setiap dua titik berbeda u dan v di G terdapat lintasan pelangi yang menghubungkan keduanya. Misalkan e = uv dan f = xy adalah elemen sisi di G. Jarak antara dua sisi e dan f, dinotasikan dengan d(e, f), didefinisikan sebagai d(e, f) = ( min{d(u, x), d(u, y), d(v, x), d(v, y)} + 1, jika e ?= f; 0, jika e = f. Untuk i ? {1, 2, ..., k}, misalkan Ri adalah himpunan sisi dengan warna i dan ? = {R1,R2, ...,Rk} merupakan partisi terurut dari E(G). Kode pelangi dari sisi e ? E(G) terkait ? dinotasikan dengan rc?(e) = (d(e,R1), d(e,R2), ..., d(e,Rk)) dengan d(e,Ri) = min{d(e, y)|y ? Ri} untuk setiap i ? {1, 2, ..., k}. Jika setiap sisi di G memiliki kode pelangi yang berbeda, maka pewarnaan c disebut pewarnaan-k sisi pelangi lokasi pada G. Bilangan bulat positif terkecil k sehingga terdapat suatu pewarnaan-k sisi pelangi lokasi pada G disebut bilangan terhubung sisi pelangi lokasi graf G, dinotasikan dengan recl(G). Pada tesis ini, ditentukan batas bawah dan batas atas bilangan terhubung sisi pelangi lokasi pada suatu graf. Selanjutnya ditentukan juga bilangan terhubung sisi pelangi lokasi pada beberapa kelas graf, seperti graf pohon, graf siklus, graf tadpole, graf dumbel, graf ular segitiga, dan graf tangga miring.
HIMPUNAN INDEPENDEN-[1,2] PADA BEBERAPA GRAF COMB SISI
Misalkan ???? graf sederhana dengan himpunan titik dan sisi masing-masing ????(????) dan ????(????). Misalkan ?????????(????). Himpunan W dikatakan sebagai himpunan independen-[1,2] dari ???? jika setiap dua titik berbeda dalam ???? tidak saling bertetangga, dan setiap titik ?????????(????)????? bertetangga dengan tepat satu atau dua titik di ????. Kardinalitas minimum dari semua himpunan-[1,2] dari ???? disebut bilangan independen-[1,2] dari ????. Untuk dua graf terhubung ???? dan ????, graf comb sisi antara ???? dan ???? di suatu sisi ?????????(????), dinotasikan dengan ????????????? adalah graf yang diperoleh dari |????(????| kopian ???? dan satu kopian ????, kemudian mengidentifikasi di sisi ???? untuk kopian ke-i dari ???? pada sisi ke-???? dari ????. Dalam tugas akhir ini, beberapa graf sederhana yang memiliki himpunan independen-[1,2], ditunjukkan. Kemudian untuk ????,???????? graf lengkap, dan ????????,???? graf bipartit lengkap sedemikian rupa sehingga ????????????????? dan ?????????????????,???? memiliki himpunan independen-[1,2],juga ditunjukkan. Selanjutnya nilai eksak dari bilangan independen-[1,2] untuk ????,????????, dan ????????,???? sedemikian rupa sehingga ????????????????? dan ?????????????????,???? memiliki himpunan independen-[1,2] juga ditentukan.
DIMENSI MULTISET LUAR DARI GRAF DENGAN DIMENSI MULTISET TAK HINGGA
Dimensi multiset dari suatu graf G atau md(G) adalah kardinalitas terkecil dari W ? V(G) yang dapat mengidentifikasi semua titik di V(G) secara unik dengan menggunakan multiset jarak terhadap titik-titik di W. Graf G dikatakan memiliki md(G) = ? jika tidak ada subhimpunan titik W ? G yang membedakan semua titik di G dengan multiset jarak terhadapW. Dimensi multiset luar graf G atau dimms(G) adalah modifikasi dari dimensi multiset dengan hanya meninjau titik di luar subhimpunan W. Pada tugas akhir ini, akan dikaji nilai dimensi multiset luar dari graf-graf yang berdimensi multiset tak hingga, seperti graf lengkap dikurangi beberapa sisi, graf roda, dan graf hasil perkalian korona dengan graf tanpa sisi.
HUBUNGAN ANTARA DIMENSI METRIK DAN SPEKTRUM GRAF
Pendekatan aljabar untuk masalah-masalah teori graf telah dipelajari secara luas dengan melihat spektrum dari graf. Di tesis ini, kami menyelidiki beberapa hubungan antara dimensi metrik suatu graf dengan nulitasnya, yaitu multiplisitas nilai eigen 0 dari matriks ketetanggaannya, dan nilai eigen matriks Laplace dan matriks jaraknya. Lebih lanjut, kami juga membahas hubungan antara dimensi metrik suatu graf dan nulitasnya menggunakan kelas kembar.
PELABELAN GRACEFUL GRAF PEMBAGI NOL $\GAMMA(\MATHBB{Z}_{N})$ UNTUK BERBAGAI NILAI $N$
Konsep graf pembagi nol lebih banyak ditinjau dari aspek aljabar. Hal ini membuat penulis ingin meninjau graf pembagi nol dari aspek teori graf. Beberapa paper sudah memberikan pelabelan graceful untuk beberapa jenis graf pembagi nol. Rumusan masalah yang muncul adalah mencari teknik pelabelan graceful untuk graf pembagi nol ?(Zn) untuk nilai n tertentu. Tujuan dari penelitian ini adalah mengidentifikasi teknik pelabelan graceful untuk graf pembagi nol ?(Zn) untuk nilai n tertentu, khususnya ketika n = pk dan n = pkq untuk p, q bilangan prima dan k ? N. Metode yang digunakan pada penelitian ini antara lain adaptasi dari hasil yang sudah diperoleh, modifikasi, dan penggunaan metode lainnya. Setelah dilakukan analisis, diperoleh jenis graf pembagi nol ?(Zn) dengan nilai n tertentu yang dapat dilabeli secara graceful.