Pengetahuan Dasar Teori Graf
Prof. Dr. H. Didi Suryadi, M.Ed.
Prof. Dr. H. Nanang Priatna, M.Pd.
UNIVERSITAS PENDIDIKAN INDONESIA
P
|
ada bagian ini Anda akan mempelajari sejarah
singkat perkembangan teori graph serta beberapa pengertian dasar teori graph
mencakup definisi teori graph; graph hingga dan graph tak hingga; insidensi dan
ajasensi; titik (simpul) terisolasi, titik
anting, serta derajat suatu titik. Setelah Anda mengenal beberapa pengertian
teori graph, selanjutnya akan disajikan materi graph sebagai model matematika
dan aplikasinya yang mencakup graph sebagai model matematika, graph berarah
sebagai model matematika, jaringan kerja, silsilah keluarga, sistem komunikasi,
jaringan transportasi, desain arsitektur, dan ikatan kimia.
Mengingat materi yang akan Anda pelajari ini
merupakan landasan utama dalam mempelajari modul-modul berikutnya, maka
pemahaman yang baik tentang materi yang disajikan merupakan langkah yang tepat
dalam upaya memahami materi setiap modul secara keseluruhan.
Setelah mempelajari modul ini Anda diharapkan
mengenal sejarah singkat munculnya teori graph, beberapa pengertian dasar teori
graf, serta
aplikasi teori graph.
Setelah mempelajari modul ini, secara khusus
Anda diharapkan mampu:
1.
menjelaskan sejarah perkembangan
teori graph;
2.
menjelaskan beberapa pengertian
dasar teori graph;
3.
menggambar graph sebagai model
matematika.
Kegiatan Belajar 1
Sejarah Singkat dan Beberapa
Pengertian Dasar Teori Graf
a. SEJARAH SINGKAT TEORI GRAPH
Teori
graph lahir pada Tahun 1736 melalui tulisan Euler yang berisi
tentang upaya pemecahan masalah jembatan Konigsberg yang sangat terkenal di Eropa.
Kurang lebih seratus tahun setelah lahirnya tulisan Euler tersebut tidak ada
perkembangan yang berarti berkenaan dengan teori graph.
Tahun 1847, G.R. Kirchoff (1824 – 1887)
berhasil mengembangkan teori pohon (Theory of trees) yang digunakan
dalam persoalan jaringan listrik. Sepuluh tahun kemudian, A. Coyley (1821 –
1895) juga menggunakan konsep pohon untuk menjelaskan permasalahan kimia yaitu
hidrokarbon.
Pada masa Kirchoff dan Coyley juga telah lahir
dua hal penting dalam teori graph. Salah satunya berkenaan dengan konjektur empat
warna, yang menyatakan bahwa untuk mewarnai sebuah atlas cukup dengan
menggunakan empat macam warna sedemikian hingga tiap negara yang berbatasan
akan memiliki warna yang berbeda.
Para ahli teori graph berkeyakinan bahwa orang
yang pertama kali mengemukakan masalah empat warna adalah A.F. Mobius (1790 –
1868) dalam salah satu kuliahnya di Tahun 1840. Sepuluh tahun kemudian, A. De
Morgan (1806 – 1871) kembali membahas masalah ini bersama ahli-ahli matematika
lainnya di kota London. Dengan demikian tulisan De Morgan dianggap sebagai
referensi pertama berkenaan dengan masalah empat warna. Masalah empat warna ini
menjadi sangat terkenal setelah Coyley mempublikasikannya Tahun 1879 dalam Proceedings
of the Royal Geographic Society volume pertama.
Hal lain yang penting untuk dibicarakan
sehubungan dengan perkembangan teori graph adalah apa yang dikemukakan oleh Sir
W.R. Hamilton (1805 – 1865). Pada Tahun 1859 dia berhasil menemukan suatu
permainan yang kemudian dijualnya ke sebuah pabrik mainan di Dublin. Permainan
tersebut terbuat dari kayu berbentuk dodecahedron beraturan yakni berupa
sebuah polihedron dengan 12 muka dan 20 pojok. Tiap muka berbentuk sebuah
pentagon beraturan dan tiap pojoknya dibentuk oleh tiga sisi berbeda. Tiap
pojok dari dodecahedron tersebut dipasangkan dengan sebuah kota terkenal
seperti London, New York, Paris, dan lain-lain. Masalah dalam permainan ini
adalah, kita diminta untuk mencari suatu rute melalui sisi-sisi dari dodecahedron
sehingga tiap kota dari 20 kota yang ada dapat dilalui tepat satu kali.
Walaupun saat ini masalah tersebut dapat dikategorikan mudah, akan tetapi pada
saat itu tidak ada seorang pun yang bisa menemukan syarat perlu dan cukup dari
eksistensi rute yang dicari.
Kurang lebih setengah abad setelah masa
Hamilton, aktivitas dalam bidang teori graph dapat dikatakan relatif kecil.
Pada Tahun 1920-an kegiatan tersebut muncul kembali yang dipelopori oleh D.
Konig. Konig berupaya mengumpulkan hasil-hasil pemikiran para ahli matematika
tentang teori graph termasuk hasil pemikirannya sendiri, kemudian dikemasnya
dalam bentuk buku yang diterbitkan pada Tahun 1936. Buku tersebut dianggap
sebagai buku pertama tentang teori graph.
Tiga puluh tahun terakhir ini merupakan
periode yang sangat intensif dalam aktivitas pengembangan teori graph baik
murni maupun terapan. Sejumlah besar penelitian telah dilakukan, ribuan artikel
telah diterbitkan dan lusinan buku telah banyak ditulis. Di antara orang
terkenal yang banyak berkecimpung dalam bidang ini adalah Claude Berge, Oysten
Ore, Paul Erdos, William Tutte, dan Frank Harary.
B. PENGERTIAN DASAR TEORI GRAPH
Sebuah
graph linier (atau secara sederhana disebut graph) G = (V, E)
terdiri atas sekumpulan
objek V = {v1, v2, ...} yang disebut himpunan
titik, dan
sebuah himpunan
lain E = {e1, e2, ...} yang merupakan himpunan
sisi sedemikian
hingga tiap sisi ek dikaitkan dengan suatu
pasangan tak terurut (vi, vj ). Titik vi, vj yang berkaitan dengan ek disebut titik-titik ujung sisi ek. Cara merepresentasikan sebuah graph yang paling umum adalah berupa
diagram. Dalam diagram tersebut, titik-titik dinyatakan sebagai noktah dan tiap
sisi dinyatakan sebagai segmen garis yang menghubungkan tiap dua titik. Untuk
lebih jelasnya perhatikan contoh graph pada Gambar 1.1 di bawah ini.
Dalam sebuah graph, seperti terlihat pada
contoh di atas, dimungkinkan adanya suatu sisi yang dikaitkan dengan pasangan
(v1, v2). Sisi yang dua
titik ujungnya sama disebut loop. Dalam graph pada Gambar 1.1, e1 merupakan sebuah loop. Dari
contoh di atas juga perlu dicatat bahwa dalam sebuah graph dimungkinkan adanya
lebih dari satu sisi yang dikaitkan
dengan sepasang titik. Sebagai contoh, e4 dan e5 pada graph di atas dikaitkan dengan pasangan
titik (v1, v3). Pasangan sisi
semacam ini disebut sisi-sisi paralel atau sejajar.
Sebuah
graph yang tidak memiliki loop dan sisi paralel disebut graph sederhana. Dalam beberapa literatur teori graph, pembahasan hanya dibatasi pada
graph sederhana, akan tetapi dalam banyak aplikasi teknik, penggunaan loop dan
sisi paralel sangat diperlukan. Untuk membedakan antara graph yang memuat loop
dan sisi paralel dengan graph yang tidak memuat kedua hal tersebut, sebagian
penulis menggunakan istilah graph sederhana untuk graph yang tidak
memuat loop dan sisi paralel, serta graph umum untuk yang lainnya.
Dalam sebuah graph
mungkin terdapat dua sisi atau lebih yang menghubungkan dua titik yang
berlainan. Kedua sisi tersebut dinamakan sisi rangkap atau sisi ganda. Graph yang mengandung loop
atau sisi rangkap dinamakan graph ganda.
Contoh:
 |
