ANALISIS TENTANG GRAF PERFECT

Abstract

Abstrak

Seiring perkembangan kemajuan teknologi maka ilmu matematika juga semakin berkembang, salah satu analisis matematika khususnya metode graf yang perlu dikembangkan adalah analisis mengenai graf perfect. Graf perfect adalah suatu graf yang memiliki bilangan chromatik  dan bilangan clique yang sama. Bilangan khromatik adalah bilangan terkecil pada pewarnaan yang diberikan pada titik-titik yang dimiliki graf G sedemikian sehingga untuk setiap dua titik yang terhubung langsung mendapatkan warna yang berbeda. Sedangkan bilangan Clique adalah order maksimum dari subgraf komplit yang dapat dibentuk dari suatu graf G dengan order dari G adalah banyaknya titik yang dimiliki oleh graf G.

Berdasarkan pembahasan pada artikel ini maka diperoleh bahwa graf kosong, graf komplit, graf bipartite komplit, graf sikel genap, dan graf lintasan adalah graf perfect karena masing-masing graf tersebut memiliki bilangan chromatik  dan bilangan clique yang sama.

Kata kunci: Graf, Graf Perfect, bilangan Clique, bilangan Chromatik

Abstract

As  technology advances  the development of mathematics  is also growing, one of mathematical analysis particularly method graph that needs to be developed is the analysis of the perfect graph. Perfect graph  is a graph  that has chromatik numbers and numbers of  the same clique . Numbers khromatik is the smallest number in  a given coloring dots owned graph G such that for every two points are  connected directly  to get  different colors. While the  number Clique  is  the maximum  order  of  a complete  subgraph which  can be formed of a graph G with the order of G is the number of dots that are owned by the graph G.

Based on the discussion  in this article  is obtained  that the empty  graph,  complete  graph,  complete  bipartite  graph,  graph  sikel even, and the graph  trajectory  is a graph perfect  for each graph has chromatik  numbersand  numbers  of the same  clique .

Keywords: Graf, Graf Perfect, Clique numbers, numbers Chromatik