Jenis – Jenis Graf dan Graf Bipartisi PDF

Preview

Summary

Jenis – Jenis Graf dan Graf Bipartisi Edi Sutomo email : [email protected] twitter : @ed_1st Abstrak mekalah ini membahas tentang pengklasifikasian graf serta termasuk mengupas tentang Graf Bipartisi. secara umum graf dapat dikelompokan berdasar ada tidaknya edge yang paralel atau loop, jumlah...

Description

Jenis – Jenis Graf dan Graf Bipartisi Edi Sutomo email

: [email protected] twitter : @ed_1st

Abstrak mekalah ini membahas tentang pengklasifikasian graf serta termasuk mengupas tentang Graf Bipartisi. secara umum graf dapat dikelompokan berdasar ada tidaknya edge yang paralel atau loop, jumlah titiknya, ada atau tidaknya arah pada sisinya, ada atau tidak bobot pada sisinya, serta ada atau tidaknya korelasi dengan graf yang lain. Selain berdasarkan ada atau tidaknya sisi yang paralel atau loop, graf dapat pula di-kelompokan berdasarkan berdasarkan arah sisinya dan bisa juga ditinjau dari jumlah titik (vertex) yang menyusun suatu graf. Terdapat beberapa poin dari pembahasan graf bipartisi suatu graf yaitu himpunan titiknya dapat dikelompokkan menjadi dua himpunan dan setiap pasang titik di (demikian pula dengan titik – titik di ) tidak bertetangga. Kata Kunci: Jenis Graf, Graf Bipartisi

1. Pendahuluan Teori graf sebagai sub cabang dari matematika diskrit dengan objek kajian segala sesuatu

yang berbeda dan saling terpisah (lawan dari kontinu)

dipergunakan untuk menampilkan

obyek-obyek diskrit dan hubungannya.

Representasi visual dari graf adalah dengan menyatakan

obyek sebagai

noktah, bulatan atau titik, sedangkan hubungan antara obyek

dinyatakan

dengan garis (Munir, 2003). Secara kontekstual graf digunakan untuk menggambarkan berbagai macam struktur yang ada sebagai visualisasi obyek-obyek agar lebih mudah dimengerti. Tiap-tiap diagram memuat sekumpulan obyek (kotak, titik, dan lain-lain) beserta garis-garis yang menghubungkan obyek-obyek tersebut. Garis bisa berarah ataupun tidak berarah. Garis yang berarah biasanya digunakan untuk menyatakan hubungan yang mementingkan urutan antar objek-objek. Urut-urutan objek akan mempunyai arti yang lain jika arah garis diubah. Sebagai contoh adalah garis komando yang menghubungkan titik-titik struktur sebuah organisasi. Sebaliknya, garis yang tidak berarah digunakan untuk menyatakan hubungan antar objek-objek yang tidak mementingkan urutan.

2. Dasar – dasar Graf Telah diketahui bersama, secara umum terdapat 3 (tiga) komponen graf, yaitu; (1) titik (vertices) atau noktah yang merepresentasikan objek pada suatu graf, (2) sisi (edge) yaitu garis yang menunjukan menunjukan keterhubungan antar titik titik tersebut, dan (3) loop atau sebuah sisi yang menghubungkan titik pada dirinya sendiri.

Gambar 1. Graf yang memuat loop Definisi 1 Suatu graf G terdiri dari 2 himpunan yang berhingga, yaitu himpunan titik-titik tidak kosong

dan himpunan garis-garis

yang dipasangkan degan

aturan tertentu dan dinotasikan dengan Contoh 1: Diberikan

dengan

dan maka penggambaran graf yang dimaksud

adalah

Gambar 2. Graf . Dua

titik

dikatakan

berhubungan

(adjacent)

jika

ada

garis

yang

menghubungkan keduanya. Titik yang tidak mempunyai garis yang berhubungan dengannya disebut Titik Terasing (Isolating Point) Graf yang tidak mempunyai titik (sehingga tidak mempunyai garis) disebut graf kosong.

Jika semua garisnya berarah maka graf-nya disebut Graf Berarah (Directed Graph, atau sering disingkat digraph). Jika semua garisnya tidak berarah, maka graf-nya disebut Graf Tak Berarah (undirected graph). Dalam kajian ini, jika hanya disebutkan graf saja, maka yang dimaksud adalah graf tak berarah. Definisi 2 Sisi �

dikatakan menghubungkan titik

dan

.

Jika �

adalah sisi pada graf , maka u dan v disebut terhubung langsung (adjacent), dan � serta

sisi �

