186,438 research outputs found
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
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
ANALISIS PEWARNAAN r-DINAMIS PADA GRAF-GRAF KHUSUS
No full textPewarnaan graf merupakan salah satu topik kajian pada teori graf. Pe-
warnaan r-dinamis merupakan pengembangan dari pewarnaan k-warna dinamis
yang diperkenalkan oleh Montgomery pada tahun 2002. Pewarnaan k-warna di-
namis pada graf G merupakan pewarnaan titik pada graf G sebanyak k warna
sedemikian hingga setiap titik berderajat minimum dua pada G setidaknya memi-
liki dua warna berbeda dengan titik-titik ketetanggaannya. Nilai k terkecil dimana
graf G memiliki pewarnaan k-warna dinamis disebut sebagai bilangan kromatik
dinamis, disimbolkan dengan Âd(G).
Graf-graf khusus yang digunakan dalam penelitian ini adalah graf Prisma,
graf Circulant, graf Lintasan, graf Sikel, graf Roda, graf Bintang, graf Tangga,
dan graf Friendship. Metode yang digunakan dalam penelitian ini adalah metode
deduktif aksiomatik, yang diawali dengan istilah yang tidak dide¯nisikan dan
istilah yang dide¯nisikan, kemudian dapat disusun pernyataan pangkal yang biasa
disebut aksioma atau postulat. Setelah itu, disusun teorema-teorema ataupun
de¯nisi-de¯nisi. Adapun teorema yang disusun harus dibuktikan melalui proses
deduktif sehingga kebenarannya berlaku secara umum dalam ruang lingkupnya.
Hasil penelitian ini berupa teorema baru mengenai pewarnaan titik r-dinamis
dan pewarnaan sisi r-dinamis pada graf-graf khusus. Teorema yang dihasilkan
adalah:
a. Bilangan kromatik r-dinamis pewarnaan titik r-dinamis pada graf Prisma,
Pn, dapat ditulis sebagai berikut:
Â(Pn) =
(
2; untuk n genap
3; untuk n ganjil
Âd(Pn) =
(
3; untuk n = 3k; k 2 N
4; untuk n lainnya
Âr¸3(Pn) =
8>><
>>:
4; untuk n = 4k; k 2 N
6; untuk n = 3; 7; 11
5; untuk n lainnya
ix
yang telah dibuktikan pada Teorema 4.1.1;
b. Misalkan G merupakan graf Circulant, yakni Cn(1; n
2 ), dimana n ¸ 4 dan
n genap. Bilangan kromatik dinamis pewarnaan titik r-dinamis pada graf
Circulant, Cn(1; n
2 ), dapat ditulis sebagai berikut:
Â(Cn(1;
n
2
)) =
8>><
>>:
4; untuk n = 4
2; untuk n = 4k + 2; k 2 N
3; untuk n = 4k + 4; k 2 N
Âd(Cn(1;
n
2
)) = 4
Âr¸3(Cn(1;
n
2
)) =
8>>>><
>>>>:
n; untuk n = 4; 6; 8
4; untuk n = 8k + 4; k 2 N
5; untuk n = 8k + 6; k 2 N
6; untuk n lainnya
yang telah dibuktikan melalui pembuktian Teorema 4.1.2;
c. Misalkan G merupakan graf Circulant, yakni Cn(1; 2), dimana n ¸ 5. Bi-
langan kromatik dinamis pewarnaan titik r-dinamis pada graf Circulant,
Cn(1; 2), dapat ditulis sebagai berikut:
Â(Cn(1; 2)) = Â2(Cn(1; 2)) =
8>><
>>:
5; untuk n = 5
3; untuk n = 3k; k 2 A
4; untuk n lainnya
Â3(Cn(1; 2)) =
(
4; untuk n = 4k; k 2 A
5; untuk n lainnya
Âr¸4(Cn(1; 2)) =
8>>>><
>>>>:
n; untuk 5 · n · 9
5; untuk n = 5k + 5; k 2 A
6; untuk n = 5k + 6; 5k + 7; k 2 A
7; untuk n = 5k + 8; 5k + 9; k 2 A
yang telah dibuktikan pada Teorema ??;
d. Jika G merupakan graf hasil operasi join antara Pn dan Cm, dinotasikan
dengan Pn + Cm maka bilangan kromatik r-dinamis graf G adalah sebagai
x
berikut:
Â4(Pn + Cm) =
(
5; untuk m = 3k; k 2 A
6; untuk m lainnya
Â5(Pn + Cm) =
8>><
>>:
6; untuk m = 3
8; untuk m = 5
7; untuk m lainnya
Âr¸6(Pn+Cm) =
(
r + m ¡ 2; untuk 3 · m · r ¡ 2;m ¸ r ¡ 1; n ¸ m ¡ 1
2r ¡ 3; untuk m lainnya; n ¸ r ¡ 1
yang telah dibuktikan pada Teorema 4.1.4;
e. Misalkan G merupakan graf hasil operasi korona antara Pn dan Cm, yaitu
Cm ¯ Pn. Jika n ¸ 2, m ¸ 3, and r ¸ 4 maka bilangan kromatik r-dinamis
graf G adalah sebagai berikut:
Âr¸4(Cm ¯ Pn) =
8>>>><
>>>>:
4; untuk m 6= 5; n = 1;
5; untuk n = 2 dan m = 5; n = 1;
n + 3; untuk 3 · n · r ¡ 3;
r + 1; untuk n lainnya;
yang telah dibuktikan pada Teorema 4.1.5;
f. Misalkan G merupakan graf hasil operasi korona antara Pn dan Cm, yaitu
Pn ¯ Cm. Jika n ¸ 2, m ¸ 3, dan r ¸ 6 maka bilangan kromatik r-dinamis
graf G adalah sebagai berikut:
Âr¸6(Pn ¯ Cm) =
(
m + 3; untuk 3 · m · r ¡ 3;
r + 1; untuk m lainnya;
yang telah dibuktikan pada Teorema 4.1.6;
g. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Lintasan,
Pn, dapat ditulis sebagai berikut:
¸(Pn) = 2; n ¸ 2
¸2(Pn) = ¸r(Pn) = 3; n ¸ 2; r ¸ 2
yang telah dibuktikan pada Teorema 4.2.1;
h. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Sikel, Cn; n ¸
3, dapat ditulis sebagai berikut:
¸(Cn) =
(
2; untuk n genap
3; untuk n ganjil
¸r¸2(Cn) =
8>><
>>:
3; untuk n = 3k; k 2 N
4; untuk n = 3k + 1; k 2 N
5; untuk n = 3k + 2; k 2 N
yang telah dibuktikan pada Teorema 4.2.2;
i. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Bintang,
Sn; n ¸ 3, dapat ditulis sebagai berikut:
¸r¸1(Sn) = n
yang telah dibuktikan pada Teorema 4.2.3;
j. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Roda, Wn; n ¸
5, dapat ditulis sebagai berikut:
¸r·n¡1(Wn) = n; untuk 1 · r · n ¡ 1
¸r¸n(Wn) =
8>><
>>:
10; untuk n = 5; r ¸ n
n + 3; untuk untukn = 3k + 3; k 2 N; r ¸ n
n + 4; untuk n lainnya; r ¸ n
yang telah dibuktikan pada Teorema 4.2.4;
k. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Prisma, Pn,
dapat ditulis sebagai berikut:
¸(Pn) = ¸2(Pn) =
(
2; untuk n genap
3; untuk n ganjil
¸3(Pn) =
(
4; untuk n = 3
5; untuk n lainnya
¸r¸4(Pn) =
8>>>><
>>>>:
9; untuk n = 3
6; untuk n = 4k; k 2 N
8; untuk n = 5; 6; 4k + 7; k 2 N
7; untuk n lainnya
yang telah dibuktikan pada Teorema 4.2.5;
l. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Tangga,
Ln; n ¸ 3, adalah:
¸(Ln) = ¸2(Ln) = 3
¸3(Ln) = 5
¸4(Ln) = ¸r(Ln) = 6
yang telah dibuktikan pada Teorema 4.2.6;
h. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Sikel, Cn; n ¸
3, dapat ditulis sebagai berikut:
¸(Cn) =
(
2; untuk n genap
3; untuk n ganjil
¸r¸2(Cn) =
8>><
>>:
3; untuk n = 3k; k 2 N
4; untuk n = 3k + 1; k 2 N
5; untuk n = 3k + 2; k 2 N
yang telah dibuktikan pada Teorema 4.2.2;
m. Bilangan kromatik dinamis pewarnaan sisi r-dinamis pada graf Friendship,
Fn, adalah:
¸r·2n¡1(Fn) = 2n
¸r¸2n(Fn) = 2n + 1
yang telah dibuktikan pada Teorema 4.2.7;
n. Misalkan G adalah graf hasil operasi amalgamasi dari graf Lintasan Pn,
dinotasikan G = amal(Pn; v;m); n ¸ 2;m ¸ 3, maka bilangan kromatik sisi
r-dinamis pada graf G adalah:
¸(amal(Pn; v;m)) = ¸2(amal(Pn; v;m)) = m
¸r¸3(amal(Pn; v;m)) = m + 1
yang telah dibuktikan pada Teorema 4.2.8;
o. Jika T adalah graf Pohon, maka berlaku:
Â(Cn + T) = Â2(Cn + T) = Â3(Cn + T) =
(
4; untuk n genap
5; untuk n ganjil
yang telah dibuktikan pada Teorema 4.3.1;
p. Misalkan G adalah graf yang merupakan hasil operasi join graf G1 dan G2,
maka pada graf G berlaku pewarnaan titik r-dinamis sebagai berikut:
Â(G1 + G2) = Â2(G1 + G2) = ¢ ¢ ¢ = Âr(G1 + G2) = Â(G1) + Â(G2)
dimana r = minfjc(N(v(G1)))j; jc(N(v(G2)))jg+minfÂG1 ; ÂG2g, yang telah
dibuktikan pada Teorema 4.3.2;
q. Jika G merupakan graf Pohon maka ¸r(G) = minfr; maxfd(u)+d(v)¡2gg+
1, dimana r ¸ maxfd(u)+d(v)¡2gg, yang telah dibuktikan pada Teorema
4.3.3.
Dari penelitian juga terdapat dugaan mengenai pewarnaan titik r-dinamis
pada graf Pn + Cm sebagaimana tertulis pada Dugaan 4.3.1:
Misalkan G adalah graf yang merupakan hasil operasi join graf G1 dan G2, maka
Âr(G1 + G2) ¸ Âr(G1) + Âr(G2)
ANALISA NILAI KROMATIK PEWARNAAN TOTAL r−DINAMIS PADA OPERASI COMB PRODUCT DARI GRAF-GRAF KHUSUS
No full textTeori graf pertama kali diperkenalkan oleh seorang matematikawan berkebangsaan Swiss bernama Leonhard Euler pada tahun 1736. Salah satu teori yang dikembangkan dalam teori graf adalah pewarnaan graf (coloring). Terdapat tiga macam pewarnaan dalam teori graf, yaitu pewarnaan titik (vertex coloring), pewarnaan sisi (edge coloring), dan pewarnaan wilayah (region coloring). Selanjutnya, H. Lai dan B. Montgomery memperkenalkan konsep pewarnaan dinamis danmenuangkannyadalamsebuahartikelyangberjudulDynamicColoringofGraphs. Dari penelitian diatas mulai dikembangkan lagi tentang pewarnaan dinamis pada graf. Terdapat tiga macam pewarnaan r−dinamis dalam teori graf yaitu pewarnaan titik r−dinamis, pewarnaan sisi r−dinamis, dan pewarnaan total r−dinamis. Pewarnaan total r-dinamis pada graf G adalah pemetaan c : V (G)∪E(G) ke himpunan warna sedemikian hingga memenuhi kondisi∀v ∈ V (G),|c(N(u))|≥ min{r,d(u) + N(u)} dan ∀e = uv ∈ E(G),|c(N(e))| ≥ min{r,d(u)+ d(v)}. Bilangan kromatik dari pewarnaan total r-dinamis adalah banyaknya nilai k minimum yang dibutuhkan untuk mewarnai graf G, dan dinotasikan dengan χ”r(G). Pewarnaan total r-dinamis dapat diterapkan pada graf khusus maupun graf operasi. Operasi yang digunakan pada penelitian ini yaitu operasi Comb Product. Operasi comb product dari graf L dan H dinotasikan L ◃ H adalah operasi graf yang diperoleh dengan mengambil salinan dari graf L dan |L| salinan dari H dan merekatkan salinan ke-i dari graf H di titik cangkok o pada titik ke-i dari graf L. Adapun graf yang digunakan dalam penelitian ini yaitu graf Pn ◃ Wd3,3, Ln ◃ Pm, Pn ◃F1,3, Ln ◃S3, Pn ◃H2,2, TLn ◃C3 dan Sn ◃C3. Penelitian ini menggunakan metode deduktif dan pendeteksian pola. Tujuan penelitianiniadalahmenentukanhimpunantitikdansisipadagrafoperasidanbilangan kromatikpewarnaantotalr-dinamispadagrafPn◃Wd3,3,Ln◃Pm,Pn◃F1,3,Ln◃S3, Pn ◃ H2,2, TLn ◃ C3 dan Sn ◃ C3 sehingga dihasilkan 7 teorema baru, diantaranya adalah Penelitian ini dikategorikan sebagai penelitian eksploratif dan menggunakan metode pendeteksian pola. Tujuan penelitian ini adalah menentukan nilai kromatik total dari beberapa graf khusus dan dihasilkan 7 teorema baru, diantaranya adalah: 1. Teorema4.1Misalkan G adalah graf Pn ◃Wd3,3 dimana n ≥ 3 dan titik z sebagai titik cangkok pada graf Wd3,3. Bilangan kromatik pewarnaan total r-dinamis pada graf G adalah
χ”r(G) =
9,untuk 1 ≤ r ≤ 7 10,untuk r = 8 12,untuk 9 ≤ r ≤ 10 r + 2,untuk 11 ≤ r ≤ 13 16,untuk 14 ≤ r ≤ 15 17,untuk r ≥ 16 2. Teorema 4.2 Misalkan G adalah graf Ln ◃ Pm dimana n ≥ 2, m ≥ 3 dan titik y1 sebagai titik cangkok pada graf Pm. Bilangan kromatik pewarnaan total r-dinamis pada graf G adalah
χ”r(G) =
5,untuk 1 ≤ r ≤ 3 8,untuk r = 4
10,untuk r = 5 13,untuk 6 ≤ r ≤ 7 15,untuk r ≥ 8
3. Teorema 4.3 Misalkan G adalah graf Pn ◃F1,3 dimana n ≥ 3 dan titik y3 sebagai titikcangkokpadagrafF1,3. Bilangankromatikpewarnaantotalr-dinamispadagraf G adalah
χ”r(G) =
5,untuk 1 ≤ r ≤ 3 6,untuk r = 4
8,untuk r = 5 10,untuk 6 ≤ r ≤ 7 11,untuk r ≥ 8 4. Teorema 4.4 Misalkan G adalah graf Ln ◃ S3 dimana n ≥ 2 dan titik z3 sebagai titik cangkok pada graf S3. Bilangan kromatik pewarnaan total r-dinamis pada graf G adalah
χ”r(G) =
5,untuk 1 ≤ r ≤ 3 6,untuk r = 4
8,untuk r = 5
10,untuk r = 6 12,untuk r = 7 dan r ≥ 8 5. Teorema 4.5 Misalkan G adalah graf TLn ◃C3 dimana n ≥ 3 dan titik y3 sebagai titik cangkok pada graf C3. Bilangan kromatik pewarnaan total r-dinamis pada graf G adalah
χ”r(G) =
7,untuk 1 ≤ r ≤ 4 8,untuk 5 ≤ r ≤ 6 9,untuk r = 7 r + 3,untuk 8 ≤ r ≤ 9 15,untuk r = 10
18,untuk r = 11 20,untuk r ≥ 12 6. Teorema 4.6 Misalkan G adalah graf Pn ◃H2,2 dimana n ≥ 3 dan titik y4 sebagai
ix
titik cangkok pada graf H2,2. Bilangan kromatik pewarnaan total r-dinamis pada graf G adalah
χ”r(G) =
5,untuk 1 ≤ r ≤ 3 8,untuk r = 4 9,untuk 5 ≤ r ≤ 7 10,untuk r ≥ 8 7. Teorema 4.7 Misalkan G adalah graf Sn ◃ C3 dimana n ≥ 4 dan titik z3 sebagai titik cangkok pada graf C3. Bilangan kromatik pewarnaan total r-dinamis pada graf G adalah
χ”r(G) =
n + 3,untuk 1 ≤ r ≤ n + 2 n + 4,untuk r = n + 3 n + 6,untuk n + 4 ≤ r ≤ n + 5 r + 1,untuk n + 6 ≤ r ≤ 2n + 3 2n + 5,untuk r ≥ 2n +
Faktorisasi Graf beraturan-r dengan order genap
No full textINDONESIA:
Salah satu permasalahan dalam teori graf adalah faktorisasi pada graf G. Faktorisasi adalah penjumlahan (union) sisi dari faktor-faktor graf G. Penelitian ini bertujuan untuk menentukan pola umum faktorisasi graf beraturan-r (r≥2) dengan order genap yang memiliki faktor-1, faktorisasi graf beraturan-r yang memiliki faktor-2 dan faktor-3. Permasalahan yang dikaji dibatasi pada faktorisasi graf beraturan-r yang memiliki faktor-1, faktor-2 dan faktor-3. Sedangkan metode dalam skripsi ini adalah metode penelitian pustaka (library research).
Langkah-langkah menentukan pola faktorisasi graf beraturan-r adalah sebagai berikut: (1) Menggambar beberapa graf beraturan-r dengan order genap(2n)untuk n≥2 sampai dengan order sepuluh,(2) Menentukan faktor pada graf beraturan-r, dan (3) Menentukan pola faktorisasi pada graf beraturan-r. Kemudian merumuskan teorema yang dilengkapi dengan bukti-bukti.
Berdasarkan hasil pembahasan dapat diperoleh pola jumlah faktor-faktor pada graf beraturan-r sebagai berikut: a) Graf beraturan-r (r≥2) dimana 2≤r≤2n-1 dengan order genap memiliki faktor-1 sebanyak r. b) Graf beraturan-r dimana 2≤r≤2n-2 dengan syarat rΞ0(mod 2) dan order genap memiliki faktor-2 sebanyak 1/2r. c) Graf beraturan-r dimana 3≤r≤2n-1, n=2+3p, untuk p≥0, 3≤r≤2n-3, n=3+3p untuk p≥0 dan 3≤r≤2n-2, n=0+3p untuk p≥0 dengan syarat rΞ0(mod 3), dan order genap memiliki faktor-3 sebanyak 1/3r, untuk n≥2 dan n Є .
Pembahasan skripsi ini penulis hanya membahas fakorisasi graf beraturan-r dengan order genap yang memiliki faktor-1, faktor-2 dan faktor-3. Oleh karena itu diharapkan pada peneliti berikutnya dapat dikembangkan sampai faktor ke-n (n Є ) dan atau menggunakan order ganjil yang memiliki faktor-n (n Є )
ENGLISH:
One problem of graph theory is factorization at graph G. Factorization is edge union from factors of graph G. This research aim at determine general pattern of factorization of r-regular graph ... with even order which has 1-factor and r-regular graph which has 2-factor and 3-factor. The problems studied were limited at factorization of r-regular graph which have 1-factor, 2-factor and 3-factor. While the thesis method is library research method.
The steps to determine factorization pattern of r-regular graph are, (1) Draw some r-regular graphs with even order (2n) for ... up to ten order, (2) Determine the factor at r-regular graph, and (3) Determine factorization pattern in r-regular graph. Then the researcher formulates the theorem and proof it.
Based on the result of the discussion, the researcher obtained some patterns of factors sum at r-regular graph, are: a) r-Regular graph ... with ... 1-factor equals to the amount of r and even order which has ... 1-factor equals to the amount of r. b) r-Regular graph where ... with ... and even order which has 2-factor equals to the amount of 1 r. c) r-Regular graph where ...,for ... for ... and ... for ... with ... and even order which has 3-factor equals to the amount of 1 r , for ... and ...
This thesis writer only study factorization of graph regular-r with even order which have 1-factor, 2-factor and 3-factor. Therefore expected at the next researcher can be developed at n-factors and or applies odd order which have n- factors
ANALISA PEWARNAAN TOTAL r-DINAMIS PADA GRAF KHUSUS DAN GRAF HASIL OPERASI
No full textPewarnaan titik r-dinamis dikembangkan menjadi pewarnaan sisi r-dinamis
yang disesuaikan dengan de¯nisi atau syarat pada pewarnaan sisi r-dinamis pada
graf. Selain itu, pewarnaan r-dinamis juga dikembangkan menjadi pewarnaan
total r-dinamis pada graf. Pewarnaan total r-dinamis merupakan pewarnaan pada
graf yang mewarnai titik dan sisi pada suatu graf. Pewarnaan total r-dinamis
merupakan kajian baru dalam teori graf. Pada penelitian ini menghasilkan suatu
de¯nisi baru tentang pewarnaan total r-dinamis. Pewarnaan total r-dinamis
pada suatu graf dide¯nisikan sebagai pemetaan fungsi ci dari himpunan titik
dan sisi (V (G) [ E(G)) ke himpunan warna sedemikian hingga untuk setiap
titik v 2 V (G) maka jc(N(v))j ¸ min[r; d(v) + jN(v)j] dan untuk setiap sisi
e = uv 2 E(G), jc(N(e))j ¸ min[r; d(v) + d(u)]. Penggunaan k-warna dinamis
yang paling minimal disebut dengan bilangan kromatik total r-dinamis yang
dinotasikan dengan Â00(G)
NILAI KROMATIK PEWARNAAN SISI r-DINAMIS PADA GRAF EKSPONENSIAL DAN GRAF OPERASI
No full textTeori graf merupakan salah satu topik matematika yang banyak dikaji oleh
peneliti, salah satu topik dalam teori graf yang sering diteliti yaitu pewarnaan
graf. Pewarnaan graf digolongkan menjadi pewarnaan titk (vertex coloring), pe-
warnaan sisi (edge coloring), dan pewarnaan wilayah (region coloring). Pada
perkembangannya pewarnaan graf telah mengalami variasi, diantaranya yaitu pe-
warnaan dinamis yang dikembangkan oleh Bruce Montgomery pada tahun 2001.
Pewarnaan k-warna dinamis pada graf G merupakan pewarnaan titik pada graf G
sebanyak k warna sedemikian hingga setiap titik berderajat minimum dua pada
G memiliki dua warna berbeda dengan titik-titik ketetanggaannya. Nilai k warna
pada graf G yang memiliki k-warna dinamis disebut dengan bilangan kromatik
dinamis, disimbolkan dengan Âd(G). Pewarnaan titik r-dinamis kemudian digene-
ralisasiakan menjadi pewarnaan titik r-dinamis.
Pewarnaan titik r-dinamis pada akhirnya mengalami perkembangan yaitu
pewarnaan sisi r-dinamis yang disesuaikan dengan kondisi/syarat pada pewar-
naan sisi graf. Pewarnaan sisi r-dinamis pada suatu graf G dide¯nisikan seba-
gai pemetaan c dari E(G) ke himpunan warna sedemikian hingga jc(N(e))j ¸
minfr; d(u) + d(v) ¡ 2g untuk setiap e = uv 2 E(G), dimana N(e) merupakan
himpunan sisi yang bersisian dengan sisi e, dan d(u) merupakan derajat dari titik
u. Penggunaan k-warna dinamis yang paling minimal disebut dengan bilangan
kromatik sisi r dinamis yang dinotasikan dengan ¸r(G).
Pewarnaan sisi r-dinamis dapat diterapkan pada hasil operasi dari graf
beberapa graf khusus, misalnya seperti hasil operasi graf cycle, windmill, star,
stecked book, dan triangular book. Sedangkan operasi graf adalah suatu metode
yang digunakan untuk memproleh graf baru dengan cara mengombinasikan dua
graf atau lebih
ein ander Reyen Lied, Vonn dem Mythart, im thon, Waer ich der Mey, waer etc
No full text[Joerg Graf]. ein ander hüpsch Reyenlied vonn der frouw Klapperin, in dess Mytharts thon / [J. R.]. ein ander Reyen Lied, Vonn dem Mythart, im thon, Waer ich der Mey, waer etc.Impressum: Höchstwahrscheinlich in Bern von der Familie Apiarius gedruckt (Mathias Apiarius 1537-1554, Samuel Apiarius 1554-1564, Siegfried Apiarius 1560-1565), jedoch keinem bestimmten Drucker zuzuordnenLiedincipit: Was kan ich bessers singen, merckend ein kurtzen bscheyd, das groesser nutz moeg bringenZusammengebunden mit 84 weiteren Werke
PEWARNAAN SISI r-DINAMIS PADA GRAF KHUSUS SERTA GRAF OPERASI SAKEL DAN GENERALISASINYA
No full textTeori graf berkembang semakin luas. Terdapat banyak topik yang menarik
untuk dikaji salah satunya adalah pewarnaan. Pewarnaan graf digolongkan menjadi
pewarnaan titik (vertex coloring), pewarnaan sisi (edge coloring), dan pewarnaan
wilayah (region coloring). Pada pewarnaan graf, tidak boleh ada warna yang sama
saling bertetangga. Dalam hal ini pewarnaan dengan k-warna yang paling mini-
mum pada suatu graf disebut sebagai bilangan kromatik yaang dinotasikan dengan
(G). Pada pewarnaan graf, tidak boleh ada warna yang sama saling bertetangga.
Pengembangan dari k-warna dikembangkan oleh Hong-Jian Lai dan Bruce Mont-
gomory pada tahun 2002 yang memperkenalkan konsep pewarnaan dinamis. Pe-
warnaan k- warna dinamis pada graf G merupakan pewarnaan titik pada graf G
sebanyak k warna sedemikian hingga setiap titik berderajat minimum dua pada graf
G setidaknya memiliki dua warna berbeda dengan titik - titik ketetanggaannya. Ni-
lai k terkecil dimana graf G memiliki pewarnaan k-warna dinamis disebut sebagai
bilangan kromatik dinamis, dinotasikan dengan (G), kemudian digeneralisasikan
menjadi pewarnaan titik r-dinamis.
Perwarnaan titik r-dinamis kemudian mengalami perkembangan yaitu pe-
warnaan sisi r-dinamis yang disesuaikan dengan kondisi atau syarat pada pewar-
naan sisi graf. Pewarnaan sisi r-dinamis pada suatu graf G didefinisikan seba-
gai pemetaan c dari E(G) ke himpunan warna sedemikian sehingga jC(N(e))j
minr; d(u) + d(v) 2 untuk setiap e = uv 2 E(G), dimana N(e) merupakan
himpunan sisi yang bersisian dengan sisi e, dan d(u) merupakan derajat dari titik u.
Penggunakan k-warna dinamis yang paling minimal disebut dengan bilangan kro-
matik sisi r-dinamis yang dinotasikan dengan r(G).
Pewarnaan sisi r-dinamis dapat diterapkan pada graf khusus maupun graf
operasi. Operasi graf adalah metode yang digunakan untuk memperoleh graf baru
dengan cara mengkombinasikan dua atau lebih. Adapun graf yang digunakan dalam
penelitian ini yaitu TLn; TCLn;BTn; shack(H2;2; v; n); shack(Pr4; e; n); shack
(BTn; v; n); shack(W6; v; n), dan shack(Wd3;3; v; n)
PEWARNAAN SIMPUL r-DINAMIS PADA GRAF TERATAI T_n
No full textG=(V,E) merupakan pasangan dari himpunan V tak kosong dan berhingga yang dinamakan sebagai himpunan simpul dan himpunan E yang seluruh elemennya merupakan subhimpunan dari dua elemen dari V atau bisa disebut juga dengan busur. Pewarnaan dinamis didefinisikan sebagai pewarnaan tepat sedemikian sehingga untuk setiap simpul berderajat minimal dua mempunyai lebih dari satu warna yang berbeda pada setiap simpul-simpul tetangga. Pewarnaan r-dinamis merupakan bentuk perumuman dari pewarnaan dinamis. Misalkan r merupakan bilangan bulat positif. Pewarnaan r-dinamis dengan k-warna pada suatu graf G adalah pewarnaan tepat simpul dengan k-warna pada graf G sedemikian sehingga untuk setiap simpul v maka himpunan tetangganya akan menggunakan warna setidaknya min{r,deg(v)}. nilai minimal k untuk graf G pada pewarnaan r-dinamis dengan k-warna disebut dengan bilangan kromatik r-dinamis pada graf G, dan dapat dinotasikan dengan χ_r (G). Graf teratai T_n merupakan hasil dari operasi korona antara graf lengkap K_1 dengan graf bintang S_n (K_1⊙S_n) yang kemudian n-1 simpul pada graf bintang digantikan menjadi n-1 simpul baru dan terhubung pada simpul pusat pada graf bintang. Sehingga, graf teratai akan memiliki 2n+2 simpul dan 2n+1 busur. Dari hasil konstruksi dengan menggunakan definisi pewarnaan r-dinamis pada graf teratai T_n, diperoleh bilangan kromatik graf teratai T_n adalah χ_r (T_n )=3, untuk r=1 dan 2, serta χ_r (T_n )=min(r,2n+1)+1 untuk r≥
- …
