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 b(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 b1(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 Kn 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
b(Kn) = 1
dan
b1(Kn) =
2. Jika Km,n adalah graf bipartisi komplit, dengan m £ n dan m, n Î N, maka
rumus bilangan kebebasan titik dan sisi masingmasing
adalah
b(Km,n) = n
dan
b1(Km,n) = m.
Disarankan kepada pembaca untuk mengkaji masalah bilangan kebebasan
titik dan sisi pada grafgraf
yang lain.
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 b(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 b1(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 Kn 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
b(Kn) = 1
dan
b1(Kn) =
2. Jika Km,n adalah graf bipartisi komplit, dengan m £ n dan m, n Î N, maka
rumus bilangan kebebasan titik dan sisi masingmasing
adalah
b(Km,n) = n
dan
b1(Km,n) = m.
Disarankan kepada pembaca untuk mengkaji masalah bilangan kebebasan
titik dan sisi pada grafgraf
yang lain.
No comments:
Post a Comment