SKRIPSI GRAF PETERSEN DAN BEBERAPA SIFAT-SIFAT YANG BERKAITAN (PETERSEN GRAPH AND SOME RELATED PROPERTIES)

SKRIPSI

GRAF PETERSEN DAN BEBERAPA SIFAT-SIFAT YANG BERKAITAN (PETERSEN GRAPH AND SOME RELATED PROPERTIES) Diajukan untuk memenuhi salah satu syarat memperoleh derajat Sarjana Sains Ilmu Matematika

WILLY YANDI WIJAYA 04/178347/PA/10222

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS GADJAH MADA YOGYAKARTA 2011

SKRIPSI

GRAF PETERSEN DAN BEBERAPA SIFAT-SIFAT YANG BERKAITAN (PETERSEN GRAPH AND SOME RELATED PROPERTIES)

Diajukan untuk memenuhi salah satu syarat memperoleh derajat Sarjana Sains Ilmu Matematika

WILLY YANDI WIJAYA 04/178347/PA/10222

DEPARTEMEN PENDIDIKAN NASIONAL UNIVERSITAS GADJAH MADA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM YOGYAKARTA 2011

HALAMAN PENGESAHAN SKRIPSI GRAF PETERSEN DAN BEBERAPA SIFAT-SIFAT YANG BERKAITAN

Telah dipersiapkan dan disusun oleh WILLY YANDI WIJAYA 04/178347/PA/10222

Telah dipertahankan di depan Tim Penguji Pada tanggal 17 Januari 2011

Susunan Tim Penguji

Drs. Aluysius Sutjijana, M.Sc

Diah Junia Eksi Palupi, Dra., MS

Pembimbing Utama

Penguji

Dr. Indah Emilia Wijayanti, M.Si. Penguji

Irwan Endrayanto, S.Si.,M.Sc. Penguji

HALAMAN PERNYATAAN

Dengan ini saya menyatakan bahwa dalam skripsi ini tidak terdapat karya yang pernah diajukan untuk memperoleh gelar kesarjanaan di suatu perguruan tinggi, dan sepanjang pengetahuan saya juga tidak terdapat karya atau pendapat yang pernah ditulis atau diterbitkan oleh orang lain, kecuali yang secara tertulis diacu dalam naskah ini dan disebutkan dalam daftar pustaka.

Yogyakarta, 17 Januari 2011

Willy Yandi Wijaya

HALAMAN MOTTO

Jangan menerima atau mempercayai sesuatu hanya karena telah berlangsung lama yang diturunkan secara lisan. Jangan menerima atau mempercayai sesuatu hanya karena beberapa hal yang dilakukan telah menjadi tradisi/budaya. Jangan menerima atau mempercayai sesuatu hanya karena isu, desas-desus atau pendapat umum yang berkembang di masyarakat. Jangan menerima atau mempercayai sesuatu hanya karena dikatakan tertulis dalam sebuah kitab suci. Jangan menerima atau mempercayai sesuatu hanya karena cocok dengan akal/logika. Jangan menerima atau mempercayai sesuatu hanya karena telah benar secara asumsi atau penyimpulan. Jangan menerima atau mempercayai sesuatu hanya karena cocok dengan pengertian umum seseorang atau seperti yang terlihat. Jangan menerima atau mempercayai sesuatu hanya karena sesuai dengan opini/teori/anggapan sebelumnya yang telah dipertimbangkan berulang-ulang. Jangan menerima atau mempercayai sesuatu hanya karena pembicaranya tampak dapat dipercaya/kelihatan suci. Jangan menerima atau mempercayai sesuatu hanya karena guru sendiri. Tetapi, Apabil setelah Engkau mengamati, memperdalam, mempraktikkan, Engkau mendapatkan hal-hal tersebut baik, tidak bisa disalahkan, dipuji oleh para bijaksana, bila dilakukan dan dijalankan, akan mendapatkan kebahagiaan, ketenangan dan kedamaian, Terimalah hal tersebut. Sang Buddha (Anguttara Nikaya III, No. 65)

iv

HALAMAN PERSEMBAHAN

Kupersembahkan buku ini kepada Ibu yang tanpa lelah memberikan cahaya cinta tanpa batas Ayah yang mendidik dan mendorong kebijaksanaan dan Semua teman-teman yang memberi dorongan semangat Serta Semua makhluk hidup sebagai saudara-saudaraku

May All Being Be Happy Semoga semua makhluk berbahagia

v

PRAKATA

Pertama-tama Penulis ucapkan penghormatan terhadap Sang Buddha, Siddhartha Gautama, sebagai seorang Guru yang mengajarkan kebijaksanaan dan cinta kasih universal tanpa batas, “Namo Tassa Bhagavato Arahato Sammasambuddhasa.” Berkat semangat dan dorongan dari semua pihak sehingga penulis berhasil menyelesaikan penyusunan skripsi yang berjudul “Graf Petersen dan Beberapa Sifat-sifat yang Berkaitan”. Penulisan tugas akhir ini disusun sebagai salah satu syarat untuk memperoleh gelar kesarjanaan, serta sebagai wujud nyata dari disiplin ilmu yang telah penulis dapatkan selama mengikuti perkuliahan di Jurusan Matematika Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Gadjah Mada. Dalam proses penyusunan skripsi ini tak lepas dari hambatan dan kesulitan. Namun berkat bantuan dari berbagai pihak akhirnya skripsi ini dapat terselesaikan dengan baik. Untuk itu, pada kesempatan ini penulis mengucapkan banyak terima kasih kepada: 1. Ayah dan Ibu tercinta atas kasih sayang, semangat, serta dorongan dalam menyelesaikan skripsi ini. 2. Kakak dan Adik-adik yang terus memberi dorongan semangat. 3. Bapak Drs. Aluysius Sutjijana, M.Sc. selaku Dosen Pembimbing Utama yang dengan sabar telah memberikan bimbingan, pengarahan, saran, dan masukan yang berguna sehingga penulis dapat menyelesaikan skripsi ini dengan baik. 4. Ibu Dr. Christina Rini Indrati, M.Si selaku Dosen Wali yang telah memberikan semangat dan dorongan kepada penulis selama proses mengerjakan skripsi. 5. Tim Penguji: Ibu Drs. Diah Junia Eksi Palupi,MS, Ibu Dr. Indah Emilia Wijayanti,M.Si., dan Bapak Irwan Endrayanto,S.Si.,M.Sc. terima kasih atas

vi

waktu, saran, dan bantuannya sehingga penulis mendapatkan tambahan ilmu yang sangat berharga untuk menyempurnakan penulisan skripsi ini. 6. Segenap dosen pengajar Program Studi Matematika FMIPA UGM, yang telah memberikan bekal ilmu kepada penulis selama mengikuti perkuliahan. 7. Segenap Staff dan Karyawan di Program Studi Matematika FMIPA UGM atas semua fasilitas, pelayanan, dan dukungan yang telah diberikan kepada penulis selama kuliah di Matematika UGM. 8. Teman-teman seperjuangan matematika angkatan 2004, khususnya: Adif, Teguh K, Ipin, Harto, Ervan, Abi. Terima kasih atas segala bantuan dan dukungannya. 9. Teman-teman Keluarga Mahasiswa Buddhis Universitas Gadjah Mada (Kamadhis UGM) dan Wihara Vidyaloka Yogyakarta. 10. Teman-teman satu kontrakan, Seng Hansun, Neo, Awong, dan Standie. 11. Semua pihak yang telah membantu, baik secara langsung maupun tidak langsung, yang tidak bisa penulis sebutkan satu-persatu dikarenakan keterbatasan yang Penulis miliki. Penulis menyadari bahwa dalam penulisan dan penyusunan skripsi ini masih terdapat kekurangan-kekurangan dan masih jauh dari sempurna. Untuk itu penulis sangat mengharapkan kritik dan saran yang membangun dan dapat menyempurnakan tulisan skripsi ini di masa mendatang. Kritik dan saran dapat disampaikan

langsung kepada

penulis

atau

dikirimkan

melalui

email

[email protected]. Akhir kata penulis berharap semoga tulisan skripsi ini dapat memberikan manfaat bagi penulis dan pembaca pada umumnya.

Yogyakarta, 17 Januari 2011

Willy Yandi Wijaya

vii

DAFTAR ISI

HALAMAN JUDUL ............................................................................. HALAMAN PENGESAHAN ................................................................. HALAMAN PERNYATAAN .................................................................. HALAMAN MOTTO ............................................................................ HALAMAN PERSEMBAHAN ................................................................ PRAKATA ............................................................................................. DAFTAR ISI .......................................................................................... DAFTAR GAMBAR ............................................................................... DAFTAR TABEL .................................................................................... DAFTAR LAMPIRAN ............................................................................ INTISARI .............................................................................................. ABSTRACT .......................................................................................... BAB I

PENDAHULUAN 1.1 Latar Belakang dan Permasalahan .................................... 1.2 Tujuan Penulisan ............................................................... 1.3 Tinjauan Pustaka ............................................................... 1.4 Metodologi Penelitian ....................................................... 1.5 Sistematika Penulisan .......................................................

i ii iii iv v vi viii x xii xiii xiv xv

1 2 2 3 3

BAB II DASAR TEORI 2.1 Pengertian Dasar Graf........................................................ 2.2 Derajat Graf.............. ....................................................... 2.3 Graf Khusus ...................................................................... 2.4 Subgraf ............................................................................. 2.5 Keterhubungan ................................................................. 2.6 Eulerian dan Hamiltonian ................................................. 2.7 Isomorfisma Graf .............................................................. 2.8 Komplemen ...................................................................... 2.9 Planaritas .......................................................................... 2.10 Permutasi dan Grup Permutasi.........................................

5 9 10 15 17 24 29 31 31 34

BAB III SIFAT-SIFAT GRAF PETERSEN 3.1 Graf Petersen dan Eulerian .............................................. 3.2 Graf Petersen dan Planaritas ........................................... 3.3 Graf Petersen dan Faktorisasi .......................................... 3.4 Graf Petersen dan Grup Automorfisma........................... 3.5 Transitif-titik dan Transitif-garis...................................... 3.6 Graf Garis dan Bipartit........... .......................................... 3.7 Graf Petersen dan Hamiltonian.........................................

39 43 46 51 57 60 64

viii

3.8 Graf Petersen dan Hipohamiltonian.................................. 70 BAB IV KESIMPULAN DAN SARAN 4.1 Kesimpulan ....................................................................... 79 4.2 Saran ................................................................................. 79 DAFTAR PUSTAKA LAMPIRAN Lampiran 1. Daftar istilah

ix

DAFTAR GAMBAR

Gambar 2.1 Graf
 Gambar 2.2 Pseudograf Gambar 2.3 Multigraf  Gambar 2.4 Graf teratur Gambar 2.5 (a) Graf  dan (b) Graf  Gambar 2.6 (a) Graf bipartit dan (b) Partisi graf bipartit Gambar 2.7 Graf bipartit lengkap Gambar 2.8 Graf Kubik Gambar 2.9 Graf Petersen  Gambar 2.10 Subgraf dari graf Petersen Gambar 2.11 Graf Petersen  1 Gambar 2.12 Subgraf Perentang dari graf Petersen Gambar 2.13 Graf sederhana  Gambar 2.14 Suatu graf dengan tujuh komponen Gambar 2.15 Jembatan Konigsberg Gambar 2.16 Graf jembatan konigberg Gambar 2.17 (a) Graf Eulerian, (b) semi-Eulerian, (c) Graf bukan Eulerian Gambar 2.18 (a) Dodekahedron, dan (b) Graf dodekahedron Gambar 2.19 (a) Graf Eulerian sekaligus Hamiltonian, (b) Graf Eulerian bukan Hamiltonian, (c) Graf Hamiltonian bukan Eulerian, (d) Graf bukan Hamiltonian maupun Eulerian Gambar 2.20 Graf yang isomorfik Gambar 2.21 (a) Graf Petersen, (b) Isomorfik graf Petersen, (c) Isomorfik graf Petersen Gambar 2.22 Graf dan Komplemennya Gambar 2.23 Graf Planar 

x

Gambar 2.24 (a) Graf Planar serta (b) dan (c) Graf Bidang Gambar 2.25 Permukaan graf planar Gambar 2.26 Derajat Permukaan Graf

Gambar 3.1 Graf dan Faktorisasinya Gambar 3.2 Partisi Graf Petersen menjadi faktor-1 dan faktor-2 Gambar 3.3 (a) Graf , dan (b) faktorisasi-1 dari Graf , Gambar 3.4 (a) Graf  dan (b) faktorisasi-2 dari  Gambar 3.5 Graf Petersen tidak terfaktor-1 Gambar 3.6 Automorfisma  Graf Petersen Gambar 3.7 Automorfisma  Graf Petersen Gambar 3.8 Graf Petersen Gambar 3.9 Graf Petersen P Gambar 3.10 Graf dan Graf Garisnya Gambar 3.11 Awal konstruksi titik konsitik Gambar 3.12 Kemungkinan pertama titik konsitik Graf Petersen Gambar 3.13 Kemungkinan lanjutan titik konsitik Graf Petersen Gambar 3.14 Kemungkinan akhir titik konsitik Graf Petersen Gambar 3.15 Graf dan siklus hamiltonian Gambar 3.16 Kemungkinan graf 8 titik Gambar 3.17 Kemungkinan graf bertitik 9 Gambar 3.18 Graf bertitik 10 Gambar 3.19 Graf Petersen Gambar 3.20 Graf Petersen dan Graf isomorfik dengan Graf Petersen

xi

DAFTAR TABEL Tabel 2.1 Tabel Penggandaan komposisi grup simetrik berelemen tiga  Tabel 3.1 Kedekatan titik pada   dan  

xii

DAFTAR LAMPIRAN

Lampiran 1. Daftar Istilah

xiii

INTISARI Graf Petersen dan Beberapa Sifat-Sifat Yang Berkaitan Oleh Willy Yandi Wijaya 04/178347/PA/10222

Graf Petersen adalah graf kubik dengan 10 titik. Graf Eulerian adalah graf dengan sirkuit yang mengandung semua garis, dan suatu graf yang dapat digambarkan pada bidang tanpa ada garis yang berpotongan disebut graf planar. Graf Petersen merupakan transitif-titik, transitif-garis, dan komplemen dari graf garis atas graf lengkap dengan lima titik, tetapi graf Petersen bukan Eulerian, bukan planar, tidak terfaktor-1, dan bukan graf bipartit. Graf Petersen juga bukan graf Hamiltonian, tetapi graf Petersen merupakan graf hipohamiltonian terkecil dengan 10 titik. Himpunan automorfisma graf Petersen isomorfik dengan grup simetrik berelemen lima.

xiv

ABSTRACT PETERSEN GRAPH AND SOME RELATED PROPERTIES by Willy Yandi Wijaya 04/178347/PA/10222

Petersen graph is a cubic graph with 10 vertices. Eulerian graph is a graph with a circuit that contains all of edges, and a graph that can be drawn in the plane without any of its edges intersecting is called a planar graph. Petersen graph is a vertex-transitive, edge-transitive, and complement of the line graph of the complete graph with five vertices, but Petersen graph is non-Eulerian, nonplanar, not 1-factorable, and not bipartite graph. Petersen graph is also nonHamiltonian graph, but Petersen graph is a smallest hypohamiltonian graph with 10 vertices. The set of automorphism of Petersen graph is isomorphic to simetric group of five element.

xv

BAB I PENDAHULUAN 1.1 Latar Belakang dan Permasalahan Teori

Graf

berawal

pada

tahun

1736

ketika

Leonhard

Euler

