Maria Remisiansi Gatur Pengarang MEKSIANIS ZADRAK NDII Dosen Pembimbing 2 Meksianis Zadrak Ndii Penguji 1 Irvandi G. Pasangka Penguji 2 Ganesha Lapenangga Putra Ketua Penguji

Graf G didefinisikan sebagai pasangan himpunan (V,E) dengan V adalah himpunan tak kosong dari simpul-simpul (vertex) dan E adalah himpunan sisi (edges) yang menghubungkan sepasang simpul. Jika setiap simpul pada graf G memiliki derajat yang sama maka disebut graf reguler. Selanjutnya, graf G direpresentasikan dalam bentuk matriks dan ditentukan matriks ketetanggaan. Matriks ketetanggaan adalah suatu matriks yang bernilai 1 jika (v_i,v_j ) bertetangga dan 0 lainnya. Selanjutnya, jika matriks ketetanggaan graf G telah diperoleh maka akan ditentukan polinomial karakteristik. Polinomial karakterstik adalah suatu polinomial p(λ)=det(λI-A). Akar p(λ)=0 adalah nilai eigen dari matriks ketetanggaan. Nilai eigen dan vektor eigen suatu graf diperoleh dengan Ax=λx, dengan λ adalah nilai eigen dan x adalah vektor eigen. Pada skripsi ini, diperoleh nilai eigen terkecil matriks Laplace dari suatu graf yaitu μ=0 dan semua nilai eigen matriks Laplace bernilai non negatif. Selanjutnya, diperoleh nilai eigen matriks Laplace dari graf reguler berderajat k yaitu μ_i=k-λ_i dengan λ_i adalah nilai eigen dari matriks ketetanggaan. Kata kunci: matriks ketetanggaan, polinomial karakteristik, nilai eigen dan vektor eigen