Dalam menggambar sebuah graph, bentuk sisi
dapat berupa garis lurus atau garis lengkung. Demikian pula ukurannya, dalam
penggambaran sebuah graph tidaklah diperhatikan. Hal yang penting untuk
diperhatikan dalam sebuah graph adalah insidensi antara titik-titik dengan
sisi-sisinya. Sebagai contoh, dua graph yang disajikan pada Gambar 1.3 di bawah
ini menggambarkan graph yang sama, karena insidensi antara sisi-sisi dan
titik-titik pada graph tersebut adalah sama.
Sekarang perhatikan Gambar 1.4 di bawah ini.
Pada gambar tersebut sisi e dan f
nampaknya seperti berpotongan, akan tetapi perpotongannya tidak berupa titik.
Kedua sisi seperti itu harus dipandang sebagai dua ruas garis yang terletak
pada dua bidang berbeda, sehingga kedua sisi itu tidak berpotongan.
c. GRAPH HINGGA DAN GRAPH TAK HINGGA
Walaupun dalam definisi graph tidak disebutkan
secara eksplisit bahwa himpunan titik V dan himpunan sisi E tidak perlu
merupakan sebuah himpunan hingga, akan tetapi dalam kebanyakan aplikasi teori
graph kedua himpunannya tersebut kebanyakan merupakan himpunan hingga. Sebuah
graph G = (V, E) dengan V dan E hingga
disebut graph hingga atau graph
terhingga dan jika sebaliknya yakni
jika V dan E tak hingga, maka G disebut graph tak hingga. Contoh graph
hingga dapat dilihat pada Gambar 1.1, Gambar 1.2, Gambar 1.3 dan Gambar 1.4.
Sedangkan Gambar 1.5 di bawah ini merupakan contoh dari bagian graph tak
hingga.
Untuk pembahasan selanjutnya, yang dimaksud
dengan graph dalam modul ini adalah graph hingga.
d. INSIDENSI DAN AJASENSI
Jika
sebuah titik v1 merupakan titik ujung dari suatu sisi ej , maka v1 dan ej disebut
saling berinsidensi atau titik v1 insiden dengan sisi ej. Sebagai contoh,
pada Gambar 1.1 di atas sisi e2, e6, dan e7 adalah sisi-sisi yang insiden dengan titik v4. Dua sisi yang
tidak paralel disebut ajasen, bila kedua sisi tersebut insiden dengan titik
yang sama. Sebagai contoh, e2 dan e7 dalam Gambar 1.1 merupakan dua sisi yang
ajasen. Selain itu, dua buah titik disebut ajasen jika kedua titik tersebut
merupakan titik-titik ujung dari sisi yang sama. Dalam Gambar 1.1, v4 dan v5 adalah dua titik yang saling
ajasen, sedangkan titik v1 dan v4 merupakan dua titik yang tidak saling ajasen.
Jumlah
atau banyaknya sisi yang insiden dengan suatu titik vi (loop
dihitung dua kali), disebut derajat (degree) dari titik tersebut, dinotasikan d(vi ). Sebagai
contoh, dalam Gambar 1.1, d (v1 ) = d (v4 ) = 3, d (v2
) = 4, dan d (v5 ) = 1. Derajat suatu titik sering juga disebut
valensi dari titik tersebut.
Selanjutnya pandang sebuah graph G dengan e
sisi dan n titik v1, v2, ..., vn. Karena tiap sisi menyumbangkan dua derajat, maka jumlah derajat dari
semua titik dalam G sama dengan dua kali jumlah sisi dalam G.
Dengan demikian,
(1)
Sebagai contoh, pada Gambar 1.1
d (v1
) + d (v2 ) + d
(v3 ) + d (v4 ) + d (v5 ) = 3 + 4 + 3 + 3 + 1 =
14
=
dua kali jumlah sisi
Berdasarkan persamaan (1) kita peroleh teorema
berikut.
Teorema
1
Banyaknya
titik berderajat ganjil dalam sebuah graph selalu genap.
Bukti
Jika
titik-titik berderajat ganjil dan genap kita pandang secara terpisah, maka
jumlah ruas kiri persamaan (1) dapat dinyatakan sebagai jumlah dari dua
bilangan. Pertama diperoleh dari titik-titik berderajat ganjil, dan kedua dari
titik-titik berderajat genap. Jadi,
(2)
dengan 
dari titik-titik genap
dan 
dari titik-titik
ganjil.
dari titik-titik genap
dan dari titik-titik
ganjil.
Karena ruas kiri
persamaan (2) genap, dan suku pertama dari Ruas kanan adalah genap, maka suku
kedua ruas kanan juga pasti genap.
= sebuah bilangan
genap. (3)
Karena dalam persamaan (3) tiap d(vk ) adalah bilangan ganjil, maka
jumlah keseluruhannya pastilah genap. (terbukti)
Sebuah
graph dengan semua titiknya berderajat sama disebut graph reguler.
Selanjutnya akan dibahas bagaimana graph dapat
digunakan untuk menunjukkan hubungan tertentu antara objek-objek sembarang.
Untuk mempelajari keterhubungan objek-objek itu secara lebih mendalam, maka
kita perlu mempelajari teori graph secara lebih mendetil. Kita memerlukan
istilah tertentu untuk menunjukkan bagaimana kedudukan titik dan garis dalam
graph itu. Istilah ini berlaku untuk semua graph.
Dua titik P dan Q yang
dihubungkan dengan sebuah garis e dikatakan ajasen. Titik P dan Q
yang terletak pada garis e atau titik P dan Q merupakan
titik ujung garis e dikatakan insiden pada garis e atau garis e
insiden pada titik P dan Q. Pada graph A berikut, titik a
ajasen dengan titik b, tetapi titik a dan c tidak ajasen,
demikian pula titik b dan c tidak ajasen. Titik a insiden
pada sisi e, titik c tidak
insiden pada sisi e. Pada graph B
tidak ada pasangan titik yang ajasen.
e. TITIK TERISOLASI DAN TITIK ANTING/UJUNG
Sebuah
titik yang tidak memiliki sisi insiden disebut titik terisolasi.
Dengan kata lain, titik terisolasi adalah titik yang berderajat nol. Titik v4 dan v7 dalam Gambar 1.7 di bawah ini
adalah dua contoh titik terisolasi. Sebuah titik berderajat satu disebut titik anting/ujung. Titik v3 dalam Gambar 1.7 merupakan
contoh titik anting. Dua sisi yang saling berajasensi atau berbatasan disebut seri
jika titik sekutunya berderajat dua. Dalam
Gambar 1.7, dua sisi yang insiden dengan v1 adalah seri.
 |