mempublikasikan bukunya mengenai pemecahan masalah Jembatan Königsberg yang berjudul Solutio Problematis Ad Geometriam Situs Pertinentis. Walaupun demikian, minat akan Teori Graf baru berkembang setelah tahun 1920 hingga akhirnya buku teks tentang Teori Graf muncul pada tahun 1936. Buku tersebut ditulis oleh Denes Konig dengan judul “The Teory of Finite and Infinite Graphs” yang diterjemahkan dari bahasa Jerman (Capobianco dan Molluzo, 1978). Sejak itulah minat terhadap Teori Graf berkembang pesat. Daya tarik Teori Graf adalah penerapannya yang sangat luas, mulai dari ilmu komputer, kimia, fisika, biologi, sosiologi, teknik kelistrikan, linguistik, ekonomi, manajemen, pemasaran, hingga pemecahan teka-teki dan permainan asah otak. Walaupun penerapannya sangat banyak, yang menarik adalah bahwa Teori Graf hanya mempelajari titik dan garis. Salah satu contoh Graf yang paling dikenal dan sangat populer adalah Graf Petersen. Graf Petersen diambil dari nama Peter Christian Julius Petersen untuk menghargainya karena pada tahun 1898 ia membuktikan bahwa Graf Petersen tidak terfaktor-1. Graf Petersen sangat populer untuk dipelajari karena keunikannya sebagai contoh penyangkal (counterexample) di banyak tempat dan mempunyai banyak sifat-sifat menarik (Holton dan Sheehan, 1993). Dalam indeks buku “Examples and Counterexamples in Theory Graph” karangan Copabianco dan Molluzo (1978), Graf Petersen muncul sebanyak sembilan kali sebagai contoh penyangkal maupun sifat unik yang berkaitan dengan macam-macam topik pada Teori Graf.

1

Banyak topik pada Teori Graf yang bisa dikaitkan dengan Graf Petersen, antara lain masalah Eulerian, Hamiltonian dan Hipohamiltonian, Faktorisasi, Planaritas, hingga Automorfisma suatu Graf. Pendekatan yang dapat dilakukan untuk mempelajari Teori Graf adalah dengan pendekatan aljabar, kombinatorik maupun geometris. Dalam skripsi ini, pendekatan kombinatorik akan digunakan untuk menguji apakah Graf Petersen planar atau tidak. Pendekatan aljabar juga digunakan untuk membentuk grup automorfisma graf sehingga dapat diuji apakah Graf Petersen transitif titik atau transitif garis. Salah satu topik pada Teori Graf yang berkaitan dengan keterhubungan adalah masalah Hamiltonian dan Eulerian. Dalam skripsi ini akan diselidiki apakah Graf Petersen Eulerian atau tidak, kemudian hamiltonian atau tidak, hingga akhirnya dikembangkan dengan menyelidiki kaitan antara hipohamiltonian dengan Graf Petersen.

1.2 Tujuan Penelitian Tujuan dari penelitian/penulisan Tugas Akhir ini adalah melihat keterkaitan antara Graf Petersen dengan sifat-sifat dalam Teori Graf, khususnya planaritas, Eulerian, faktorisasi, hamiltonian, hipohamiltonian, dan grup automofirma serta kaitannya dengan transitif-garis dan transitif-titik.

1.3 Tinjauan Pustaka Dalam penulisan Tugas Akhir ini digunakan beberapa sumber pustaka. Beberapa pengertian dasar Graf diambil dari sumber yaitu Chartrand dan Oellermann (1993). Untuk beberapa pengertian graf khusus diacu dari sumber Harary (1969). Beberapa macam pengertian keterhubungan, meliputi pengertian graf Eulerian dan graf Hamiltonian mengacu pada Wilson dan Watkins (1990). Pemutasi dan grup permutasi diacu dari Fraleigh dan Katz (1994) serta Gallian (1990)

2

Pembahasan graf Petersen yang dikaitkan dengan Eulerian diacu dari Slamet dan Makaliwe (1991). Kaitannya dengan Planaritas, beserta teorema Euler yang cukup penting, diacu dari buku Liu (1995). Masalah faktorisasi yang berkaitan dengan graf Petersen diacu dari sumber Balakrishnan (1997). Grup automorfisma graf diacu dari Biggs (1974), kemudian pembahasan yang terkait graf transitif-titik dan graf transitif-garis diacu dari sumber Suryoto (2001) serta Holton dan Sheehan (1993). Berkaitan dengan Hamiltonian diacu dari sumber Hu (2010) serta Holton dan Sheehan (1993). Pada bagian akhir, pembahasan hipohamiltonian kaitannya dengan graf Petersen diacu dari sumber Busacker dan Saaty (1965) serta Holton dan Sheehan (1993).

1.4 Metodologi Penelitian Metodologi penelitian yang digunakan dalam penyusunan Tugas Akhir ini adalah dengan metode studi literatur (tinjauan pustaka). Pembahasan diawali dengan pengertian dasar graf disertai contoh-contoh untuk memperjelas definisi yang dimaksud, sifat-sifat terkait graf teori, dan grup permutasi. Pada bagian utama dibahas sifat-sifat terkait graf Petersen, antara lain Eulerian, planaritas dan faktorisasi. Pembahasan mengenai grup automorfisma graf dan graf transitiftitik serta graf transitif-garis memerlukan dasar grup permutasi. Berkaitan dengan

masalah

hipohamiltonian

dengan

graf

Petersen,

pembahasan

memerlukan dasar hamiltonian. Kemudian, pada bagian akhir dari Tugas Akhir ini disajikan kesimpulan dari hasil pembahasan sebelumnya.

1.5 Sistematika Penulisan Penulisan Tugas Akhir ini dibagi dalam 4 bab dengan rincian masingmasing sebagai berikut.

3

BAB I

PENDAHULUAN Membahas mengenai latar belakang dan permasalahan, tujuan penelitian, tinjauan pustaka, metodologi penelitian, dan sistematika penulisan.

BAB II DASAR TEORI Membahas mengenai teori-teori penunjang yang digunakan dalam bab selanjutnya, meliputi pengertian dasar graf, definisi-definisi dasar dari graf, meliputi derajat suatu graf, macam-macam graf khusus, subgraf, keterhubungan,

Eulerian

dan

hamiltonian,

Isomorfisma

graf,

komplemen suatu graf, planaritas. Pada bagian akhir juga dibahas pengertian permutasi dan grup permutasi.

BAB III

SIFAT-SIFAT GRAF PETERSEN Membahas graf Petersen dan sifat-sifat yang berkaitan. Sifat-sifat yang berkaitan tersebut meliputi Eulerian, planaritas, faktorisasi, grup automorfisma, graf transitif-titik dan transitif-garis, graf garis, graf bipartit, Hamiltonian dan hipohamiltonian.

BAB IV

KESIMPULAN DAN SARAN Membahas mengenai kesimpulan dan saran yang diperoleh dari pembahasan yang telah dilakukan.

4

BAB II DASAR TEORI Pada bab ini akan dibahas pengertian-pengertian dasar dan teorema-teorema pada Teori Graf yang akan digunakan sebagai landasan dalam pembahasan selanjutnya.

2.1 Pengertian Dasar Graf Berikut akan diberikan pengertian graf secara umum, meliputi multigraf dan pseudograf. Istilah-istilah dasar yang berkaitan dengan titik-titik maupun garisgaris pada suatu graf juga diberikan. Beberapa contoh dan ilustrasi gambar disajikan pula agar memperjelas suatu definisi.

Definisi 2.1

Sebuah Graf (Graph) G ditulis   VG, EG terdiri dari dua

bagian: i.

Suatu himpunan VG  v , v , … , v  himpunan tidak-kosong yang memiliki elemen-elemen yang disebut titik-titik (vertices).

ii.

Suatu himpunan EG  e , e , . . . , e  merupakan himpunan dari elemenelemen yang menghubungkan titik yang disebut garis (edge).

Notasi untuk himpunan titik-titik () dan garis-garis () pada suatu graf mengikuti nama graf. Misalnya graf  , terdiri dari himpunan titik-titik ditulis  dan himpunan garis-garisnya ditulis  .

Garis-garis EG  e , e , . . . , e  dapat ditulis sebagai himpunan dua titik pada VG,

yaitu

EG  e , e , . . . , e   v , v , v , v , . . . , v , v .

selanjutnya, suatu garis e  u, v dapat ditulis sebagai  atau .

5

Untuk

Garis-garis EG tidaklah harus disajikan dalam bentuk garis lurus. Dalam dua titik yang sama pada suatu Graf dapat dihubungkan oleh garis lebih dari satu. Garis-garis tersebut didefinisikan melalui definisi berikut.

Definisi 2.2

Dua atau lebih garis yang menghubungkan (joining) dua titik yang

sama disebut garis-garis paralel (multiple edges). Garis yang menghubungkan titik dengan dirinya sendiri disebut gelung (loop). Sebuah graf yang tidak memiliki garis-garis paralel atau gelung disebut graf sederhana.

Contoh 2.3

Diberikan graf    ,      ,  ,  ,  ,  ,  ,  

dengan    ,  ,  ,      ,   ,   ,   , sehingga graf  bukan graf sederhana karena memiliki garis-garis paralel yaitu garis  dan  . Graf  tidak mempunyai gelung. Graf  dapat disajikan seperti pada Gambar 2.1

Gambar 2.1 Graf

!

Pada suatu graf mungkin terdapat garis-garis paralel atau gelung seperti definisi berikut ini.

Definisi 2.4

Sebuah graf yang mempunyai garis-garis paralel disebut sebagai

multigraf (multigraph).

Definisi 2.5

Sebuah graf yang mempunyai garis-garis paralel dan gelung

disebut pseudograf (pseudograph).

6

Graf seperti yang ditunjukkan Gambar 2.1 merupakan suatu multigraf, sedangkan suatu Pseudograf akan diberikan melalui Contoh 2.6 berikut.

Contoh 2.6

Graf G  VG, EG   v , v , v , e , e , e , e , e    v , v , v , v v , v v , v v , v v , v v 

Gambar 2.2 Pseudograf

Gambar 2.2 merupakan salah satu bentuk gambar yang dapat disajikan dari hubungan titik dan garis Graf G . Graf tersebut adalah pseudograf karena memiliki garis-garis paralel yang menghubungkan v dan v yaitu e dan e , serta mempunyai gelung e .

Definisi 2.7

Titik-titik  dan  disebut berdekatan (adjacent) atau 

berdekatan dengan  jika ada suatu garis , sedemikian sehingga     . Garis  dikatakan menggabungkan (join)  dan  .

Definisi 2.8

Titik  dan  insiden pada (incident on) garis  atau dikatakan

garis  insiden dengan (incident to) titik  dan  jika     .

7

Contoh 2.9

Diberikan suatu graf  seperti pada Gambar 2.2

Gambar 2.3 Multigraf "#

Graf  pada Gambar 2.3 merupakan multigraf karena mempunyai garis-garis paralel, namun bukan suatu pseudograf karena tidak mempunyai gelung. Titik  pada graf tersebut berdekatan dengan  , tetapi tidak berdekatan dengan  maupun  . Garis  insiden dengan titik  dan  .

Definisi 2.10 Banyaknya titik pada suatu Graf G disebut orde (order) graf G dinotasikan ||. Banyaknya garis pada suatu Graf G disebut ukuran (size) graf G dinotasikan ||.

Contoh 2.11 Graf  seperti pada contoh 2.6 (lihat Gambar 2.2) mempunyai jumlah titik sebayak tiga dan garis sebanyak lima. Dengan kata lain,  memiliki orde tiga atau dapat ditulis |VG |  3, serta mempunyai ukuran lima atau dapat ditulis |EG |  5. Perhatikan bahwa gelung dihitung satu buah garis. Graf  seperti yang terlihat pada Gambar 2.3 mempunyai | |  4

8

2.2 Derajat Graf Pada subbab ini akan dijelaskan pengertian derajat dari suatu Graf beserta contoh untuk memperjelas makna yang dimaksud. Pada bagian ini juga diberikan Teorema yang mengkaitkan hubungan antara derajat graf dengan jumlah titik yang dikenal sebagai Lemma Persalaman. Graf Sederhana untuk selanjutnya cukup disebut sebagai graf.

Definisi 2.12 Derajat (degree)  dinotasikan () * adalah banyaknya garis yang insiden dengan titik * .

Contoh 2.13 Diketahui Graf  seperti pada Gambar 2.3, maka deg   1 karena banyaknya garis yang insiden dengan titik  adalah satu yaitu garis  . Sedangkan titik lainnya pada Graf  yaitu titik  ,  , dan  berturut-turut berderajar tiga, dua, dan nol atau dapat ditulis sebagai deg   3, deg   2 dan deg   0.

Teorema 2.14 Jumlah derajat titik-titik dari sebuah graf adalah sama dengan dua kali jumlah garisnya. Bukti: Mengikuti kenyataan bahwa setiap garis dihitung dua kali dalam perhitungan derajat suatu titik pada sebuah Graf. 0

Perhatikan bahwa Teorema 2.14 juga berlaku untuk suatu multigraf karena gelung didefinisikan mempunyai derajat dua. Teorema 2.14 ini dikenal sebagai Lemma Persalaman (Handshaking Lemma).

Teorema 2.15 Banyaknya titik dari suatu graf G yang berderajat ganjil adalah berjumlah genap.

9

