Hasil Pencarian  ::  Simpan CSV :: Kembali

"ABSTRACTPelabelan graf merupakan salah satu topik yang menarik dalam teori graf. Adabeberapa cara untuk melabeli sebuah graf, dan salah satunya yaitu pelabelan graceful.Misalkan G(V,E) adalah sebuah graf. Pemetaan injektif f : V → {0,1,...,|E|}disebut graceful jika label dari busurnya w(uv) = | f(u) − f(v)| semuanya memilikinilai yang berbeda untuk setiap busur uv. Ada sebuah konjektur terkenal yangbelum terbukti dalam pelabelan graceful. Konjektur tersebut mengatakan bahwasemua graf pohon adalah graceful. Untuk membuktikan konjektur ini, maka harusditunjukan bahwa setiap graf pohon adalah graceful. Terdapat banyak paper penelitianyang membahas tentang pelabelan graceful untuk kelas-kelas graf pohon yangberstruktur tinggi atau kelas-kelas graf pohon yang bersyarat. Banyak kelas graf pohonpun telah dibuktikan adalah graceful dan salah satunya adalah graf Supercaterpillar.Adapun penelitian sebelumnya telah membuktikan bahwa graf Supercaterpillaryang memenuhi syarat tertentu adalah graceful. Dalam tesis ini, konsep darigraf Supercaterpillar diperumum dan ditunjukkan sub-kelas dari graf Supercaterpillaryang belum dibahas pada penelitian sebelumnya juga merupakan graceful.

---

ABSTRACTGraph labeling is one of the interesting topic in graph theory. There are manyway to labeling a graph, and one of them is graceful labeling. Let G(V,E) is agraph. The injective mapping f : V → {0,1,...,|E|} is called graceful if the weightof edge w(uv) = | f(u) − f(v)| are all defferent for every edge uv. There is a famousconjecture in graceful labeling. It said that all trees are graceful. To provethis conjecture, then we must showing that every trees are graceful. There are numerousresearch papers dealing with special cases of highly structured or otherwiserestricted classes. Many classes of trees have been proven are graceful, and one ofthem is Supercaterpillar. Previous research had proved that supercaterpillar satisfyingcertain conditions are also graceful. In this paper, we generalized the conceptof supercaterpillar and show subclass of supercaterpillar graph that has not beendiscussed earlier is also graceful."

"Kelas Graf Tangga Umum GTU(n,m) adalah graf lingkaran n C dengan penambahan ( 1) m- tali-busur, yang disebut busur partisi, dengan syarat tidak ada busur partisi yang memiliki simpul persekutuan, tidak ada busur partisi yang saling bersilangan di sisi dalam graf, dan setiap blok graf memiliki maksimal 2 busur partisi. Untuk mengkonstruksi GTU(n,m) berlabel Total Busur Ajaib Super (TBAS), bobot busur partisi yang ditambahkan adalah min{ } 1 W - atau max{ } 1 W + , di mana W adalah himpunan bobot busur dari GTU(n,m-1). Berdasarkan bobot busur partisinya, GTU(n,m) dapat digolongkan menjadi 3 jenis yaitu GTU(n,m) dengan busur partisi berbobot minimal, GTU(n,m) dengan busur partisi berbobot maksimal, atau GTU(n,m) dengan busur partisi berbobot kombinasi minimal dan maksimal. Di dalam tesis ini, konstruksi Kelas Graf Tangga Umum GTU(n,m) dilakukan dengan menggunakan matriks ketetanggaan (a,1)-Simpul Antiajaib Busur (SAB). Pola pelabelan TBAS yang digunakan adalah pola pelabelan TBAS untuk n C dari Enomoto et al. (1998) untuk n ganjil, dan pola pelabelan TBAS untuk t n C dari MacDougall dan Wallis (2003) untuk n genap. Berdasarkan sifatsifat pada matriks ketetanggaan SAB untuk GTU(n,m), sifat-sifat dari kelas GTU(n,m) dapat diketahui.

