Hasil Pencarian  ::  Simpan CSV :: Kembali

"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"

"Lintasan pelangi adalah lintasan pada suatu graf yang setiap busurnya diwarnai dengan warna berbeda. Bilangan keterhubungan pelangi pada graf $G$ atau dapat disimbolkan $rc(G)$ adalah warna minimal yang dibutuhkan untuk mewarnai busur-busur pada suatu lintasan pada graf $G$ sehingga setiap pasang simpul dihubungkan oleh suatu lintasan pelangi. Lintasan pelangi geodesic $u-v$ di $G$ adalah lintasan pelangi yang panjangnya sama dengan $d(u,v)$ dengan $d(u,v)$ adalah jarak antara $u$ dan $v$. Graf $G$ dikatakan memiliki keterhubungan pelangi kuat $src(G)$ jika \textit{geodesic} $u-v$ untuk sembarang dua simpul $u$ dan $v$ di $G$ adalah lintasan pelangi. Bilangan keterhubungan pelangi kuat $src(G)$ merupakan banyaknya pewarnaan minimum yang dibutuhkan untuk membuat $G$ terhubung pelangi kuat. Misalkan $G_{1}$ adalah graf dengan ${|V(G_{1})|= p_{1}}$. Suatu korona ${G_{1}\odot G_{2}}$ dari dua graf $G_{1}$ dan $G_{2}$ adalah graf yang diperoleh dengan mengambil satu salinan dari graf $G_{1}$ dan $p_{1}$ salinan dari $G_{2}$, kemudian pada simpul ke-$i$ dari $G_{1}$ dikaitkan, ke setiap simpul salinan ke-$i$ dari $G_{2}$. Pada tesis ini dibahas hasil kajian tentang $rc$ dan $src$ pada beberapa kelas graf yaitu graf kristal ${(CR_{m,r})}$, graf neuro5n ${(NR_{m})}$, dan graf ${K_{m}\odot W_{n}}$.

---

Rainbow path is a path which each edge colored with different colors. The rainbow connection number of $G$, denoted by $rc(G)$, is the smallest number of colors needed to color the edges of $G$ such that each pair of vertices in $G$ has a rainbow path. Rainbow ${u-v}$ geodesic of $G$ is rainbow path of length $d(u,v)$, where $d(u,v)$ is the distance between $u$ and $v$. A graph $G$ is a strongly rainbow connected if ${u-v}$ rainbow geodesic for any two vertices $u$ and $v$ in $G$. A strong rainbow connected number $src(G)$ of $G$ is the minimum number of colors needed to make $G$ strongly rainbow connected. Let $G_{1}$ is a graph with ${|V(G_{1})|= p_{1}}$. A corona product ${G_{1}\odot G_{2}}$ of $G_{1}$ and ${G_{2}$ is a graph obtained by taking one copy of ${G_{1}}$, and $p_{}$ in copies of $G_{2}$, and then joining the ith vertices of $G_{1}$, to every vertex in the ith copy of $G_{2}}$ . In this thesis we present some results regarding the $rc$ and $src$ for some classes of graphs, that are crystal graph ${(CR_{m,r})}$, neurons graph ${(NR_{m})}$, and ${K_{m}\odot W_{n}}$ graph."

"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"

"ABSTRAKMengolah data dalam bentuk graf dapat dilakukan dengan cara clustering graf, yaitu mengelompokkan graf ke dalam cluster-cluster dimana data pada satu cluster memiliki karakter yang relatif sama. Two way spectral clustering adalah salah satu cara clustering graf yang menggunakan informasi dari dua nilai eigen untuk mendapatkan dua cluster setiap melakukan proses clustering. Pada skripsi ini akan dibahas bagaimana cara clustering graf dengan metode two way spectral clustering berdasarkan kriteria partisi graf dan akan dilakukan simulasi untuk melihat hasil clustering menggunakan graf terhubung dan graf tidak terhubung.

---

ABSTRACT

Data processing of graph data can be done by graph clustering, where data are grouped into clusters which data on each cluster have the similar characteristic. Two way spectral clustering is one of a graph clustering which using the smallest two eigenvalues to obtain two clusters. This skripsi will discuss how to clustering graph with two way spectral clustering method based on graph partitioning criteria and moreover data simulations will be conducted to see the results of clustering using a connected and disconnected graphs."