1)
Teori graph lahir pada Tahun 1736
melalui tulisan Euler yang mengupas masalah ....
2)
G.R. Kirchoff berhasil
mengembangkan salah satu cabang/bagian teori graph yang disebut teori ....
3)
Para ahli teori graph berkeyakinan
bahwa yang pertama kali mengembangkan atau membahas masalah empat warna adalah
....
4)
Pada Gambar 1.1, sebutkan sebuah
sisi yang dua titik ujungnya sama!
5)
Perhatikan kembali graph pada
Gambar 1.1. Apakah graph tersebut memiliki sisi sejajar?
6)
Apa yang dimaksud dengan graph
sederhana!
7)
Perhatikan kembali graph pada
Gambar 1.1. Sebutkan sisi-sisi yang insiden dengan titik v3!
8)
Jika dua buah sisi yang tidak paralel insiden di sebuah titik
yang sama, maka kedua sisi itu disebut .....
9)
Banyaknya titik berderajat ganjil
dalam sebuah graph selalu ....
10)
Dalam sebuah graph G = (V, E),
himpunan mana yang dimungkinkan merupakan sebuah himpunan kosong?
Petunjuk Jawaban Latihan
1)
Jembatan Konigsberg
2)
Teori pohon
3)
Mobius
4)
Sisi e1
5)
Ya, yaitu e4 dan e5
6)
Graph sederhana adalah graph yang
tidak memuat loop dan sisi paralel
7)
Sisi-sisi yang insiden dengan v3 adalah e4, e5, dan e6
8)
Ajasen
9)
Genap
10)
Himpunan sisi E
Berikut adalah beberapa hal penting menyangkut
sejarah teori graph dan beberapa pengertian dasar terori graph.
1. Teori graph lahir pada Tahun 1736 melalui
tulisan Euler tentang masalah jembatan Konigsberg.
2. Tahun 1647 G.R. Kirchoff pertama kali
mengembangkan teori pohon.
3. A.F. Mobius diyakini sebagai orang pertama
yang mengkaji masalah empat warna dalam pewarnaan sebuah peta.
4. Tahun 1859, Hamilton berhasil menciptakan
sebuah permainan teori graph dengan menggunakan kayu berbentuk dodecahedron.
5. Buku pertama tentang teori graph ditulis
Tahun 1936 oleh D. Konig.
6. Loop adalah sebuah sisi yang dua titik
ujungnya sama.
7. Dua buah sisi yang insiden dengan dua
titik yang sama disebut sisi paralel.
8. Graph sederhana adalah sebuah graph yang
tidak memuat loop dan sisi paralel.
9. Sebuah graph G = (V, E) dengan V dan E
berupa himpunan hingga disebut graph hingga, dan jika sebaliknya disebut graph
tak hingga.
10. Dua sisi yang tidak paralel disebut ajasen,
jika kedua sisi tersebut insiden dengan titik yang sama.
11. Dua buah titik disebut ajasen, jika kedua
titik tersebut merupakan titik-titik ujung dari sisi yang sama.
12. Banyaknya titik berderajat ganjil dalam
sebuah graph selalu genap.
13. Titik terisolasi adalah titik yang tidak
memiliki sisi insiden.
14. Titik anting atau titik ujung adalah sebuah
titik berderajat satu.
 |
