Bilangan clique dan faktorisasi pada perkalian graf komplit

INDONESIA:

Salah satu topik permasalahan dalam graf adalah bilangan clique dan faktorisasi dalam suatu graf. Bilangan clique merupakan order subgraf komplit terbesar dari suatu graf G, sedangkan faktorisasi pada graf G merupakan penjumlahan sisi dari faktor-faktor yang dimiliki graf G. Graf mempunyai jenis yang bermacam-macam, salah satunya yaitu graf komplit. Dalam penelitian ini bilangan clique dan faktorisasi tidak pada graf komplit yang bersifat tunggal akan tetapi dikembangkan pada perkalian graf komplit. Perkalian graf G_1 × G_2 merupakan operasi pada graf yang mempunyai himpunan titik V(G)= V(G_1) × V(G_2) yang terhubung apabila u_1=v_1 dan [u_2,v_2]ϵE G_2 atau u_2=v_2 dan [u_1,v_1]ϵE G_1

Permasalahan yang diangkat dalam penelitian ini adalah bagaimana menentukan bilangan clique dan faktorisasi pada perkalian graf komplit. Dari definisi bilangan clique dan faktorisasi akan diberikan beberapa contoh perkalian graf komplit. Clique dan faktorisasi pada graf hasil perkalian tersebut diamati sehingga diperoleh bentuk umum dari bilangan clique pada perkalian graf komplit dan faktorisasi pada perkalian graf komplit, yang selanjutnya dinyatakan sebagai konjektur yang dilengkapi dengan bukti-bukti.

Berdasarkan hasil penelitian diperoleh bilangan clique pada perkalian graf (K_n) sebanyak m kali adalah n. Graf hasil perkalian graf komplit (K_n) sebanyak m kali dapat dekomposisikan dengan menggunakan faktor-i dengan i adalah faktor bilangan positif dari (n - 1)× m untuk n genap dan untuk n ganjil i adalah faktor bilangan genap positif dari (n - 1)× m. Penulis menyarankan untuk mengembangkan penelitian dengan mengkaji pada perkalian graf komplit yang heterogen yakni (K_n×K_m×...×K_z) sebanyak m faktor.

ENGLISH:

One topic is the problem in graph clique numbers and factorization in a graph. Clique numbers is a largest order of complete subgraph of graph G. A factorization of graph G is the sum of edges of factors from graf G. Graf has a variety of types, one of that is complete graph. In this tesis clique numbers and factorization is not on a single graph but on Cartesian product of complete graph. Cartesian product of graf G = G_1 × G_2 is an operation on graphs that have vertex set V(G)= V(G_1) × V(G_2) connected if u_1=v_1 and [u_2,v_2]ϵE G_2 or u_2=v_2 and [u_1,v_1]ϵE G_1

The problem in this research is how to determine the clique numbers and factorization on Cartesian product of complete graph. From the definition of clique numbers and factorization will be given some examples in order to obtain the general form of the clique number of graphs on the Cartesian product and factorization on Cartesian product of complete graph, writer will give some examples, so can found the general shape from clique numbers on Cartesian product of complete graph and factorization on Cartesian product of complete graph.

Based on this examination, the number clique on Cartesian product of complete graphs (K_n) counted m times is n. and factorization on Cartesian product of complete graph (K_n) m times as much as ca be factorized by using the factor-i with i is a positive number of factor (n - 1)× m for n even, and n odd i is an even number of positive factor of (n - 1)× m The author recommends to expand research by reviewing the complete graph on a heterogeneous multiplication (K_n×K_m×...×K_z) of m factors.