"Misalkan 𝐺 adalah graf berarah asiklik. Matriks adjacency dari graf berarah 𝐺 dengan 𝑉 𝐺 = 𝑣1, 𝑣2, ? , 𝑣𝑛 adalah matriks 𝐴 = 𝑎𝑖𝑗 berukuran 𝑛 × 𝑛 di mana 𝑎𝑖𝑗 = 1, untuk 𝑖 ≠ 𝑗 jika terdapat busur berarah dari 𝑣𝑖 ke 𝑣𝑗 , 𝑎𝑖𝑗 = 0 untuk yang lainnya. Matriks antiadjacency dari graf berarah G adalah matriks 𝐵 = 𝐽 − 𝐴 dengan 𝐽 adalah matriks berukuran n × n yang semua entrinya adalah 1. Pada tesis ini diberikan kaitan nilai eigen terbesar matriks antiadjacency dengan derajat terkecil, derajat terbesar graf berarah asiklik yaitu graf bipartit lengkap berarah 𝐾 𝑟,𝑠 dengan 𝑟, 𝑠 ≥ 1, graf lintasan lengkap berarah 𝐶 𝑃 𝑛 dengan 𝑛 ≥ 3, graf lingkaran berarah asiklik 𝐶𝑛 , dan graf lintasan berarah 𝑃 𝑛. Selain hal tersebut juga diberikan relasi nilai eigen terbesar matriks antiadjacency dengan operasi maksimum dari dua graf berarah asiklik.

---

Let 𝐺 be a directed acyclic graph. The adjacency matrix of directed graph 𝐺 with 𝑉 𝐺 = 𝑣1, 𝑣2, ? , 𝑣𝑛 is a matrix 𝐴 = 𝑎𝑖𝑗 of order 𝑛 × 𝑛, where 𝑎𝑖𝑗 = 1 for 𝑖 ≠ 𝑗 if there is an arc from 𝑣𝑖 to 𝑣𝑗 , otherwise 𝑎𝑖𝑗 = 0. Antiadjacency matrix of directed graph 𝐺 is a matrix 𝐵 = 𝐽 − 𝐴, with 𝐽 is a matrix of order 𝑛 × 𝑛 with all entries are 1. In this thesis is given relation between the largest eigen value of antiadjacency matrix with degree minimum and degree maximum of directed acyclic graphs that are complete bipartite directed graph 𝐾 𝑟 ,𝑠 with 𝑟, 𝑠 ≥ 1, complete path directed graph 𝐶 𝑃 𝑛 with 𝑛 ≥ 3, acyclic cycle directed graph with 𝑛 ≥ 4 and path directed graph with 𝑛 ≥ 3. In addition, here are also given relation between the largest eigen value of antiadjacency matrix and maximum operation of two directed acyclic graph."

"Misalkan graf dengan merupakan himpunan tak kosong simpul dan merupakan himpunan busur. Didefinisikan pewarnaan busur dari graf dimana busur yang bertetangga dapat memiliki warna yang sama. Untuk sembarang pasangan simpul berbeda, lintasan pelangi adalah lintasan yang semua warna busur pada lintasan tersebut berbeda. Lintasan terpendek dari sembarang dua simpul di yang di dalamnya tidak terdapat pengulangan warna disebut sebagai geodesik pelangi. Panjang lintasan terpendek merupakan jarak antara sembarang dua simpul. Pewarnaan pelangi dengan suatu geodesik pelangi untuk setiap pasang simpul berjarak maksimum disebut pewarnaan pelangi kuat lokal-. Banyak -warna minimum yang dibutuhkan untuk membentuk pewarnaan pelangi kuat lokal-pada graf disebut bilangan keterhubungan pelangi kuat lokal- pada graf . Graf hasil operasi korona didefinisikan sebagai graf yang terbentuk dari satu graf dan salinan graf , dimana untuk tiap simpul ke- di dihubungkan dengan tiap simpul dari salinan ke- graf . Penelitian ini bertujuan untuk mencari bilangan keterhubungan pelangi kuat lokal graf bipartit lengkap serta graf hasil operasi koronanya dengan komplemen graf lengkap. Graf bipartit lengkap adalah graf yang himpunan simpulnya dapat dipartisi menjadi dua sub-himpunan , sehingga setiap busur di menghubungkan simpul di dan simpul di dan setiap simpul di bertetangga dengan setiap simpul di dan graf lengkap adalah graf yang setiap pasang simpulnya bertetangga.

---

Let be graph where is a non-empty set of vertices and is set of edge. Define an edge coloring , of , where adjacent edges may be have the same color. For any distinct vertices , a rainbow path is a path whose edge color on that path are all distinct. The shortest path from any two vertices in where there are no repeating colors is called a rainbow geodesic. The smallest length of path is a distance between for any vertices and denoted by . A rainbow coloring such that any two vertices with a distance at most with a rainbow geodesic is called -local strong rainbow coloring. Minimum number of -colors required for a -local strong rainbow coloring in is called local strong rainbow connection number-, it can be written as . The corona product is define as a graph that form by taking one grah and copies of graph , where for every -th vertex of is connected to each vertex of the -th copy of . This study aims to find local strong rainbow connection number of complete bipartite graph and it’s corona product with a complement complete graph. Complete bipartite graph is a gaph that the set of vertices can be partitioned into two subset and , such that for every edge in connects the vertices in and vertices in and for every vertices in adjacent with every vertices in and complete graph is a graph that every vertices in that graph is adjacent."

