Hasil Pencarian  ::  Simpan CSV :: Kembali

"Teori penduplikasian genom menyeluruh memotivasi munculnya masalah pem-belahan genom. Masalah pembelahan genom adalah masalah mencari genom awal (nenek moyang) jika diketahui genom terduplikasi yang mengalami penyusunan kembali dengan mengasumsikan jarak reversal minimum. Jarak reversal antara dua genom didefinisikan sebagai banyaknya reversal yang dibutuhkan untuk mengubah satu genom menjadi genom lainnya. Salah satu cara mencari jarak reversal antar dua genom adalah dengan memodelkan genom dalam graf dengan tiga jenis busur (hitam, abu-abu dan putus-putus) yang disebut graf simpul-terpisah. Pada graf simpul-terpisah terdapat lingkaran hitam-abu-abu. Besarnya jarak reversal antara dua genom bergantung pada banyaknya lingkaran hitam-abu-abu pada graf simpul-terpisah yang memodelkan kedua genom tersebut, sehingga masalah pembelahan genom direduksi menjadi weak genome halving problem. Weak genome halving problem adalah masalah mencari banyaknya lingkaran hitam-abu-abu pada graf simpul-terpisah yang memodelkan genom. Perhitungan banyaknya lingkaran hitam-abu-abu dapat dilakukan dengan menggunakan dekomposisi lingkaran dari graf simpul-terpisah. Pada skripsi ini akan dibahas bagaimana mendapatkan banyak maksimal lingkaran hitam-abu-abu dari graf simpul-terpisah."

"Pelabelan dari suatu graf adalah suatu pemetaan bijektif dari gabungan himpunan simpul dan himpunan busur ke himpunan bilangan asli. Pelabelan yang dibahas pada skripsi ini adalah pemetaan bijektif dari gabungan himpunan simpul dan himpunan busur ke himpunan bilangan asli berurutan yang dimulai dari 1. Pada pelabelan didefinisikan jumlah dari label sembarang simpul dan label semua busur yang hadir pada simpul tersebut sebagai bobot simpul. Apabila bobot dari semua simpul membentuk barisan aritmatika dengan suku awal a dan beda d, maka pelabelan tersebut merupakan pelabelan total (a,d)-simpul antiajaib ((a,d)-vertex antimagic total labeling). Apabila d = 0, maka pelabelan disebut pelabelan total simpul ajaib (vertex magic total labeling). Dalam skripsi ini akan dibahas pelabelan total (a,d)-simpul antiajaib dari gabungan graf tak-isomorfik untuk beberapa nilai d, khususnya kelas graf matahari dan petersen diperumum."

"Teori graf adalah sebuah bidang studi interdisipliner yang memiliki berbagai aplikasi dalam pemodelan matematika dan ilmu komputer. Penelitian dalam teori graf tidak hanya bergantung pada teorema baru, namun juga pada konjektura baru. Algoritma penyanggah konjektura dapat digunakan untuk menyanggah suatu konjektura dengan cara mencari sebuah counterexample, seringnya dengan cara memaksimumkan suatu fungsi skor pada graf. Penelitian ini mengusulkan sebuah algoritma penyanggah konjektura baru, disebut sebagai algoritma adaptive Monte Carlo search (AMCS), yang diperoleh dari hasil modifikasi algoritma Monte Carlo tree search. Setelah dievaluasikan berdasarkan keberhasilannya dalam menemukan counterexample untuk beberapa konjektura teori graf, ditemukan bahwa AMCS mengungguli algoritma-algoritma penyanggah konjektura yang sudah ada. Algoritma tersebut kemudian digunakan untuk menyanggah enam konjektura terbuka, dua di antaranya merupakan konjektura teori graf kimia yang diformulasikan oleh Liu et al. pada 2021 dan empat di antaranya diformulasikan menggunakan sistem komputer AutoGraphiX pada 2006. Akhirnya, empat dari enam konjektura terbuka tersebut disanggah secara kuat dengan cara memperumum konjektura yang telah diperoleh menggunakan AMCS untuk menghasilkan keluarga graf yang mengandung banyak counterexample. Algoritma ini diharapkan dapat membantu para peneliti menguji konjektura-konjektura yang berkaitan dengan teori graf secara lebih efektif.