Bukti: Titik-titik pada graf dibagi menjadi dua kelompok, yaitu kelompok titik-tiitk yang berderajat genap 1 , 1 , … , 12 dan titik-titik yang berderajat ganjil 3 , 3 , … , 34 . Dimisalkan bahwa (5  deg 1 6 deg 1 6 7 6 deg 14 (8  deg 3 6 deg 3 6 7 6 deg 34 . Menurut Teorema 2.14, jumlah derajat selalu genap, berarti (5 6 (8 genap. Oleh karena (5 adalah jumlah dari bilangan genap maka (5 genap, sehingga (8 juga genap. Di sisi lain, (8 adalah jumlah bilangan ganjil, sehingga banyaknya titik pada (8 haruslah genap. Jadi, terbukti bahwa jumlah titik berderajat ganjil adalah genap. 0

2.3 Graf Khusus Pada subbab berikut akan diberikan beberapa macam graf yang sering digunakan dalam Teori Graf beserta ilustrasi gambar dan contoh untuk memperjelas pengertian graf yang dimaksud. Graf khusus yang akan dibahas antara lain graf teratur, graf lengkap, graf bipartit, graf bipartit lengkap, graf kubik, dan graf Petersen.

Definisi 2.16 Suatu graf dikatakan graf teratur (regular graph) apabila setiap titik pada graf mempunyai derajat yang sama. Secara khusus, apabila setiap titik pada suatu graf mempunyai derajat r, maka graf dikatakan teratur-r.

10

Contoh 2.17 Beberapa contoh Graf teratur terlihat melalui Gambar 2.4.

Gambar 2.4 Graf teratur (Wilson dan Watkins, 1990)

Teorema 2.18 Diberikan Graf G adalah Teratur-r dengan banyaknya titik 9, maka  mempunyai

4:

garis.

Bukti: Misalkan ukuran graf G adalah ;. Diketahui bahwa graf mempunyai 9 titik dan setiap titik berderajat <, maka jumlah semua derajatnya adalah 9<. Menurut Lemma Persamalan (Teorema 2.14), jumlah derajat suatu graf sama dengan dua kali banyaknya garis, berarti 9<  2; atau ;  mempunyai ukuran

4:

4:

. Jadi, terbukti graf G

.

Definisi 2.19 Graf lengkap (complete graphs) adalah graf yang setiap dua titiknya dihubungkan dengan tepat oleh satu garis. Graf lengkap dinotasikan 4 dengan 9 menunjukkan jumlah titik pada graf.

11

Contoh 2.20 Graf  dan = dapat digambarkan seperti pada Gambar 2.5(a) dan Gambar 2.5(b).

(a)

(b) Gambar 2.5 (a) Graf >? dan (b) Graf >@

Teorema 2.21 Graf lengkap 4 mempunyai ukuran

44

.

Bukti: Misalkan ukuran 4 adalah A. Diketahui bahwa derajat setiap titiknya adalah 9 B 1 dan terdapat 9 titik. Bersadarkan Lemma Persalaman (Teorema 2.14), maka jumlah derajatnya yaitu 99 B 1  2A. Akibatnya A 

44

dengan kata lain banyaknya garis atau ukuran graf lengkap 4 adalah



. Jadi,

44

.0

Definisi 2.22 Suatu graf  adalah graf bipartit (bipartite graph) jika  dapat dipartisi menjadi dua himpunan bagian (tidak kosong)  dan  sedemikian sehingga setiap garis  menggabungkan sebuah titik  dengan sebuah titik  .  dan  adalah partisi graf G dinotasikan  ,  .

12

Contoh 2.23 Graf yang diberikan seperti pada Gambar 2.6(a) merupakan contoh graf bipartit karena dapat digambar ulang menjadi seperti Gambar 2.6(b) yang dapat dipartisi menjadi dua himpunan bagian,    , C  dan    ,  ,  ,  .

(a)

(b)

Gambar 2.6 (a) Graf bipartit dan (b) Partisi graf bipartit

Definisi 2.24 Graf bipartit lengkap (complete bipartite graph) dinotasikan dengan 2,4 adalah graf bipartit dengan A adalah banyaknya titik pada  dan 9 adalah banyaknya titik pada  .

Contoh 2.25 Graf seperti yang digambarkan pada Gambar 2.7 merupakan graf bipartit lengkap.

Gambar 2.7 Graf bipartit lengkap

13

Teorema 2.26 Graf bipartit lengkap 2,4 mempunyai ukuran A9. Bukti: Misalkan ukuran graf 2,4 adalah D. Diketahui bahwa derajat setiap titiknya di  adalah A, dan derajat setiap titiknya di  adalah 9. Sehingga jumlah derajat A titik di  adalah A9, dan jumlah derajat 9 titik di  adalah A9. Oleh karena itu jumlah derajat seluruh titiknya adalah 2A9. Menurut Lemma Persalaman (Teorema 2.14), jumlah derajat suatu graf sama dengan dua kali jumlah titiknya, berarti 2A9  2D. Jadi, didapat D  A9. 0

Definisi 2.27 Graf kubik (cubic graph) adalah graf teratur yang berderajat tiga atau graf teratur-3.

Contoh 2.28 Graf kubik dengan empat titik dan delapan titik terlihat pada Gambar 2.8.

Gambar 2.8 Graf Kubik

Teorema 2.29 Setiap graf kubik mempunyai orde genap. Bukti: Diketahui bahwa setiap graf kubik mempunyai derajat tiga (ganjil). Menurut Lemma Persalaman (Teorema 2.14), jumlah derajat seluruh titiknya haruslah berjumlah genap, sehingga jumlah titik yang mungkin hanyalah genap. 0

14

Definisi 2.30 Graf Petersen (Petersen Graph) P adalah graf kubik dengan sepuluh titik.

Salah satu gambar representasi dari Graf Petersen P adalah seperti yang terlihat pada Gambar 2.9 dengan VP  1, 2, 3, 4, 5, 1’, 2’, 3’, 4’, 5’ , dan EP  12, 23, 34, 45, 51, 1’3’, 2’4’, 3’5’, 1’4’, 5’2’, 11’, 22’, 33’, 44’, 55’

1

1' 5 2 2'

5' 3'

4'

3

4

Gambar 2.9 Graf Petersen P

2.4 Subgraf Definisi 2.31 Suatu Graf F  F, F disebut subgraf (subgraph) dari   ,  jika ES merupakan himpunan bagian dari  dan F merupakan himpunan bagian dari  sedemikian rupa sehingga garis-garis di dalam F berinsidensi hanya dengan titik-titik di dalam F.

Dengan kata lain,  subgraf dari  jika  G  dan  G . Subgraf dari suatu graf tentu saja adalah suatu graf pula. Untuk memperjelas pengertian subgraf akan diberikan contoh.

15

Contoh 2.32 Diberikan Graf Petersen (Gambar 2.9). Berikut adalah subgraf dari Graf Petersen (lihat Gambar 2.10)

1'

1'

5 2 2'

5'

2'

5'

3'

4'

3'

4'

3

4

Gambar 2.10 Subgraf dari Graf Petersen

Definisi 2.33 Suatu Subgraf dikatakan subgraf hapus titik (vertex deleted subgraph) ditulis " B H jika sebuah titik dan garis-garis yang berinsiden dengan titik tersebut pada suatu Graf dibuang.

Contoh 2.34 Diberikan Graf Petersen I. Titik 1 pada Graf Petersen yang dihapus ditulis P B 1 adalah subgraf dari Graf Petersen P (lihat Gambar 2.11)

1' 5 2 2'

5'

3'

4'

3

4

Gambar 2.11 Graf Petersen J B !

16

Definisi 2.35 Subgraf H dari Graf G dikatakan subgraf perentang (spanning subgraph) G jika   .

Contoh 2.36 Subgraf pada Gambar merupakan beberapa subgraf perentang dari Graf Petersen. Ketiga Subgraf tersebut merupakan subgraf perentang karena setiap subgraf tersebut masih mengandung semua titik Graf Petersen. 1

1 1' 5 2

1' 5

2'

5'

2 2'

5'

4'

4'

3'

3' 3

4 1

3

4

1' 5 2 2'

5'

4'

3'

3

4

Gambar 2.12 Subgraf perentang dari Graf Petersen

2.5 Keterhubungan Pada bagian ini akan dijelaskan pengertian jalan, lintasan, jalur, siklus dan sirkuit, serta keterhubungan suatu graf. Contoh-contoh juga diberikan untuk memperjelas definisi yang dimaksud. Pengertian tertutup dan terbuka suatu barisan (jalan) juga diberikan.

17

Definsi 2.37

Barisan titik-titik dan garis-garis pada graf G yang berselang-

seling, yaitu K: M ,  ,  ,  , … , 4 , 4 , 4

9 N 0

yang dimulai dari suatu titik dan berakhir pada suatu titik sedemikian sehingga *  * * , untuk O  1,2, … , 9 (tiap garis insiden dengan tiap dua titik pada barisan tersebut), dikatakan sebagai suatu jalan (walk) pada G.

Jalan pada graf dapat dinotasikan dengan M   … 4 dan dapat dikatakan sebagai Jalan M B 4 yang bermakna barisan dimulai dari titik awal M dan berakhir di titik akhir 4 . (Harary, 1969)

Contoh 2.38 Diberikan Graf  seperti pada Gambar 2.13

Gambar 2.13 Graf Sederhana "P

Misal diketahui bahwa K :  ,  ,  ,  ,  ,  ,  , C ,  Berarti K merupakan suatu jalan pada graf G. K dapat ditulis lebih sederhana sebagai  ,  ,  ,  ,  . Diberikan K :  ,  ,  ,  ,  ,  ,  maka K juga merupakan suatu jalan, walaupun garis  dan  dilewati lebih dari satu kali.

18

Definisi 2.39 Panjang (length) dari suatu jalan M  … 4 adalah banyaknya garis yang muncul (dilalui) sepanjang barisan.

Contoh 2.40 Diberikan graf seperti pada Contoh 2.38 (Gambar 2.13). Didefinisikan juga jalan K :  ,  ,  ,  ,  dan K :  ,  ,  ,  ,  ,  ,  Maka jalan K mempunyai panjang empat karena barisan melalui garis sebanyak empat buah. Jalan K mempunyai panjang enam, karena melalui empat garis yang berbeda namun dua garis berulang sehingga panjangnya menjadi enam.

Teorema 2.41 Diberikan suatu graf dengan 9 titik. Jika ada suatu jalan dari titik  ke titik  , maka ada suatu jalan dengan tidak lebih dari 9 B 1 garis dari titik  ke titik  . Bukti: Misalkan ada suatu jalan dari  ke  . Misalkan juga  , … , * , … ,  adalah barisan titik yang ditemui jalan itu ketika ditelusuri dari  ke  . Apabila ada A buah garis pada jalan tersebut, maka ada A 6 1 titik di dalam barisan titik tersebut. Agar A lebih besar dari 9 B 1, maka harus ada titik Q yang muncul lebih dari sekali di dalam barisan itu. Berarti barisan titik tersebut memiliki bentuk umum  , … , * , … , Q , … ,  . Jika garis-garis pada jalan yang membawa Q kembali ke Q itu dibuang, maka akan didapat suatu jalan dari  ke  yang mempunyai lebih sedikit garis daripada jumlah garis sebelumnya. Cara ini diulang hingga didapat jalan dengan 9 B 1 garis atau lebih sedikit. 0

19

Definisi 2.42 Suatu barisan titik-titik dan garis-garis (jalan) dikatakan tertutup (close) apabila M  4 . Jika M R 4 , maka dikatakan terbuka (open).

Contoh 2.43 Diberikan Graf  seperti pada Contoh 2.38 (Gambar 2.13), jalan K :  ,  ,  ,  ,  dan K :  ,  ,  ,  ,  ,  ,  . Dimisalkan bahwa K :  ,  ,  ,  ,  ,  ,  maka K merupakan jalan tertutup. Sedangkan K dan K merupakan jalan terbuka karena titik awalnya tidak sama dengan titik akhirnya.

Definisi 2.44 Lintasan (path) adalah jalan dengan semua titik dalam barisan adalah berbeda.

Contoh 2.45 Diberikan graf seperti pada Contoh 2.38 (Gambar 2.13), jalan K :  ,  ,  ,  ,  dan K :  ,  ,  ,  ,  ,  ,  Berdasarkan definisi lintasan, berarti K merupakan suatu lintasan sedangkan K bukan suatu lintasan. K bukan lintasan karena ada titik yang dilewati lebih dari satu kali, yaitu titik  .

Teorema 2.46 Diberikan suatu graf G. Ada jalan dari suatu titik  ke titik  jika dan hanya jika terdapat sebuah lintasan dari titik  ke titik . Bukti: S Dari definisi lintasan, jelas bahwa lintasan adalah suatu jalan. T Diketahui bahwa jalan K:  B  pada suatu graf G. Apabila   , maka jelas, sehingga diasumsikan bahwa  R . Dimisalkan K:   M ,  , … , 4   (mungkin terdapat titik yang berulang di dalam K).

20

Jika tidak ada titik yang berulang dalam K, maka K adalah lintasan itu sendiri. Sebaliknya, untuk kasus ada titik yang berulang pada jalan K lebih dari sekali. Misalkan O dan U (O V U adalah bilangan bulat positif berbeda sedemikian sehingga *  W . Jika barisan * , *X , … , W dibuang dari barisan jalan K, maka didapat jalan baru K :  B  yang mempunyai panjang lebih kecil dari panjang K. Apabila tidak ada titik yang berulang pada K , maka K adalah lintasan  B . Jika masih ada titik yang berulang, maka dilakukan kembali proses tersebut hingga diperoleh lintasan  B . Jadi, terbukti ada lintasan dari titik  ke titik . 0

Definisi 2.47 Jalur (trail) adalah jalan dengan semua garis dalam barisan adalah berbeda.

Contoh 2.48 Diberikan Graf seperti pada Contoh 2.38, yaitu jalan K :  ,  ,  ,  ,  K :  ,  ,  ,  ,  ,  ,  K :  ,  ,  ,  ,  ,  ,  maka K dan K merupakan suatu jalur sedangkan K bukan merupakan suatu jalur karena barisan K melewati garis yang sama yaitu garis  dan  .

Definisi 2.49 Misalkan  dan  adalah titik pada graf G. Titik  dikatakan terhubung dengan (connected to)  jika G mengandung suatu lintasan  B .

Definisi 2.50 Suatu Graf dikatakan terhubung (connected) jika untuk setiap dua titik dari graf G, selalu terdapat lintasan yang menghubungkan kedua titik tersebut.

21

Suatu graf tak-terhubung jika terdapat dua titik sedemikian sehingga tidak ada lintasan yang menghubungkan kedua titik.

Teorema 2.51 Suatu graf G tak-terhubung jika dan hanya jika himpunan titik  dapat dibagi menjadi dua himpunan bagian  dan  yang tidak kosong dan terpisah sedemikian sehingga tidak ada garis di G yang satu titik ujungnya berada di  dan titik ujung lainnya di  . Bukti: S Diketahui bahwa ada partisi  yaitu  dan  . Dimisalkan dua titik sembarang  dan  dari G, sedemikian sehingga  Y  dan  Y  . Tak ada lintasan yang dapat muncul antara titik  dan  , sedangkan Kebalikannya akan ada paling sedikit satu garis yang satu titik ujungnya di  dan titik ujung lainnya di  . Jadi, apabila partisi muncul maka  tak-terhubung. T Misalkan  merupakan graf tak-terhubung. Diketahui suatu titik  di . Misalkan  adalah himpunan semua titik yang dihubungkan oleh lintasan ke . Karena  tak-terhubung, berarti  tidak meliputi semua titik dari . Titik-titik sisanya akan membentuk suatu himpunan tidak kosong  . Tak ada titik di  yang dihubungkan dengan suatu titik di  oleh suatu garis. Terbukti. 0

Definisi 2.52 Subgraf  dari suatu graf  dikatakan komponen (component) dari  jika  merupakan subgraf terhubung maksimal dari .

22

Contoh 2.53 Diberikan suatu graf seperti pada Gambar 2.14

Gambar 2.14 Suatu Graf dengan tujuh komponen

Graf pada Gambar 2.14 mempunyai sebanyak tujuh komponen. Titik yang berdiri sendiri dihitung satu komponen karena merupakan salah satu subgraf terhubung maksimal.

Teorema 2.54 Jika suatu graf (terhubung atau tak-terhubung) mempunyai tepat dua titik yang berderajat ganjil, maka ada lintasan yang menghubungkan kedua titik tersebut. Bukti: Misalkan  merupakan graf dengan semua titiknya berderajat genap kecuali titik  dan . Dari Teorema 2.15, yang berlaku untuk setiap graf sehingga setiap komponen graf tak-terhubung tak akan mempunyai jumlah ganjil untuk titik yang berderajat ganjilnya. Oleh karena itu, pada graf , titik  dan  haruslah menjadi milik komponen yang sama dan itu berarti harus ada lintasan antara kedua titik tersebut. 0

Definisi 2.55 Siklus (cycle) adalah jalan tertutup (closed walk) dengan titik tidak berulang, kecuali titik awal sama dengan titik akhir. Dengan kata lain, siklus adalah lintasan yang tertutup.

Contoh 2.56 Diberikan Graf Petersen seperti pada Gambar 2.9, maka 1,2,3,4,5 dan 1Z , 3Z , 5Z , 2Z , 4Z , 1[ merupakan siklus pada graf tersebut.

23

Definisi 2.57 Sirkuit (circuit) adalah jalan tertutup (closed walk) dengan garis tidak berulang. Dengan kata lain, sirkuit adalah jalur yang tertutup.

Contoh 2.58 Diberikan Graf Petersen seperti pada Gambar 2.9, maka 1,2,3,4,5 dan 1Z , 3Z , 5Z , 2Z , 4Z , 1[ merupakan sirkuit graf tersebut.

Teorema 2.59 Jika sebuah graf G mengandung suatu sirkuit dari  ke , maka G mengandung suatu siklus dari  ke . Bukti: Misalkan \  M ,  ,  , … , * , * , *X , … , W , W , WX , WX , … , 4 , 4 Adalah sebuah sirkuit dari  ke  dengan   M  4 . Jika \ bukan siklus, maka *  W , untuk beberapa O V U V 9, sehingga didapat \ dengan sirkuit \ Z  M ,  ,  , … , * , * , WX , WX , … , 4 , 4 Jika \[ bukan siklus dari  ke , proses penghapusan titik yang berulang dilakukan kembali sehingga akhirnya akan didapat suatu siklus dari  ke . 0

2.6 Eulerian dan Hamiltonian Graf Eulerian muncul pada abad ke-18 dari masalah teka-teki jembatan Konigsberg yang diciptakan oleh bangsa Prusia yang merupakan penduduk kota Konigsberg (sekarang kota Kaliningrad, Rusia). Aliran sungai Pregel di Konigsberg mengapit dua pulau (Pulau C dan D) seperti tampak pada Gambar 2.15. Keempat bagian daratan dihubungkan satu sama lain oleh tujuh jembatan. Teka-teki penduduk kota tersebut adalah mengenai perjalanan yang melalui jembatan

24

tersebut hanya satu kali dan kembali ke tempat semula. Apakah hal tersebut mungkin?

Gambar 2.15 Jembatan Konigsberg

Ternyata persoalan teka-teki tersebut dapat direpresentasikan ke dalam bentuk graf seperti yang ditunjukkan pada Gambar 2.16.

Gambar 2.16 Graf Jembatan Konigsberg

Leonhard Euler membuktikan bahwa tidak mungkin melalui perjalanan demikian dalam makalahnya yang berjudul, “Solutio problematis ad geometriam situs pertinentis” pada tahun 1736. Model graf tersebut saat ini dikenal sebagai Graf Eulerian dan ia berhasil membuktikan syarat perlu dan cukup untuk menunjukkan suatu graf Eulerian.

Definisi 2.60 Suatu jalur antara dua titik yang berbeda pada suatu graf terhubung  disebut Jalur Eulerian (Eulerian trail) jika jalur tersebut

25

mengandung semua garis dari . Suatu graf dikatakan graf semi-Eulerian (semiEulerian) jika graf mempunyai suatu jalur Eulerian.

Definisi 2.61 Suatu sirkuit yang mengandung semua garis pada suatu graf disebut sirkuit Eulerian (Eulerian circuit).

Definisi 2.62 Suatu graf dikatakan Graf Eulerian (Eulerian graph) apabila graf tersebut mempunyai sirkuit Eulerian.

Contoh 2.63 Diberikan tiga buah Graf seperti pada Gambar 2.17

(a)

(b)

(c)

Gambar 2.17 (a) Graf Eulerian, (b) semi-Eulerian, (c) Graf bukan eulerian

Perhatikan bahwa graf pada Gambar 2.17 (a) merupakan Graf Eulerian dengan sirkuit Euleriannya adalah sebagai berikut:  ,  ,  ,  ,  , C ,  , ] ,  ,  , ] , C ,  Graf pada Gambar 2.17 (b) merupakan graf semi-Eulerian karena mempunyai jalur Eulerian, yaitu:  ,  ,  ,  ,  ,  , C ,  ,  , C ,  Sedangkan graf pada Gambar 2.17 (c) bukan graf Eulerian maupun semi-Eulerian karena tidak ada sirkuit Eulerian ataupun jalur Eulerian.

26

Sir William Rowan Hamilton (1805-1865) di tahun 1859 menciptakan permainan “all around the world”. Di dalam permainan tersebut, pemain memulai dari sembarang titik dan harus mencari rute pada dodekahedron yang melalui setiap titik sudut sekali dan hanya sekali. (Liu, 1995) Setiap titik pada dodekahedron mewakili suatu kota, misal London, New York, Delhi, Paris, dan lain-lain. Tujuan dari permainan yang diciptakan Hamiltonian ini adalah mengunjungi setiap kota tepat satu kali dan bisa kembali ke kota tempat awal mulai dengan tanpa mengunjungi kota yang sama lebih dari satu kali. Dodekahedron (Gambar 2.18(a)) adalah suatu segi banyak yang berbentu mirip dengan bola, namun setiap sisi dari dodekahedron berbentuk suatu segilima sama sisi. Jadi, pada seluruh permukaannya ada sejumlah dua puluh titik yang berbeda, tiga garis bertemu pada satu titik. Persoalan yang akan diselesaikan adalah berjalan sepanjang garis pada sisi-sisi dodekahedron dan melalui setiap titik pada permukaan dodekahedron tepat satu kali. (Slamet dan Makaliwe, 1991)

(a)

(b)

Gambar 2.18 (a) Dodekahedron dan (b) Graf dodekahedron

Definisi 2.64 Suatu lintasan antara dua titik berbeda pada suatu graf disebut lintasan Hamiltonian (Hamiltonian path) jika lintasan tersebut melewati setiap titik pada suatu graf.

27

Definisi 2.65

Suatu siklus yang melewati setiap titik pada graf tepat satu

kali disebut siklus Hamiltonian (Hamiltonian cycle). Dengan kata lain, lintasan Hamiltonian yang tertutup adalah siklus Hamiltonian.

Contoh 2.66 Diberikan persoalan Dodekahedron seperti telah disebutkan sebelumnya seperti yang terlihat pada Gambar 2.18(a). Untuk menyelesaikan persoalan tersebut, dodekahedron diproyeksikan pada bidang datar sedemikian sehingga membentuk seperti graf Gambar 2.18(b). Salah satu penyelesaian, yaitu terdapat siklus Hamiltonian seperti yang ditunjukkan pada Gambar (b) yaitu garis dicetak tebal hitam yang melalui setiap titik pada graf.

Definisi 2.67 Suatu graf dikatakan Graf Hamiltonian (Hamiltonian graph) apabila graf tersebut mempunyai siklus hamiltonian.

Contoh 2.68 Diberikan graf seperti pada Gambar berikut

(a)

(b)

(c)

(d)

Gambar 2.19 (a) Graf Eulerian sekaligus Hamiltonian, (b) Graf Eulerian bukan hamiltonian, (c) Graf Hamiltonian bukan Eulerian, (d) Graf bukan Hamiltonian maupun Eulerian

Perhatikan bahwa Graf pada

2.19(a) merupakan graf Eulerian sekaligus

Hamiltonian dengan sirkuit Euleriannya adalah  ,  ,  ,  ,  ,  , ] ,  , C , ] ,  , C , _1 28

dan siklus Hamiltoniannnya adalah  ,  , ] ,  ,  ,  , C ,  Perhatikan graf pada Gambar 2.19(b). Graf tersebut merupakan graf Eulerian namun bukan graf Hamiltonian. Sirkuit Euleriannya adalah  ,  ,  ,  ,  ,   Perhatikan bahwa graf pada Gambar 2.19(c) merupakan graf Hamiltonian, namun bukan merupakan graf Eulerian. Siklus Hamiltoniannya adalah _ , _ , _ , _ , _ , _ Perhatikan bahwa graf pada Gambar 2.19(d) bukan Graf Eulerian maupun hamiltonian. Jadi dapat disimpulkan bahwa tidak ada ciri-ciri yang menunjukkan adanya hubungan antara graf Hamiltonian dan graf Eulerian. Meskipun masalah penentuan keberadaan lintasan atau siklus Hamiltonian mempunyai kemiripan dengan masalah penentuan keberadaan jalur atau sirkuit Eulerian, namun sayangnya belum ditemukan syarat perlu dan cukup yang sederhana. (Liu, 1995)

2.7 Isomorfisma Graf Dalam berbagai bidang matematika, penting diketahui apakah dua objek yang sedang dihadapi itu sama atau berbeda. Sebagai contoh bilangan 2 dan

C 

dapat

dipandang sebagai dua bilangan yang bernilai sama namun tidak identik. Konsep tersebut dapat diterapkan pada dua buah graf.

Definisi 2.69 Graf G dan H dikatakan isomorfik jika terdapat korespondensi satu-satu fungsi f: VG b VH sedemikian sehingga uv Y EG jika dan hanya jika fufv Y H. Dengan kata lain, G isomorfik dengan H G c H jika pemetaan f mempertahankan kedekatan dua titik. Fungsi f disebut isomorfisma.

29

Contoh 2.70 Diberikan graf seperti pada Gambar 2.20

(a)

(b) Gambar 2.20 Graf yang Isomorfik

Graf seperti Gambar 2.20(a) isomorfik dengan graf seperti Gambar 2.20(b) karena terdapat isomorfisma d yang didefinisikan sebagai berikut d    d    d    d    d   

Contoh 2.71 Diberikan graf Petersen seperti pada Gambar 2.21 (a). Graf seperti pada Gambar 2.18 (b) dan (c) isomorfik dengan graf Petersen.

(a)

(b)

(c)

Gambar 2.21 (a) Graf Petersen, (b) Isomorfik graf Petersen, (c) Isomorfik graf Petersen

30

2.8 Komplemen Graf Pada bagian ini didefinisikan tentang komplemen dari suatu graf. contoh sederhana juga diberikan untuk memperjelas makna komplemen suatu graf.

Definisi 2.72 Komplemen (complement) dari Graf  ditulis e adalah Graf dengan e   dan  Y e jika dan hanya jika  f . Dengan kata lain Komplemen e dari Graf G adalah setiap titik VG dan garis e adalah seluruh garis graf lengkap kecuali garis G.

Contoh 2.73 Diberikan graf seperti pada Gambar 2.22

Gambar 2.22 Graf dan Komplemennya

Perhatikan bahwa banyaknya titik pada komplemen dari suatu graf tetap berjumlah sama, sedangkan garis-garisnya berbeda. Kalau digabungkan graf menjadi graf lengkap.

2.9 Planaritas Pada bagian ini akan diperkenalkan pengertian graf planar dan graf bidang. Contoh-contoh diberikan untuk memperjelas definisi. Dibahas juga pengertian derajat suatu permukaan graf planar dan diakhiri dengan pembahasan suatu sifat yang menghubungkan jumlah derajat dengan banyaknya garis pada suatu graf.

31

Definisi 2.74 Suatu graf dikatakan planar (planar) jika graf tersebut dapat digambarkan pada bidang datar sedemikian sehingga tidak ada dua garis yang bersilangan. Contoh 2.75 Graf  merupakan graf planar (Gambar 2.23) . Graf  Planar karena dapat digambar ulang pada bidang sedemikian sehingga menjadi graf yang tidak mempunyai garis yang bersilangan (berpotongan)

Gambar 2.23 Graf Planar >g

Definisi 2.76 Graf Bidang (Plane graph) adalah Graf Planar yang digambarkan pada bidang datar sedemikian sehingga tidak ada garis yang bersilangan. Contoh 2.77 Graf pada gambar merupakan graf planar karena dapat digambarkan pada bidang sedemikian sehingga tidak ada garis yang bersilangan, seperti yang terlihat pada gambar. Graf pada gambar (a) merupakan Graf planar, sedangkan Gambar (b) dan (c) merupakan Graf Bidang.

(a)

(b) Gambar 2.24 (a) Graf Planar serta (b) dan (c) Graf Bidang

32

(c)

Definisi 2.78 Jika G graf planar, maka setiap bidang pada G terbagi dalam daerah-daerah yang disebut permukaan (faces). Satu dari permukaan tersebut tak terbatas dan disebut permukaan tak terbatas (infinite face), sisanya dikatakan permukaan terbatas (finite face). Permukaan dinotasikan dengan d.

Contoh 2.79 Diberikan graf seperti pada Gambar 2.25

Gambar 2.25 Permukaan graf planar

Perhatikan bahwa terdapat empat permukaan, yaitu d , d , d , d . Permukaan d dibatasi oleh siklus  ,  ,  ,  . Permukaan d , d , d merupakan permukaan terbatas, sedangkan d merupakan permukaan tak terbatas.

Definisi 2.80 Jika d adalah permukaan graf planar, maka derajat permukaan (degree of face) graf planar dinotasikan () d adalah banyaknya garis yang membentuk jalan yang membatasi area permukaan d.

33

Contoh 2.81 Diketahui graf seperti pada Gambar 2.27. Berarti deg d  deg d  deg d  3, sedangkan deg d  6 dan deg d  7.

Gambar 2.26 Derajat Permukaan Graf

Teorema 2.82 Jumlah derajat permukaan dari suatu Graf Bidang adalah sama dengan dua kali jumlah garisnya. Bukti: Setiap garis  dari suatu graf bidang akan membatasi dua permukaan atau termuat dalam sebuah permukaan, dan akan muncul dua kali dalam suatu Graf.0

2.10 Permutasi dan grup permutasi Pada bagian ini akan diberikan pengertian Permutasi, grup permutasi. Sifat yang terkait dengan permutasi juga dibahas.

Definisi 2.83 Permutasi dari himpunan A adalah fungsi dari A ke A yang sekaligus satu-satu (one-to-one) dan pada (onto). Dengan perkataan lain, permutasi A adalah fungsi korespondensi satu-satu (bijektif) dari A ke A.

34

j  1, 2, 3, 4, 5 . d adalah permutasi sebagai

Contoh 2.84 Diberikan berikut: d1  4

1→ 4

d2  2

2→2 3→5 4→3 5 →1

d3  5 atau d4  3 d5  1

d ditulis dalam notasi baku sebagai berikut :

 1 2 3 4 5  f =   4 2 5 3 1 Teorema 2.85 Jika fungsi d dan ) permutasi pada A, maka d k ) juga permutasi 1−1 pada A. ( f o g : A → A)

Bukti: •

Jika l  l , maka d k )l  = d)l 

karena ) fungsi maka d)l   d)l   d k )l . •

