BAB I PENDAHULUAN
Latar Belakang Masalah pelabelan dalam teori graph mulai
dikembangkan pada pertengahan tahun 1960-an.
Pelabelan pada suatu graph muncul
pertama kali darikarya Rosa pada tahun 1967. Pelabelan pada suatu graph adalah sebarang pemetaan (fungsi)
yang memasangkan unsur-unsur graph (titik atau sisi) dengan bilangan (biasanya bilangan bulat).
Jika domain dari fungsi adalah titik, maka pelabelan disebut pelabelan titik (vertex labeling).
Jika domainnya adalah sisi, maka disebut pelabelan sisi (edge labeling), dan jika domainnya titik dan sisi,
maka disebut pelabelan total (total labeling) (Miller, 2000:165).
Graph ulat (caterpillar) adalah graph yang
jika semua titik ujungnya dihilangkan akan menghasilkan lintasan. Perlu diingat kembali
bahwa titik ujung adalah titik yang berderajat satu.
Rumusan Masalah Pertanyaan dalam penelitian ini dirumuskan
sebagai berikut. “Bagaimana pelabelan super sisi ajaib pada graph ulat model “ ” dengan panjang n, untuk nbilangan asli?” Tujuan Penelitian Sesuai rumusan masalah, maka tujuan penelitian
ini adalah untuk menjelaskan prosedur pelabelan
super sisi ajaib pada graph ulat model “
” dengan panjang n, untuk nbilangan asli.
Manfaat Penelitian Penelitian ini diharapkan dapat memberikan
bukti atau penjelasan bahwa graph ulat model “ ”dengan panjang n, untuk nbilangan asli adalah
super sisi ajaib. Penelitian ini diharapkan dapat menambah wawasan mengenai pelabelan super sisi
ajaib dan merangsang peneliti lain untuk melakukan penelitian lebih lanjut mengenai
pelabelan super sisi ajaib pada beberapa jenis graph lainnya.
Sistematika Penulisan Laporan penelitian ini disusun dalam 5 (lima)
bab. Pada bab I dijelaskan mengenai
latar belakang, rumusan masalah, tujuan penelitian, manfaat penelitian, dan sistematika penulisan.
Padabab II dijelaskan mengenai definisi
graph, derajat titik, graph terhubung, graph ulat, pelabelan pada graph, dan pelabelan super sisi ajaib.
Pada bab III dijelaskan mengenai jenis
penelitian, dan langkah-langkah penelitian. Pada bab IV dijelaskan mengenai pelabelan super sisi ajaib pada graph
ulatmodel “ ” dengan panjang n, untuk n
bilangan asli genap dan n bilangan asli ganjil. Pada bab V dijelaskan mengenai simpulan dan penutup.
Bagian terakhir merupakan daftar pustaka.
BAB II KAJIAN PUSTAKA A. Definisi Graph Graph Gadalah pasangan (V, E) dengan Vadalah
himpunan tidak kosong dan berhingga dari objek-objek yang disebut titik, dan Eadalah
himpunan (mungkin kosong) pasangan takberurutan dari titik-titik berbeda di Vyang disebut
sisi(Miller, 2000:165). Banyaknya unsur di Vdisebut orderdari Gdan dilambangkan dengan p(G), dan banyaknya
unsur di Edisebut ukuran dari Gdan dilambangkan dengan q(G). Jika graph yang dibicarakan hanya
graph G, maka order dan ukuran dari Gcukup masing-masing ditulis pdan q (Chartrand dan
Leniak, 1986:4).
Berdasarkan definisi graph
tersebut, maka suatu graph sederhana tidak boleh mempunyai sisi rangkap dan lup. Sisi rangkap adalah sisi yang
diwakili oleh dua pasangan takberurutan yang sebenarnya sama, misal (a, b) dan (b, a). Lup
adalah sisi yang diwakili oleh pasangan takberurutan yang unsurnya sama, misal (a, a) (Siang,
2002:187). Sebagian penulis menyebut graph yang tidak mempunyai sisi rangkap dan lup sebagai graph
sederhana (simple graph), sedangkan yang membolehkan adanya sisi rangkap dan lup
disebut graph ganda atau multigraph.
Bukti Setiap menghitung derajat suatu titik di G,
maka suatu sisi dihitung 1 kali. Karena setiap sisi menghubungkan dua titik berbeda maka ketika
menghitung derajat semua titik, sisi akan terhitung dua kali. Dengan demikian diperoleh
bahwajumlah semua derajat titik di Gsama dengan 2 kali jumlah sisi di G. Terbukti bahwa
∑ ∈G v v)
deg( = 2q. (Chartrand dan Leniak, 1986:7 dan Siang, 2002:206-207) Berdasarkan hubungan tersebut, maka banyak
titik ganjil dalam suatu graph selalu genap. Hal ini dinyatakan dalam teorema berikut.
Teorema 2.
Banyaknya titik ganjil dalam suatu graph
selalu genap.
Bukti Misalkan Ggraph dan misalkan X adalah himpunan
titik genap di Gdan Y adalah himpunan titik
ganjil di G. Maka ∑ ∈G v v) deg( = ∑ ∑ ∈ ∈ + Y v X v v v ) deg( ) deg( = 2q.
Karena X adalah himpunan titik
genap maka ∑ ∈X v v) deg( adalah genap.
Karena 2q adalah bilangan genap
dan ∑ ∈X v v)
deg( juga genap maka ∑ ∈Y v v) deg( haruslah bilangan
genap.
Karena Y himpunan titik ganjil
dan ∑ ∈Y v v)
deg( adalah bilangan genap, maka banyak titik di Y haruslah genap, sebab jika banyak titik di Y
ganjil maka ∑ ∈Y v v) deg( adalah ganjil.
Terbukti bahwa banyaknya titik
ganjil di Gadalah genap. (Chartrand dan Leniak, 1986:7-8 dan Siang, 2002:207-208) Himpunan derajat dari graph G, ditulis DG ,
adalah himpunan yang memuat derajat semua titik di G. Pada graph Gberikut, G: diperoleh
bahwa deg G w= 2, deg G x= 2, deg G z = 3, dan deg G y= 1.
Jadi himpunan derajat dari graph
Gadalah DG = {1, 2, 3}. Jika yang dibicarakan hanya satu graph, maka himpunan derajat akan ditulis D.
C. Graph Terhubung Jalan u-v dalam graph Gadalah barisan
berhingga yang berselang-seling W: u=v o,
e 1, v 1, e 2, v 2, …, e n, v n =v antara titik dan sisi, yang dimulai dari
titik dan diakhiri dengan titik, dengan •
• • x z y w • Gambar
4: Graph G e i = v i- v i adalah sisi di
G. v 0disebut titik awal, v ndisebut titik akhir, titik v 1, v 2, …, v n- disebut
titik internal, dan nmenyatakan panjang
dari W. Jalan yang tidak mempunyai sisi disebut jalan trivial (Chartrand dan Leniak, 1986:26 dan Siang, 2002:211).
Karena dalam graph, dua titik selalu dihubungkan oleh tepat satu sisi, maka jalan u-v W: u=v o, e 1, v 1, e 2, v 2, …, e n, v n =v dapat ditulis menjadi W: u=v o, v 1, v 2, …, v n- , v n =v.
Contoh Skripsi Matematika:Super Edge Magic Labeling pada Graph Ulat Model ” ” dengan Panjang n TitikDownloads Versi PDF >>>>>>>Klik Disini
0 komentar:
Posting Komentar