ANALISIS MORFOLOGI JALAN KOTA DENGAN PENERAPAN TEORI GRAF DOMINATING SET

Abstract

Analisis Morfologi Jalan Kota dengan Penerapan Teori Graf Domi- nating Set; Agustina Muharromah, 101810101002; 2014: 58 halaman; Jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Jember. Teori graf merupakan salah satu cabang matematika diskrit yang memiliki banyak aplikasi dalam kehidupan sehari-hari, terutama dalam analisis morfologi jalan. Jalan sebagai bagian dari sistem transportasi nasional mempunyai peranan penting terutama dalam mendukung bidang ekonomi, sosial dan budaya serta lingkungan. Peta jalan direpresentasikan kedalam J-graph menggunakan teknik konstruksi line graph, dan juga masalah lain yang dapat dikaitkan dengan teori graf misalkan penempatan pos pantau dengan teori dominating set. Salah satu upaya penting yang dapat dikerjakan adalah mengembangkan teori dominating set pada beberapa family graf khusus. Line graph dengan sebuah graf G, L(G) = (A, N) adalah sebuah graf sedemikian hingga himpunan titik dari L(G) merupakan himpunan sisi dari G dan himpunan titik dari L(G) yaitu jika (u, v) ∈ G maka (uv) = (vu) ∈ E(G) jadi V (L(G)) = E(G).L(G) merupakan line graph yang memiliki D = 2 ∗ (∆(G)) − 2 dan D(L(G)) = D(G) + 1. Dominating set merupakan subset S ⊆ V dari titik di G sedemikian sehingga untuk semua titik v ∈ V , salah satu dari v ∈ S atau sebuah tetangga u dari v ada di S. Metode yang digunakan dalam penelitian ini adalah deskriptif aksiomatik yaitu dengan menurunkan teorema yang telah ada tentang nilai batas bawah dan batas atas, kemudian diterapkan dalam penentuan titik-titik sebagai dominating set. Teorema yang dihasilkan adalah sebagai berikut: 1. Teorema 4.4.1 Misal G adalah graf join C , untuk n ≥ 2 dan m ≥ 3 memiliki domination number γ(C n 2. Teorema 4.2.2 Misal G adalah graf join P + S m n ) = 1. n +S +C m , untuk n ≥ 2 dan m ≥ 3 memiliki domination number γ(P n + C viii m ) = 1. m 3. Teorema 4.2.3 Misal G adalah graf Shackel(S , n) yang dinotasikan dengan Shackel (S m m , n) untuk n ≥ 2 dan m ≥ 3 memiliki domination number γ(Shackel (S m , n)) = n. 4. Teorema 4.2.4 Misal G adalah graf C n ⊙(P ), untuk n ≥ 3 memiliki domination number γ(C n ⊙ (P 4 + K 5. Teorema 4.2.5 Misal G adalah graf Join C 1 )) = n. 4 n +K + P 1 , untuk n ≥ 3 memiliki domination number γ(C n + P n ) = ⌈ n 3 ⌉. 6. Teorema 4.2.6 Misal G adalah graf Triangular Ladder L n memiliki domination number γ(L n ) = ( ⌈ n 2 ⌉, untuk n = 3 dan n = 2k dimana k ≥ 2 ⌊ n 2 ⌋, untuk n = 2k + 1 dimana k ≥ 2 7. Teorema 4.2.7 Misal G adalah graf P 2 ⊗ C n n , untuk n ≥ 3 memiliki domination number γ(P 2 ⊗ C n ) = ⌈ 8. Teorema 4.2.8 Misal G adalah graf P n 3 ⌉. ], untuk n ≥ 4 memiliki domination number γ(P n [C 3 ]) = ⌈ n+1 3 ⌉.