Jika d k )l   d k )l , maka d)l   d)l 

karena d fungsi satu-satu maka )l   )l  karena ) fungsi satu-satu maka l  l •

Jadi d k ) adalah fungsi satu-satu pada A

Jika m Y j, maka ada 1 Y j sedemikian sehingga d1   m (d onto) dan ada 1 Y j sedemikian sehingga )1   1 () onto). Sehingga jika m Y j maka ada 1 Y j sedemikian sehingga d)1   d k )1   m. Jadi d k ) adalah fungsi onto pada A ∴

1−1 f o g : A → A

0

35

Contoh 2.86 Misalkan f =  1 2 4 2   1 2 3 4 5 1   Maka d k ) =   4 2 5 3 1 3 sehingga

3 4 5  dan  5 3 1  2 3 4 5  5 4 2 1 

1 2 3 4 5  g =  3 5 4 2 1

d)1  d)1  d3  5 d k )5  d)5  d1  4, dst.

1 2 3 4 5  Jadi didapat d k ) =  5 1 3 2 4 Teorema 2.87 Diberikan A ≠ φ , dan SA adalah koleksi semua permutasi pada j. Maka SA merupakan suatu grup terhadap pergandaan permutasi. Bukti: Ada tiga aksioma harus dipenuhi suatu grup. Ambil sembarang d, ), dan o Y SA. 1. Aksioma assosiatif dipenuhi, sebab Jika l Y j, maka berlaku pd)oql  d)ol  d)ol  d)ol  pd)oql Jadi, d)o  d)o, r d, ), o Y SA. 2. Aksioma ada elemen identitas dipenuhi, sebab: permutasi O sedemikian sehingga Ol  l, rl Y j, jelas merupakan elemen identitas dalam SA. 3. Setiap d Y SA mempunyai invers dipenuhi, sebab: Jika didefinisikan d  dengan d  l  l’ Y j, dengan sifat dl’  l Y j, maka d  Y SA . Adanya tepat satu elemen l’ demikian adalah akibat dari kenyataan bahwa, sebagai fungsi, d adalah sekaligus satu-satu dan onto, dan jelas bahwa : Ol  l  dl’  dd  l  dd  l, rl Y j

36

dan juga Ol’  l’  d  l  d  dl’  d B 1dl’, rl’ Y j sehingga: dd   d  d  O Dari 1, 2, dan 3, maka Fs adalah grup. 0

Dari teorema dapat didefinisikan pengertian grup permutasi dari himpunan A yang ternyata membentuk grup atas fungsi komposisi.

Definisi 2.88 Grup permutasi dari himpunan A adalah himpunan permutasi A yang membentuk suatu grup atas fungsi komposisi.

Definisi 2.89 Diberikan A adalah himpunan berhingga 1,2,3, … , 9. Grup semua permutasi untuk A disebut grup simetrik (symetric group) pada 9 huruf/angka, dan ditunjukkan dengan F4 . Perhatikan bahwa F4 mempunyai 9!  99 B 19 B 2 … 321.

Contoh 2.90 Contoh yang menarik grup S3 dari 3! = 6 elemen. Diberikan himpunan j  1,2,3. Didaftar permutasi-permutasi untuk A sebagai berikut:

1 2 3 

1 2 3 

, β1 =   α o =  1 2 3  1 3 2   1 2 3 1 , β 2 =  3  2 3 1 1 2 3 1 , β 3 =  α 2 =  3 1 2 2

α1 = 

37

2 3  2 1  2 3  1 3 

Dapat ditunjukkan melalui tabel bahwa penggandaan komposisi adalah benar.

Tabel 2.1 Tabel penggandaan enggandaan komposisi grup simetrik berelemen tiga

Perhatikan bahwa grup simetrik tersebut di atas tidaklah komutatif dan ini salah satu contoh grup berhingga yang tidak komutatif.

38

BAB III SIFAT-SIFAT GRAF PETERSEN