---

General Ladder Graph class GTU(n,m) is a cycle graph n C added with ( 1) m- chords, called as partition edges, by conditions that there are no partition edges sharing a vertex, there are no partition edges crossing each other in the inner side of the graph, and every block has maximum 2 partition edges. To construct GTU(n,m) with Super Edge-Magic Total (SEMT) labeling, the weight of the newly added partition edge is min{ } 1 W - or max{ } 1 W + , where W is a set of edge weights of GTU(n,m-1). Based on the weight of partition edges, GTU(n,m) is divided into three categories. There are GTU(n,m) with minimum weight of partition edges, GTU(n,m) with maximum weight of partition edges, and GTU(n,m) with combination of minimum and maximum weight of partition edges. The construction of General Ladder Graph class GTU(n,m) explained in this thesis is done by using (a,1)-Edge-Antimagic Vertex (EAV) adjacency matrix. SEMT labeling function for n C from Enomoto et. al (1998) is used for n odd, and SEMT labeling function for t n C from MacDougall and Wallis (2003) is used for n even. Based on the properties of EAV adjacency matrix for GTU(n,m), the properties of GTU(n,m) graph can be discovered."

"Pencacahan clique maksimal adalah suatu metode graph clustering yang bertujuan untuk mencari simpul mana saja yang memiliki peranan paling besar dalam suatu graf. Pencacahan clique maksimal ini telah banyak diaplikasikan, diantaranya analisis pada jaringan sosial, pendeteksian hierarki melalui jaringan email, analisis statistik jaringan finansial, clustering pada jaringan dinamis, dan komputasi biologi. Algoritma Bron-Kerbosch merupakan salah satu algoritma tercepat dalam pencarian clique maksimal, maka pada penelitian ini, digunakanlah algoritma Bron-Kerbosch. Dalam mencacah semua clique maksimal dari suatu graf, matriks yang biasa digunakan adalah matriks ketetanggaan dari graf tersebut, sehingga dapat diperoleh simpul mana saja pada graf yang memiliki peranan paling besar. Selain matriks ketetanggaan, penelitian ini juga menggunakan matriks komplemen dalam mencacah clique maksimal. Data yang digunakan dalam penelitian ini adalah graf yang merepresentasikan rute jalur penerbangan domestik dari salah satu maskapai penerbangan di Indonesia. Dengan menerapkan algoritma Bron-Kerbosch, semua clique maksimal dari graf terkait akan didaftar, sehingga dapat diperoleh simpul yang memiliki peranan paling besar dalam graf ini. Graf tersebut direpresentasikan dalam bentuk matriks ketetanggaan dan juga matriks komplemen. Hasil penerapan algoritma Bron-Kerbosch pada data, baik yang menggunakan matriks ketetanggaan maupun matriks komplemen, keduanya memberikan hasil yang sama dalam menentukan simpul yang memiliki peranan paling besar dari graf terkait. Selain itu, melalui hasil penerapan yang menggunakan matriks komplemen, dapat diketahui pula simpul-simpul yang hanya bertetangga langsung dengan simpul yang memiliki peranan paling besar.

---

Maximal clique enumeration is a graph clustering method for finding all vertices that have the most influence in a graph. This maximal clique enumeration has largely been applied, including social network analysis, hierarchy detection through email networks, statistical analysis of financial networks, clustering in dynamic networks, and computational biology. The Bron-Kerbosch algorithm is one of the fastest algorithms to find all maximal cliques, hence this research will focus on that algorithm to find all maximal cliques. Counting all maximal cliques of a graph usually uses an adjacency matrix of the graph to find all vertices in the graph that have the most influence. Other than adjacency matrix, this research will also use a complement matrix in counting all maximal cliques. This research uses a graph that represents a domestic flight route of one of the airlines in Indonesia. By using Bron-Kerbosch algorithm, all maximal cliques of the graph will be listed, so that it will come up with the vertices which are the most influential in this graph. The graph will be represented in an adjacency matrix as well as a complement matrix. The result of applying the Bron-Kerbosch algorithm both the adjacency and the complement matrix?will give the same result in determining vertices that have the most influence in the graph. Besides that, by using a complement matrix, the result gives more information on the vertices which are only connected to the vertices that have the most influence."

