Menentukan bilangan kebebasan titik dan sisi pada graf komplit Kn dan graf bipartisi komplit Km,n, dengan m,n Є N

INDONESIA:

Himpunan titik bebas (independent set of vertices) pada suatu graf G adalah himpunan titik­titik dari graf G yang titik satu sama lain dalam himpunan tersebut tidak terhubung langsung (adjacent). Kardinalitas maksimum dari himpunan­himpunan 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 sisi­sisi dari graf G yang sisi satu sama lain tidak terkait langsung dengan satu titik yang sama. Kardinalitas maksimum dari himpunan­himpunan 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, langkah­langkah 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 data­data bilangan kebebasan titik dan sisi, dan (e) Menyatakan konjektur sebagai teorema dan membuktikannya. Berdasarkan langkah­langkah tersebut diperoleh bahwa:

1.Jika Kn adalah graf komplit, maka rumus bilangan kebebasan titik dan sisi masing­masing adalah...dan...

2.Jika Km,n adalah graf bipartisi komplit, dengan m...n dan m, n...N, maka rumus bilangan kebebasan titik dan sisi masing­masing adalah...(Km,n) = n dan...1(Km,n) = m.

Disarankan kepada pembaca untuk mengkaji masalah bilangan kebebasan titik dan sisi pada graf­graf yang lain.