Pada bagian ini akan dilihat sifat-sifat yang berkaitan dengan Graf petersen. Pembahasan akan dimulai dari menunjukkan bahwa graf Petersen tidak Eulerian, kemudian ditunjukkan pula graf Petersen tidak planar. Pada pembahasan selanjutnya akan ditunjukkan bahwa graf Petersen tidak terfaktor-1. Selanjutnya berkaitan dengan automorfisma graf, graf Petersen isomorfik dengan graf lengkap berelemen lima, kemudian dapat dibuktikan bahwa graf Petersen transitif-titik dan transitif-garis. Graf Petersen dapat dilihat sebagai suatu graf garis dan ternyata graf Petersen tidak bipartit. Akhir pembahasan akan ditunjukkan melalui dua cara bahwa graf Petersen tidak Hamiltonian, dan ditutup dengan ditunjukkannya graf Petersen sebagai graf Hipohamiltonian terkecil berderajat sepuluh.

3.1 Graf Petersen dan Eulerian Pada bagian ini akan ditunjukkan bahwa graf Petersen bukan Graf Eulerian dengan memanfaatkan Teorema 3.2. Pembahasan diawali dengan pembuktian Teorema 3.1 yang telah dibuktikan oleh Leonhard Euler ketika menyelesaikan teka-teki jembatan Konigsberg. Teorema 3.1 Diketahui
graf terhubung. Suatu Graf
memiliki jalur Eulerian jika dan hanya jika semua titik pada graf berderajat genap, kecuali dua titik yang berderajat ganjil. Bukti:  Diketahui bahwa suatu
memiliki jalur Eulerian. Jika suatu jalur Eulerian ditelusuri akan terlihat bahwa setiap kali jalur ini bertemu dengan sebuah titik, ia 39

akan melalui dua garis yang insiden dengan titik tersebut dan belum pernah ditelusuri sebelumnya. Jadi, kecuali untuk kedua titik di kedua ujung jalur, derajat titik di dalam graf pasti genap. Jika kedua titik di kedua ujung jalur Eulerian ini berbeda, hanya keduanyalah yang merupakan titik berderajat ganjil. Jika keduanya berimpitan (titik ujungnya sama), berarti semua titik berderajat genap dan jalur Eulerian tersebut berupa sirkuit Eulerian. Jadi, syarat perlu telah dibuktikan.  untuk membuktikan syarat cukupnya, akan dibangun suatu jalur Eulerian mulai dari salah satu dari dua titik yang berderajat ganjil dan akan menempuh semua garis graf sedemikian sehingga tidak ada garus yang ditelusuri lebih dari sekali. Untuk titik yang berderajat genap, bila jalur tersebut menuju (masuk) ke titik melalui sebuah garis, ia selalu bisa melanjutkan (meninggalkan) titik tersebut melalui rusuk yang lain yang belum ditelusuri. Oleh karenanya, ketika jalur yang dibangun tersebut berakhir, pasti sampai (diakhiri) ke titik berderajat ganjil lainnya. Jika semua garis di dalam graf itu ditelusuri dengan cara seperti ini, akan diperoleh sebuah jalur Eulerian. Jika tidak semua garis di dalam graf itu tertelusuri, garis-garis yang tertelusuri itu akan dibuang dan akan diperoleh subgraf yang terbentuk oleh garis-garis yang tersisa. Semua titik di dalam subraf tersebut berderajat genap. Lebih lanjut, subgraf tersebut pasti menyinggung jalur yang telah dilalui di satu atau lebih titik karena graf diketahui terhubung. Dimulai dari salah satu titik pada subgraf, sekali lagi akan dapat dibuat sebuah jalur yang melalui garis-garis tersebut. Karena semua titik berderajat genap, jalur pada akhirnya akan kembali ke titik awal dimulainya jalur. Dengan demikian, jalur pada subgraf dapat digabung dengan jalur yang telah dihasilkan sebelumnya untuk mendapatkan jalur yang bermula dan berakhir di

40

kedua titik yang berderajat ganjil. Jika diperlukan, cara ini dapat diulang hingga didapat suatu lintasan yang melalui semua garis di dalam graf tersebut.  Akibat dari Teorema 3.1 adalah Teorema 3.2 yang menunjukkan syarat perlu dan cukup suatu graf dikatakan graf Eulerian.

Teorema 3.2 Diberikan suatu graf G yang terhubung. Graf G Eulerian jika dan hanya jika setiap titik G berderajat genap. Bukti:  Diketahui bahwa graf G Eulerian berarti G mempunyai suatu sirkuit Eulerian. Dalam melakukan penelusuran terhadap sirkuit Eulerian tersebut, maka pada setiap titik yang dilalui harus dilakukan dua hal berikut. Pertama adalah bahwa titik pada graf akan dikunjungi melalui suatu garis tertentu, kemudian titik tersebut ditinggalkan dengan melalui salah satu garis yang lain. Oleh karena setiap garis dari graf G adalah bagian dari sirkuit Eulerian, maka terlihat bahwa setiap titik G mempunyai derajat genap (setiap mengunjungi suatu titik, derajat dari titik tersebut bertambah dengan kelipatan dua, yaitu satu garis yang masuk ke titik dan satu garis yang ke luar dari titik).  Diketahui bahwa graf G mempunyai titik berderajat genap. Diambil sembarang titik  dari graf G dan misalkan  adalah jalur terpanjang yang dapat

dibuat dari titik  ke titik lain . Sekarang dimisalkan bahwa  , dengan

demikian titik akan insiden dengan sebanyak ganjil garis pada . Oleh karena diketahui bahwa setiap titik mempunyai derajat genap, maka pasti ada satu garis lagi yang belum digunakan yang insiden dengan suatu titik . Hal tersebut berarti

ada jalur yang lebih panjang dari , sehingga bertentangan dengan pemisalan

bahwa  adalah jalur terpanjang. Jadi, pemisalan bahwa titik  tidak benar.

41

Dengan demikian jelas bahwa titik  dan itu berarti  merupakan suatu sirkuit. Selanjutnya masih harus ditunjukkan bahwa setiap garis dari G berada di dalam . Bila hal ini dipenuhi, maka sirkuit  merupakan sirkuit Eulerian dalam G dan bukti selesai. Sebaliknya, apabila tidak dipenuhi maka harus ada sekurang-kurangnya satu garis lain (katakan sebagai garis ) dari G yang tidak termasuk dalam . Oleh karena G

adalah graf terhubung, maka garis  tersebut dapat dipilih sedemikian sehingga

garis  insiden dengan sebuah titik  (yang dilalui oleh sirkuit ). Jadi, garis 

menghubungkan (insiden dengan) suatu titik  yang dilalui oleh sirkuit  dan suatu titik lain (mungkin juga dilalui oleh sirkuit ).

Sekarang dibentuk suatu graf baru G’ yang merupakan bagian dari graf G tanpa titik dan garis yang dialui . Oleh karena setiap titik G bertemu dengan sirkuit  sebanyak genap kali, dan karena diketahui bahwa setiap titik dari G mempunyai derajat genap, maka dengan demikian dapat disimpulkan bahwa setiap titik pada G’ akan mempunyai derajat genap. Perhatikan sekarang subgraf G’ yang terhubung. Dengan cara seperti pada graf G, maka dapat dicari suatu sirkuit dalam G, yang dimulai dari titik  dan kembali ke

titik , yaitu suatu sirkuit . Bila sirkuit  digabungkan dengan sirkuit , maka diperoleh suatu sirkuit yang lebih panjang daripada sirkuit , tetapi hal ini

bertentangan dengan kenyataan bahwa sirkuit  adalah yang terpanjang. Jadi,

pemisalan bahwa ada garis  lain yang tidak termasuk dalam  adalah salah,

berarti terbukti bahwa  adalah sirkuit Euler.  Teorema 3.3 Graf Petersen tidak Eulerian.

Bukti: Setiap titik pada Graf Petersen berderajat tiga. Sehingga berdasarkan Teorema 3.2, Graf Petersen tidak Eulerian.  42

3.2 Graf Petersen dan Planaritas Pada bagian ini akan ditunjukkan bahwa graf Petersen tidak planar dengan memanfaatkan dasar Teorema yang diberikan Euler dan dikenal sebagai Teorema Euler (Teorema 3.4). Teorema 3.4 (Teorema Euler) Jika G adalah graf planar terhubung dengan , 

dan  berturut-turut menyatakan banyaknya titik, garis dan permukaan dari graf

G, maka graf memenuhi      2. Bukti: Teorema tersebut akan dibuktikan dengan induksi matematika. Teorema pasti benar untuk  0 dengan  1 (G terhubung) dan  1 (yaitu permukaan takhingga). Andaikan teorema benar untuk G dengan   1 garis, persoalan selesai jika dapat dibuktikan berlakunya teorema untuk G dengan banyak garis sama dengan m. Kemudian tambahkan pada G satu garis baru yaitu garis , maka berlaku salah satu: (i)

Jika  merupakan gelung, maka timbul permukaan baru tetapi banyaknya titik tidak berubah

(ii)

Jika  hanya insiden dengan salah satu titik, maka dalam hal ini harus ditambahkan dengan satu titik lagi. Jadi banyaknya titik dari G bertambah satu, tetapi banyak permukaan tetap.

(iii)

Jika  menghubungkan dua titik yang berlainan dari G dan e tersebut mengakibatkan satu permukaan pecah menjadi dua permukaan, maka banyaknya permukaan dari G bertambah, tetapi banyaknya titik tetap.

Teorema benar untuk G dengan banyak garis sama dengan , maka terbukti.  43

Akibat 3.5

Jika G adalah graf terhubung planar dengan banyaknya titik

   3 dan banyaknya garis , maka

  3  6.

Bukti: Diketahui bahwa permukaan terbatas sekurang-kurangnya mempunyai tiga garis yang membatasi (derajat permukaan-terbatas sekurang-kurangnya tiga). Begitu pula sebuah garis membatasi paling banyak dua permukaan. Jadi didapat, 2  3 atau



  .

Dengan mensubstitusikan      2 dari Teorema Euler didapat 2 

2  3

  3  6 Contoh 3.6



Diberikan graf !" . Graf !" tidak planar. Buktinya adalah dengan

memisalkan !" sebagai graf planar. Diketahui bahwa !" mempunyai lima titik

dan sepuluh garis. !" tidak memenuhi Akibat 3.5. Kontradiksi. Berarti !" tidak

planar.

Akibat 3.7

Jika G graf sederhana terhubung planar dengan banyaknya titik

   3 dan banyaknya garis  serta tidak ada segitiga, maka   2  4.

Bukti: Diketahui bahwa permukaan terbatas sekurang-kurangnya mempunyai empat garis yang membatasi karena derajat permukaan terbatas sekurang-kurangnya tiga dan tidak terdapat segitiga. Begitu pula sebuah garis membatasi paling banyak dua permukaan, sehingga didapat,

44

2  4 $

atau    . 

Dengan mensubstitusikan      2 dari Teorema Euler didapat 2 

1  2

  2  4 Contoh 3.8 Oleh sebab !

!

,

tidak planar. Untuk membuktikannya, dimisalkan !

,

mempunyai enam titik dan sembilan garis dan tanpa segitiga,

maka tidak memenuhi Akibat 3.7 sehingga kontradiksi. Jadi, !

,

,

planar.

tidak planar.

Teorema 3.9 Jika G graf sederhana terhubung planar dengan banyaknya titik n (n ≥ 3) dan banyaknya garis m dengan siklus terpendeknya mempunyai panjang lima, maka "

    2. Bukti: Diketahui bahwa permukaan terbatas sekurang-kurangnya mempunyai lima garis yang membatasi karena derajat permukaan terbatas sekurang-kurangnya tiga dan diketahui bahwa siklus terpendeknya mempunyai panjang lima. Begitu pula sebuah garis membatasi paling banyak dua permukaan, sehingga didapat, 2  5 

atau "    .

Dengan mensubstitusikan      2 dari Teorema Euler didapat 2 

2  5

5     2 3

45

Teorema 3.10 Graf Petersen tidak Planar. Bukti: Misalkan Graf Petersen planar. Diketahui bahwa Graf Petersen tidak mengandung segitiga atau siklus dengan pajang empat, maka Akibat 3.5 dan Akibat 3.7 tidak dapat digunakan. Oleh karena Graf Petersen mempunyai sepuluh titik dan lima belas garis, maka tidak memenuhi Teorema 3.9. Kontradiksi. Jadi, terbukti bahwa Graf Petersen tidak planar.  3.3 Graf Petersen dan Faktorisasi Pada bagian ini, akan dibuktikan bahwa graf Petersen tidak terfaktor-1. Pembahasan akan dimulai dengan pengertian suatu faktor dari graf, faktorisasi suatu graf dan graf yang terfaktor. Contoh diberikan untuk memperjelas definisi yang dimaksud.

Definisi 3.11 Suatu Faktor (factor) dari graf G adalah subgraf perentang dari G yang tidak seluruhnya tak-terhubung.

Definisi 3.12 Diketahui bahwa
$ ,
 , … ,
'

merupakan pasangan subgraf perentang terpisah-garis (edge-disjoint) dari
sedemikian sehingga ('*+$ )
* )
,

maka
dikatakan terfaktor (factorable) atau difaktor menjadi subgraf-subgraf

(factored into subgraphs) atau faktor-faktor (factors)
$ ,
 , … ,
' dan ditulis



$ ,
 , … ,
' . Ekspresi gabungan tersebut disebut faktorisasi (factorization) dari
menjadi faktor-faktor
$ ,
 , … ,
' .

46

Definisi 3.13 Suatu faktor yang teratur-r dari dari graf G dikatakan sebagai faktor-r (r-factor) dari G. Contoh 3.14 Diberikan graf
- seperti Gambar 3.1 (a). Gambar 3.1 (b)

merupakan contoh faktorisasi graf
- yang terdiri dari dua faktor-2 dengan kedua faktor tersebut tidak isomorfik. 1

2

6

5

3

4

(a) 1

1

2

6

5

5

3

6

2

3

4

4

(b) Gambar 3.1 Graf dan Faktorisasinya

Teorema 3.15 Graf Petersen dapat dipartisi menjadi suatu faktor-1 dan suatu faktor-2. Bukti: Graf Petersen terdiri dari lima belas garis, yaitu .12, 23, 34, 45, 51, 1’3’, 2’4’, 3’5’, 1’4’, 5’2’, 11’, 22’, 33’, 44’, 55’/ 47