dan � disebut terkait langsung (incident). Untuk selanjutnya,

ditulis dengan �

.

Definisi 2 dapat digambarkan sebagai berikut : � Gambar 3. Sisi e = (u, v). Karena �

sisi di

(adjacent), sedangkan � dan Definisi 3

Banyaknya unsur di

, maka

dan

serta � dan

disebut “order” dari

dan banyaknya unsur di

disebut terhubung langsung

disebut terkait langsung (incident).

dan dilambangkan dengan

disebut “size” dari

dan dilambangkan dengan

.

Definisi 3 bisa digambarkan melalui salah satu graf berikut, �

�

Gambar 4. Graf

� �

dengan order 4 dan size 4.

Gambar 4 menunjukan bahwa graf dan

� � � � .

,

tersebut diperoleh dari

Definisi 4 Graf

disebut subgraf dari graf

himpunan titik di di

jika himpunan titik di

dan himpunan sisi di

, atau ditulis dengan

adalah subset dari

adalah subset dari himpunan sisi dan

subgraf , maka dapat ditulis

. Jika

adalah

.

Deskripsi dari definisi 4 bisa dilihat pada gambar berikur,

Gambar 5.

subgraf .

Definisi 5 Misal

adalah graf dengan

merupakan subgraf dari adalah semua sisi di

dan

dengan himpunan titik

, maka dan sisinya

yang tidak terkait langsung dengan

Penggambaran dari definisi 5 adalah,

Gambar 6. Penghapusan vertex pada graf . Melalui gambar

bagian

jumlah vertex maupun edge nya makin

lama makin berkurang jumlahnya. Definisi 6 Jika terdapat graf

dan �

himpunan titiknya adalah

,maka

� adalah subgraf

dan himpunan sisinya adalah

Definisi 6 digambarkan melalui contoh berikut,

yang � .

Gambar 7. Penghapusan sisi dari Graf Gambar 7 �

merupakan penurunan dari gambar

dan gambar

dengan menghilang sisi

merupakan penurunan dari gambar

dengan

menghilangkan sisi � .

3. Beberapa Jenis Graf

Secara umum graf dapat dikelompokan berdasar ada tidaknya edge yang paralel atau loop, jumlah titiknya, ada atau tidaknya arah pada sisinya, ada atau tidak bobot pada sisinya, serta ada atau tidaknya korelasi dengan graf yang lain. Berikut ini adalah jenis graf berdasarkan ada tidaknya sisi yang paralel atau loop. i. Graf Sederhana (simple graph), graf ini merupakan graf tak berarah yang tidak mengandung sisi ganda ataupun loop. Contoh gambar graf sederhana adalah,

�

�

�

�

�

�

�

�

�

Gambar 8. contoh graf sederhana. ii. Graf tak sederhana (unsimple graph)¸graf tak sederhana merupakan inverse dari graf sederhana, sehingga setiap graf yang memiliki sisi ganda dan atau loop masuk dalam kategori graf tak sederhana. Secara umum, graf tak sederhana dibagi dalam dua kategori, yaitu:

a. graf ganda (multigraph), yaitu graf yang mengandung lebih dari satu sisi untuk dua titik yang sama. Salah satu representasi graf ganda ditunjukan oleh gambar 9 dibawah ini,

� �

�

�

�

� �

gambar 9. graf ganda b. graf semu (pseudograph), graf ini merupakan graf yang memiliki loop, termasuk juga graf yang memiliki loop dan sisi ganda. Salah satu representasi dari graf semu ditunjukan oleh gambar 10 dibawah ini,

� �

�

�

�

� �

Gambar 10. Graf semu Selain berdasarkan ada atau tidaknya sisi yang paralel atau loop, graf dapat pula di-kelompokan berdasarkan berdasarkan arah sisinya. Graf ini dikelompokan dalam dua kategori, yaitu: a. graf berarah (directed graph atau digraph) yaitu graf yang setiap sisinya memiliki arah, pada graf berarah kondisi

,

b. graf tak berarah (undirected graph) merupakan graf yang setiap sisinya tak memiliki arah. Bila ditinjau dari jumlah titik (vertex) yang menyusun suatu graf, secara umum graf dapat digolongkan menjadi dua jenis, yaitu:

a. graf berhingga (limited graph), yaitu graf yang jumlah titiknya berhingga. Gambar 1 sampai gambar 10 diatas merupakan representasi dari graf berhingga. b. graf

tak berhingga (unlimited graph), merupakan graf

titiknya

yang jumlah

tak berhingga. Gambar dibawah ini merepresentasikan graf tak