1) Jembatan
Konigsberg di daratan Eropa telah menjadi inspirasi kelahiran teori graph.
Orang yang pertama kali membahas masalah jembatan tersebut dengan menggunakan
teori graph adalah ....
A. Hamilton
B. Konigsberg
C. Euler
D. Konig
2) Teori
pohon merupakan bagian teori graph yang sangat penting. Orang yang pertama kali mengemukakan teori ini
adalah ....
A. Kirchoff
B. Konig
C. Hamilton
D. Euler
3) Dua
buah sisi yang insiden pada dua titik yang sama disebut sisi ....
A. seri
B. sejajar
C. insiden
D. ajasen
4) Sebuah
graph yang tidak memuat loop dan sisi paralel disebut graph ....
A. nol
B. tree
C. sederhana
D. terhubung
5) Graph
G = (V, E) disebut graph hingga jika
....
A. V
dan E merupakan himpunan hingga
B. V
merupakan himpunan hingga
C. E
merupakan himpunan hingga
D. V
atau E merupakan himpunan hingga
6) Graph
G = (V, E) disebut graph tak hingga jika ....
A. V
dan E merupakan himpunan hingga
B. V
atau E merupakan himpunan tak hingga
C. V
dan E merupakan himpunan tak hingga
D. V
merupakan himpunan kosong
7)
Derajat titik v2 dari graph di atas adalah ....
A. 1
B. 2
C. 3
D. 4
8) Misalkan
e1 dan e2 adalah dua sisi dari suatu graph G yang tidak
paralel dan v1 dalam G. Jika e1 dan e2 insiden di v1, maka kedua
sisi itu disebut ....
A. ajasen
B. insiden
C. sejajar
D. seri
9) Misalkan
dua titik v1 dan v2 dalam sebuah graph G merupakan titik-titik
ujung dari sebuah sisi e. Maka kedua titik tersebut merupakan titik-titik yang
saling ....
A. seri
B. paralel
C. ajasen
D. insiden
10) Sebuah
titik dalam graph G yang tidak memiliki satu pun sisi insiden disebut ....
A. titik
pendan
B. titik
terisolasi
C. titik
insidensi
D. titik
ajasensi
Cocokkanlah jawaban Anda dengan Kunci Jawaban
Tes Formatif 1 yang terdapat di bagian akhir modul ini. Hitunglah jawaban yang
benar. Kemudian, gunakan rumus berikut untuk mengetahui tingkat penguasaan Anda
terhadap materi Kegiatan Belajar 1.
 |