"

Graf berarah G didefinisikan sebagai pasangan terurut dari himpunan (V,E) yang ditulis dengan notasi G=(V,E) dimana V merupakan himpunan berhingga tak kosong yang disebut simpul, dan E adalah himpunan pasangan terurut anggota dari V yang disebut busur. Graf berarah unisiklik adalah graf berarah yang memuat tepat satu subgraf lingkaran. Graf helm berarah unisiklik Hn adalah graf yang diperoleh dari graf roda berarah Wn dengan menambahkan 1 pendant berarah pada tiap simpul lingkaran graf roda. Suatu graf berarah dapat direpresentasikan dalam beberapa bentuk matriks, salah satunya adalah matriks antiketetanggaan. Matriks antiketetanggaan adalah suatu matriks yang setiap entrinya merepresentasikan ada atau tidaknya busur berarah dari suatu simpul kesimpul lainnya. Pada skripsi ini dibahas mengenai polinomial karakteristik dan nilai eigen matriks antiketetanggaan graf helm berarah unisiklik. Bentuk umum dari koefisien-koefisien polinomial karakteristik dari matriks antiketetanggaan diperoleh dengan menjumlahkan nilai-nilai determinan matriks antiketetanggaan dari semua subgraf terinduksi siklik dan asiklik. Nilai-nilai eigen dari matriks antiketetanggaan dari graf helm berarah unisiklik diperoleh dengan mencari akar-akar dari polinomial karakteristik dengan faktorisasi polinomial

---

A directed Graph G is defined as ordered pairs from set (V,E) which is represented by notation G=(V,E) where V is a finite nonempty set of vertices and E is a set of ordered pairs of elements of V called edges.  A directed unicyclic graph is a directed graph that has only one directed cycle subgraph. A directed unicyclic helm graph Hn is obtained from a directed wheel graph Wn by adjoining a directed pendant edge at each vertex of the cycle. A directed graph can be represented into  several matrix representations, one of them is the antiadjacency matrix. The antiadjacency matrix is a matrix in which the entries represent whether there is a directed edge from one vertex to another. This paper discusses the characteristic polynomial and eigenvalues of the antiadjacency matrix of the unicyclic helm graph. The general form of the coefficients of the characteristic polynomial that obtained by adding all of the determinants of antiadjacency matrix from each induced acyclic and cyclic subgraphs. The eigenvalues of the antiadjacency matrix of the directed unicyclic helm graph obtained by factorization its characteristic polynomial.

"

"Dalam teori komputasi dikenal beberapa kelas problema. Salah satu dari kelas-kelas tersebut adalah kelas NP—problem. Di daiam kelas ini terdapat himpunan problema—problema dimana sampai saat ini belum dapat ditemukan alqoritma—algoritma penyelesaian untuk masing—masing problema tersebut yaitu dapat bekerja dalam waktu polinormial agar menghasilkan solusi yang optimal. Selain kelas HP-problem terdapat kelas lain yaitu kelas HP—Complete. Kelas ini merupakan sebuah himpunan problema—problema yang paling berat (the hardest problem) dari himpunan problema-problema di dalam kelas HP—problem. Artinya jika dapat ditemukan algoritma penyelesaian yang bekerja dalam waktu polinomial untuk menghasilkan solusi optimal bagi salah satu anggota kelas ini maka seluruh kelas MP—problem akan dapat pula ditemukan algoritma penyelesaiannya yang polinomial untuk memperoleh solusi yang optimal. Dalam menentukan apakah sebuah anggota HP—problem termasuk di dalam HP—Complete dipergunakan suatu teknik pembuktian yang disebut reduksi. Teknik inilah yang dibahas dan merupakan inti dari tulisan berikut."

"Rainbow connections are natural combinatorial measures that are used in applications to secure the transfer of classified information between agencies in communication networks. Rainbow connections of graphs covers this new and emerging topic in graph theory and brings together a majority of the results that deal with the concept of rainbow connections, first introduced by Chartrand et al. in 2006.The authors begin with an introduction to rainbow connectedness, rainbow coloring, and rainbow connection number. The work is organized into the following categories, computation of the exact values of the rainbow connection numbers for some special graphs, algorithms and complexity analysis, upper bounds in terms of other graph parameters, rainbow connection for dense and sparse graphs, for some graph classes and graph products, rainbow k-connectivity and k-rainbow index, and, rainbow vertex-connection number."