"Graf merupakan himpunan simpul dan busur dengan setiap busurnya menghubungkan dua simpul. Graf dapat direpresentasikan dalam sebuah matriks. Matriks representasi graf di antaranya yaitu matriks ketetanggaan, matriks jarak, matrik kehadiran, dan matriks Laplacian. Matriks ketetanggaan merepresentasikan ada tidaknya busur yang menghubungkan dua buah simpul. Matriks jarak merepresentasikan jarak lintasan terpendek antara dua simpul pada graf. Pada graf berdiameter dua, yaitu jarak terpanjang di antara dua simpul adalah dua. Graf berdiameter dua di antaranya yaitu graf bipartit, graf roda, dan graf kipas. Pada tesis ini akan dibahas hubungan antara matriks ketetanggaan dan matriks jarak dari suatu graf berdiameter dua, dan sifat-sifat matriks jarak pada graf berdiameter dua, serta polinomial karakteristik dari matriks jarak pada kelas graf khusus berdiameter dua yaitu graf bipartit lengkap 𝐾𝑛,𝑛.

---

Graph is the set of vertices and edges where each edge connects two vertices. The graph can be represented by a matrix. There are several matrix representation of graph, such as adjacency matrix, distance matrix, incidence matrix, and Laplacian matrix. The adjacency matrix represents the presence or absence of an arc connecting two vertices. Distance matrix represent the shortest path between two vertices on a graph. The example of two-diameter graphs are bipartite graphs, wheel graphs, and fan graphs. In this thesis we discuss the relationship between the adjacency matrix and the distance matrix of a two-diameter graph, and the properties of the distance matrix in the twodiameter graph, and the characteristic polynomial of the distance matrix of special family of two-diameter graph that is complete bipartite graph 𝐾𝑛,𝑛."

"Pelabelan graf, atau juga dikenal sebagai valuation graf, adalah pemetaan dari elemen graf ke himpunan bilangan yang disebut sebagai label, yang memenuhi beberapa ketentuan sesuai dengan jenis pelabelannya. Pemetaan ?? disebut sebagai pelabelan graceful dari graf dengan busur sebanyak "jika" adalah suatu fungsi injektif dari himpunan simpul di ke himpunan 0,1, hellip;, "sedemikian sehingga ketika masing-masing busur" diberi label "minus", label yang dihasilkan untuk semua busur adalah berbeda. Tidak banyak teknik umum yang diketahui untuk menghasilkan pelabelan graceful. Secara khusus, konjektur Ringel-Kotzig yang menyatakan bahwa semua graf pohon adalah graceful masih terbuka sampai saat ini. Pada dasarnya, semua graf pohon dapat direpresentasikan sebagai suatu graf pohon berakar, yaitu graf pohon dengan sebuah simpul yang dibedakan dan disebut sebagai simpul akar. Di dalam tesis ini dibahas tentang konstruksi pelabelan graceful pada graf pohon berakar khusus menggunakan matriks ketetanggaan.

---

A graph labeling, also known as a valuation of a graph, is a mapping which carries graph elements onto numbers called labels that meet some properties depending on the type of labeling that is being considered. A function is called a graceful labeling of a graph with edges if is an injection from the vertices of to the set 0,1, hellip, such that, when each edge is assigned the label minus, the resulting edge labels are distinct. Not many general techniques are known in order to generate graceful labeling of graphs. In particular the famous Ringel ndash Kotzig conjecture which states that all trees are graceful remains open until present. Every tree can be represented as a rooted tree with a distinguished vertex called the root. In this thesis we discuss on construction of specific graceful rooted tree using the adjacency matrix."