Sebuah titik dan sisi dikatakan saling cover pada graf G jika titik dan sisi
tersebut incident pada G. Titik cover di G merupakan himpunan dari titik-titik
yang mengcover semua sisi di G dan sisi cover pada graf G (tanpa titik terisolasi)
merupakan himpunan sisi-sisi yang mengcover semua titik di G. Kardinalitas
minimum titik cover pada graf G disebut bilangan cover titik (vertex covering
number) dan dilambangkan dengan α(G). Sedangkan kardinalitas minimum sisi
cover pada graf G disebut bilangan cover sisi (edge covering number) dan
dilambangkan dengan α1(G). Skripsi ini membahas penentuan bilangan cover titik
dan cover sisi pada graf komplit Kn, graf bipartisi komplit Kn,n dan graf bipartisi
komplit Km,n.
Penelitian ini dilakukan dengan tujuan untuk mengetahui cara menentukan
bilangan cover titik dan cover sisi pada graf komplit Kn, graf bipartisi komplit Kn,n
dan graf bipartisi komplit Km,n.
Berdasarkan hasil pembahasan, langkah-langkah yang dilakukan dalam
membahas penelitian ini adalah sebagai berikut: a) Menggambar beberapa contoh
graf komplit dan graf bipartisi komplit, b) Mencari himpunan cover titik dan
himpunan cover sisi pada beberapa contoh graf komplit dan graf bipartisi komplit,
c) Menentukan bilangan cover titik dan cover sisi dengan menghitung kardinalitas
minimum dari himpunan cover titik dan himpunan cover sisi, dan d) Mencari pola
dari bilangan cover titik dan cover sisi pada graf komplit dan graf bipartisi
komplit. Pola tersebut kemudian dirumuskan sebagai konjektur dan dibuktikan
kebenarannya. Berdasarkan langkah-langkah tersebut, diperoleh bahwa:
1. Jika Kn adalah graf komplit dengan n , maka rumus bilangan cover titik dan
cover sisi masing-masing adalah
α (Kn) = (n-1) dan α1(Kn) =
2. Jika Kn,n adalah graf bipartisi komplit dengan n , maka rumus bilangan
cover titik dan cover sisi masing-masing adalah
α (Kn,n) = n dan α1(Kn,n) = n.
3. Jika Km,n adalah graf bipartisi komplit dengan m, n dan m n, maka
rumus bilangan cover titik dan cover sisi masing-masing adalah
α (Km,n) = m dan α1(Km,n) = n.
tersebut incident pada G. Titik cover di G merupakan himpunan dari titik-titik
yang mengcover semua sisi di G dan sisi cover pada graf G (tanpa titik terisolasi)
merupakan himpunan sisi-sisi yang mengcover semua titik di G. Kardinalitas
minimum titik cover pada graf G disebut bilangan cover titik (vertex covering
number) dan dilambangkan dengan α(G). Sedangkan kardinalitas minimum sisi
cover pada graf G disebut bilangan cover sisi (edge covering number) dan
dilambangkan dengan α1(G). Skripsi ini membahas penentuan bilangan cover titik
dan cover sisi pada graf komplit Kn, graf bipartisi komplit Kn,n dan graf bipartisi
komplit Km,n.
Penelitian ini dilakukan dengan tujuan untuk mengetahui cara menentukan
bilangan cover titik dan cover sisi pada graf komplit Kn, graf bipartisi komplit Kn,n
dan graf bipartisi komplit Km,n.
Berdasarkan hasil pembahasan, langkah-langkah yang dilakukan dalam
membahas penelitian ini adalah sebagai berikut: a) Menggambar beberapa contoh
graf komplit dan graf bipartisi komplit, b) Mencari himpunan cover titik dan
himpunan cover sisi pada beberapa contoh graf komplit dan graf bipartisi komplit,
c) Menentukan bilangan cover titik dan cover sisi dengan menghitung kardinalitas
minimum dari himpunan cover titik dan himpunan cover sisi, dan d) Mencari pola
dari bilangan cover titik dan cover sisi pada graf komplit dan graf bipartisi
komplit. Pola tersebut kemudian dirumuskan sebagai konjektur dan dibuktikan
kebenarannya. Berdasarkan langkah-langkah tersebut, diperoleh bahwa:
1. Jika Kn adalah graf komplit dengan n , maka rumus bilangan cover titik dan
cover sisi masing-masing adalah
α (Kn) = (n-1) dan α1(Kn) =
2. Jika Kn,n adalah graf bipartisi komplit dengan n , maka rumus bilangan
cover titik dan cover sisi masing-masing adalah
α (Kn,n) = n dan α1(Kn,n) = n.
3. Jika Km,n adalah graf bipartisi komplit dengan m, n dan m n, maka
rumus bilangan cover titik dan cover sisi masing-masing adalah
α (Km,n) = m dan α1(Km,n) = n.
No comments:
Post a Comment