Kajian tentang graf perfect

Imamah AH, Nurul (2008) Kajian tentang graf perfect. Undergraduate thesis, Universitas Islam Negeri Maulana Malik Ibrahim.

[img]
Preview
Text (Full text)
04510008.pdf - Accepted Version
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (595kB) | Preview

Abstract

INDONESIA:

Pewarnaan titik pada graf G adalah pemberian warna untuk setiap titik pada graf G, sehingga tidak ada dua titik yang terhubung langsung mendapatkan warna yang sama. Banyaknya warna terkecil yang diberikan pada titik-titik di graf G sedemikian hingga untuk setiap dua titik yang terhubung langsung mendapatkan warna yang berbeda disebut dengan bilangan khromatik. Banyaknya titik yang dimiliki oleh graf G disebut dengan order dari G. Order maksimum dari subgraf komplit yang dapat dibentuk dari suatu graf G disebut dengan bilangan clique.

Salah satu aplikasi dari bilangan clique dan bilangan khromatik suatu graf G adalah pada graf perfect. Graf perfect adalah suatu graf yang memiliki bilangan clique dan bilangan khromatik yang sama.

Adapun langkah-langkah menentukan graf perfect adalah sebagai berikut:
1. Menentukan subgraf komplit maksimum yang dapat dibentuk dari graf G
2. Menentukan bilangan clique(G) dan menentukan bilangan khromatik (G) pada beberapa kasus untuk menentukan pola.
3. Pola yang diperoleh dinyatakan dengan teorema.
4. Membuktikan teorema.
Berdasarkan pembahasan dalam skripsi ini diperoleh bahwa graf kosong, graf komplit, graf bipartisi komplit, graf sikel genap, dan graf lintasan adalah graf perfect, karena masing-masing graf tersebut memiliki bilangan clique dan bilangan khromatik yang sama

Item Type: Thesis (Undergraduate)
Supervisor: Abdussakir, Abdussakir and Aziz, Abdul
Keywords: Graf; Pewarnaan titik; Order; Clique; Khromatik graf perfect.
Departement: Fakultas Sains dan Teknologi > Jurusan Matematika
Depositing User: Siti Maimunah
Date Deposited: 14 Aug 2016 03:43
Last Modified: 14 Aug 2016 03:43
URI: http://etheses.uin-malang.ac.id/id/eprint/4423

Actions (login required)

View Item View Item