Garis tersebut dapat dipartisi menjadi lima faktor-1 dan dua faktor-2. Garis-garis {11’, 22’, 33’, 44’, 55’/ 10 , 30 , 50 , 20 , 40

adalah

faktor-1

sedangkan

siklus

1,2,3,4,5

dan

merupakan faktor-2 graf Petersen. Untuk memperjelas,

perhatikan Gambar 3.2. Garis putus-putus pada gambar merupakan faktor-1 sedangkan garis sisanya membentuk dua buah faktor-2 (siklus). 

1

1' 5 2 2'

5' 3'

4'

3

4

Gambar 3.2 Partisi Graf Petersen menjadi faktor-1 dan faktor-2

Definisi 3.16 Graf G dikatakan terfaktor-r (r-factorable) jika terdapat suatu faktorisasi dari graf G menjadi faktor-r, sedangkan gabungannya dikatakan sebagai faktorisasi-r (r-facrtorization).

48

Contoh 3.17 Diberikan graf !

,

dan !" berturut-turut seperti yang ditunjukkan

oleh Gambar 3.3 (a) dan Gambar 3.4 (a). Graf-graf tersebut dapat difaktorisasi berturut-turut menjadi suatu faktorisasi-1 (Gambar 3.3 (b)) dan faktorisasi-2 (Gambar 3.34(b)). 1

4

2

5

3

6

(a) 1

4

1

4

2

5

2

5

3

6

3

6

1

4

2

5

3

6

(b) Gambar 3.3 (a) Graf 12,2 dan (b) faktorisasi-1 dari Graf 12,2

49

1

5 2

3

4

(a) 1

1

5

5

2

4

2

3

4

3

(b) Gambar 3.4 (a) Graf 13 dan (b) faktorisasi-2 dari 13

Teorema 3.18 Graf Petersen tidak terfaktor-1. Bukti: Diketahui bahwa Graf Petersen mempunyai lima belas garis. Misal titik 1,2,3,4,5 adalah titik-titik luar (perhatikan gambar). Andaikan Graf Petersen terfaktor-1, maka graf akan mempunyai tiga faktor-1, yaitu 4$ , 4 , 4 dengan masing-masing

mempunyai lima garis. Karena titik-titik 1,2,3,4,5 merupakan siklus dengan

panjang lima, maka siklus tersebut tidak dapat didekomposisikan ke dalam dua buah faktor-1, sehingga ketiga faktor tersebut harus mempunyai paling sedikit satu garis pada siklus tersebut. Berarti akan ada satu faktor-1, katakanlah 4$ yang mempunyai tepat satu garis di

siklus tersebut. Garis tersebut disebut dengan  dan ditunjukkan pada gambar.

50

Karena setiap titik harus insiden dengan tepat satu garis di 4$ , maka garis

11’,22’,55’ haruslah di 4$ . Satu garis yang sisanya akan menghubungkannya

dengan titik lain dan ada titik dengan dua garis insiden dengannya. Kontradiksi. Jadi, terbukti Graf Petersen tidak terfaktor-1.  1

1'

5 5'

2

2'

4'

3' e 3

4

Gambar 3.5 Graf Petersen tidak terfaktor-1

3.4 Graf Petersen dan Grup Automorfisma Pada bagian ini akan dibuktikan bahwa automorfisma graf Petersen merupakan grup simetrik pada lima elemen. Pembahasan akan diawali dengan pengertian automorfisma, kemudian grup automorfisma dan di bagian akhir akan dibuktikan bahwa automorfisma graf Petersen isomorfik dengan grup simetrik berelemen lima. Definisi 3.19 Automorfisma 5 dari suatu graf
adalah pemetaan 1-1 dari

himpunan titik-titik G onto dirinya sendiri dengan sifat bahwa 5 dan 5  berdekatan jika dan hanya jika  dan berdekatan.

51

Definisi automorfisma 5 dari suatu graf tersebut dapat juga dikatakan secara

lain, yaitu: Automorfisma 5 dari graf
adalah suatu isomorfisma
ke dirinya

sendiri (Harary, 1969). Jadi, setiap automorfisma dari
adalah permutasi dari

himpunan titik-titik 6 yang mempertahankan (mengawetkan) kedekatan. VP .1, 2, 3, 4, 5, 1’, 2’, 3’, 4’, 5’/

Contoh 3.20 Misalkan

dan

5

adalah

pemetaan dari titik-titik pada Graf Petersen P ke dirinya sendiri, yaitu : 6: ;

6: sedemikian sehingga 1 2

1 2

2 3

2 3

3 4

3 4

4 5

5 1

4 5

5 1

adalah suatu automorfisma dari P (Gambar 3.6).

1

5

5' 4

1

1'

4'

α

1' 5 2 2'

5'

3'

4'

2' 3

3

4

2

Gambar 3.6 Automorfisma < Graf Petersen

Begitu pula, pemetaan 5: 6: ; 6: sedemikian sehingga 51 1

51 1

52 4

52 4

53 2

53 2

52

54 5

54 5

3'

55 3

55 3

merupakan automorfisma dari P juga karena mengawetkan titik-titik yang berdekatan (Gambar 3.7). 1'

1

1'

1

3'

5

ϕ

2

4' 4

3

2'

5'

4' 4

2

3' 5'

3

5 2'

Gambar 3.7 Automorfisma > Graf Petersen

Teorema 3.21 Automorfisma-automorfisma dari graf
membentuk himpunan yang merupakan grup automorfisma dari
ditulis ?
. Bukti: Akan dibuktikan himpunan automorfisma .5, @, , … / dari suatu graf
onto

dirinya sendiri merupakan grup automorfisma ?
. Untuk membuktikannya, haruslah dipenuhi aksioma Grup, antara lain: 1. Tertutup Karena 5 suatu automorfisma maka $ dibawa ke elemen tunggal  oleh 5 dan sebaliknya  menentukan dengan tunggal $ . Dan, jika $ $

adalah garis maka menurut definisi automorfisma 5$ 5 $  pun

merupakan garis. Karena @ juga merupakan automorfisma, maka 

menentukan dengan tunggal  dan sebaliknya, dan jika  merupakan

garis, maka @ @  adalah garis. Selanjutnya @5 membawa $ ke

elemen tunggal  dan  ini menentukan dengan tunggal $ sehingga

53

karena $ $ merupakan garis maka @5  juga merupakan garis. Jadi, @5 merupakan automorfisma. 2. Assosiatif Sifat ini pasti berlaku untuk setiap elemen dalam ?
, sebab setiap automorfisma adalah suatu pemetaan, dan penggandaan pemetaan mempunyai sifat assosiatif. 3. Ada elemen netral Aksioma ini dapat ditunjukkan dengan adanya elemen netral, yaitu terdapat A B ?
, sehingga untuk setiap 5 B ?
 berlaku 5A A5 5. Jelas dipenuhi, sebab untuk setuap  B
berlaku 5A 5CAD 5, dan A5 AC5D 5. 4. Ada invers Karena 5 automorfisma, berarti bijektif sehingga berlaku 5 E$ 5 A 55 E$ , 5 E$ juga merupakan pemetaan dan menjadi invers dari 5. Sifat kedekatannya pun dibawa oleh 5 E$ . Karena ke empat aksioma grup tersebut dipenuhi untuk semua elemen dalam ?
, yaitu himpunan automorfisma .5, @, , … / dari graf sederhana onto dirinya sendiri, maka terbukti ?
 adalah grup, yaitu grup automorfisma.  Lemma 3.22 Jika F B ?
 dan G B 6
, maka HI FG HI G. Bukti: Jika G B )
, maka FGF B )
karena F B ?
. Oleh sebab itu,

deg FG  deg G. Setiap titik-titik yang berdekatan dengan FG didapat dari

titik-titik yang berdekatan dengan G yang dipetakan, karena F adalah suatu automorfisma. Sehingga derajat G sama dengan derajat FG. 

54

Lemma 3.23 Diketahui graf
dan komplemennya
M , maka ?
 ?
M . Bukti: Misalkan F B ?
. Karena F mengawetkan kedekatan titik, maka FG B )
jika dan hanya jika G B )
. Akibatnya, FG N )
jika dan hanya jika G N )
. Ekuivalen FG B )
M jika dan hanya jika G B )
M . Jadi, F B ?
M . Dengan cara yang sama, tukar
menjadi
M seperti di atas akan memberikan hasil yang sama.  Contoh 3.24 Diketahui Graf
.1,2,3,4/, .12,14,23,34/ dan akan dicari ?
, dan ?
M .

Komplemen
adalah
M .1,2,3,4/, .13,24/

Grup automorfisma ?
 .1234, 1234, 1423, 1324/

Grup automorfisma ?
M  .1234, 1234, 1423, 1324/ Jadi, didapat kesamaan bahwa ?
 ?
M .

Teorema 3.25 ?!'  merupakan Grup simetrik pada n elemen.

Bukti: Diketahui bahwa !' adalah Graf Lengkap dengan n titik. Automorfisma pada !' dapat disajikan sebagai berikut:

 1 2 3 4 P … 5Q 51 52 53 54

Dengan 5 adalah korespondensi satu-satu yang membawa  B
ke 5 B
.

Apabila titik 1 dan titik 2 berdekatan, maka 51 dan 52 berdekatan juga, begitu pula sebaliknya. Sementara itu, setiap permutasi pasti merupakan suatu automorfisma, sebab setiap dua titik adalah berdekatan. Dengan demikian, semua automorfisma dari !' ekuivalen dengan himpunan semua permutasi berorder . Karena Grup Simetrik adalah grup permutasi, maka 5!'  merupakan grup simetrik pada  elemen. 

55

Pengertian

kedekatan

(Adjacency)

dapat

digunakan

juga

untuk

mendefinisikan kedekatan pada garis. Suatu garis dikatakan berdekatan (adjacent) dengan garis lainnya apabila kedua garis tersebut insiden dengan titik yang sama.

Teorema 3.26 Diberikan Graf Petersen :. Maka ?: R S" . Bukti: Diberikan Graf Petersen seperti pada Gambar 3.8. Masing-masing garis diberi label angka 1,2,...5 seperti pada Gambar 3.8. Dapat terlihat bahwa dua garis berbeda  dan  mempunyai label yang berbeda jika dan hanya jika mereka berdekatan atau terdapat tiga garis yang berdekatan dengan keduanya.

v1 1

3

4 v6

v5 5

v10 1

5

2

4

2

v2

v7

3

2

5 4

v8

v9

3

1

v3

v4 Gambar 3.8 Graf Petersen

Akibatnya, jika  B ?: serta  dan  adalah garis-garis graf Petersen :, maka  dan  mempunyai label yang sama jika dan hanya jika  dan  mempunyai label yang sama. Begitu pula  menginduksi suatu elemen 4 dari

56

S" yang membawa A ke label , dengan  adalah garis manapun yang dilabeli A. Berarti 4  44 . Sekarang labeli setiap titik  dari graf Petersen dengan pasangan .A, T/ dengan A dan T adalah angka yang bukan merupakan label garis yang insiden dengan titik tersebut. Sebagai contoh, titik $ diberi label {2,5} karena tiga garis yang insiden dengannya adalah angka 1,3,4. Dapat ditunjukkan secara langsung bahwa untuk setiap himpunan bagian berelemen dua .A, T/ dari .1,2,3,4,5/ terdapat dengan tepat masing-masing satu, dan bahwa titik G dan  berdekatan jika dan hanya jika labelnya tidak ada yang sama (contohnya garis G labelnya tidak sama dengan garis-garis yang berdekatan dengannya). Dengan demikian terlihat bahwa untuk setiap @ B S" terdapat dengan unik  B ?: dengan 4 @, yang mengirim suatu titik berlabel .A, T/ ke titik berlabel .@A, @T/.

3.5 Transitif-titik dan Transitif-garis Pada bagian ini akan ditunjukkan bahwa graf Petersen transitif-titik dan transitif-garis. Pembahasan dimulai dari pengertian orbit dan stabilizer, kemudian dilanjutkan dengan pengertian grup permutasi transitif, graf transitiftitik, graf transitif-garis, dan diakhiri dengan pembuktian graf Petersen transitiftitik dan transitif-garis.

Definisi 3.27 Diketahui U adalah grup permutasi atas himpunan A dan V B ?. UW . B U: V V/ dikatakan sebagai stabilizer dari V dan UV . V: B U/ adalah orbit dari V pada U.

57

Contoh 3.28 Diberikan permutasi sebagai berikut

1 2 3 4 5 6 7 8

 σ =  3 8 6 7 4 1 5 2 Berarti

1 → 3 → 6 → 1 → 3 → 6 → 1L 2 → 8 → 2 → 8 → 2L 4 → 7 → 5 → 4 → 7 → 5L Sehingga orbit-orbitnya adalah . 1 ,3 ,6 / , . 2 ,8 / , . 4 ,5 ,7 / Definisi 3.29 Grup permutasi dikatakan transitif (transitive) jika UV ? untuk suatu V B ?, dengan A suatu himpunan.

Definisi 3.30 Suatu graf dikatakan graf transitif-titik (vertex-transitive) jika ?
 transitif. Teorema 3.31 Graf Petersen merupakan graf transitif-titik. Bukti: Diberikan graf Petersen seperti pada Gambar 3.9. Diketahui bahwa $

1234510 20 30 40 50 

dan

 110 240 530 320 450 

B ?:.

Dengan

melakukan penggandaan terhadap $ yaitu $ , $  , $ , … , $ " berturut-turut didapat

orbit

dari

1

adalah

.1,2,3,4,5/ Z Γ1,

sedangkan

 ,  $ ,  $  ,  $ ,  $ - berturut-turut akan didapat orbit dari 1, yaitu

.10 , 20 , 30 , 40 , 50 / Z Γ1.

Jadi, orbit dari 1 yaitu Γ1 .1,2,3,4,5,10 , 20 , 30 , 40 , 50 / 6:. Akibatnya Graf Petersen transitif-titik. 

58

1

1' 5 2 2'

5' 3'

4'

3

4 Gambar 3.9 Graf Petersen P

Suatu Graf G adalah isomorfik-garis dengan Graf H jika terdapat korespondensi satu-satu fungsi f: EG ; EH sedemikian sehingga garis x dan y di G berdekatan jika dan hanya jika fx dan fy berdekatan di H. Dengan kata lain, G isomorfik garis dengan H jika pemetaan f mempertahankan kedekatan dua garis. Fungsi f disebut isomorfisma garis. Automorfisma garis dari G dinotasikan ?a 
 adalah suatu isomorfisma garis ke dirinya sendiri.

Definisi 3.32 Graf G dikatakan transitif-garis (edge-transitive) jika untuk setiap $ ,  B )
, terdapat F B ?a 
 sedemikian sehingga F$   .

Teorema 3.33 Graf Petersen merupakan graf transitif-garis. Bukti: Perhatikan graf Petersen (Gambar 3.9). Misakan

59

? .12,23,34,45,51/, b .110 , 220 , 330 , 440 , 550 /

c .10 30 , 20 40 , 30 50 , 40 10 , 50 20 /

Jika  B ?
 maka  mengawetkan garis AT ke AT. Akibatnya  menyebabkan  a B ?a 
.

Dengan operasi penggandaan dari $ (Lihat Bukti Teorema 3.31) yang

mengawetkan titik, berarti setiap anggota ? diawetkan ke anggota lain pada ?.

Cara yang sama dapat diterapkan untuk anggota b dan c.

Operasi penggandaan  akan mengawetkan setiap anggota ? ke anggota c.

Terakhir  210 340 20 30  akan mengawetkan beberapa anggota b ke ?, beberapa anggota b ke C dan b ke 55.

Dari $ ,  ,  atau penggandaan-penggandaan mereka, akan mengawetkan $ ke  untuk setiap $ ,  B ):. Jadi, Graf Petersen transitif-garis.  3.6 Graf Garis dan Bipartit Pada subab ini, akan diperlihatkan bahwa graf Petersen dapat dipandang sebagai komplemen dari suatu graf garis dan graf Petersen bukan graf bipartit. Dimulai dari pengertian graf garis kemudian dilanjutkan dengan contoh, kemudian akan dibuktikan bahwa graf Petersen merupakan komplemen graf garis dari !" . Dilanjutkan dengan sifat yang berkaitan dengan graf bipartit dan diakhiri dengan menunjukkan bahwa graf Petersen tidak bipartit. Definisi 3.34 Graf garis (line graph)
, dinotasikan d
, adalah graf dengan

6d
 )
dan memenuhi ketentuan bahwa dua titik di d
 berdekatan jika dan hanya jika kesesuaiannya dengan garis-garis di G juga berdekatan.

60

Contoh 3.35 Diberikan graf
$ dan
 seperti pada Gambar 3.10 (a) dan (c). Maka graf garis d
$  dan d
  berturut-turut ditunjukkan oleh Gambar 3.10 (b) dan (d). Perhatikan bahwa garis pada Graf
$ menjadi titik pada graf garis d
$ . Begitu pula garis pada graf
 yang berjumlah lima menjadi titik berjumlah lima pada graf garisnya d
 .

(a)

(b)

(c)

(d)

Gambar 3.10 Graf dan Graf Garisnya

eeeeeeee Teorema 3.36 Graf Petersen P adalah d! " . Bukti: Graf !" dapat dilihat pada Gambar 3.4 (a) dengan lima titik berlabel 1,2,3,4,5. Dimisalkan  adalah garis yang menghubungkan titik G dan titik  pada graf. Berarti titik G insiden dengan tiga garis selain garis . Begitu pula titik  insiden dengan tiga garis selain garis . Jadi, graf garis dari f" , yaitu d!"  akan mempunyai sepuluh titik dan teratur-6. Oleh sebab itu, komplemennya adalah graf yang teratur-3 dengan sepuluh titik.

61

