9,106 research outputs found
GRAF PEMBAGI NOL ATAS GELANGGANG PERKALIAN
No full textKajian tentang graf adalah kajian yang menarik untuk diteliti. Banyak peneliti yang mengkaji graf dan menghubungk annya dengan gelanggang. Dari hal tersebut penulis tertarik melakukan penelitian mengenai graf yang dihubungkan dengan gelanggang perkalian. Penelitian ini menggunakan metode penelitian studi pustaka, yaitu mengumpulkan data dan informasi dari buku, jurnal ilmiah, thesis dan skripsi. Setelah membuktikan gelanggang zn dengan n tertentu adalah gelanggang perkalian, diperoleh teorema bentuk graf, jumlah simpul, jumlah sisi dan jumlah derajat semua simpul pada graf tersebut melalui pembuktia
KLASIFIKASI GRAF POHON BINER LENGKAP LEVEL- n (n = 1,2,3) BERDASARKAN PEWARNAAN-f
No full textGraf G adalah pasangan himpunan (V,E) dengan V merupakan himpunan berhingga tidak kosong dari objek-objek yang disebut titik dan E merupakan himpunan berhingga, mungkin kosong, pasangan tidak terurut dari titik-titik berbeda. Setiap pasangan titik disebut sisi. Pewarnaan sisi (edge-coloring) pada suatu graf G merupakan salah satu cara pewarnaan pada graf G sedemikian sehingga sisi-sisi yang bertetangga memiliki warna yang berbeda. \ud
Penelitian ini akan mengkaji perumuman dari pewarnaan sisi, yaitu pewarnaan-f. Pewarnaan-f pada graf G(V,E) adalah pemberian warna pada sisi-sisi G sedemikian sehingga sisi-sisi yang bertetangga pada suatu titik v dapat memiliki warna yang sama paling banyak f(v) buah. Banyaknya warna minimum yang digunakan pada pewarnaan-f pada suatu graf G disebut f-kromatik indeks, dinotasikan dengan ?????^'???_f (G). \ud
Misalkan ???_f (G)=maks{??? ???d(v)/f(v) ??? ???| v ?? V} maka batas bawah dan batas atas dari f-kromatik indeks pada suatu graf G memenuhi:\ud
???_f (G) ????????? ?????^'???_f (G)??? ???_f (G)+1\ud
Jika ?????? ?????^'???_f (G)=???_f (G) maka graf G tergolong dalam c_f 1 dan jika ?????? ?????^'???_f (G)= ???_f (G)+1 maka graf G tergolong dalam c_f 2.\ud
Pada penelitian ini diperoleh bahwa graf pohon biner lengkap level-n (n=1,2,3) tergolong dalam c_f 1
Bilangan Ramsey untuk Kombinasi Graf Lingkaran Terhadap Graf Roda
No full textDiberikan dua buah graf G dan H. Bilangan Ramsey R(G,H) adalah bilangan bulat positif terkecil n sedemikian sehingga jika graf Kn diwarnai dengan warna merah dan biru maka senantiasa memuat suatu subgraf G dimana semua sisinya berwarna merah atau subgraf H dimana semua sisinya berwarna biru. Bilangan Ramsey R(G,H) dapat juga didefinisikan sebagai suatu bilangan bulat terkecil n sedemikian sehingga setiap sebarang graf F dengan n simpul akan senantiasa memuat subgraf G atau komplemen dari F akan memuat H. Huai Lu Zhou (1995) telah menunjukkan bahwa bilangan Ramsey R(Cn,Wm) = 2m 1 untuk n ganjil dan . Dalam tulisan ini akan ditunjukkan R(C5,W3) = 13. Disamping itu, kita akan menunjukkan hasil yang lebih umum untuk graf lingkaran, yakni R(C3,Cn) = 2n-1 jika . Tesis ini juga mengkaji bilangan Ramsey untuk graf berarah. Hasil yang diperoleh adalah bila dengan = dimana adalah suatu lintasan dari a ke b
POLINOMIAL KROMATIK GRAF LOLLIPOP DAN GRAF HASIL OPERASI COMB GRAF BINTANG DENGAN GRAF LENGKAP
No full textGraf Lollipop dan graf hasil operasi comb merupakan graf yang terbentuk dengan menggabungkan beberapa graf menjadi bentuk graf yang baru. Graf Lollipop L_(m,n) diperoleh dengan menghubungkan graf lengkap K_m dengan graf lintasan P_n melalui sebuah sisi. Graf hasil operasi comb graf bintang dengan graf lengkap S_p⊳K_q diperoleh dengan menempelkan p+1 buah salinan graf lengkap K_q pada titik-titik dari graf bintang S_p. Polinomial kromatik dari graf G, yang dilambangkan dengan P(G,λ), didefinisikan sebagai banyak cara mewarnai graf G dengan λ warna. Pada penelitian ini, dengan metode pendeteksian pola dan induksi dihasilkan polinomial kromatik graf Lollipop L_(m,n) dan graf hasil operasi comb graf bintang dengan graf lengkap S_p⊳K_q. Metode ini mendeteksi dan menganalisis pola-pola berulang polinomial kromatik graf Lollipop L_(m,n) dan graf hasil operasi comb graf bintang dengan graf lengkap S_p⊳K_q kemudian dilakukan rumusan umum pada pola tersebut. Temuan penelitian ini menunjukkan bahwa polinomial kromatik graf Lollipop L_(m,n) untuk m≥3 dan n≥1 adalah:
P(L_(m,n),λ)=λ(λ-1 )^(n+1) (λ-2)…(λ-m+1).
Sementara itu, polinomial kromatik graf hasil operasi comb graf bintang dengan graf lengkap S_p⊳K_q untuk p≥3 dan q≥3 adalah:
P(S_p⊳K_q,λ)=λ(λ-1 )^(2p+1) (λ-2)^(p+1)…(λ-q+1)^(p+1).
A Lollipop graph and a comb product of graphs are graphs formed by combining several graphs into a new graph. The Lollipop graph L_(m,n) is obtained by connecting a complete graph K_m with a path graph P_n through an edge. The comb product of a star graph and a complete graph S_p⊳K_q is obtained by grafting p+1 copies of the complete graph K_q at the vertices of the star graph S_p. The chromatic polynomial of a graph G denoted by P(G,λ), is defined as the number of ways to colour the graph G with λ colours. In this study, using pattern detection and induction methods, the chromatic polynomial of Lollipop graph L_(m,n) and the comb product of a star graph and a complete graph S_p⊳K_q are obtained. This method detects and analyses the repeating patterns of the chromatic polynomials of Lollipop graph L_(m,n) and the comb product of a star graph and a complete graph S_p⊳K_q, then applies a general formulation to the pattern. The result shows that the chromatic polynomials of Lollipop graph L_(m,n) for m≥3 and n≥1 is:
P(L_(m,n),λ)=λ(λ-1 )^(n+1) (λ-2)…(λ-m+1).
Additionally, the chromatic polynomials of the comb product of a star graph and a complete graph S_p⊳K_q for p≥3 and q≥3 is:
P(S_p⊳K_q,λ)=λ(λ-1 )^(2p+1) (λ-2)^(p+1)…(λ-q+1)^(p+1)
Bilangan rainbow connection graf garis dari graf kincir (Wd3,n) dan (Wd4,n)
No full textABSTRAK
Bilangan rainbow connection dari G, dinotasikan rc(G), adalah minimum warna
yang digunakan untuk mewarnai sisi graf G, dimana untuk setiap pasang titik di
G dihubungkan oleh sisi yang tidak berwarna sama. Dalam penelitian ini akan
ditentukan bilangan rainbow connection Graf Garis dari Graf Kincir (Wd3;n) dan
(Wd4;n) dimana setiap sisi pada graf kincir menjadi titik pada graf garisnya, yang
menghasilkan suatu bentuk graf baru L(Wd3;n dan L(Wd4;n). Graf kincir (Wd3;n)
dengan banyak sisi 3�n dan graf kincir (Wd4;n) dengan banyak sisi 4�n, setiap
graf garis dari masing-masing graf kincir (Wd3;n) dan (Wd4;n) memuat graf leng-
kap K2n untuk n > 1, dan terdapat n buah K3 dan K4.
Kata kunci : Bilangan Rainbow Connection, Graf Kincir, Graf Garis, Graf
Lengkap dan Graf Garis dari Graf kincir
GRAF-GRAF BERORDE n DENGAN BILANGAN KROMATIK LOKASI n - 1
No full textMisalkan c suatu pewarnaan pada graf terhubung G. Misalkan Π={C1,C2,…,Ck} adalah suatu partisi terurut dari V (G) ke dalam kelas-kelas warna yang dihasilkan. Untuk suatu titik v di G, kode warna cΠ(v) dari v adalah k-tuple terurut
(d(v,C1),d(v,C2),…,d(v,Ck)),
dimana d(v,Ci)=min{d(v,x)| xECi} untuk 1≤i≤k . Jika setiap titik yang berbeda di G memiliki kode warna yang berbeda terhadap Π, maka c disebut pewarnaan lokasi (locating coloring) bagi G. Bilangan kromatik lokasi XL(G) adalah minimum dari banyaknya warna pada pewarnaan lokasi di G. Hal ini menunjukkan bahwa, jika G adalah graf terhubung dengan orde n≥3 yang diinduksi oleh subgraf multipartit lengkap berorde n−1, maka n+12≤XL(G)≤n. Graf dengan orde n yang diinduksi oleh subgraf multipartit lengkap berorde n−1 digunakan untuk mengkarakterisasi graf dengan orde n≥4 yang mempunyai bilangan kromatik lokasi n−1. Selanjutnya untuk n≥5, jika G=Gn+2K2 dengan Gn adalah suatu graf multipartit lengkap berorde n−4 dan K2adalah graf lengkap berorde 2, maka G adalah graf dengan bilangan kromatik lokasi n−1.
Kata kunci: Himpunan lokasi, Pewarnaan lokasi, Bilangan kromatik lokas
PENGEMBANGAN KAJIAN BILANGAN RAMSEY UNTUK GRAF BINTANG
No full textABSTRAK TEKNOSAINS 2009Bilangan Ramsey R(G,H) untuk suatu graf G dan H Adalah bilangan bulat terkecil n sedemikian sehingga untuk sebarang graf F dengan n titik memenuhi sifat:F memuat G atau komplemen dari F memuat H.Batas bawah bilangan Ramsey R(G,H) yang diberikan oleh Chvatal dan Harary adalah R(G,H)> (X(H)-1)(C(G)-1+,denganX(H)adalah bilangan kromatik graf H dan C(G) adalah banyaknya titik pada komponen tersebasar graf G.Sejak adanya batas bawah ini, kajian bilangan Ramsey untuk graf pohon.Hal ini disebabkan oleh struktur pohon yang berbeda-beda.Struktur yang paling sederhana adalah lintasan dan bintang. Karena itu,pengkajian bilangan Ramsey untuk graf pohon umumnya dimulai dengan pengkajian bilangan Ramsey untuk lintasan atau bintang. Hasil kajian Baskoro dkk.(2002) tentang bilangan Ramsey untuk pohon dan roda menunjukkan bahwa struktur yang paling berpengaruh pada penentuan bilangan Ramsey untuk pohon adalah bintang,meskipun struktur bintang tersebut adalah struktur pohon yang paling sederhana.Dalam penelitian ini,kami mengaji penentuan bilangan Ramsey untuk bintang versus beberapa graf tertentu,R(Sn,H)dimana H adalah roda dan bipartite lengkap. Kami membuktikan bahwa bilangan Ramsey untuk bintang dan roda R(S4,W6)=9,R(S6,W8)=14 dan R(Sn,Wm)=3n-2 untuk n> 3 dan m ganjil dengan 3<m<2n-1.Selain itu,kami menentukan bilangan Ramsey untuk bintang dan roda berorde genap, R(Sn,Wm,),untuk m=2n-2,m=2n-8 atau m=2n-6,dan m>2n-1 dengan n>3. Kajian bilangan Ramsey untuk bintang dan graf bipartite lengkap,R(Sn,Kt,m) belum banyak dilakukan.Dalam penelitian ini, kami mengkaji R(Sn,Kt,m)untuk n,t yang kecil dan beberapa m tertentu.Kami menentukan R(Sn,K2,2) untuk n= 6,atau 8,dan R(S6,K,2,m) untuk m = 3,4,6,5,4n -7,atau m=-2+4 k 3i serta R(Sn,K22) untuk n=6 atau 8
Dimensi Partisi Graf Lintasan Korona Graf Bintang Pmʘ K1,n untuk m≥1 dan n≥3
No full textAbstract
Abstrak. Misalkan G dan H adalah suatu graf. Graf hasil Korona G � H
dide�nisikan sebagai graf yang diperoleh dari G dan H dengan mengambil sebuah
salinan graf G dan salinan graf H dan kemudian menghubungkan setiap titik dari
salinan ke-i graf H dengan sebuah titik ke-i dari G. Dalam tugas akhir ini akan
dibahas tentang penentuan dimensi partisi dari graf Pm�K1;n, dimana Pm adalah
graf lintasan dengan orde m dan K1;n adalah graf bintang dengan orde n+1, untuk
m � 1 dan n � 3. Untuk m � 1; n � 3, dimensi partisi dari graf hasil korona
Pm � K1;n, adalah sebagai berikut:
pd(Pm � K1;n) =
8<
:
n; jika m � bn=2c;
n + 1; jika m > bn=2c:
Kata kunci : dimensi partisi, graf Korona, graf lintasan, graf bintan
Penentuan Bilangan Kromatik Fraksional pada Operasi Amalgamasi Graf Lintasan dan Graf Siklus
No full textDalam pewarnaan graf terdapat tiga macam pewarnaan yaitu pewarnaan titik, pewarnaan sisi, dan pewarnaan wilayah. Masalah utama pada pewarnaan titik adalah mencari bilangan kromatik dan bilangan kromatik fraksional. Pewarnaan fraksional titik adalah pemberian lebih dari satu warna pada setiap titik graf sedemikian sehingga setiap dua titik bertetangga memiliki warna yang berbeda. Minimal dari pewarnaan fraksional disebut bilangan kromatik fraksional. Amagamasi titik (G_i,v_0i) adalah graf yang dibentuk dengan mengambil semua graf G_i dimana v_0i=v_0j,???i,j???{1,2,???,k} dan amagamasi sisi (G_i,e_0i) adalah graf yang dibentuk dengan mengambil semua graf G_i dimana e_0i=e_0j,???i,j???{1,2,???,k}.\ud
Dalam tulisan ini dibahas bilangan kromatik dari amalgamasi titik dan sisi graf lintasan terhadap graf siklus. Beberapa bilangan kromatik fraksional yang telah diketahui diantaranya bilangan kromatik fraksional pada graf lintasan adalah ??_f (P_n )=2, dan bilangan kromatik fraksional pada graf siklus adalah ??_f (C_(2(k+1)) )=2 dan ??_f (C_(2k+1) )=2+1/k,???k???N. Sedangkan untuk bilangan kromatik fraksional dari hasil operasi amalgamasi titik pada graf lintasan dan graf siklus adalah ??_f (P_n,V:C_m,V)=??_f (C_m ) dan bilangan kromatik fraksional dari hasil operasi amalgamasi sisi pada graf lintasan dan graf siklus adalah ??_f (P_n,E:C_m,E)=??_f (C_m )
Pelabelan Analytic Mean pada Graf Bayangan dari Graf Bintang K_(1,n) dan Graf Bistar B_(n,n).
No full textMisalkan G(V,E) adalah suatu graf dengan banyaknya titik p dan banyaknya sisi q. Suatu graf G(V,E) dikatakan sebagai graf analytic mean jika terdapat paling sedikit satu pelabelan titik f yang melabeli setiap titik v di V dengan elemen yang berbeda dari 0,1,2,…,p-1, sedemikian sehingga jika e=uv dilabeli dengan pelabelan sisi f^* (e=uv)=|〖[f(u)]〗^2-〖[f(v)]〗^2 |/2 jika |〖[f(u)]〗^2-〖[f(v)]〗^2 | adalah genap dan f^* (e=uv)=(|〖[f(u)]〗^2-〖[f(v)]〗^2 |+1)/2 jika |〖[f(u)]〗^2-〖[f(v)]〗^2 | adalah ganjil, maka tidak ada dua sisi berbeda yang memperoleh label yang sama. Dalam tugas akhir ini dibuktikan bahwa graf bayangan dari graf bintang K_(1,n) dan graf bayangan dari graf bistar B_(n,n) merupaka graf analytic mean
- …
