Banyaknya pohon rentangan pada graf commuting dari grup dehidral

INDONESIA :

Teori graf pertama kali diperkenalkan oleh Leonhard Euler pada tahun 1736. Salah satu kajian teori graf yang menarik untuk diteliti adalah banyaknya pohon rentangan pada suatu graf sederhana. Beberapa penelitian tentang banyaknya pohon rentangan telah banyak dilakukan. Namun, penelitian itu dapat diperluas dengan menghubungkan kajian teori graf pohon rentangan pada suatu graf dengan kajian aljabar yaitu grup dihedral. Sehingga pada penulisan skripsi ini akan diteliti mengenai banyaknya pohon rentangan pada graf commuting grup dihedral.

Metode penelitian yang yang digunakan dalam peneltian ini adalah studi kepustakaan dengan tahapan analisis yang diawali dengan menentukan elemen-elemen grup dihedral-2n dengan 3≤n≤9,n bilangan asli ganjil. Langkah selanjutnyanya adalah menggambarkan bentuk graf commuting dari grup dihedral Γ(D_2n,X), dengan elemen-elemen di X sebagai titik, dan elemen-elemen di X dikatakan terhubung jika elemen-elemen di X komutatif, X⊆D_2n, selanjutnya dapat ditentukan banyaknya pohon rentangan τ(D_2n,X).

Hasil dari penelitian ini adalah:
τ(D_2n,X)=1 untuk n bilangan asli ganjil dan X=(1,s,sr,…,sr^(n-1) )
τ(D_2n,X)=n^(n-2) untuk n bilangan asli ganjil dan X=(1,r,…,r^(n-1) )
τ(D_2n,X)= τ(K_n ) untuk setiap n bilangan asli ganjil dan X=(D_2n )

Penelitian selanjutnya dapat dilakukan dengan n bilangan genap pada graf commuting dari grup dihedral dan pada graf noncommuting dari grup dihedral.

ENGLISH :

Graph theory was first introduced by Leonhard Euler in 1736. One of graph studies which is interesting to be studied is spanning tree number on simple graph. Some researches of spanning tree number have been conducted. However, the research can be expanded by linking the study of graph theory of spanning tree number on graph with study of algebra namely dihedral group. Therefore, the writing of this thesis will be about the spanning tree number on commuting graphs of dihedral group.

The research method that used in this research is the Study of literature with the analysis step begins with determining the elements of dehidral-2n group with 3≤n≤9,n is odd natural number. The next step is drawing commuting graphs of dihedral group Γ(D_2n,X), with elements on X as vertex and elements on X consider to be connected if element on X is commutative and X⊆D_2n, can be further determined spanning tree number τ(D_2n,X).

The results of this study:
τ(D_2n,X)=1 for n is odd natural number and X={1,s,sr,…,sr^(n-1) }
τ(D_2n,X)=n^(n-2) for n is odd natural number and X={1,r,…,r^(n-1) }
τ(D_2n,X)= τ(K_n ) for n is odd natural number and X={D_2n }

The next research can be done by using n even natural number on commuting graphs of dihedral group and on noncommuting graphs of dihedral group.