📚 Eksplorasi & Komparasi Topik Dokumen
Pencarian topik
Hasil Dokumen
Ditemukan: 3 dokumenALGORITMA PENCARIAN PELABELAN GRACEFUL,GRACEFUL ANTIMAGIC, DAN GRACEFUL DISTANCE–ANTIMAGIC
Penelitian ini mengkaji keberadaan graceful labeling (GL), graceful antimagic labeling (GAL), dan graceful distance–antimagic labeling (GDAL) pada graf sederhana tak berarah berorde kecil hingga orde n ? 9 menggunakan pendekatan komputasional berbasis backtracking teroptimasi. Hasil komputasi menunjukkan bahwa GL memiliki persentase eksistensi tertinggi, diikuti GAL, lalu GDAL. Selain itu, diperoleh bahwa GL tidak menjamin keberadaan GAL maupun GDAL, serta GAL dan GDAL tidak saling mengimplikasikan. Pada graf pohon, hasil komputasi menunjukkan bahwa meskipun setiap graf pohon diduga memiliki GL dan setiap graf terhubung selain K2 diduga memiliki pelabelan antimagic, keberadaan kedua sifat tersebut tidak secara langsung menjamin keberadaan GAL. Secara khusus, ditemukan beberapa graf pohon berorde kecil yang tidak memenuhi GAL, sehingga penentuan syarat perlu dan syarat cukup bagi graf pohon untuk memiliki GAL masih menjadi masalah terbuka. Selain itu, hasil komputasi menunjukkan bahwa graf pohon dengan orde 4 ? n ? 9 yang tidak memiliki dua simpul dengan himpunan tetangga yang sama memiliki GDAL. Oleh karena itu, terdapat dugaan bahwa setiap graf pohon yang tidak memiliki dua simpul dengan himpunan tetangga yang sama memiliki solusi GDAL. Algoritma teroptimasi yang dikembangkan juga terbukti lebih efisien dibandingkan pendekatan brute-force tanpa mengubah hasil pencarian pelabelan.
PELABELAN AJAIB DAN ANTIAJAIB PADA GRAF DENGAN DEKOMPOSISI SUBGRAF TERURUT NAIK
Misalkan n, q, t ? N dan G = (V (G),E(G)) adalah graf sederhana dan berhingga yang memiliki orde |V (G)| = n dan ukuran |E(G)| = q. Misalkan f : V (G) ? E(G) ? {1, 2, . . . , n + q} adalah suatu pelabelan total pada G yang bersifat bijektif. Pelabelan f disebut pelabelan total sisi ajaib jika terdapat suatu konstanta k sehingga bobot setiap sisi e = uv di G, yaitu w(uv) = f(u)+f(v)+f(uv) = k. Dalam hal ini, k disebut konstanta ajaib. Sebaliknya, jika seluruh bobot sisi berbeda, maka f disebut sebagai pelabelan total sisi antiajaib. Pelabelan total sisi ajaib dapat diperluas dengan memandang subgraf dari G dalam perhitungan bobot. Misalkan {H1,H2, . . . ,Ht} adalah koleksi yang berisi t subgraf dari G, dan Hi isomorfik dengan suatu graf H, 1 ? i ? t. Graf G disebut memuat dekomposisi-H apabila setiap sisi di G termuat pada tepat satu subgraf di antara H1,H2, ...,Ht. Pelabelan f disebut pelabelan total H-ajaib dari G jika setiap 1 ? i ? t, bobot subgraf w(Hi) = P v?V (Hi) f(v) + P e?E(Hi) f(e) bernilai konstan. Sebaliknya, jika seluruh bobot subgraf berbeda, maka f disebut sebagai pelabelan total H-antiajaib. Selain dekomposisi suatu graf menjadi subgraf-subgraf yang saling isomorfik, di dalam literatur juga dikenal dekomposisi menjadi subgraf-subgraf yang tidak isomorfik. Misalkan q dan t memenuhi ????t+1 2 ? q < ????t+2 2 . Graf G disebut memuat dekomposisi subgraf terurut naik (ascending subgraf decomposition) atau ASD jika G dapat didekomposisi menjadi t subgraf H1,H2, . . . ,Ht tanpa titik terisolasi, dengan {E(H1), . . . ,E(Ht)} mempartisi E(G) sedemikian hingga Hi isomorfik ke suatu subgraf sejati dari Hi+1 untuk 1 ? i ? t ? 1. Graf yang memuat dekomposisi subgraf terurut naik disebut graf ASD dan barisan subgraf {H1,H2, . . . ,Ht} disebut barisan subgraf terurut naik. Termotivasi oleh pelabelan total H-(anti)ajaib, dalam disertasi ini diperkenalkan dan dikaji eksistensi pelabelan ajaib dan antiajaib pada suatu graf ASD. Misalkan G adalah graf ASD dengan himpunan subgraf {H1,H2, . . . ,Ht}, dan f adalah pelabelan total pada G. Apabila untuk setiap 1 ? i ? t diperoleh w(Hi) = k, maka f disebut pelabelan ASD-ajaib dari G dan G disebut sebagai graf ASD-ajaib. Dalam penelitian ini dikaji sifat umum yang dimiliki oleh graf ASD-ajaib, yaitu rata-rata bobot dari seluruh subgraf terbatas di atas oleh bobot terbesar yang dapat dicapai oleh subgraf terkecil. Fakta ini kemudian digunakan untuk melakukan karakterisasi graf bintang, graf lintasan, dan graf siklus yang memuat pelabelan ASD-ajaib. Di sisi lain, jika dengan pelabelan f diperoleh bahwa w(Hi) ?= w(Hj) untuk setiap i ?= j, maka f disebut pelabelan ASD-antiajaib dari G. Apabila seluruh bobot tersebut membentuk suatu barisan aritmetika dengan bobot terkecil a dan beda d, maka f disebut pelabelan (a, d)-ASD antiajaib. Lebih khusus, f adalah pelabelan ASD-antiajaib super atau (a, d)-ASD-antiajaib super jika f(V (G)) = {1, 2, . . . , n}. Penelitian mengenai pelabelan ASD-antiajaib (super) dalam disertasi ini dimulai dengan konstruksi pelabelan ASD-antiajaib (super) berdasarkan pelabelan total sisi (anti)ajaib (super). Pada konstruksi ini, didefinisikan suatu graf konektor yang digunakan sebagai alat untuk mengonstruksi keluarga graf ASD. Kemudian, diperoleh syarat cukup bagi graf konektor sehingga graf ASD yang telah dibangun memuat pelabelan ASD-antiajaib. Selain itu, didefinisikan pula dekomposisi bobot terurut naik (AWD) pada graf. AWD bersama pelabelan total sisi antiajaib digunakan sebagai alat untuk membuktikan bahwa graf bintang, graf lintasan, dan graf siklus memuat pelabelan ASD-antiajaib. Selain itu, dalam penelitian ini dilakukan pula konstruksi pelabelan ASD-antiajaib (super) berdasarkan pelabelan totalH-ajaib dari graf dengan barisan subgraf terurut naik yang memuat graf padanan atau graf siklus dengan orde tiga. Dengan berbagai hasil yang diperoleh, kami menduga bahwa semua graf dengan banyak sisi positif memiliki pelabelan ASD-antiajaib. Disertasi ini ditutup dengan konstruksi pelabelan (a, d)-ASD-antiajaib yang diperoleh dengan memanfaatkan multihimpunan (t, ?)-antiseimbang terurut naik. Misalkan ? ? N dan X adalah multihimpunan. X disebut multihimpunan (t, ?)-antiseimbang terurut naik jika X dapat dipartisi menjadi submultihimpunan X1,X2, . . . ,Xt dengan ketentuan bahwa untuk 1 ? i < j ? t ? 1 berlaku |Xi| < |Xj | dan P x?Xi+1 x ? P x?Xi x = ?. Kelas-kelas graf yang dikaji adalah graf bintang, lintasan, siklus, dan graf lengkap. Selain itu, dikaji pula pelabelan (a, d)-ASD-antiajaib pada graf hasil operasi, yaitu graf hasil gabungan saling lepas, graf hasil amalgamasi-titik, amalgamasi-sisi, amalgamasi-subgraf, graf rantai, graf rantai yang diperluas, dan graf hasil korona yang diperluas.
PELABELAN TAK TERATUR MODULAR PADA GRAF DOUBLE BROOM
Misalkan G = (V, E) adalah graf berorde n dengan himpunan titik V yang tak kosong dan himpunan sisi E. Misalkan t adalah bilangan bulat positif. Pelabelan tak teratur modular pada graf G adalah pelabelan-t sisi ? : E ? {[1, t]} sedemikian sehingga terdapat fungsi bobot wt? : V ? Zn yang bijektif, dimana Zn adalah grup bilangan bulat modulo n. Fungsi bobot modular dari titik u didefinisikan sebagai wt?(u) = P v?N(u) ?(uv). Selanjutnya, ms(G) menotasikan kekuatan tak teratur modular dari graf G, yaitu nilai minimum t sedemikian sehingga graf G memiliki pelabelan tak teratur modular dengan label terbesar t. Misalkan k, l adalah bilangan bulat positif. Graf double broom yang dinotasikan dengan DBk,l adalah graf berorde k + 2l yang diperoleh dari mengidentifikasi setiap titik ujung z1 dan zk dari graf lintasan berorde k dengan titik tengah setiap graf bintang berorde l + 1. Dalam penelitian ini, kami mengonstruksi pelabelan tak teratur modular dari graf double broom dan menentukan nilai eksak dari kekuatan tak teratur modular untuk nilai k + 2l yang cukup besar.