ADLN - PERPUSTAKAAN UNIVERSITAS AIRLANGGA
BILANGAN KROMATIK DAN BILANGAN
KROMATIK GARIS PADA HASIL KALI KARTESIAN
GRAPH
SKRIPSI
SRISUPATMI
JURUSAN MATEMATIKA
FAKULTAS MATEMATIKAOAN ILMU PENGETAHUAN ALAM
UNIVERSITAS AIRLANGGA
!'lURABAYA
2002
SKRIPSI
BILANGAN KROMATIK DAN BILANGAN KROMATIK GARIS...
SRI SUPATMI
ADLN - PERPUSTAKAAN UNIVERSITAS AIRLANGGA
BILANGAN KROMATIK DAN BlLANGAN
KROMATIK GARIS PADA HASIL KALI KARTESIAN
GRAPH
SKRIPSf Sebllgai Salab Salu Syarol tJntuk Memperoleh
Gelar Sarjana Sa;D' Bidang Maternatika
Pads f akulla. ~fatemalika dan IImu Pengelahuan .\Iam
l iniversitas Airla ngga
Oleh; SRI SlJPATMI
NIM. DS'611550
Tanggal Lulus; 15 Aguslus 2002
l)ist'tujui Oleh :
rembimbing I~
Pembimbing II.
;i·~_~ I
nt. "II'.
.
;\101>. Imam
i
SKRIPSI
t
UO)O,
131 8(H 397
~1.Si
~
/1
.',
I. I' \''J,-/,~
: \1
,.
\
---~-
Bra. Rini ~miati 'IP. HI 287 4QS
BILANGAN KROMATIK DAN BILANGAN KROMATIK GARIS...
SRI SUPATMI
.I
ADLN - PERPUSTAKAAN UNIVERSITAS AIRLANGGA
LEMBAR PENGESAHAN SKRIPSI
JuduI
: BILANGAN KROMATIK DAN BILANGAN KROMATIK GARIS P ADA HASIL KALI KARTESIAN GRAPH
SRISUPATMI
PaJyumn NIM T ongga1IJ",..-'
15 Agudus 2002
DlsetuJui Oleh : Pemblmbinl!
n.
\\/) Y~'--l,J,
\
, :I
prs, ;M~. Imam {JWyo. MSl
Dr., Rlnl Semlall NIP. 131287498
NIP. 131 801 397 Mengetahul :
Keto. Jurusan Matemallka
Dekan Fakulla. MJl'A Universitas AlrlaJl!lga.
!
I
I
I
I ~.~
~.,
Drs. lL A. L~Uer Durhan. MS. NIP. 131 286 709
SKRIPSI
FMlPA Unalr.
.,-
/
;!~.l I
,,
Dr... Moh, Imam Utoyo. M.SI •, NIP. 131lilll .197
BILANGAN KROMATIK DAN BILANGAN KROMATIK GARIS...
SRI SUPATMI
L ADLN - PERPUSTAKAAN UNIVERSITAS AIRLANGGA
Sri Supatmi, 2002, Bilangan kroma!ik da.n Bilangan Kromalik Garis pada Ha!;il Kali Kartesian Graph.Sknf)'}1 im dlba\',ah himbmgal1 Dr:. \101'1 Imam Utuyo J"tSi. dan Dra Rini SemiatL .Tufus.an Maternatika FMIPA Umvcrslias Alrlangga Surabaya.
ABSTRAK
Pcwarnaan paJa graph meilpU!i pewarna;m titiL p~\-"arnaal1 gmis, dan pewumaan totaL Dan pcwarnaan titlk dapat ditemukan bilangan kr(;manK dan dan pcwarnaan garj~ dapat ditcr1tukan bllangan kromat!l.; garis Hasil krdi kane:'lan graph (it dan Ci: dinotasikan dengan (i l '\ G> dan hasi! kah kart..::sian graphtJl.(J:... __ .G"dinota:.!h:.andeoganulxG:X. _.xC". Dcngan ml!ncari hubungan antam bilangal1 kromalik duri Ci; dan U; dengan hlJangan t.:romatik dad G: x G: dJpcmJch bilang-an krornatlk CJ' ;.; (1: YJitu xJ G! x (1:)'- Z(GIl. jlka XfU:) 2: Z{G~) dan bilangan h.rornal!k G,x (;~x x (i-" :vauu x( U 1 '( G~" ,'\; (1,,)'- mak~ ;X(G :,ZIG:), . _ X(O",!;, Dengan mcncari ' dad (j I dan G: dl.:ngan bilang-an hubungun antara bllangan kromatik garis kromatlh. .gatis pacta G: \. G: dlpcrokh bata~ alas nilangan Kro1l13Uk garis OJ .\ (j~ yaitu IAG i x G:) S Z.1Gd ' 11{G~) dan hatas atas birangan kromatik garlS 0.;0.;0:;.;, ,:\G"yailuJ(tl(/,,,G:x .. _xG,J:::zjG:I-X~t1::-4 .1 ZAG,,}.
I\Rta kunci-
pewarnaan uiik, pt:\\arnaan garis hJ!angan kmmalik, hilangan kWlllatik garis. has!! hall karK's!an,
III
I
"
,, SKRIPSI
BILANGAN KROMATIK DAN BILANGAN KROMATIK GARIS...
SRI SUPATMI
ADLN - PERPUSTAKAAN UNIVERSITAS AIRLANGGA
Sri Supatml. 2002. The Chromatic Number nnd Th~ Edge Chromatic Number of Cartl;!sian Pwduct of (,mph, This s(.'ripl IS under ~upcrvisc of DrsJvtoh.lmam (Jtovo fvtSI. and Dm Rini Semtau, Ocpartcment ,of Mathem
ABSTRACT
The co!ourmg on graph {.'(m:-.i~l of vcrh.:'X I,,:OIOUflllg. edge colouring and total colouring, B) \crtcx colourmg can be dctcrmim:d chromatic number and b:v .:dgc colounng: can be dctennmed edge chromatic number. Cartesian product {Jf graph G; and G:: dt.;notcd by G: x Geo and CartesIan product of graph (j,. U:_ ",(in d.::noted by U \; G:<\ :\ G" fh tinding rhe connectIOn betw~n chromatic number or 0 1 and C!~ and \:hromatfl...· Humber of Ci) x n, we obtain dunmatJc number (il x Ci> I.e Xl(JiXG:,I- X{G.), lor fJU I ) ~ x(G:) and chromatic numher ofGlx G:x ,,\ Gn u: Xi (IIX G:\ .X Un) max :X(G;},',(!G:;. __ ZiG,);, Bv tlnding the: connc(;tiOrl hehVC0fi cdg..:; Chmm&tlc nwnbcr or G) and G: and edge <:hmmatic number of C;' x U: we obtain upper bound of edge chromatic numher of G I .\ Ci 2_ i.e Xtl(ll x G:) 5 ZlfGd Z,{GJ and upper bound edge chromatic number of 01 \:lI~'c :\ rh u; Xii G jX (~:,x . ,.x {It,) ::;. X/G:) , X.{ (5..: ) "', .- X,~ G;j I. <
er
-.
I\:c)l\ords vertex colouring. edge cnlouring.. chromat1/.; numocr, cdge chromatic nUI1'.OeL Cartesian product
r
•
)V
SKRIPSI
BILANGAN KROMATIK DAN BILANGAN KROMATIK GARIS...
SRI SUPATMI