Total k-defisiensi titik dari pohon merentang suatu graf terhubung

INDONESIA:

Salah satu permasalahan dalam teori graf adalah k-defisiensi titik. Suatu titik V dari suatu pohon merentang T pada graf G disebut k-defisiensi titik jika derajat dari titik tersebut memenuhi persamaan ..., bilangan bulat k di atas disebut defisiensi dari V. Tujuan dari penelitian ini adalah menentukan jumlah k-defisiensi titik dari suatu pohon merentang dari graf terhubung.

Dalam penelitian ini, metode yang digunakan adalah metode penelitian pustaka (library research), dengan menggunakan graf sikel, graf komplit, graf tangga, graf bintang dan graf roda sebagai contoh. Adapun langkah-langkah penelitian sebagai berikut: (1) Menggambar graf yang akan digunakan dan menentukan derajat titik; (2) Mencari pohon merentang (mencari semua kemungkinan pohon merentang); (3) Menentukan derajat titik dari pohon merentang; (4) Menentukan k-defisiensi titik; (5) Menentukan pola rumusan k- defisiensi titik; (6) Membuktikan pola rumusan k-defisiensi titik.

Berdasarkan hasil pembahasan, dapat diperoleh (1) Nilai k-defisiensi titik pada graf sikel adalah 2; (2) rumus k-defisiensi titik pada graf komplit adalah ...; (3) Rumus k-defisiensi titik untuk graf tangga adalah 2(n-1); (4) Rumus k-defisiensi titik pada graf bintang adalah 0; (5) k-defisiensi titik pada graf roda adalah 2n.

k-defisiensi titik digunakan pada graf dan pohon merentangnya. Sehingga pada penelitian selanjutnya penulis menyarankan untuk melanjutkan penelitian pada graf yang lain atau dengan menggunakan pola yang lain misalnya dengan menggunakan graf tak identik.

ENGLISH:

One of problem in graph theory is k-deficient vertex. A point of V from a spanning tree T in graph G is k-deficient vertex if degree of vertex to complete equation , zahlen number k is deficiency from V. The object of the research is knowing is value from k-deficient vertex from a spanning tree in connected graph.

The method of this method is library research, to example used cycle graph, complete graph, ladder graph, star graph, and wheel graph. The steps of research are: (1) describe of graf and determine vertex of degree; (2) Search spanning tree from graph; (3) Determine vertex of degreefrom spanning tree; (4) Determine k-deficient vertex; (5) Determine conjecture of k-deficient vertex; (6) Proofe conjecture of k-deficient vertex.

According a discussion have (1) Value of k-deficient vertex of cycle graph is 2; (2) Formulate of k-deficient vertex in complete graph is ...; (3) Formulate of k-deficient vertex in ladder graph is 2(n-1); (4) Formulate of k- deficient vertex in star graph is 0; (5) Formulate of k-deficient vertex in wheel graph is 2n. k-deficient vertex used in it’s graph and spanning tree. So in next researcher suggest to continuing this research in other graph or use other formulate, example use nonidentical graph.