rssN 0854-0675 1.7 ArtikelPenelitian:
JurnalSains& Matematika Volumel?Nomor I Jsnuari2009 GRAF SIMETRI LEMAH Susils Hariyanto, Y.D. Sumanto dan l'atliihurohman JurusanMatematikaFMIPA UniversitasDiponegoroSemarang
X de,nganhimpunansemuaaliknya (,Y), himpunan ABSTRAK-Diberikan suarrigraf sederharra graf Xdinotasitan Aut X dm semuaendomorfisme pada semuagarisnya{X). }fimpunan sernuaautomorfisme apakahgraf Xmerupkan graf sime*riataugraf diidentifil€si akan ini, artikel dinsas*an degg1End X. iXt"* punaharnan telrtang gnrp, semigrup, automorfismedan diputukan mengidentifikasi lernah. Untuk simeti terdapatpemetaati/ e Aut X eY(X), r,y titik pada grafsebaiag Jika endomorfismeitalrrm ttasarig jika sed€nikiar hinggc b€rlaku f (x) = y maka graf ,Y dik*akan sabaezigraf verteks-simehi,sedmgkan b€rlakupadasebaranggarisFdaXniaka grafXdik*akn giaf edge'sim€fi danjika b€rlakupadasebarangtitik dansebarangFris maka*seU* graf sin€Ei. Jika pemetaandianrbil danEndX mckagraf simetri yangdiperoleh adalahgraf simdi yangdiperlemahataudisebutgraf sime,ri lffitah. Kda knnei : wtanoifame tbn endsawrftntepde gllqf,
L PENDAHT'LUAN Perkembanganteori graf tidak lepas dari perkembangan bidangbahasanMatematikayang lain" salah satunya adalah aljabar khususnya teori Sup. Teori gnlp digunakan untuk mendefinisikangraf simeri- Kemudian dalam aljabar juga dikenal istilah semignrp dimana persyaratannyalebih ringan daripada grup. Dengan pasyardan yang lebih ringan ini, semigupakan digunakanuntuk mendefinisikan graf simeti lematr- Graf yang didefinisikan denganmsnt€uraftanpndekatariteori semigrup ini akan dibandingkan dengan gmf simeti' Adapun yang menjadi pemrasalahandalam tulisan ini adalah bagaima{tamengidentifikasi graf simehi dan graf simetri lemah dengan pendekaanAljabar. Untuk mengidentiflkasigraf simefi dangraf simetri lemahdigunakankonsep automorftsmedanendomorfismegraf. U. DASAR TEORI adomsrfismedan Untuk menjelaskan endomorfismedibutuhkanbeberapadefinisi berikut: Definisi2.lI2l
MisalkanGcS$ -i 5(himpmanG adalahhimpunanbagiandari S) dan andaikan bahwa suatu relasi : dan operasibiner * terdefinisi di S. Himpunan G adalah suatu grup (goup) terhadapoperasibiner * jika dan hanya jika berlaku kondisi-kondisi sebagai berilnfi: l. G adalah himPunan Yang t€rfitup tertradapoperasibiner *, artinyajika . re G -r € d d a nY e G r € S , ma k a x * y e 6 3 a +Y * . & . 2- Operasi biner t bersifat assosiatif artinya pada Vx,y,z eGVx,Y,e ti S, Mahu x + (y * z )= { x * y )* z r. : , { y * " ): { r* y )+ s . 3. G merniliki elemen identius a{, artinya AeeG,ll r! (i, sedemikian bedaku hingga
,Sra/oH., {D. Sr*n*tto.,Fatkhwolanan:Gr$Simetri Lenah
e
t* 1= 1* X = t-T:i ,
= I * -t * f,, ,
untuksetiapxeGxl*4.
Artikel ?enelitim
4. Setiap elemendari 6 memiliki invers, artinya VaeG,SbeGVr S rj, Ilr ri ff, hingga sedemikian a * b=b* a=la r f' : L i dt = 1. , dengan I merupakanelemen identitas dari G. Definisi LZI2I Misalkan suatuhimpunanH. Diberil€n operasi biner * pada H. Maka H menrpakan semigrupjika dantunyajika memenuhi: 1. Himpman H benifat tertr.dup terhadap operasi biner *, artinya untuk setiry x,/€ f1 makax*yeH. 2. Op€rasibiner * bersifat assosiatifdi dalam H" artinyarmtuksetiap x,y,z e H Maku x*(y*z): (x*y)*2. Definisi2.3 Misalkansuafirgraf sedertuinaXdengan himpunan semua titik-titiknya V{X} dan himpunansemrn garis-garisnyaE{X). Jika dua buah titik \,x, ey{X, adjacer*di dalamX makadituliskan{.rr,tr} e E{X}. Definisi2.4 Misalksn dua buahgraf yaitu X dan Y denganhimprmansemuatitik-titiknya masing: masingV(X) dan V(Y) sera himpunansemua garis-gadsnyamasing-masingE{X) dan F,(Y). Sudu pemetaanf memetakanV(X) ke V(Y), dikabkan sebagai ditrtlis:/ :tt(X) -rF(n adjancy, homomorfismejika f memperfahankan jika berlaku artinya bahwa: {r,,xr} e E(f,)maka {f(xr),f (xr)) e E{Y). Definisi 2.5 Misalksn/ :It(X) +Y(X),
f
homomorfisme,f bijektif dan f-t adalah homomorfisne maka f dikatakan sebagai automorfismedari graf X.
J. Sabw& Mat. Yol. i7. No. l Jamnri 20A9:1-7
IIt PEMBAIIASAN 3.1Graf Simetri Dsfinisi3.Lf Suatugraf X titiktitiknya V(X) verte*s-simetrijika suatu pemetaan f
denganhimpunansemua dikatakan sebagai gmf dan hanya jika terdapat e Aut & sedernikian setiap x,xz eV(X)
hingga rmtuk berlaku/(xr) = r:. Definisi3.l.2 Suatugraf X denganhimpunansemlra garis-garisnyaE(X) dikatakan sebaeni graf edge-simetrijiLa dan hanya jika terdapat f eAvt & sedemikianhingga ur*uk setiap {x1'x2},{y1,yz) e E{X)
berlaku
{f (xr),f (xr)} = ly,vr} Definisi3.l.3 Suatugraf X dikatakangraf simetrijika danhanyajika graf X morupakangraf vertekssimeri dangraf edge-simetri. Dclinisi 3.1.4 Misalkansuafirgraf X denganhimpunan suatu l/(X)dan semua titik-titiknya pemetaaan f :Y(X) -+Y(X). Jika f homomorfismemaka f dikatskan sebagaiendomsrfismedari graf X. Contohgraf simeri: Berilcut ini al
A*ikel Penelitian
eJ merupakan bahwa setiap f homomorfisma c.) IJntuk setiap f e J, hlaku untuk setiap f{x) = x,ye V(X), jika x = y maka {y). Ini menunjukkan bahwa setiap elemen J rnerupakari fimpi injekif. Berlaku pulq rxrtuk setiap y€V(X), terdapd xeV(X), sedemikian hingga {xFy. Ini menunjutftan bahwa setiap funpi surjektif, Jadi elernenJ merupa'kan setiap elemen J merupakan pemetaan biiektit Diperhatikan tabel operasi komposisi fungsiberik* Dibentuk penic;taan yang memetakan I/(X) ke Y(X) adalah:
Sebarang Tabel 3.1.1Pasangan Titik-titik rada Grafx Pasangan / eAutX semustitiksedsmikhn titik sehtlg* pedagnlf X f(x)= v *,! eV{X)
r2 3l ro 3)
i:l ",=[ ",=[: (or z 3\ "'=[.o 3 2 t)
(o | 2 3'i "'=[t o 3 2) (0r 2 3 ) =[r "o z 3 o)
(a t2
1) ,l
"u:[, 30 (o 12 *=[, 0l 2) ( o t2 "'=[, 2l a)
,l
Misalkan J :{cr, az, G3,c+,cs, crnca cs}, dengancr merupakanfunpi identias. Akan dibuktikan bahwa setiap elemen I menrpakanautomorfisma Untuk membu**ikan bahwasetiapelemenJmerupakanautomorfisma, makaharusdibuktikan4 hal yaitu setiapelemen J menryakanpemaaanpadaX setiapelemenJ merupakan homomorfisme, setiap elemen J pemetaanbijektif dan invers dari setiapelemenJ merupakanhomomorfisma a) Jelas bahwa setiap elemen J memetakan himpunanV(X) padadirinya s€ndiri. b.) Untuksetiapf eJ, berlakujika {&y} eE(X), maka {{x), f(y)} eE(x). Ini menunjukkan
0,0 0, I
ca
4,7
c5
4,3
cs
[, I
cl
1,2
c8
1,3
c6
2,2
c2
213
e3
3,3
cs
er
Dari tabel 3.1.1 di aras, dapat ditmjukkan bahwa untuk setiap pasang semua titiktitiknya & ! €Il (X), makaterdapat/ eAut X , sedemikianhingga{x) : y. Jadi graf X menrpakangraf simetrititik.
SusiloH., YD.&manto., Faldnrahmut: Graf SimetriI'emah
Artikel Penelitian
Sebarang Tabel 3.12 Pasangan Graf x Pasengrnsedinr / eAutX garis'garis sedemikisn pdagrnfX sehinggr v,we E(X, .f(v)=w 4a cr a"b
c,
4c
c6
ard
c2
b,b
cr
b ,c
c4
b 'd
ca
or G
cr
c rd
c5
d ,d
cr
Dari tabel 3.1.2 di atas, untuk setiap pasangangaris v,w c E(X), maka t€rdapat /(v) = w. / eAutx, sedemikiansehingga Karena graf X merupak@graf vertekssimetri dan graf edge-simeri maka graf X menpakangrafsimeri. 3.2 Graf Simetri Lcmlh Berikr* ini akan dibahasmengslraigraf simeti lematr Pembahasandimdai dengan memberikandefinisi graf simehi lernah. Detinisi3.l1 Dua buahtitik x dan x' dari suatugraf X dikaaakm similar lernah jika dan hanya jika End X sedemikian hingga terdaprt f,ge dan dinotasikan f(x)= x' dan g(x')=.r, Jf-,
J'
Oefinisi 3.2.2 dari Dua buah garis {r,x'} dan {y'l} jika suatu graf X dikfiakan similar lemah terdapat .f,Ee End X sedemikian hi.gga dan U@),.f(x')l= {.v,.v'} dinotasikan dan {S$),g(y');={x,x'}n
{r't'} -* {y'l}.
J. Sains& Mat. Yol. 17.No- l Jarusi 2009: 1-7
Ilefinisi 3-2.3 Suanr graf X dikatakan sebagai graf verteks-simetrilemah jika dan hanya jika sebarang dua titiknya x,y€V00 berelasi similar lemah.Graf X dil€takan sebagaigraf edp-simeni lernatr jika dan hanya jika sebarangdua garisnya tay),{v,w}€E(X) berelasisimilar lemah. Ilefinisi3.L4 Stuitu graf X dikatakan sebagai graf simetri lemah jika dan hanya jika gnf X menrpakangraf verteks-simetrilemah dan graf edge-simetrilerialt. Contshgraf,simetrilemah: MisalkansuatugrafY denganhimpunan sedruatitik*itiknya v(Y) = {0, 1,2,3} dan himpunansemuagaris-garisnyaE(Y): {q b, e , 4 e ). c
3
2
e
d
b
a Dibentuk p€metaail yang memetakan V{Y) ke V(Y) sepertiberikut :
fttz
a.=l ' [ 0 t 2 3 )' \ 2
3\ I
(0t23)
a.=l
lO 3 )
I
4=01 l;? ) ;l o* =[ MisalkanG: {a1rfl2rarranl ,
Artikel Penelitian
Perhatikantabel operasikomposisifrmgsi pada G berikut:
o
Tabel3.2.1Operasi G gr Q3 crz
ar
a1
g2
c3
Q4
g2
a2
ar
o1
Q3
a3
43
Q4
q
a2
g4
a4
a3
g2
gr
a4
AkandibuktikanbahwaG merupakanAut Y a) JelasbatrwasetiapelemenG memetakan V(Y) ke V(Y). sebarang efus diambil b.) Jika rmtuk setiaP maka e E{n, {r,y} .f eG berlaku {f{x},f (y}l e E(Y). Ini menmjrXrkanbahwasetiapelemenG merupakanhornomofisme. c-) Jika dianbil sebarangy ey(n, maka terdapat x eI/(Y), sedemikianhinggp untuk setiap f eG. Jika f{x)=y, berlaku tliambil sebararrgx,y€V(n, jika r=y, Inr maka /(x)=ftfi. seliaP untuk bahwa menu$ulrkan elemenG merupakanpemetaanbijektif. d.) Dari tabel operrasikomposisi funpi di atas, maka dapat dilihat bahwa invers dari setiapelemenG menrpkan elemer G. Karena setiap elenienG merupakan hotrromorffsmefiaka setiap inversnya juga merupakanhomomorfisme. Dari pembuktian di atas daPat disimpulkanbahwaG menryakanhimpunan automorfismegtaf X ditulis G = Aut Y. Akan diselidiki apakahgraf Y mempakan grafsimeri: Perhatikan setiap elemen G, untuk OleIr(Y\, tidak terdapatf eG sedemikian atau f$)= 0" Jadi ercf Y hingga "f(0)=l bukanmerupakangraf vertks-simeei. KarenaY
bulCInmerupakangraf sernuaverte*s-simeti bukan maka menunrt Definisi 3.1.3, Y merupakangraf simetri. Dipandang kembali graf Y di atas, diperh*ikan pemetaanyangmemetakanV(X) keV(X)berilfft:
h t2 rl 4=[:| ?,;) 4 =l.t 0ra)
r2 3 l t2r) 4=t 4=fi r2r) (o =[z 4=fi 4, 1l 03a)
l2 23
)
6.=fi r) t2 32
,, =[:
,)
t 2 3) 32
t2 l0
(a t 2 =[z 4'
Jl
1 0 3)
(o t2 rl 4' =[z 30r)
')
t2 r ) Ur=[: 020)
12rl
4 -[: 2 s2 ) Misalkan:
b5,bo,4,4,4,4*4r,4r,{r}Per H = {4,4,4,bn berlakujika hatikanbahwa setiap /ell, e E(Y), {r,y} e f(I") maka {f{x),f{y)l Jadi setiap rmtnk sebarang L!€Y(n. pada homomorfisme H menrpakan elemen graf Y. SehinegaH = End Y. Tidak semua elenren H merupakan automorfismepadagraf I buktinya: terdapat Diperhatikan bre H, l,3eY(Y), dan jelas l*30 sedemikian sehingga bz{l) = bt(3'; =1. Sehingga b2 injektif danjelas brrkanmerupakanperne,taan bukan merupakan pemetaan b{ektif, Jadi terdapat elemen H yang bukan merupakan arltomorfismgsehinggal/ * Ats Y.
SusiloH., YD.&'manto.,Fatkhwohnan: GrSSimetri Lemah
Artikel Penelitist
menryakan Jadi setiap elem€Nr H endomorfismetetapi tidak setiap elemen H merupakanautomorfisme. Diperhatikanbahwa: Sebarang Ttbd 3.2-l Pasangari pasrilgon scmm titiktitik graf Y
Titik-titikpada Oraf I €EndY, / eEnd! Sedcmikian Sedenlkian htngg{ hingga
Sebarang Tabel 3.2.2Pasangan Graf Y g €End Y, Patangen /eEndY, semua $edcmikian Sedcmilnen grriq"Fris htryga hingg* grafY 8(s) = r f(r)=s r,s eY(Y) Q,Q
br
b2
arb
b7
b8
f{x)= v
E(y) = x
arc
bE
bfi
br
b2
€trd
b4
b2
0,t
b6
bs
dr€
b3
b7
0r 2
b8
b7
b,b
br
b2
0r 3
bB
b6
b,c
b3
b4
1.1
bl
b2
b,d
bs
b7
1,2
b3
bs
bre
b6
b8
1,3
b1
bn
C,C
br
b3
2,2
bl
b2
crd
bn
bi l
2,3
b3
b7
C t€
b7
bs
3,3
br
bs
d,d
b1
b5
d,e
b3
b3
€r8
br
b4
x,y eY(Y) 0,0
Dari tabel di atas,dryat diketatruibahwa urrtuk setiap pasang semua titik-titiknya rc,I €Y(n, hrdapatpemetaanf ,g e End Y, dm g(y)=x. sedemikianhingga f(x)=y Jadi graf Y merupakan graf verteks-simetri lemah. Diperhatikanbahwa:
J. Saiw & Mat- Yol. i7. No. I Jmuari 2009:I-7
Dari tabel di atas, dapatdilihd bahwa untuk setiap pasang gads r,s e E(n, terdapat -f ,ge End Y, sede,rrikianhingga f(r)= s dan 8(s) = r. Jadi graf Y merupakangraf edge-simetrilemah. Benlasarkan Definisi 3.2.4, dapat disimpulkanbahwagraf Y bukanmerupakan graf simetri tetapi ms,rupakailgraf simetri lennah.
6
Artikcl Penelition
KESIIUPUL\II Dri pembahasm , dapat disimpulkan bahwa: l. Penerapanteori gup pada suatu graf menghasilkan graf ysng dinamakan sebrigaigraf simetri 2. Penenpanteori semigruppada suafirgraf mengbasilkangraf simeti lemah. I}AFTARPUSTAKA tll Fan, Suohai. 2003. Weakly Symmebic Graphs and Their EndomorfismMonoids. YunnanUuiveniry and SorrthChim Normal University South East Asian Mathematical Society. t2l Gilbert, Jimmie and Linda Gilbert. 1984. Elemerrts of Mod€rn Algeba PWS Publishers. t3l Harery, Frank l%9. Graph Theory. Addison-WesleyR$lishing Company. [4] Hersteifi,IN. 1975.Topicsin Alpbia Xerox Ccrporation, [5] Lallemerr, Gerard" 1979. Semigroupsand Combiantcnial Applications- New York :JohnWilley&Sons. [6] Sepuuq Theresia MH Tirta" 1992. Graf Pengantar.Surabaya: UniversityPressIKIP Surabaya [{ Silabarl Panhr. 1995. Teori Himpunan. Jakarta: PenerbitErlangga ISlhttp://mathworld.wolfram.corn/sesrch/?Slery =symmetriql-eraph&>F t 3&y= I 0 . (Diaksestmggal3l Januari2008)
&lailo E, YD-Swtsrto., Fatklnnolunan:Gr$simetri lamah