berhingga,

Gambar 11. Graf tak berhingga. 4. Beberapa Graf Sederhana yang Khusus Selain pengelompokan graf seperti diatas, terdapat juga graf sederhana yang khusus. Beberapa graph sederhana khusus yang sering dijumpai dan banyak didiskusikan adalah, a. Graf Lengkap (Complete Graph) Graph lengkap merupakan graph sederhana yang setiap titiknya terhubung ke setiap titik yang lain. Graph lengkap dengan dinotasikan dengan

. Setiap titik

pada graf lengkap yang terdiri dari

berderajat

buah titik

. Jumlah sisi

buah titik adalah

. Contoh

graf lengkap direpresentasikan oleh gambar berikut,

Gambar 11. Graf Lengkap. b. Graf Kosong Graf kosong pada

titik yang dinotasikan dengan

merupakan graf

yang himpunan sisi–sisinya merupakan himpunan kosong. Dengan

kata lain graf yang tidak memiliki sisi sehingga setiap titik tidak saling terhubung. Contoh graf kosong direpresentasikan oleh gambar berikut;

Gambar 12. Graf Kosong c. Graf Komplemen Apabila terdapat graf

, maka komplemen dari

yang dinotasikan

oleh ̅ merupakan graf yang titiknya adalah titik dari graf sisinya bukanlah sisi dari graf

atau ditulis dengan

. Perhatikan gambar dibawah ini,

Gambar 13. Graf d. Graf Lingkaran (cycles)

, namun

̅ komplemen

̅ dan komplemennya

Graph lingakaran merupakan graf sederhana yang setiap titiknya berderajat dua. Graph lingkaran dengan dengan

. Jika titik–titik pada

buah titik dilambangkan

adalah

maka sisi-

sisinya adalah

dan

Gambar 14. Graf lingkaran

.

e. Graf Teratur (Reguler Graph) Syarat dari graf teratur adalah setiap titiknya memiliki derajat yang sama. Apabila derajat setiap titik adalah graf teratur berderajat

maka dikatakan sebagai

. Jumlah sisi pada graph teratur

berderajat

dengan

buah titik adalah

graf reguler dengan

. Graf kosong merupakan

. Gambar berikut merupakan contoh dari

graf teratur,

Gambar 15. Graf teratur. 5. Graf Bipartisi(Bipartisie Graph) Suatu graf

yang himpunan titiknya dapat dikelompokkan menjadi dua

himpunan bagian misal

dan

sedemikian sehingga setiap sisi di dalam

menghubungkan sebuah titik di

ke sebuah titik di

dan dinotasikan dengan

merupakan graf Bipartisi

. Dengan kata lain, setiap pasang titik di

(demikian pula dengan titik – titik di

) tidak bertetangga. Gambar 16

merupakan contoh graf Bipartisi,

Gambar 16. Graf Bipartisi. Apabila setiap titik di

terkoneksi dengan semua simpul di disebut

sebagai

(complete Bipartisie graph), dinotasikan dengan Bipartisi lengkap adalah

.

graph

Bipartisi

, maka lengkap

. Jumlah sisi pada graf

Teorema 1 Graf

jika dan hanya jika tidak terdapat sikel ganjil (odd cycles)

Bukti Harus ditunjukan bahwa terdapat sikel ganjil bukanlah graf bipartit. Misalkan

merupakan titik dari sikel ganjil

pada

. Jika

dari

atau

merupakan graf bipartisi, maka , maka

karena merupakan tetangga dari

karena merupakan tetangga dari diperoleh

akan menjadi bagian

. Akan tetapi apabia

dan

dan seterusnya hingga dan

saling bertetangga

hal ini menimbulkan kontradiksi dan merupakan dirinya sendiri, sehingga partisi yang dilakukan tidak valid untuk graf . Selanjutnya, kita tetapkan sebuah partisi dari dari

dengan aturan :

1. 2. Selanjutnya perlu ditunjukan bahwa Andaikan

dan

memang partisi dari

adalah dua titik di , sehingga

menjadi lintasan terpendek

,

menjadi titik temu pertama dari

. Jelas bahwa sejak

adalah lintasan – lintasan terpendek, maka bagian lintasan terpendek Andaikan dari dan

dan

dan . Karena

. Misalkan

menjadi lintasan terpendek dan

.

dan dan

juga merupakan

. Faktanya mereka memiliki panjang yang sama. berturut – turut adalah bagian dan

dan

memiliki panjang yang sama menyebabkan

juga memiliki kesamaan yang sama. maka tidak ada dua titik di

