Menentukan bilangan kebebasan titik dan sisi pada graf komplit Kn dan graf bipartisi komplit Km,n, dengan m,n Є N
| Main Author: | Handayani, Denok Sanggrahati Ika Puji |
|---|---|
| Format: | Thesis NonPeerReviewed Book |
| Bahasa: | ind |
| Terbitan: |
, 2009
|
| Subjects: | |
| Online Access: |
http://etheses.uin-malang.ac.id/6510/1/05510042.pdf http://etheses.uin-malang.ac.id/6510/ |
Daftar Isi:
- INDONESIA: Himpunan titik bebas (independent set of vertices) pada suatu graf G adalah himpunan titiktitik dari graf G yang titik satu sama lain dalam himpunan tersebut tidak terhubung langsung (adjacent). Kardinalitas maksimum dari himpunanhimpunan titik bebas disebut bilangan kebebasan titik (vertex independence number) dan disimbolkan dengan ...(G). Himpunan sisi bebas (independent set of edges) pada suatu graf G adalah himpunan sisisisi dari graf G yang sisi satu sama lain tidak terkait langsung dengan satu titik yang sama. Kardinalitas maksimum dari himpunanhimpunan sisi bebas disebut bilangan kebebasan sisi (edge independence number) dan disimbolkan dengan 1(G). Skripsi ini membahas penentuan bilangan kebebasan titik dan sisi pada graf komplit Kn dan graf bipartisi komplit Km,n. Berdasarkan hasil pembahasan, langkahlangkah menentukan bilangan kebebasan titik dan sisi pada graf komplit Kmn dan graf bipartisi komplit Km,n adalah sebagai berikut. (a) Menggambar beberapa contoh graf komplit dan graf bipartisi komplit, (b) Mencari himpunan bebas titik dan himpunan bebas sisi, (c) Menentukan bilangan kebebasan titik dan sisi, (d) Mencari pola dari datadata bilangan kebebasan titik dan sisi, dan (e) Menyatakan konjektur sebagai teorema dan membuktikannya. Berdasarkan langkahlangkah tersebut diperoleh bahwa: 1.Jika Kn adalah graf komplit, maka rumus bilangan kebebasan titik dan sisi masingmasing adalah...dan... 2.Jika Km,n adalah graf bipartisi komplit, dengan m...n dan m, n...N, maka rumus bilangan kebebasan titik dan sisi masingmasing adalah...(Km,n) = n dan...1(Km,n) = m. Disarankan kepada pembaca untuk mengkaji masalah bilangan kebebasan titik dan sisi pada grafgraf yang lain.