LIPATAN GRAF DAN KAITANNYA DENGAN MATRIKS INSIDENSI PADA BEBERAPA GRAF Septian Adhi Pratama1, Lucia Ratnasari2, Widowati3 1,2,3
Jurusan Matematika FSM Universitas Diponegoro Jl. Prof. H. Soedarto, S.H. Tembalang Semarang
[email protected] [email protected]
ABSTRACT. Let and be graphs with vertex-set and and edge-set and . Then is called a graph map, if for each vertex and for each edge A graph map is called folding graph if and only if f maps verices to vertices and edges to edges, i.e., for each and for each . On this paper shown that what is there a folding graph into itself ( in tree graph, complete graph, bipartite graph, complete bipartite graph, cycle graph and multiple graph contains no cycle. For graphs which have a non-trivial folding, limit folding from the graphs is a edge, and graphs which have trivial folding, limit folding from the graphs is a vertex, in this paper also know the relation between folding graph with incidence matrices. Keyword :
Graph map, dim(e), folding graph , non-trivial folding, trivial folding and incidence matrices.
I. PENDAHULUAN Salah satu topik dalam teori graf yang akan dibahas adalah lipatan graf. Lipatan graf sendiri pertama kali diperkenalkan oleh E. El-Kholy dan A. ElEsawy (2005), yang berasal dari Universitas Tanta, Mesir melalui sebuah jurnal,[4]. Terhitung cukup baru, perkembangan lipatan graf sendiri sampai saat ini cukup luas, salah satu buktinya E. El-Kholy, El-Said R. Lashin, dan Salama N. Daoud di Universitas Tanta memperkenalkan operasi baru pada lipatan graf melalui jurnal [5] yang telah terbit tahun 2012, selain itu lipatan graf juga dikembangkan oleh E. H. Hamouda dan Nada S. melalui sebuah jurnal [7]. Jurnal [7] tersebut membahas mengenai lipatan graf dan bilangan lipatan graf.
II. HASIL DAN PEMBAHASAN Definition 2.1. [4] Misalkan fungsi kontinyu. Fungsi (i) untuk setiap titik
dan
adalah graf dan
adalah
disebut pemetaan graf jika: adalah titik di
,
(ii) untuk setiap garis Contoh 2.1 Diberikan
graf
dan
dengan
himpunan dan
garis
} seperti Gambar 2.1.
V3
u2
V2
u1
Gambar 2.1 Graf Pemetaan
masing-masing
himpunan
},
V1
titik
dan graf
didefinisikan sebagai berikut: .
Diperoleh
sebagai berikut. V3
u2
f
V1
Gambar 2.2 Pemetaan graf
V2
u1
ke graf
dan menghasilkan
Dari Contoh 2.1 dapat dilihat bahwa untuk setiap titik
adalah
titik di
, yaitu
dan untuk setiap garis Oleh
karena
itu
merupakan
pemetaan graf. Definisi 2.2 [4] Suatu pemetaan graf hanya jika
disebut lipatan graf jika dan
memetakan titik ke titik dan garis ke garis yaitu untuk setiap dan untuk setiap
Contoh 2.2 Diberikan graf sikel himpunan garis seperti Gambar 2.3.
dengan himpunan titik
dan )}
V1
V2
V6
V5
V3
V4 C6
Gambar 2.3 Graf sikel Berikut ini diberikan pemetaan graf pada
. Misal
adalah pemetaan
graf yang didefinisikan sebagai berikut:
. Adapun ilustrasi gambarnya sebagai berikut. V1 V1
V6
V2 V2
f
V3
V5
V3
V4 V4
Gambar 2.4 Pemetaan graf
ke graf
dan menghasilkan
Dari Contoh 2.2 dapat disimpulkan pemetaan graf
memetakan dari
titik ke titik dan garis ke garis, yaitu untuk setiap untuk setiap lipatan graf pada graf
dan sedemikian sehingga diperoleh
.
Proposisi 2.3 [4] Setiap graf tree T dapat dilipat ke dirinya sendiri dengan suatu barisan dari lipatan graf menjadi suatu garis. Teorema 2.4 Jika
adalah graf lengkap maka tidak ada lipatan graf non-trivial
yang dapat didefinisikan untuk Teorema 2.5 Setiap graf bipartit
. dapat dilipat.
Teorema 2.6 Setiap graf bipartit lengkap
dapat dilipat ke suatu garis.
Lemma 2.7 [9] Batas akhir lipatan dari graf sikel garisnya.
tergantung pada banyak
Lemma 2.8 [9] Jika
adalah graf yang tidak memuat sikel ganjil maka batas
akhir dari lipatan pada graf
adalah sebuah garis.
Contoh 2.3 Diberikan graf H dengan loop sebagaimana terlihat pada Gambar 2.6. v3
v2
v1
Gambar 2.6 Graf Misal
adalah pemetaan graf yang didefinisikan sebagai berikut:
Adapun ilustrasi gambarnya sebagai berikut. v3
v3
f
v2
v1
Gambar 2.7 Pemetaan graf Selnjutnya misal
v2
ke graf
dan menghasilkan
adalah pemetaan graf yang didefinisikan sebagai
berikut:
Adapun ilustrasi gambarnya sebagai berikut. v3
g v3 v2
Gambar 2.8 Pemetaan graf Lemma 2.10 [9] Jika
ke graf
dan menghasilkan
adalah graf multiple yang tidak memuat sikel
batas akhir dari lipatan graf pada graf Definisi 2.11 [10] Gabungan dua graf
maka
adalah loop. dan graf
mempunyai himpunan titik
yang
dan himpunan sisi yang dinotasikan dengan
.
Contoh 3.18 Diberikan graf sebagai berikut : v1
v2
v3 v1
v4
v5
v4
v2
Gambar 2.10 Graf Diberikan graf
dan
v3
v1
v2
v3
v6
v4
v5
v6
,
, dan
dengan
subgraph dari
dan tidak memuat
sikel ganjil. Lipatan graf dapat memenuhi pemetaan linier asalkan
tidak
memuat sikel ganjil. Dalam mendefinisikan pemetaan graf untuk masing-masing graf, definisi pemetaan graf menggunakan satu definisi sama yang berlaku untuk kedua graf dan gabungan kedua graf yang dicari. Contoh 2.4 Diberikan
graf
dan
dengan
himpunan
,
titik
dan
masing-masing
himpunan
)}
garis },
seperti Gambar 2.11. V5
V5
V4
V3
V4
V3
V4
V3
V1
V2
V1
V2
V1
V2
Gambar 2.11 Graf Misal
,
, dan
adalah pemetaan graf yang didefinisikan sebagai berikut:
ii.
Misal
adalah pemetaan graf yang didefinisikan sebagai berikut:
ii. Misal berikut:
adalah pemetaan graf yang didefinisikan sebagai
ii.
Adapun ilustrasi graf hasil pemetaan graf berdasarkan pendefinisian diatas adalah sebagai berikut. V4
V3
V4
V3
V4
V3
V1
V2
V1
V2
V1
V2
Gambar 2.12 Graf
,
, dan
Dari Gambar 2.12 dapat dilihat bahwa
yang
berarti untuk Lipatan graf dapat memenuhi pemetaan linier asalkan dari
dan tidak memuat sikel ganjil dan
Definisi 2.12 [4] Diberikan graf
tidak memuat sikel ganjil.
dengan himpunan titik
dan himpunan garis
. Misal
. Matriks insiden dinotasikan jika
insiden dengan
(ii)
jika
tidak insiden dengan
Misal subgraf dari
,
dan
dan
sedemikian sehingga dan didefinisikan oleh:
(i)
untuk
,
adalah graf dan
, khususnya jika
subgraph
, maka dengan
adalah maka
adalah subgraf dari Matriks I dapat dipartisi menjadi empat bagian, atas dan matriks nol
terletak di pojok kiri
di sebelah kananya. Matriks R, komplemen dari , akan
menjadi submatriks dari
setelah menghapus baris dan kolom dari
bukan merupakan bayangan dari setiap garis Matriks nol O menyatakan bahwa tidak terdapat titik dengan setiap garis dari bayanganya.
dan titik
yang .
yang insiden
Selanjutnya jika matriks insidensi I dari graf
dapat dipartisi kedalam empat
bagian dengan matriks nol terletak pada bagian pojok kanan atas, maka lipatan graf mungkin dapat didefinisikan jika disetiap pemetaan f pada yang dikarakterisasi oleh matriks insidensi
ke bayangan
yang terletak pada bagian
pojok kiri atas I. Pemetaan ini dapat didefinisikan dengan memetakan: (i)
Titik
ke titik
jika kolom ke
dalam R sama dengan kolom ke
dalam
setelah
menghilangkan nol dari kolom ke . (ii)
Garis
ke garis
jika
dan
insidensi. Contoh 2.5 Diberikan
graf
bipartit
lengkap
dengan
dan dipisah
himpunan ,
dan himpunan garisnya
titik },
seperti Gambar
2.13. v6 e5
e6
v1 e1
e7 e8
v5
v2
e9
e4 v4
e3
e2 v3
Gambar 2.13 Graf bipartit lengkap Selanjutnya akan dibentuk matriks insidensi I dari graf tersebut diatas.
I=
Berdasarkan Definisi 2.12, matriks I diatas dapat dipartisi menjadi empat bagian sedemikian sehingga mendapatkan bentuk seperti dibawah ini.
I=
Berdasarkan matriks I yang telah diatur ulang letaknya maka didapat empat bagian hasil partisi, didapatkan juga definisi pemetaan graf
yaitu:
Adapun ilustrasi gambar hasil pemetaanya adalah sebagai berikut. v6
e6
v1
e5 v5
e9
v3
Gambar 2.14 Hasil pemetaan graf
dengan matriks insidensi yang
menghasilkan Berdasarkan Definisi 2.12, Contoh 2.5 memiliki lipatan graf karena matriksnya dapat dipartisi kedalam empat bagian sedemikian sehingga matriks nol terletak pada bagian pojok kanan atas, dan lipatan graf dapat didefinisikan, karena terdapat pemetaan f dari
ke bayangan
yang dikarakterisasi oleh matriks
insidensi
yang terletak pada bagian pojok kiri atas I. Oleh karena itu pemetaan
grafnya dapat didefinisikan dengan memetakan: (i)
Titik
ke titik
jika
dalam R sama dengan kolom ke dalam
kolom ke
setelah menghilangkan
nol dari kolom ke . (ii)
Garis
ke garis
jika
dan
insidensi.
III. KESIMPULAN Lipatan graf non-trivial dapat didefinisikan pada graf tree, graf bipartit, graf bipartit lengkap dan graf sikel
dengan n genap, sedangkan lipatan graf
trivial dapat didefinisikan pada graf lengkap
dan graf sikel
dengan n ganjil.
Batas akhir lipatan graf pada graf tree, graf bipartit lengkap dan graf sikel dengan n bernilai genap adalah sebuah garis. Graf sikel
dengan n bernilai
ganjil tidak memiliki lipatan graf non-trivial. Batas akhir dari graf G yang tidak memuat sikel ganjil adalah sebuah garis. Batas akhir dari graf multiple (graf yang terdiri dari garis berganda dan memiliki loop) yang tidak memuat sikel adalah sebuah loop. Kaitan antara matrik insidensi I dengan lipatan graf pada graf jika matriks insidensi I dari graf
adalah
dapat dipartisi kedalam empat bagian yaitu
terletak di pojok kiri atas dan matriks nol
di sebelah kananya, kemudian matriks
Q teletak dipojok kiri bawah, dan matriks R dipojok kanan bawah. Lipatan graf dapat didefinisikan jika terdapat pemetaan
dari
ke bayangan
yang
dikarakterisasi oleh matriks .
IV. DAFTAR PUSTAKA [1]
Abdul Mutholib, 2012, Pelabelan Titik a-Consecutive Edge Bimagic Total pada Graf, Skripsi, FSM UNDIP. Semarang.
[2]
Berlina Tirtaningrum, 2012, Pelabelan Super Ajaib Sisi, Skripsi, FSM UNDIP. Semarang
[3]
Diestel, Reinchard. 2005. Graph Theory. Springer-Verlag Heidelberg, New York.
[4]
El-Kholy E. M. dan El-Eshawy A. 2005. Graph folding of some special graphs, J.Math. Statistics Nal (1), 66-70, Sci. Pub. U.S.A.
[5]
El-Kholy E. M., Lashin El-Said R. dan Daoud Salama N. 2012. New Operations on Graphs and Graph Foldings, International Mathematical Forum., vol.7, no.46, 2253-2268, Sci. Pub. U.S.A.
[6]
Giblin, P.J. 1997. Graphs, Surfaces and Homology. Chapman and Hall, London.
[7]
Hamouda E.H. 2012. On the based folding of based graphs, Applied Mathematical Science, vol. 6, no. 80, 3975-3979, Sci. Pub. U.S.A.
[8]
Jeksiang, Jong . 2009. Matematika diskret dan aplikasinya pada computer. Yogyakarta. Andi offset.
[9]
Nada S.I. dan E.H. Hamouda. 2009. On the folding of graphs-theory and application, Chaos, Solitons and Fractals 42, 669-675, Sci. Pub. U.S.A.
[10] Rosen, Kenneth H. 2007. “Discrete Mathematics and Its Aplications Sixth Edition”. New York : McGraw – HILL BOOK COMPANY. [11] Wilson R.J. dan Watkins J.J. 1981. Graph an introductory approach. John Wiley and Son, Inc.New York, U.S.A. [12] Wojcik, Michal Ryszard. 2008. Closed and Connected Graphs of Functions; Examples of Connected Punctiform Spaces. Slaski University: Institute of Mathematic. [13] Yuni
Dwi
Astuti,
17
Februari
2012,
Logika
http://kur2003.if.itb.ac.id/file/Graf-1.doc.(17 juli 2013).
dan
Algoritma,