Pada graf garis d!" , titik 1 berdekatan dengan titik 3,4,10,7,8,9 sehingga komplemen titik 1 menjadi berdekatan dengan 2,5,6. Begitu seterusnya untuk titik 2,3,...,10 yang akan diberikan pada tabel dibawah eeeeeeee ini (Lihat Tabel 3.1). Jadi, terbukti bahwa d! "  :.  eeeeeeee Tabel 3.1 Kedekatan titik pada g13  dan g1 3

Titik d!" 

d!" 

eeeeeeee d! "

1

3,4,7,8,9,10

2,5,6

2

4,5,6,8,9,10

1,3,7

3

1,5,6,7,9,10

2,4,8

4

1,2,6,7,8,10

3,5,9

5

2,3,6,7,8,9

1,4,10

6

2,3,4,5,7,10

1,8,9

7

1,3,4,5,6,8

2,9,10

8

1,2,4,5,7,9

3,6,10

9

1,2,3,5,8,10

4,6,7

10

1,2,3,4,6,9

5,7,8

Berikut akan ditunjukkan bahwa graf Petersen bukan merupakan graf Bipartit dengan memanfaatkan sifat yang berkaitan dengan graf Bipartit. Teorema 3.37 Suatu graf G dikatakan bipartit jika dan hanya jika G mempunyai siklus genap. Bukti:  Misalkan G bipartit dengan partisinya (X,Y) dan misalkan c h , $ , … , i , h suatu siklus di G. Tanpa mengurangi perumuman, diasumsikan h B j. Dengan demikian, karena h $ B )
dan
bipartit maka 62

$ B k. Dengan cara yang sama maka  B j,  B k, - B j, … dst. Secara umum, * B j dan *l$ B k. Karena h B j dan i B k maka f 2A  1, untuk suatu A, maka c merupakan siklus genap. m Misalkan
graf terhubung yang tidak mempunyai siklus ganjil. Pilih sembarang titik G dan definisikan dua partisi j, k dan 6
sebagai berikut: j .V B 6
| HG, V Iop/ k . B 6
| HG,  IoTAq/ Sekarang akan dibuktikan bahwa j, k adalah bipartit dari
. Misalkan  dan adalah dua titik di j. Misalkan : adalah panjang lintasan u-v terpendek dan r adalah panjang lintasan u-w terpendek. Misalkan pula G* sebagai titik terakhir yang berada di : dan r. Karena : dan r merupakan lintasan terpendek maka barisan G  G* dari : dan r adalah lintasan G  G* terpendek yang panjangnya sama. Perhatikan bahwa : dan r memiliki panjang genap. Oleh karena itu, misalkan :$ adalah panjang barisan G$   dari : dan r$ adalah panjang barisan G$  dari r, keduanya memiliki kesamaan dalam hal panjang. :$ dan r$ bisa memiliki panjang genap atau ganjil sehingga :$E$ r$ yang merupakan lintasan   yang memiliki panjang genap. Jika  berdekatan dengan , :$E$ r$  adalah siklus dengan panjang ganjil, kontradiksi dengan pemisalan awal. Hal serupa berlaku untuk k. Jadi, tidak ada dua titik yang berdekatan di j, begitu pula tidak ada dua titik yang berdekatan di k. 

Teorema 3.38 Graf Petersen bukan graf bipartit. Bukti: Karena Graf Petersen mengandung siklus-5, yaitu 1,2,3,4,5 maka jelas graf Petersen bukan graf bipartit. 

63

3.7 Graf Petersen dan Hamiltonian Pada bagian ini akan dibuktikan bahwa graf Petersen tidak Hamilton melalui dua cara. Pembuktian pertama memanfaatkan sifat graf Petersen yang transitiftitik, dan cara kedua melalui titik konsitik.

Definisi 3.39 Himpunan garis-garis yang membuat suatu graf tak-terhubung disebut himpunan garis potong (edge cutset).

Teorema 3.40 Diberikan Graf Petersen :, maka Graf Petersen : tidak Hamiltonian. Bukti: Diberikan Graf Petersen P seperti pada Gambar 3.9. Misalkan bahwa ? .12,23,34,45,51/ b .110 , 220 , 330 , 440 , 550 / c .10 30 , 20 40 , 40 50 , 40 10 , 50 20 / Merupakan himpunan bagian dari ):. Misalkan juga s merupakan siklus Hamiltonian dari graf Petersen. Diketahui bahwa b merupakan sebuah himpunan garis potong dari P. Dengan demikian, H haruslah menggunakan banyak garis sebanyak genap dari garis-garis b. Oleh sebab itu, s mempunyai dua atau empat garis (karena maksimal garis yang dimiliki b adalah lima garis). Karena graf Petersen transitif-garis, maka dapat diasumsikan bahwa 110 B )s. Maka salah satunya 12 atau 15 B )s. Dengan sifat simetri, tanpa kehilangan keumuman, dapat diasumsikan bahwa 12 B )s. Karena graf Petersen merupakan graf kubik, 15 N )s dan karena itu 45,550 B )s atau lainnya 5 tidak pada s.

64

Jika s menggunakan hanya dua garis b, yaitu 11 dan 550 maka 23,34 B )s begitu pula 20 40 , 20 50 , 30 10 , 35 dan 41. Akan tetapi keadaan ini memaksa dua titik (1’ dan 5’) mempunyai derajat tiga pada siklus s.

Akibatnya |)s t b| 4.

Dengan sifat simetri salah satu dari 220 , 440 B )s. Misalkan, tanpa kehilangan

keumuman, bahwa 440 B )s. Karena 34 N )s ini, memaksa 23 dan 33 menjadi garis dari s. Karena |)s t b| 4, 22 N )s dan akibatnya 20 40 , 20 50 B )s. Hal

ini berarti memaksa subsiklus 20 , 50 , 5, 4, 40 , 2’ pada s.

Oleh karena itu s tidaklah mungkin ada. Kontradiksi. Jadi, graf Petersen tidak

Hamiltonian. 

Pembuktian berikut menggunakan pengertian baru graf yaitu konsitik (concytic) yang diperkenalkan oleh Yanzhong Hu pada tahun 2010 melalui papernya, “New Proof of Some Properties about Petersen Graph” (Hu, 2010). Sebelum dibuktikan graf Petersen tidak Hamiltonian, akan dimulai dari definisi keliling suatu graf, titik konsitik, kemudian sifat yang terkait antara titik konsitik dan Hamiltonian suatu graf.

Definisi 3.41 Panjang dari siklus terpanjang suatu graf disebut keliling (circumference).

Definisi 3.42 Graf terhubung dikatakan sebagai titik konsitik (concytic points) jika semua titik pada suatu graf dapat digambarkan pada keliling yang sama dan memelihara kedekatan antara titik.

65

Teorema 3.43 Graf terhubung merupakan titik konsitik jika dan hanya jika graf tersebut graf Hamiltonian. Bukti: Diketahui
graf terhubung. Jika G graf Hamiltonian, maka mengandung suatu jalan tertutup atau siklus Hamiltonian. Dengan kata lain setiap titiknya dilewati (muncul) secara tepat satu sekali. Akibatnya, G adalah titik konsitik. Di sisi lain, jika G titik konsitik, maka kelilingnya adalah siklus hamiltonian G.  Teorema 3.44 Graf Petersen tidak Hamiltonian. Bukti: Untuk membuktikannya, awal-awal akan dideskripsikan melalui Gambar 3.11. Dimisalkan graf Petersen P Hamiltonian. Melalui Teorema 3.43, berarti graf Petersen adalah titik konsitik.

Gambar 3.11 Awal konstruksi titik konsitik

Sepuluh titik pada graf Petersen dibentuk keliling dan diberi label 1,2,3,4,5,6,7,8,9,0 yang berlawanan arah seperti pada Gambar (3.11)

66

Diketahui bahwa setiap titik pada graf Petersen mempunyai derajat tiga dan titik graf petersen simetris. Maka terdapat empat kemungkinan bahwa titik dapat dihubungkan dengan titik lainnya seperti pada Gambar 3.12 (a),(b),(c),(d). Karena panjang siklus terpendek graf Petersen adalah lima, kasus (a) dengan panjang siklus tiga sehingga tidak mungkin. Begitu pula dengan kasus (b) yang mempunyai siklus dengan panjang empat sehingga tidak mungkin. Untuk kasus (c) dan (d) dimungkinkan terjadi. Akan dibahas hanya kasus (d), karena kasus (c) dapat ditunjukkan dengan cara yang sama.

(a)

(b)

(c)

(d)

Gambar 3.12 Kemungkinan pertama titik konsitik Graf Petersen

67

Pada kasus (d), terdapat enam macam kemungkinan bahwa titik 2 dapat bergabung dengan titik lainnya (Gambar 3.13 H$ , H , H , H- , H" , Hu ). Pada kasus selain kasus H , siklus mempunyai panjang dibawah lima sehingga tidak mungkin.

vw 

vx 

vy 

v3 

Gambar 3.13 Kemungkinan lanjutan titik konsitik Graf Petersen

68

v2 

vz 

Pada kasus H  terdapat empat macam kemungkinan (Gambar 3.14 (a),(b),(c),(d)). Perhatikan bahwa pada semua kemungkinan tersebut, panjang siklus lebih kecil dari lima. Kontradiksi dengan panjang minimal siklus graf petersen adalah lima. Jadi, terbukti graf Petersen tidak Hamiltonian. 

(a)

(b)

(c)

(d)

Gambar 3.14 Kemungkinan akhir titik konsitik Graf Petersen

69

3.8 Graf Petersen dan hipohamiltonian Pada bagian ini, akan dibuktikan bahwa Graf Petersen merupakan graf khusus dan unik dalam kaitannya dengan graf hipohamiltonian. Pembahasan akan dimulai

dengan

pengertian

hipohamiltonian,

kemudian

sifat-sifat

graf

Hamiltonian dan diakhiri dengan dibuktikan bahwa Graf petersen merupakan satu-satunya graf hipohamiltonian dengan jumlah titik sepuluh dan graf hipohamiltonian terkecil.

Definisi 3.45 Graf
dikatakan graf hipohamiltonian (hypohamiltonian) Jika graf
bukan Hamiltonian dan jika
  hamiltonian untuk setiap  B )
.

Lemma 3.46 Jika G hipohamiltonian, maka banyaknya titik n ≥ 3. Bukti: Untuk membentuk suatu siklus diperlukan minimal tiga titik.  Lemma 3.47 Jika G hipohamiltonian, maka deg (v) ≥ 3 untuk setiap v titik pada G. Bukti: Setiap titik berada di dalam suatu siklus yang panjangnya n-1, sehingga deg (v) ≥ 2. Jika suatu titik w berdekatan dengan titik v, maka di dalam subgraf yang terbentuk melalui eliminasi w selalu mempunyai derajat deg (v) ≥ 2 (karena subgraf tersebut membentuk siklus). Akibatnya deg (v) ≥ 3.  Lemma 3.48 Jika G hipohamiltonian dan apabila w dan x adalah titik-titik berurutan (berdekatan) dari siklus yang panjangnya n-1 pada graf yang mana suatu titik v telah dieliminasi, maka v tidak akan berdekatan dengan keduanya w dan x secara bersamaan.

70

Bukti: Sebaliknya dengan menambahkan suatu titik v akan didapat siklus Hamiltonian untuk suatu graf.  Lemma 3.49 Jika G hipohamiltonian, maka deg (v) ≤

'E$ 

untuk setiap v.

Bukti: Terlihat dari Lemma 3.48, karena untuk setiap titik, titik tersebut tidak sekaligus berdekatan dengan dua titik lain yang berurutan dari siklus Hamiltonian yang mempunyai panjang n-1. Berarti setiap derajat titiknya maksimal