---

Graph theory is an interdisciplinary field of study that has various applications in mathematical modeling and computer science. Research in graph theory depends on the creation of not only theorems but also conjectures. Conjecture-refuting algorithms attempt to refute conjectures by searching for counterexamples to those conjectures, often by maximizing certain score functions on graphs. This study proposes a novel conjecture-refuting algorithm, referred to as the adaptive Monte Carlo search (AMCS) algorithm, obtained by modifying the Monte Carlo tree search algorithm. Evaluated based on its success in finding counterexamples to several graph theory conjectures, AMCS outperforms existing conjecture-refuting algorithms. The algorithm is further utilized to refute six open conjectures, two of which were chemical graph theory conjectures formulated by Liu et al. in 2021 and four of which were formulated by the AutoGraphiX computer system in 2006. Finally, four of the open conjectures are strongly refuted by generalizing the counterexamples obtained by AMCS to produce a family of counterexamples. It is expected that the algorithm can help researchers test graph-theoretic conjectures more effectively"

"Didefinisikan bahwa panjang sebuah basis dari ruang circuit pada sebuah graph adalah merupakan jumlah dan panjang semua circuit dalam basis tersebut. Sebuah algoritma untuk mencari circuit basis dengan kemungkinan panjang terpendek dalam 0 (mn2) operasi, dengan m banyaknya ruas dan n banyaknya simpul dikenal sebagai algoritma berwaktu polinomial. Waktu kompleksitas suatu algoritma menentukan cepat atau lambatnya proses menjalankan suatu algoritma. Algoritma yang dijelaskan dalain tulisan ini yang berhubungan dengan circuit basis minimum adalah algoritma Dijkstra, Quicksort dan Greedy serta dibahas juga tentang analisis waktu kompleksitas masing-masing algoritima tersebut."

"Misalkan terdapat graf G, H dan F. Notasi F -> (G,H) mempunyai arti bahwa setiap pewarnaan merah-biru pada semua sisi graf F mengakibatkan adanya subgraf G berwarna merah atau subgraf H berwarna biru. Pewarnaan-(G,H) pada graf F adalah pewarnaan merah-biru pada semua sisi graf F sehingga tidak ada subgraf G merah maupun subgraf H biru. Graf F adalah graf Ramsey (G,H)-minimal jika F -> (G,H) dan untuk setiap e anggota sisi-sisi pada graf F berlaku (F-e) memiliki pewarnaan-(G,H). Himpunan semua graf Ramsey (G,H)-minimal dinotasikan dengan R(G,H). Himpunan R(G,H) dikatakan berhingga jika banyaknya anggota di R(G,H) berhingga. Bila tidak demikian, dikatakan R(G,H) tak-berhingga.Graf padanan mK2 adalah graf yang terdiri dari m sisi saling lepas. Graf lintasan Pn adalah graf yang terdiri dari satu lintasan dengan n titik. Penelitian pada tesis ini yaitu himpunan Ramsey R(G,H) berhingga. Penelitian berfokus ketika G merupakan graf padanan mK2 dan H merupakan graf lintasan P4 atau P5. Diperoleh semua graf tak-terhubung di R(3K2,P4) dan dua puluh graf terhubung yang bukan graf lingkaran di R(3K2,P4)Selanjutnya, dibahas salah satu operasi yang akan digunakan pada graf Ramsey minimal, yaitu operasi subdivisi. Dibuktikan bahwa jika F ∈ R(2K2,P5) maka setiap graf yang diperoleh dengan subdivisi (5 titik) pada sisi yang bukan pendan di F merupakan graf Ramsey (3K2,P5)-minimal. Kemudian, dilakukan perumuman untuk mengkonstruksi graf Ramsey minimal di R((m+1)K2,Pn) dari graf Ramsey minimal di R(mK2,Pn) untuk m>=4 dan n=4 atau n=5.

---

