Hasil Pencarian  ::  Simpan CSV :: Kembali

Abstrak :
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

Abstrak :
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.

Abstrak :
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

Abstrak :
ABSTRAK
Mengolah 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.

Abstrak :
Dokumen peraturan perundang-undangan pada umumnya tersedia dalam bentuk PDF yang bersifat tidak machine-readable, sehingga data tidak dapat diproses secara otoma-tis dan dalam skala besar oleh komputer untuk dimanfaatkan dalam berbagai teknologi digital. Oleh karena itu diperlukan struktur data yang dapat memuat informasi peraturan perundang-undangan, beserta sistem yang melakukan konversi dari PDF menjadi struk-tur data tersebut. Dengan alasan tersebut, pada penelitian ini penulis mengembangkan Lex2KG, framework untuk mengonversi dokumen PDF peraturan perundang-undangan di Indonesia (Lex berasal dari Bahasa Latin yang berarti hukum) menjadi knowledge gra-ph. Knowledge graph (KG) adalah graph yang menggambarkan entitas dunia nyata be-serta keterkaitannya dan memberikan informasi terstruktur yang machine-readable. Pada penelitian ini KG dipilih dari berbagai struktur data yang tersedia karena KG terkate-gori sebagai 5-star data menurut 5-star deployment scheme for Open Data, yaitu data dengan jenis informasi paling bermanfaat, memberikan data dalam bentuk open license,terstruktur, tersedia dalam open format, menggunakan URI sebagai notasi data, dan dapat dihubungkan (linked) dengan data lain. KG peraturan perundang-undangan mengandung berbagai data terstruktur konten tekstual, struktur dokumen, seperti metadata, serta relasi antara peraturan seperti amendemen dan rujukan. Lex2KG memungkinkan pemanfaatan data peraturan perundang-undangan secara advanced, otomatis, dan dalam skala besar pada berbagai lingkup digital terutama pada industrsi hukum dan pengacara. Contoh pemanfaatan data dapat berupa search engine, sistem question answering, dan analisis statistik peraturan perundang-undangan. Menggunakan Lex2KG, penulis berhasil meng-onversi 784 undang-undang menjadi KG dengan ukuran total lebih dari 1,1 juta triple. Salah satu peraturan yang berhasil dikonversi adalah UU 11/2020 tentang Cipta Kerja yang kontennya bersifat relatif kompleks dan berukuran besar. Penulis juga menunjuk- an use case dari KG peraturan perundang-undangan yaitu chat bot sederhana, SPARQL query, dan visualisasi peraturan perundang-undangan ......Most of the legal documents are available as PDF which is not machine-readable, which means the data could not be processed automatically and in large scale by a computer to be utilized in various digital technology. Therefore, we need a data structure that can contain a legal information, and also a system which converts PDF into that structure. For that reason, in this research, author developed Lex2KG, a framework wh converting legal PDF documents in Indonesia (Lex comes from Latin which means law) into a Knowledge Graph. A knowledge graph (KG) is a graph that describes real-world entities and their relationships as machine-readable and structured information, and linkable to another KG on different domain. In this research KG is choosen from various data structure available because KG it categorized as 5-star data according to 5-star deployment scheme for Open Data, which data comes with most beneficial information, available under an open licen- se, structured, open format, uses URI to denote things, and linkable to other data. The legal KG contains various kinds of structured data such as textual content, document stru- ctures, metadata, and relations between law such as amendments and citations. Lex2KG enables the advanced and automatic utilization of legal data on a large scale on a various digital scope especially on legal industry and lawyer. The utilization could be in form of search engine, question answering system, and statistics analytics for legals. Through Lex2KG, author have successfully converted 784 Indonesian laws into a KG with a total size of over 1.1 million triples. One of the regulation that was successfully converted was Law 11/2020 on Job Creation, which the content is relatively complex and large. Author also shows use cases of the legal KG for simple chatbots, SPARQL querying, and legal visualizations.

Abstrak :
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.

Abstrak :

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.

Abstrak :
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.

Abstrak :
This book constitutes the thoroughly refereed proceedings of the 38th International Workshop on Graph Theoretic Concepts in Computer Science (WG 2012) held in Jerusalem, Israel on June 26-28, 2012. The 29 revised full papers presented were carefully selected and reviewed from 78 submissions. The papers are solicited describing original results on all aspects of graph-theoretic concepts in Computer Science, e.g. structural graph theory, sequential, parallel, randomized, parameterized, and distributed graph and network algorithms and their complexity, graph grammars and graph rewriting systems, graph-based modeling, graph-drawing and layout, random graphs, diagram methods, and support of these concepts by suitable implementations. The scope of WG includes all applications of graph-theoretic concepts in Computer Science, including data structures, data bases, programming languages, computational geometry, tools for software construction, communications, computing on the web, models of the web and scale-free networks, mobile computing, concurrency, computer architectures, VLSI, artificial intelligence, graphics, CAD, operations research, and pattern recognition

Abstrak :
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.