{E$ 

.

Lemma 3.50 Jika G graf teratur-k, maka f.  2, dengan  titik dan  garis

dan f bilangan bulat positif. Bukti:

Graf G adalah graf yang mempunyai derajat k untuk setiap titiknya, maka jumlah semua derajat titik-titiknya adalah f. Berdasarkan Lemma Persalaman (Handshaking Lemma) diketahui bahwa banyaknya garis pada suatu graf adalah setengah jumlah semua derajat titik-titiknya, yaitu

$ 

f. Misalnya banyaknya

garis adalah m, maka diperoleh bahwa banyaknya garis pada graf G adalah $

  f atau 2 f.  Lemma 3.51 Jika v, w, x, w’, x’ adalah titik-titik yang berbeda dari graf G sedemikian sehingga v berdekatan w dan w’, dan x dengan x’, serta apabila garis wx dan w’x’ adalah dua garis pada siklus Hamiltonian yang sama pada graf yang dibentuk dengan membuang v, maka G mengandung siklus Hamiltonian.

71

Bukti: Siklus ditunjukkan pada Gambar 3.15. Perhatikan bahwa garis hitam tebal pada Gambar merupakan siklus dari graf G.  w x

v

w'

x'

Gambar 3.15 Graf dan siklus hamiltonian

Teorema 3.52 Jika G hipohamiltonian, maka banyaknya titik n≥ 7. Bukti: Terlihat dari Lemma 3.47 dan Lemma 3.49 diatas. Berdasarkan Lemma 3.47, derajat HI 3 untuk setiap titik v, dan dari Lemma 3.47 maka didapat HI  

'E$

3 

'E$

  1  6



, untuk setiap derajat pada titik v



  7

Jadi terbukti   7.

72

Teorema 3.53 Jika G hipohamiltonian, maka banyaknya titik n 7. Bukti: Berdasarkan Lemma 3.47 dan Lemma 3.49, apabila n=7 maka deg (v) = 3 untuk setiap v, dan kontradiksi dengan Lemma 3.48 karena tidak ada m bilangan bulat positif yang memenuhi 2 H.  3.7 21.  Teorema 3.54 Jika G hipohamiltonian, maka banyaknya titik n 8. Bukti: Dari Lemma 3.47 dan Lemma 3.49, untuk n=8 berakibat deg (v) = 3. Jika G hipohamiltonian dengan banyak titik n adalah 8, maka berdasarkan Lemma 3.48 hanya ada satu diantara dua graf berikut, yaitu graf yang terlihat pada Gambar 3.16 (a) Dan Gambar 3.16 (b). Yang mana keduanya mempunyai siklus Hamiltonian berdasar Lemma 3.51. 

v v

(a)

(b) Gambar 3.16 Kemungkinan graf 8 titik

73

Teorema 3.55 Jika G hipohamiltonian, maka n 9. Bukti: Berdasarkan Lemma 3.50, jika G hipohamiltonian dengan banyaknya titik n = 9, maka graf tersebut bukan graf teratur berderajat tiga. Menurut Lemma 3.49, terdapat setidak-tidaknya satu titik yang berderajat empat. Dari Lemma 3.48 graf G tersebut mengandung sebagian graf pada Gambar 3.17 (a). Titik 2 haruslah berdekatan dengan setidak-tidaknya titik 4 sampai titik 8, karena deg (2) ≥ 3 (Lemma 3.47). Akan tetapi, garis 24, garis 26, dan garis 28 masing-masing menghasilkan siklus Hamiltonian (Lemma 3.51). Jika titik 2 berdekatan dengan titik 5, maka titik 8 (dengan alasan yang sama tidak akan berdekatan kecuali dengan titik 3 atau titik 5) akan tidak berdekatan dengan titik 5 tanpa memmiliki deg (5) ≥ 4 yang bertentangan dengan Lemma 3.49. Berarti titik 8 berdekatan dengan titik 3. 1

1

2

8

7

2

8

3

9

6

7

6

4

3

9

4 5

5

(a)

(b)

Gambar 3.17 Kemungkinan graf bertitik 9

Dengan cara sama, titik 6 berdekatan dengan titik 1 dan titik 4 berdekatan dengan titik 7, serta tidak mungkin ada garis lainnya karena titik-titik 9, 1, 3, 5, 7

74

dipenuhi. Gambar yang sama (lihat Gambar 3.17 (b)) akan diperoleh jika titik 2 berdekatan dengan titik 7. Catat bahwa setiap garis yang menggabungkan dua titik yang angka-angkanya mempunyai paritas berlawanan (opposite parity). Jadi, Graf tersebut diperoleh dengan mengeliminasi titik 1 yang tidak mempunyai siklus Hamiltonian, dan oleh sebab itu G tidak hipohamiltonian.  Teorema 3.56 Jika G hipohamiltonian orde 10, maka titik-titiknya serba sama berderajat tiga. Bukti: Misalkan beberapa titik mempunyai derajat empat. Berarti graf G memuat graf parsial (sebagian) Gbr.3-18. Berdasarkan Lemma 3.51, setiap dari titik-titik 2, 4, 5, 7, 9 tidak akan berdekatan kecuali dengan satu atau dua titik dari titik 1, 3, 6, 8. Karena setiap dari yang terakhir tidak berdekatan dengan setidak-tidaknya satu dari yang sebelumnya, maka didapat kontradiksi.  1

9

8

2

10 7

3

6

4 5 Gambar 3.18 Graf bertitik 10

75

Teorema 3.57 Graf Petersen (Gambar 3.19) adalah hipohamiltonian. Bukti: Eliminasi titik 1 pada Graf P akan didapat siklus (10,4,3,2,6,5,9,8,7,10). Begitu

pula

dengan

mengeliminasi

titik

2

akan

didapat

siklus

(10,1,9,8,3,4,5,6,7,10). Kasus lain diperoleh dari kesimetrisan graf. Graf tidak mempunyai siklus Hamiltonian, sehingga lintasan maksimal yang dimuali dengan titik 10, 1, 2 adalah (6,5,4,3,8,7), (6,5,4,3,8,9), (6,5,9,8,3,4), (6,5,9,8,7),

(6,7,8,3,4,5,9),

(6,7,8,9,5,4,3),

(3,4,5,6,7,8,9),

(3,4,5,9,8,7,6),

(3,8,7,6,5,4), (3,8,7,6,5,9), (3,8,9,5,4), (3,8,9,5,6,7) dan tidak ada satu pun yang memberikan suatu siklus Hamiltonian. Dengan kesimetrisan dapat diterapkan untuk semua lintasan-lintasan yang lain. 

1 9

2

8

3 10 7 4 6

5 Gambar 3.19 Graf Petersen

76

Teorema 3.58 Jika G hipohamiltonian orde 10, maka G isomorfik dengan Graf Petersen P. Bukti: Pertama-tama lakukan dengan melabelkan angka pada titik-titik siklusnya yaitu angka 1, 2, …, 9 tanpa angka 10. Dengan melakukan hal tersebut, didapat tiga tipe graf yang mungkin dari G, yaitu: 1. Tipe Graf dengan angka 10 berdekatan dengan angka 1, 4, 7 yang mana dengan Lemma 3.51 dan Teorema 3.56 memberikan Graf seperti Gbr. 3.18 atau Gbr. 3.20 (a). Graf Gbr 3.20 (a) mempunyai siklus Hamiltonian (10,1,2,9,8,7,6,5,3,4,10). 2. Tipe Graf dengan angka 10 berdekatan dengan 1, 3, 6 seperti terlihat pada

Gambar

3.20

(b)

yang

mempunyai

siklus

Hamiltonian

(10,6,7,5,4,3,8,9,1,10). 3. Tipe Graf dengan angka 10 berdekatan dengan 1, 3, 5 seperti terlihat pada Gambar 3.20 (c) dan 3.20 (d) yang mana masing-masing mempunyai siklus Hamiltonian (10,1,2,3,4,7,8,9,6,5,10) dan (10,1,2,7,8,9,6,5,4,3,10).

77

1

1

9

9

2

2

8

8

3

3

10

10

7

7

4

4

6

6

5

5

(a)

(b)

1

1 9

9

2

8

3

2

8

3

10

10

7

7

4 6

4 6

5

(c)

5 (d)

Gambar 3.20 Graf Petersen dan Graf isomorfik dengan Graf Petersen

Berdasarkan Teorema 3.57 dapat terlihat bahwa graf Petersen merupakan graf hipohamiltonian terkecil berderajat sepuluh dan berdasarkan Teorema 3.58 graf Petersen merupakan satu-satunya graf hipohamiltonian terkecil berderajat sepuluh.

78

BAB IV KESIMPULAN DAN SARAN

4.1 KESIMPULAN Berdasarkan pembahasan Bab III dapat diambil beberapa kesimpulan sebagai berikut. (i)

Graf Petersen tidak Eulerian.

(ii)

Graf Petersen tidak planar.

(iii) Graf Petersen tidak terfaktor-1. (iv) Himpunan automorfisma graf Petersen isomorfik dengan grup simetrik berelemen lima. (v)

Graf Petersen transitif-titik.

(vi) Graf Petersen transitif-garis. (vii) Graf Petersen merupakan komplemen graf garis dari graf lengkap orde 5. (viii) Graf Petersen bukan graf bipartit. (ix) Graf Petersen tidak Hamiltonian. (x)

Graf Petersen merupakan graf hipohamiltonian terkecil dengan sepuluh titik.

4.2 SARAN Melalui penulisan dan pembahasan Tugas Akhir yang telah dilakukan ini perlu dikembangkan pembahasan dan penelitian lebih lanjut mengenai graf Petersen yang diperumum (generalized Petersen graph), sifat-sifat yang berkaitan dengan graf Petersen yang diperumum tersebut.

79

DAFTAR PUSTAKA

Balakrishnan, V. K., 1997, Schaum’s Outline of Theory and Problems of Graph Theory, The McGraw-Hill Companies, Inc., New York. Biggs, N., 1974, Cambridge Tracts in Mathematics 67: Algebraic Graph Theory, Cambridge University Press, London. Busacker, R.G. dan Saaty, T.L., 1965, Finite Graphs and Network: An Introduction With Application, McGraw-Hill Book Companies, New York. Capobianco, M. dan Molluzzo, J.C., 1978, Examples and Counterexamples in Graph Theory, Elsevier North-Holland, Inc., New York. Chartrand, G. dan Oellermann O.R., 1993, Applied and Algoritmic Graph Theory, McGraw-Hill, Inc., New York. Fraleigh, J.B. dan Katz, V., 1994, A First Course in Abstract Algebra, Fifth Edition, Addison-Wesley Publishing Conpany, Reading, Massachusetts. Gallian, J.A., 1990, Contemporary Abstract Algebra, second edition, D. C. Heath and Company, Lexington, Massachusetts. Harary, F., 1969, Graph Theory, Addison-Wesley Publishing Company, Inc., Reading, Massachusetts. Holton, D. A. dan Sheehan, J., 1993, The Petersen Graph, Cambridge University Press, Cambridge. Hu, Y., 2010, New Proof of Some Properties about Petersen Graph, 2010 second International Workshop on Education Technology and Computer Science, 67 Maret 2010, 609-611, Wuhan. Liu, C.L., 1995, Dasar-dasar Matematika Diskret, edisi kedua, (diterjemahkan oleh Bambang Sumantri), Penerbit PT Gramedia Pustaka Utama, Jakarta. Slamet, S. dan Makaliwe, H., 1991, Matematika Kombinatorik, PT Elex Media Komputindo, Jakarta. Suryoto, 2001, Automorfisma Graph, Jurnal Matematika dan Komputer, No.3, Vol.4, 122-19, Universitas Diponegoro, Semarang. Wilson, R.J. dan Watkins, J.J., 1990, Graph: An Introduction Approach: A first Course In Discrete Mathematics, John Wiley & Sons, Inc., New York.

LAMPIRAN Lampiran 1. Daftar Istilah

Automorfisma (automorphism): Automorfisma
dari suatu graf  adalah pemetaan 1-1 dari himpunan titik-titik G onto dirinya sendiri dengan sifat bahwa
 dan
 berdekatan jika dan hanya jika  dan  berdekatan. Berdekatan (adjacent): dua titik dikatakan berdekatan apabila ada garis yang menghubungkan kedua titik tersebut. Derajat (degree): Banyaknya garis yang insiden dengan suatu titik v pada graf Derajat permukaan (face degree): Banyaknya garis yang membentuk jalan yang membatasi area suatu permukaan. Eulerian (Eulerian): Suatu graf dikatakan Graf Eulerian apabila graf tersebut mempunyai sirkuit eulerian. Faktor (factor): Suatu Faktor dari graf G adalah subgraf perentang dari G yang tidak seluruhnya tak-terhubung. Faktor-r (r-factor): Suatu faktor yang teratur-r dari dari graf G. Garis-garis paralel (multiple edges): Dua atau lebih garis yang menghubungkan dua titik yang sama. Gelung (loop): Garis yang menghubungkan titik dengan dirinya sendiri. Graf (graph): Pasangan dua himpunan, yaitu himpunan tidak-kosong dari titik-titik VG dan himpunan elemen-elemen (yang disebut garis) EG yang menghubungkan titik tersebut. Graf kubik (cubic graph): Graf teratur yang berderajat tiga atau graf teratur-3. Graf bidang (plane graph): Graf Bidang adalah Graf Planar yang digambarkan pada bidang datar sedemikian sehingga tidak ada garis yang bersilangan.

Graph bipartit (Bipartite Graph): Suatu graf G adalah graf bipartit (bipartite graph) jika VG dapat dipartisi menjadi dua himpunan bagian (tidak kosong) V dan V sedemikian sehingga setiap garis G menggabungkan sebuah titik V dengan sebuah titik V . Graf bipartit lengkap (complete bipartite graph): Graf Bipartit dengan banyaknya

titik pada  dan  adalah banyaknya titik pada  . Graf garis (line graph): Graf garis , dinotasikan , adalah graf dengan     dan memenuhi ketentuan bahwa dua titik di  berdekatan jika dan hanya jika kesesuaiannya dengan garis-garis di G juga berdekatan Graf Lengkap (complete graph): Graf yang setiap dua titiknya dihubungkan dengan tepat oleh satu garis. Graf planar (planar graph): Graf dapat digambarkan pada bidang datar sedemikian sehingga tidak ada dua garis yang bersilangan. Graph Petersen (petersen graph): Graf yang mempunyai sepuluh titik dan lima belas garis dengan masing-masing titiknya berderajat tiga. Graf sederhana (simple graph): Sebuah graf yang tidak memiliki garis-garis paralel atau gelung. Umumnya graf sederhana cukup disebut sebagai graf. Graf teratur (Regular Graph): Suatu graf dikatakan graf teratur apabila setiap titik pada graf mempunyai derajat yang sama. Graf teratur-r (regular-r graph): Apabila setiap titik pada suatu graf mempunyai derajat r, maka graf dikatakan teratur-r. Hamiltonian (Hamiltonian): Suatu graf dikatakan Graf Hamiltonian apabila graf tersebut mempunyai siklus hamiltonian. himpunan garis potong (edge cutset): Himpunan garis-garis yang membuat suatu graf tak-terhubung. Hipohamiltonian (hypohamiltonian): Jika graf  bukan Hamiltonian dan jika    hamiltonian untuk setiap   .

Insiden (incident): suatu titik dikatakan insiden dengan suatu garis apabila titik tersebut menghubungkan garis dengan titik lain. Titik lain tersebut juga dikatakan insiden dengan (incident to) garis. Isomorfik (isomorphic): Dua Graf dikatakan isomorfik apabila terdapat pemetaan yang mempertahankan kedekatan kedua titik. Isomorfisma (isomorphism): Fungsi yang memetakan dua Graf isomorfik. Isomorfisma garis (line isomorphism): Fungsi yang memetakan gua Graf isomorfik garis. Jalan (walk): Barisan titik-titik dan garis-garis pada graf G yang berselang-seling yang dimulai dari suatu titik dan berakhir pada suatu titik. Jalur (trail): jalan dengan semua garis dalam barisan adalah berbeda. Jalur Eulerian (Eulerian trail): jalur yang mengandung semua garis dari G. Keliling (circumference): Panjang dari siklus terpanjang suatu graf. Komponen (component): Subgraf H dari suatu graf G dikatakan komponen dari G jika H merupakan subgraf terhubung maksimal dari G. Komplemen (complement): Komplemen dari Graf  ditulis  adalah Graf dengan    dan    jika dan hanya jika   . Lintasan (path): Jalan dengan semua titik dalam barisan adalah berbeda. Lintasan Hamiltonian (Hamiltonian path): Suatu lintasan antara dua titik berbeda pada suatu graf disebut lintasan Hamiltonian jika lintasan tersebut melewati setiap titik pada suatu graf. Menggabungkan (Join): Garis  dikatakan menggabungkan titik  dan  apabila kedua titik tersebut berdekatan. Multigraf (multigraph): Graf yang mempunyai garis-garis paralel dan tanpa gelung. Orbit (orbit): Jika Γ adalah grup permutasi atas himpunan A dan   , maka Γ    :   Γ adalah orbit dari  pada Γ.

Orde (order): Banyaknya titik pada suatu Graf. Panjang (lenght) jalan: banyaknya garis yang muncul (dilalui) sepanjang barisan pada suatu jalan. Permukaan (face): Bidang pada graf planar yang terbagi menjadi suatu daerah. Permukaan terbatas (finite face): Bidang pada graf planar yang terbagi menjadi suatu daerah yang dibatasi oleh suatu jalan. Permutasi (permutation): Permutasi dari himpunan A adalah fungsi dari A ke A yang sekaligus satu-satu (one-to-one) dan pada (onto). Pseudograf (pseudograf): Graf yang mempunyai garis-garis paralel dan gelung. Semi-Eulerian (semi-Eulerian): Graf dikatakan semi-Eulerian jika graf mempunyai suatu jalur Eulerian. Siklus (cycle): lintasan yang tertutup. Siklus Hamiltonian (Hamiltonian cycle): Suatu siklus yang melewati setiap titik pada graf tepat satu kali. Sirkuit (circuit): jalur yang tertutup. Sirkuit Eulerian (Eulerian circuit): Suatu sirkuit yang mengandung semua garis pada suatu graf. Stabilizer (stabilizer): Jika Γ adalah grup permutasi atas himpunan A dan   , maka Γ!    Γ:    dikatakan sebagai stabilizer dari . Subgraf (subgraph): Suatu graf yang himpunan titik-titiknya dan himpunan garisgarisnya masing-masing merupakan himpunan bagian dari himpunan titik dan himpunan garis suatu graf. Dengan kata lain " subgraf dari  jika " #  dan " # . Subgraf hapus titik (vertex deleted subgraph): Suatu Subgraf dikatakan subgraf hapus titik jika sebuah titik dan garis-garis yang berinsiden dengan titik tersebut pada suatu Graf dibuang.

Subgraf perentang (spanning subgraph): subgraf dari suatu graf dengan syarat subgraf tersebut mengadung semua titik dari graf tersebut. Terfaktor (factorable): Diketahui bahwa  ,  , … , & merupakan pasangan subgraf perentang terpisah-garis (edge-disjoint) dari  sedemikian sehingga '&() (  , maka  dikatakan terfaktor. Terfaktor-r (r-factorable): Jika terdapat suatu faktorisasi dari graf G menjadi faktorr, maka G dikatakan terfaktor-r Terhubung (Connected): Suatu Graf dikatakan terhubung (connected) jika untuk setiap dua titik dari graf G, selalu terdapat lintasan yang menghubungkan kedua titik tersebut. Terhubung dengan (conntected to): Misalkan u dan v adalah titik pada graf G. Titik u dikatakan terhubung dengan (connected to) v jika G mengandung suatu lintasan u  v. Terbuka (open): Suatu barisan titik-titik dan garis-garis (jalan) dikatakan terbuka apabila tidak tertutup. Tertutup (close): Suatu barisan titik-titik dan garis-garis (jalan) dikatakan tertutup apabila titik awal v+  v, , titik akhir. Titik konsitik (concytic point): semua titik pada suatu graf dapat digambarkan pada keliling yang sama dan memelihara kedekatan antara titik. Transitif (transitive): Grup permutasi dikatakan transitif (transitive) jika Γ    untuk suatu   . Transitif-garis (edge-transitive): untuk setiap  ,   , terdapat -  .  sedemikian sehingga -     . Transitif-titik (vertex-transitive): Suatu graf dikatakan graf transitif-titik jika  transitif. Ukuran (size): Banyaknya garis pada suatu Graf