yang bertetangga. Begitu juga di , tidak terdapat dua titik yang saling bertetangga. Maka

memang sebuah partisi di

ini merupakan contoh graf yang bisa dipartisi,

. Gambar dibawah

Gambar 17. Graf yang bisa dipartisi. Graf

diatas tidak memiliki cycle ganjil sehingga bisa dibipartisi

menjadi graf bipartisi tanpa menghilangkan satupun titik ataupun sisi yang dimilikinya sebelum dibipartisi. Sebuah graf terhubung memiliki bipartisi yang unik. Berikut adalah gambar graf bipartisi dari graf

Gambar 18. Gambar bipartisi graf

pada gambar 17 diatas.

dari (bentuk lain dari gambar 17).

Terlihat bahwa graf tersebut bukanlah graf bipartisi komplit sehingga graf tersebut tidak dapat dijadikan biclique subgraf dari graf itu sendiri. Jika suatu graf tidak dapat dibipartisi dengan tetap mempertahankan semua titik dan sisinya maka graf tersebut bukanlah graf bipartisi tapi hanya akan memiliki subgraf bipartisi saja.

Gambar 19. Biclique dari subgraf .

Graf G pada gambar 19 memiliki cycle dengan panjang ganjil maka graf tersebut tidak dapat dipartisi tanpa menghilangkan satupun titik ataupun sisi didalamnya. Dengan kata lain graf tersebut bukanlah graf bipartisi. Untuk graf yang ada disampingnya tersebut merupakan sebuah subgraf bipartisi komplit (biclique) dengan

dan

. Sebuah subgraf

biclique dapat disebut subgraf biclique maksimal jika kita tidak mungkin menambahkan sisi lagi ke himpunan sisi

, yang berarti subgraf

tersebut mengandung tepat semua sisi yang berawal di

dan berakhir di .

Definisi 7 Sebuah bipartisi

disebut biclique jika untuk setiap

terdapat sebuah sisi antara

dan

{

dan , yaitu

}.

5.1 Subgraf Bipartisi Sebuah graf sisi

terdiri dari himpunan titik

dengan

. Diasumsikan

dan himpunan

merupakan sebuah graf tak

berarah dan tanpa lup, yaitu tidak terdapat

dan setiap

pasangan sisi tak berurut. Sebuah graf

yang dilambangkan dengan

kurung siku adalah sebuah subgraf dari graf

adalah

jika dan hanya jika

dan

. Himpunan sisi himpunan titik

dan

dari biclique

, maka kita dapat mengabaikan himpunan sisi dan

menunjukkan sebuah biclique sebuah graf tak berarah, sisi-sisi antara

dan

dapat ditentukan dengan dua

sebagai

. Diberikan

dan adalah dua subset dari

adalah

. Jika

dan semua

membentuk sebuah biclique subgraf dari

, maka

dan

dikatakan membentuk sebuah biclique subgraf dari . Berdasarkan definisi tersebut, untuk setiap subset

dari

,

dan

membentuk sebuah biclique subgraf dari .

Definisi 8 Sebuah graf biclique subgraf dari

adalah maksimal biclique subgraf jika sedemikian sehingga

dan

adalah adalah

maksimal dengan artian bahwa tidak terdapat subgraf bipartisi komplit lain

dari

dengan

dan

sedemikian sehingga

dan

6. Penutup Secara umum graf dapat dikelompokan berdasar ada tidaknya edge yang paralel atau loop, jumlah titiknya, ada atau tidaknya arah pada sisinya, ada atau tidak bobot pada sisinya, serta ada atau tidaknya korelasi dengan graf yang lain. Selain berdasarkan ada atau tidaknya sisi yang paralel atau loop, graf dapat pula di-kelompokan berdasarkan berdasarkan arah sisinya dan bisa juga ditinjau dari jumlah titik (vertex) yang menyusun suatu graf. Terdapat beberapa titik tekan dari graf bipartisi suatu graf

yaitu

himpunan titiknya dapat dikelompokkan menjadi dua himpunan dan setiap pasang titik di

(demikian pula dengan titik – titik di ) tidak bertetangga.

7. Referensi Harris, John M, Hirst, Jeffry L, Mossinghoff, Michael J. 2008. Combinatorics and Gra[h Theory (Second Edition). Springer Science+Business Media, LLC Godsil C and Gordon Royle. 2000. Algebraic Graph Theory. Graduate Texts in Mathematics 207. Springer. Asratian A. S, Tristan M. J. Denley and Roland Haggkvist. 1998. “Bipartite Graphs and Their Application”, Cambridge Tracts inMathematics 131....