Representasi Pohon dari Graf Kordal Bipartisi

Abstract

Chordal graph formerly better known as rigid-circuit graphs and triangulated graphs. A graph is chordal graphs iff everi cycle of length four and greater has a cycle chord. characterizing chordal graphs very much, one of which is a chordal bipartite graphs. Chordal bipartite graphs is a graph with a cycle length of greater than or equal to 6 (six). The graph should chord and has separator side. In this study, the authors describe the graph represented chordal bipartite graphs which represented into a tree graph with developing F ˜ ANIC˜A GAVRIL algorithms. First, the author to determine chordal graph as chordal bipartite graphs. Then chordal bipartite graph with the help of colouring graph bipartited taking into account the clique in the graph. So that chordal bipartite graphs represented into a tree with the help of algorithms F ˜ ANIC˜A GAVRIL. Determination clique and connectedness between the clique with each other is very important to represented chordal bipartite graphs because of connectedness can be shape to the tree representation.

Graf kordal dahulu lebih dikenal dengan nama rigid-circuit graphs dan triangulated graphs. Sebuah graf dikatakan graf kordal jika panjang lingkaran dari graf tersebut lebih besar atau sama dengan 4 (empat) dan graf tersebut haruslah chord. Pengkarakteristikan graf kordal sangatlah banyak, salah satunya graf kordal bipartisi. Graf kordal bipartisi adalah graf dengan panjang cycle lebih besar atau sama dengan 6 (enam). Graf tersebut haruslah chord dan memiliki sisi pemisah. Pada penelitian ini penulis mendeskripsikan graf kordal bipartisi yang direpresentasikan menjadi graf pohon dengan mengembangkan algoritma F˜ANIC˜A GAVRIL. Pertama penulis menentukan terlebih dahulu graf kordal yang juga merupakan graf kordal bipartisi. Selanjutnya graf kordal bipartisi dengan bantuan colouring graph penulis bipartisikan dengan mempertimbangkan clique pada graf tersebut. Kemudian graf kordal bipartisi direpresentasikan menjadi graf pohon dengan bantuan algoritma F˜ANIC˜A GAVRIL. Penentuan clique dan keterhubungan antara clique yang satu dengan yang lain sangatlah penting dalam merepresentasikan graf kordal bipartisi karena dari keterhubungan clique pada graf kordal dapat di bentuk menjadi representasi pohon.