Arti tingkat penguasaan: 90 - 100% = baik sekali
80
- 89%
= baik
70
- 79%
= cukup
< 70% = kurang
Apabila mencapai tingkat penguasaan 80% atau
lebih, Anda dapat meneruskan dengan Kegiatan Belajar 2. Bagus! Jika
masih di bawah 80%, Anda harus mengulangi materi Kegiatan Belajar 1, terutama
bagian yang belum dikuasai.
Kegiatan Belajar 2
Graph sebagai Model Matematika
dan Aplikasinya
a. GRAPH SEBAGAI MODEL MATEMATIKA
Konstruksi model matematika dapat dibuat dalam
berbagai cara dengan permasalahan matematika yang berbeda-beda. Salah satu
model matematika yang sudah cukup dikenal dan bisa mencakup berbagai
permasalahan adalah teori graph. Pada bagian ini akan disajikan contoh
permasalahan yang dapat dibuat model matematikanya dalam bentuk graph.
Contoh 1
Seorang guru bermaksud membuat suatu diagram
tentang hubungan antar siswa dari kelas yang diajarnya. Diagram tersebut harus
berisikan informasi apakah antara satu siswa dengan siswa lainnya berteman atau
tidak berteman. Hal semacam itu dapat dinyatakan dalam bentuk diagram yang
disebut graph. Dalam graph tersebut, seorang siswa dinyatakan sebagai sebuah
titik dan hubungan berteman antara dua siswa, dinyatakan dengan sebuah sisi
yang menghubungkan titik-titik yang mewakili dua siswa tersebut.
Contoh 2
Dalam suatu persiapan untuk menghadapi perang,
beberapa peleton tentara ditempatkan di beberapa lokasi yang berbeda.
Komunikasi antara peleton dilakukan dengan menggunakan radio telepon yang
kemampuannya terbatas pada jarak tertentu.
Jika jarak antara dua peleton masih
terjangkau, maka komunikasi dapat dilakukan. Keadaan seperti ini dapat
dinyatakan dalam suatu model matematika berbentuk graph. Dalam graph tersebut,
titik menyatakan peleton dan sisi antara dua titik menyatakan komunikasi antara
dua peleton yang diwakili oleh dua titik tersebut.
Contoh 3
Misalkan kita ingin menempuh perjalanan
dari Jakarta menuju Surabaya. Mungkin kita ingin mengetahui rute terpendek yang
dapat dipilih. Dalam permasalahan ini kota direpresentasikan sebagai titik,
sedangkan rute atau jalan direpresentasikan sebagai segmen garis atau kurva.
Contoh 4
Misalnya terdapat satuan tugas dalam
kepolisian yang bertugas mengungkap jaringan pengedar obat terlarang. Hal
tersebut dapat kita gambarkan ke dalam sebuah graph. Dalam graph tersebut,
tiap-tiap anggota komisi dinyatakan dengan sebuah titik, dan hubungan di antara
anggota dinyatakan dengan sisi atau kurva. Dalam permasalahan ini kita mungkin
ingin tahu seberapa rapuhkah jaringan komunikasi ini, dan seberapa mudahkah
kita bisa menghancurkan jaringan tersebut. Dengan menggunakan teori graph
desain jaringan komunikasi yang handal dapat diciptakan.
Contoh 5
Teori graph juga biasanya digunakan
dalam bidang elektronika, misalnya untuk mendesain sirkuit cetakan. Biasanya
sirkuit cetakan pada lembaran silikon harus didesain secara khusus. Berbeda
dengan desain sirkuit yang menggunakan kabel-kabel, sirkuit cetakan tidak boleh
mengandung bagian-bagian konduktor yang saling bersinggungan atau saling
memotong, karena hal tersebut bisa membuat munculnya hubungan pendek. Teori
graph memberi penjelasan apakah suatu pola sirkuit cetakan yang kita miliki
mempunyai pola lain yang sejenis? Apakah sebuah pola sirkuit yang memiliki
hubungan konduktor yang saling berpotongan dapat didesain ulang demikian
sehingga susunannya masih tetap tapi tidak lagi mengandung bagian-bagian yang
saling bersinggungan atau berpotongan? Melalui konsep graph isomorfik kita dapat
mengetahui apakah sebuah sirkuit cetakan memiliki desain lain yang lebih baik
tanpa mengubah susunannya.
b. GRAPH BERARAH SEBAGAI MODEL MATEMATIKA
Sebuah graph berarah D adalah suatu himpunan
yang tidak kosong dengan sebuah relasi R pada V. R adalah relasi yang tidak
refleksif. Seperti halnya dalam graph yang sudah dibicarakan di atas, elemen
dari V disebut titik. Tiap pasangan terurut dalam R disebut sisi berarah atau
arah.
Karena relasi dari sebuah graph berarah D
tidak perlu simetris, maka apabila (u, v) merupakan arah D, (v, u) belum tentu
merupakan arah dari D. Hal semacam ini dapat kita ilustrasikan pada diagram
dengan gambar segmen garis atau kurva antara titik u dan v yang memakai tanda
panah sebagai tanda arah dari u ke v atau dari v ke u. Bila dari u ke v
masing-masing mempunyai arah, maka diagramnya dapat kita buat seperti di bawah
ini (Gambar 1.8).
Misalkan D1 adalah sebuah graph berarah
dengan V = {v1, v2, v3, v4} dan E = {(v1, v2), (v2, v3), (v3, v2)}. Graph berarah D1, dapat
dibuat seperti gambar di bawah ini (Gambar 1.9)
Mungkin juga terjadi bahwa relasi yang
mendefinisikan sebuah graph berarah D merupakan sebuah relasi simetris. Graph
semacam ini disebut Graph berarah simetris. Gambar di bawah ini adalah
contoh sebuah graph simetris.
Contoh 6
Diketahui sebuah graph berarah D dengan
himpunan V = {v1, v2, v3, v4, v5, v6 } dan himpunan arah E = {(v1, v3), (v2, v3), (v3, v4), (v4, v1), (v4, v3), (v5,
v6) }. Gambarlah diagram dari graph
D.
Penyelesaian
Gambar di bawah ini merupakan diagram dari graph
D.
c. JARINGAN KERJA SEBAGAI MODEL MATEMATIKA
Sebuah jaringan kerja adalah sebuah graph
berarah dengan suatu fungsi yang memetakan himpunan sisi ke himpunan bilangan
real. Jaringan kerja yang merupakan sebuah graph disebut jaringan kerja
tidak berarah sedangkan jaringan kerja yang merupakan graph berarah disebut
jaringan kerja berarah. Gambar di bawah ini merupakan contoh diagram
dari dua jenis jaringan kerja tersebut.
Graph bertanda S adalah suatu jaringan kerja tidak berarah
yang nilai fungsinya +1 atau -1. Karena tanda positif atau negatif dipasangkan
pada tiap sisi dari S, maka dapat dipahami bila tiap sisi dari S disebut sisi
positif atau sisi negatif. Sebagai contoh, jika
V
= { v1, v2, v3 }
E = { v1v2, v1v3, v2v3 }
dan
f = { (v1v2, +1), (v1v3, -1), (v2v3, -1) }
maka graph bertanda seperti ini dapat dinyatakan
dalam dua cara yaitu seperti diperlihatkan pada gambar di bawah ini.
Gambar 1.13.
Contoh 7
Hubungan bertetangga dapat dinyatakan dalam
bentuk graph bertanda. Dua keluarga yang saling berhubungan dengan baik dapat
diwakili oleh sisi positif, dua keluarga yang berhubungan kurang baik dapat
dinyatakan dengan sisi negatif dan dua keluarga yang tidak saling berhubungan
atau tidak saling kenal dapat dinyatakan dengan tidak ada sisi antar dua titik
yang mewakili dua tetangga tersebut.
Jaringan kerja tidak berarah yang nilai
fungsinya bulat positif sering kali digunakan sebagai model matematika. Ada dua
cara yang sering digunakan untuk menyatakan jaringan kerja tidak berarah
seperti ini. Sebagai contoh, jika
V
= { v1, v2, v3 }
E = { v1v2, v1v3, v2v3 }
dan
f = { (v1 v2,
2), (v1v3, 1), (v2v3, 3) }
maka jaringan kerjanya dapat dibuat seperti
terlihat pada gambar di bawah ini.
Jaringan kerja tak berarah yang dinyatakan
seperti Gambar 1.14 disebut multigraph. Misalnya M adalah sebuah
multigraph dengan himpunan sisi E dan fungsi f. Jika uv
E dan f(uv) = n (n
adalah bilangan bulat positif), maka u dan v dihubungkan oleh n sisi. Sisi-sisi
seperti ini disebut sisi multipel.
E dan f(uv) = n (n
adalah bilangan bulat positif), maka u dan v dihubungkan oleh n sisi. Sisi-sisi
seperti ini disebut sisi multipel.
Contoh 8
Misalkan v1, v2, dan v3 adalah tiga buah kota. Tiap dua
kota dihubungkan oleh satu jalan yang jaraknya tidak sama. Jika antara salah
satu kota dengan kota lain ditempuh dengan jalan kaki, maka lama perjalanannya
adalah sebagai berikut:
antara v1 dan v2,
dua hari;
antara v1 dan v3,
satu hari;
antara v2 dan v3,
tiga hari.
Situasi seperti ini dapat dinyatakan dalam bentuk
graph seperti pada Gambar 1.14 (a).
Contoh 9
Misalkan v1, v2, dan v3 adalah tiga buah kota. Antara v1 dan v2 terdapat dua jalan, antara v1 dan v3 terdapat satu jalan, sedangkan
antara v2 dan v3 terdapat tiga jalan. Situasi ini dapat
dinyatakan dengan graph seperti
Gambar 1.14 (b).
Bila relasi yang mendefinisikan suatu graph
memuat (v, v) dengan 
, maka nama graph tersebut berubah menjadi graph dengan
loop, graph berarah dengan loop, jaringan kerja dengan loop, atau multigraph
dengan loop.
, maka nama graph tersebut berubah menjadi graph dengan
loop, graph berarah dengan loop, jaringan kerja dengan loop, atau multigraph
dengan loop.
Misalkan
V
= {v1, v2, v3, v4 }, dan
E
= { (v1, v2), (v2, v3), (v3, v2), (v3, v3), (v4, v4) }.
Karena relasi E memuat (v3, v3) dan (v4, v4), maka graph berarah
dengan loop ini dapat digambar seperti di bawah ini.
d. SILSILAH KELUARGA
Silsilah keluarga merupakan contoh masalah
sederhana yang bisa dinyatakan dalam bentuk graph. Graph yang terbentuk dari
silsilah keluarga biasanya berupa pohon atau tree. Gambar 1.16 di
bawah ini adalah contoh silsilah keluarga Andri yang dapat diubah menjadi
sebuah pohon.
e. SISTEM KOMUNIKASI
Perhatikan Gambar 1.17 di bawah ini. Gambar
tersebut merupakan suatu jaringan komunikasi dengan menggunakan komputer. Pada
gambar tersebut, bulatan kecil menyatakan komputer mikro dan bulatan berwarna
hitam kecil menyatakan komputer mini.
Komputer mini digunakan untuk mengubah signal
dari suatu sirkuit ke sirkuit lainnya serta untuk memproses data. Sedangkan
lambang diamond menyatakan komputer mainframe yang merupakan
pusat dari seluruh jaringan. Seseorang yang bermaksud mengakses jaringan
tersebut harus melalui salah satu dari komputer mini yang ada dengan
menggunakan komputer mikro miliknya. Sistem tersebut dapat digunakan untuk
mengirim pesan antarkomputer mikro, atau untuk melakukan proses pengolahan data
dengan menggunakan salah satu komputer yang lebih besar. Melalui diagram atau
graph di atas dapat diajukan berbagai pertanyaan antara lain sebagai berikut:
1. Dapatkah
komputer mikro di Seattle mengirimkan pesan melalui komputer mikro di Miami?
2. Berapa
banyak perubahan signal diperlukan untuk memperoleh pesan yang dikirim dari
Boston ke Los Angeles?
3. Jika
komputer mini di Chicago rusak, apakah pesan dari Boston ke Los Angeles masih
dapat dikirimkan?
4. Jika
sirkuit antara Boston dan New York ada kerusakan, apakah pengiriman pesan dari
Bangor ke Phoenix masih bisa dilakukan?
f. JARINGAN TRANSPORTASI
Masalah transportasi sebenarnya merupakan hal
yang sangat klasik dalam teori graph, karena kelahiran teori graph itu diawali
oleh masalah transportasi yang terkenal yaitu Jembatan Konigsberg. Ilustrasi
jembatan tersebut dapat dilihat pada Gambar 1.18 di bawah ini.
Pada gambar tersebut A, B, C, dan D adalah
daerah-daerah yang dihubungkan oleh tujuh buah jembatan. Situasi seperti ini dapat dinyatakan dalam
bentuk yang sederhana berupa graph seperti diperlihatkan pada Gambar 1.19 di
bawah ini.
g. DESAIN ARSITEKTUR
Perhatikan desain sebuah bangunan pada Gambar
1.20 di bawah ini. Pada gambar tersebut A, B, C, D, dan E menyatakan ruangan
yang ada dalam bangunan tersebut, sedangkan O menyatakan bagian luar bangunan.
Jika A, B, C, D, E, dan O dinyatakan sebagai
titik-titik dan pintu yang menghubungkan antar ruangan atau antara ruangan
dengan bagian luar dinyatakan sebagai sisi, maka situasi pada gambar di atas
dapat dinyatakan sebagai graph seperti pada Gambar 1.21 di bawah ini.
H. IKATAN KIMIA
Dalam bidang kimia pun teori
graph mempunyai kegunaan yang amat penting. Kita mengenal ikatan-ikatan kimia
seperti H2SO4, H2O, CO2, dan CH4.
Tiap molekul kimia mengandung sejumlah atom yang dikaitkan dengan ikatan kimia.
Sebagai contoh, karbon dioksida mempunyai sebuah atom karbon yang dikaitkan
terhadap 2 atom oksigen. Demikian pula dalam C2H5OH
(ethanol), sebuah atom karbon dikaitkan pada 3 atom hidrogen, sedangkan atom
karbon lainnya dikaitkan dengan atom karbon pertama, 2 atom hidrogen dan sebuah
atom oksigen. Atom oksigennya dikaitkan dengan sebuah atom hidrogen, selain
dengan sebuah atom karbon. Perhatikan Gambar 1.22.
Gambar 1.22
Konstruksi C2H5OH
seperti pada gambar di atas termasuk ikatan kimia yang cukup rumit. Dalam teori
graph ikatan kimia ini dapat dinyatakan dengan graph pada Gambar 1.23. Dalam
graph tersebut banyaknya sisi yang menghubungkan sebuah titik menyatakan
valensi dari tiap-tiap atom yang berkorespondensi.
Gambar 1.23
Diagram pada Gambar 1.23 pertama
kali digunakan tahun 1864 untuk menggambarkan bagaimana susunan atom-atom dalam
sebuah molekul. Ide pertama diketengahkan oleh Alexander Crum Brown
(1838-1922), yang pertama kali memperkenalkan fenomena isomerisme, yakni
eksistensi isomer-isomer. Isomer menyatakan molekul-molekul yang mempunyai
rumus kimia yang sama tapi mempunyai sifat kimiawi yang berlainan.
Diagram ini menunjukkan bagaimana sebuah atom
dihubungkan dengan atom lainnya. Informasi ini sangat diperlukan dalam
mempelajari perilaku kimiawi sebuah molekul. Masalah dokumentasi kimia
berhubungan dengan isomorfisme dan masalah pengkodean. Ini menunjukkan bahwa
penyelesaian bagi masalah isomorfisme graph bagian memberikan penyelesaian bagi
masalah penelitian struktur kimia.
|
1) Suatu
sekolah bermaksud membentuk sepuluh macam kepanitiaan yang anggota-anggotanya
diambil dari 15 orang siswa terpilih. Banyaknya anggota dari kepanitiaan yang
dibentuk tidak ditentukan, artinya, bisa beranggotakan sedikit atau bisa juga
banyak. Kemudian setiap siswa dari 15
orang itu dimungkinkan untuk tidak menjadi anggota kepanitiaan atau mungkin
pula merangkap sebagai anggota beberapa kepanitiaan. Berikan dua contoh graph
yang menggambarkan situasi tersebut!
2) Gambarlah
graph berarah dengan himpunan titik V = { v1, v2, v3, v4, v5,
v6 } dan himpunan sisi E = { (v1, v3), (v2, v3), (v3, v4), (v4, v1), (v4, v3), (v5, v6) }.
3) Kota A
dan kota B dihubungkan oleh sebuah jalan umum biasa, sedangkan kota B dan kota
C dihubungkan oleh dua jalan: satu jalan
umum biasa dan satu lagi jalan bebas hambatan yang dikenakan biaya bagi
siapa saja yang melaluinya. Buatlah dua graph yang menggambarkan situasi
seperti ini!
4) Silsilah
keluarga dapat dibuat atau dinyatakan dalam bentuk sederhana berupa graph.
Graph tersebut biasanya berbentuk ....
5) Selain
silsilah keluarga, sebutkan beberapa contoh masalah lainnya yang dapat
dinyatakan dalam bentuk graph!
Petunjuk Jawaban Latihan
1) Untuk
graph G1, misalkan V (G1) menyatakan siswa terpilih yang jumlahnya 15 orang. Dua titik dari G1 dihubungkan dengan sebuah sisi,
jika dan hanya jika dua siswa yang diwakili oleh titik-titik tersebut menjadi
anggota kepanitiaan yang sama. Untuk graph G2, misalkan V (G2) menyatakan 10 kepanitiaan yang dibentuk. Dua titik dari G2 dihubungkan jika dan hanya jika
dua kepanitiaan yang diwakili oleh titik-titik tersebut memuat anggota yang
sama.
2)
3)
4) Tree
atau pohon.
5) Sistem
komunikasi, jaringan transportasi, dan desain arsitektur.
1. Di
antara beberapa model matematika yang
sudah dikenal, graph merupakan salah satu contoh model matematika yang banyak
kegunaannya.
2. Terdapat
beberapa jenis graph yaitu graph tak berarah, graph berarah, dan jaringan
kerja.
3. Sebuah
graph G adalah suatu himpunan hingga V yang tidak kosong yang memenuhi sifat
tidak refleksif dan simetris dari suatu relasi R pada V.
4. Sebuah
graph berarah D adalah suatu himpunan V yang tidak kosong dengan sebuah relasi
R pada V yang tidak refleksif.
5. Jaringan kerja adalah sebuah graph atau graph berarah
dengan suatu fungsi yang memetakan himpunan sisi ke himpunan bilangan real.
6. Graph
dapat diterapkan dalam beberapa permasalahan antara lain masalah silsilah
keluarga, sistem komunikasi, jaringan transportasi, dan desain arsitektur.
1) Berikut
adalah contoh permasalahan yang bisa dinyatakan dalam bentuk graph, kecuali
....
A. masalah
hubungan keluarga
B. masalah
hubungan bertetangga
C. masalah
hubungan pertemanan
D. masalah
pengobatan penyakit menular
2) Sebuah
graph berarah G adalah suatu himpunan hingga titik yang tidak kosong dan sebuah
relasi R yang bersifat ....
A. refleksif
B. tidak
refleksif
C. antisimetri
D. transitif
3) Karena
relasi dari sebuah graph berarah D tidak perlu simetris, maka apabila (u, v)
merupakan arah dari D, (v, u) adalah ....
A. pasti
merupakan arah dari D
B. berlawanan
arah dengan (u, v)
C. searah
dengan (u, v)
D. tidak
perlu merupakan arah dari D
4) Jika
sebuah graph D, (u, v) dan (v, u) keduanya merupakan arah dari D, maka graph
tersebut disebut graph ....
A. berarah
B. berarah
simetris
C. tidak
berarah
D. tidak
berarah simetris
5) Jaringan
kerja yang merupakan graph berarah disebut ....
A. jaringan
kerja biasa
B. jaringan
tidak berarah
C. jaringan
kerja berarah
D. jaringan
kerja semu
6) Misalkan
M adalah sebuah multigraph. Jika uv Î E dan f
(uv) = n, maka u dan v dihubungkan oleh sisi sebanyak ....
A. n
B. n-1
C. n+1
D. n
(n-1)
7) Misalkan
G = (V, E) adalah sebuah multigraph. Jika G memuat (v, v) dengan v anggota V,
maka G disebut ....
A. loop
B. multi
graph dengan loop
C. multi
graph
D. graph
berarah
8) Perhatikan
Gambar 1.20. Banyaknya pintu yang terdapat dalam suatu ruangan sama dengan ...
dari graph yang merepresentasikannya.
A. banyak
sisi
B. banyaknya
sisi berarah
C. derajat
titik
D. banyaknya
loop
9) Masalah transportasi yang terkenal yaitu Jembatan Konigsberg. Masalah tersebut
dapat digambar dalam bentuk graph yang terdiri dari:
A. 4
titik dan 7 sisi
B. 4
sisi dan 7 titik
C. 4
titik dan 4 sisi
D. 7
titik dan 7 sisi
10). Orang pertama yang memperkenalkan fenomena
isomerisme untuk menggambarkan bagaimana susunan atom-atom dalam sebuah molekul
adalah ....
A. Leonhard
Euler
B. Alexander
Crum Brown
C. Konigsberg
D. Hamilton
Cocokkanlah jawaban
Anda dengan Kunci Jawaban Tes Formatif 2 yang terdapat di bagian akhir modul
ini. Hitunglah jawaban yang benar. Kemudian, gunakan rumus berikut untuk
mengetahui tingkat penguasaan Anda terhadap materi Kegiatan Belajar 2.
|
Arti tingkat penguasaan: 90 - 100% = baik sekali
80
- 89%
= baik
70
- 79%
= cukup
< 70% = kurang
Apabila mencapai tingkat
penguasaan 80% atau lebih, Anda dapat meneruskan dengan modul selanjutnya. Bagus!
Jika masih di bawah 80%, Anda harus mengulangi materi Kegiatan Belajar 2,
terutama bagian yang belum dikuasai.
Kunci Jawaban Tes Formatif
Tes Formatif 1
1) C. Baca sejarah perkembangan teori graph.
2) A. Lihat sejarah perkembangan teori graph.
3) B. Lihat definisi sisi sejajar.
4) C. Lihat definisi graph sederhana.
5) A. Lihat definisi graph hingga.
6) C. Lihat definisi graph tak hingga.
7) D. Lihat definisi derajat titik.
8) A. Lihat pengertian ajasensi sisi.
9) C. Lihat pengertian ajasensi titik.
10) B. Lihat definisi titik terisolasi.
Tes Formatif 2
1) D. Graph harus memuat relasi.
2) B. Lihat definisi graph berarah.
3) D. Lihat pengertian graph berarah.
4) B. Lihat pengertian graph berarah.
5) C. Lihat uraian tentang jaringan kerja berarah.
6) A. Jelas.
7) B. Lihat pengertian multi graph.
8) C. Ubah dulu ke dalam graph.
9) A. Lihat gambar graph tentang Jembatan
Konigsberg
10) B. Lihat sejarah aplikasi graph pada ikatan kimia
Daftar Pustaka
Bradley, J. (1988). Introduction to Discrete
Mathematics. New York:
Addison Wesley.
Buckley, F. & Lewinter, M.
(2003). A Friendly Introduction to Graph
Theory. New York: Pearson Education, Inc.
Chartrand, G. (1985). Introductory Graph
Theory. New York: Dover
Publications.
Deo, N. (1989). Graphh Theory with
Applications to Engineering and Computer Science. New Delhi: Prentice-Hall.
Suryadi, D. (1996). Matematika Diskrit.
Jakarta: Universitas Terbuka.
Sutarno, H., Priatna, N., & Nurjanah (2005). Matematika Diskrit. Malang: UM Press.
Witala, S.A.
(1987). Mathematics. New York: McGraw-Hill.
Glosarium
Ajasensi
Kedudukan dua titik (misal P dan Q) yang
dihubungkan dengan sebuah sisi e.
Derajat Titik
Banyaknya sisi yang insiden dengan suatu titik.
Graph
Sekumpulan objek (V = {v1, v2,
…} yang disebut himpunan titik), dan sebuah himpunan lain (E = {e1,
e2, …} yang merupakan himpunan sisi) sedemikian hingga tiap sisi
ek dikaitkan dengan suatu pasangan titik tak terurut (vi,vj).
Graph Berarah
Suatu graph yang sisi-sisinya
mempunyai arah.
Graph Berarah Simetris
Suatu graph berarah yang
merupakan sebuah relasi simetris.
Graph Bertanda S
Suatu jaringan kerja tidak
berarah yang nilai fungsinya +1 atau -1.
Graph Hingga
Sebuah graph G (V,E) dengan V
dan E hingga.
Graph Nol
Sebuah graph G = (V,E) dengan E
= 0.
Graph Sederhana
Sebuah graph yang tidak memiliki loop dan sisi paralel.
Graph Tak Hingga
Sebuah graph G (V,E) dengan V
dan E tak hingga.
Insidensi
Kedudukan dua titik (misal P dan Q) yang
terletak pada sisi e atau titik P dan Q merupakan titik
ujung sisi e.
Jaringan Kerja
Sebuah graph berarah dengan suatu fungsi yang
memetakan himpunan sisi ke himpunan bilangan real.
Jaringan Kerja Berarah
Jaringan kerja yang merupakan graph berarah.
Jaringan Kerja Tidak Berarah
Jaringan kerja yang merupakan sebuah graph.
Loop
Sisi yang dua titik ujungnya sama.
Seri
Dua sisi yang saling berajasensi atau berbatasan jika
titik sekutunya berderajat satu.
Sisi Paralel
Dua titik yang berlainan dihubungkan oleh dua sisi
atau lebih.
Titik Anting/Ujung
Sebuah titik yang berderajat satu.
Titik Terisolasi
Sebuah titik yang tidak memiliki sisi insiden atau
titik yang berderajat nol.
Valensi
Derajat suatu titik.
.jpg)
0 komentar:
Posting Komentar