EXTREMAL GRAPH PADA SUBGRAF LENGKAP

Oleh :
RINI TRI WARDANI - M0102044 -

ABSTRAK Rini Tri Wardani, 2006. EXTREMAL GRAPH PADA SUBGRAF LENGKAP. Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Sebelas Maret. Teori extremal graph merupakan cabang dari teori graf yang membahas mengenai relasi antara invariant graf. Jika diberikan sifat P, invariat  dan kelas graf H, ditentukan nilai paling sedikit m sehingga setiap graf G dalam H dengan (G)>m memiliki sifat P. Graf G dalam H tanpa sifat P dan invariant (G) = m disebut extremal graph. Tujuan dari skripsi ini adalah mengenalkan pembentukan extremal graph pada graf G yang memuat subgraf G1 dan struktur extremal graph pada subgraf lengkap dengan invariant graf adalah size. Metode yang digunakan dalam penulisan skripsi ini adalah studi literatur. Dari pembahasan diperoleh kesimpulan bahwa extremal graph pada graf G yang memuat subgraf G1 adalah graf dengan order n dan size maksimum ex(n; G1) tanpa memuat subgraf G1. Extremal graph pada subgraf lengkap Kr adalah (r – 1) – complete partite graph. Struktur extremal graph pada subgraf lengkap isomorfik dengan Turán graph Tr – 1(n).