Let F, G, dan H be simple graphs. The notation F -> (G,H) means that any red-blue coloring of all edges of F will contain either a red copy of G or a blue copy of H. (G,H)-coloring on F means a red-blue coloring of all edges of F such that the red copy of G and the blue copy of H cannot be found. A graph F is Ramsey (G,H)-minimal if F -> (G,H) and for each edge element of all edges of F, (F-e) has (G,H)-coloring. The set of all Ramsey (G,H)-minimal graphs will be denoted by R(G,H). The pair (G,H) is called Ramsey-finite if R(G,H) is finite and Ramsey-infinite otherwise.

The matching graph mK2 is a graph consist of m independent edges. The path graph Pn is a graph consist of one path on n vertices. This thesis is about Ramsey finite. The focus is for G is matching graph and H is a path graph P4 or P5. We obtained all disconnected graphs and twenty connected graphs belonging to Ramsey (3K2,P4)-minimal graph.

Moreover, we discuss an operation on Ramsey minimal graphs, namely subdivision operation. We prove that if F ∈ R(2K2,P5) then a graph obtained by subdividing one non-pendant edge (5 times) is a Ramsey (3K2,P5)-minimal graph. Furthermore, we do generalization for constructing Ramsey minimal graphs in R((m+1)K2,Pn) from R(mK2,Pn) for m>=4 and n=4 or 5"

"ABSTRAKInfluenza adalah penyakit yang disebabkan oleh virus bernama virus influenza tipe A sub tipe H1N1, H2N2, and H3N2. Penyakit Influenza menyerang bagian pernapasan manusia dan menyebar melalui media udara. Terdapat berbagai intervensi untuk mencegah agar tidak terserang penyakit Influenza, namun intervensi yang paling efektif yaitu dengan mendapatkan vaksinasi Influenza. Model penyebaran penyakit Influenza dengan populasi semi tertutup dan melibatkan intervensi vaksinasi akan dibahas dalam skripsi ini. Model penyebaran penyakit dalam skripsi ini melibatkan mobilitas individu dari suatu kota ke kota lain yang digambarkan sebagai graf berarah. Graf yang digunakan untuk mendeskripsikan mobilitas individu dari suatu kota ke kota lain yaitu graf bintang dan graf roda. Formula dari basic reproduction number R0 ditunjukkan menggunakan pendekatan teori graf. Dari kajian analitik dihasilkan formula dari R0 untuk masing-masing bentuk model dengan interaksi manusia yang direpresentasikan sebagai graf bintang dan graf roda adalah polinomial lambda berderajat ndanR0 dapat dicari sebagai akar karakteristik terbesar dari polinomial tersebut.

---

ABSTRACTInfluenza is a disease caused by virus Influenza type A sub type H1N1, H2N2, and H3N2. This disease attacks the respiratory part and spreads through the air. There are many interventions to prevent Influenza, but the most effective intervention is to get Influenza vaccination. The epidemiological model of Influenza with semi closed populations and involves vaccination intervention will be discussed in this thesis. This model involves the mobility of individuals from one city to another that is described as a directed graph. The graphs used to describe the individual mobility from one city to another are star and wheel graph. The formula of basic reproduction number R0 is shown using the graph theory approach. From analytical analysis we find the formula of R0 for the epidemiological models with human mobility represented as star and wheel graph are polynomial of degree n for lambdaandR0 can be found as the largest positive root of this polynomial."

"Suatu graf sederhana dapat direpresentasikan dalam bentuk matriks Laplacian. Nilai eigen kedua terkecil dari matriks Laplacian, didefinisikan sebagai konektivitas aljabar, memiliki peranan dalam menunjukkan keterhubungan dari graf. Dalam tugas akhir ini, pertama-tama dicari batas atas dari jumlah kuadrat derajat pada suatu graf sederhana. Dari hasil yang diperoleh, kemudian ditentukan batas atas dan bawah dari konektivitas aljabar pada graf. Lebih lanjut dibahas pula batas bawah dari konektivitas aljabar pada graf berbobot.

---

A simple graph can be represented by a Laplacian matrix. The second smallest eigenvalue of Laplacian matrix, defined as algebraic connectivity, is used to show the connectivity of graphs. In this skripsi, first we find some upper bounds on the sum of the squares of the degrees in a simple graph. Using these results, we obtain some upper and lower bounds on the algebraic connectivity of graph. In addition, a lower bound on the algebraic connectivity of a weighted graph is also presented."