Planaritas
Drs.
Emut, M.Si
UNIVERSITAS PENDIDIKAN INDONESIA
P
|
ada Modul 4, Anda telah
mempelajari koleksi jenis graph yang disebut pohon. Anda pun telah mempelajari
sifat-sifat pohon dan bermacam-macam pohon. Salah satu sifat yang menarik dalam
pohon G(p,q) adalah hubungan antara banyaknya simpul dan banyaknya rusuk, yakni p = q + 1. Sifat ini dan sifat lainnya
akan digunakan dalam pembahasan modul-modul selanjutnya. Oleh karena itu Anda
diharapkan untuk selalu mengingat-ingat konsep-konsep penting tersebut.
Dalam Modul 5 ini, akan
dibahas sifat planaritas dari suatu graph. Graph planar G(p,q) adalah suatu koleksi
graph yang dapat dibentangkan atau dipancangkan dalam sebuah bidang datar
dengan sifat tidak ada dua rusuk yang berpotongan. Di samping definisi graph
planar, akan dibicarakan juga tentang ciri-ciri graph planar, rumus Euler, genus,
graph polihedral, dan diakhiri dengan graph infinit.
Setelah menyelesaikan
modul ini Anda diharapkan akan memiliki kemampuan-kemampuan sebagai berikut:
1. menjelaskan perbedaan antara graph planar
dan graph sebidang;
2. menghitung banyaknya daerah suatu graph
planar;
3. menjelaskan daerah terhubung sederhana;
4. menjelaskan rumus Euler pada graph sebidang
serta perluasan rumus itu;
5. menjelaskan bahwa graph bipartit lengkap
3-3 (K3,3) dan graph lengkap 5 (K3) adalah nonplanar;
6. menjelaskan mengapa hanya terdapat lima
graph polihedral;
7. menghitung banyaknya rusuk, titik, dan sisi
setiap polihedral;
8. menjelaskan makna genus untuk suatu
permukaan;
9. menjelaskan graph-graph yang bergenus 1;
10. menjelaskan daerah terhubung sederhana (2-sel)
pada torus;
11. menggambarkan beberapa graph lengkap yang
dapat dipancangkan pada bola dan torus;
12. menuliskan beberapa rumus tentang graph-graph
nonplanar;
13. menjelaskan graph-graph dual dan graph-graph
infinit;
14. menggambarkan beberapa graph teroidal.
Kemampuan tersebut
sangat penting bagi semua guru matematika SMU. Dengan kemampuan ini cakrawala
matematika Anda akan menjadi semakin luas dan akan menambah rasa percaya diri dalam mengajar serta
bergaul. Dampak positip lain, Anda akan makin cinta terhadap bidang studi
matematika ini dan akan tumbuh rasa bangga dan bahagia terhadap tugas mengajar
matematika sendiri. Kondisi ini akan dapat memotivasi Anda untuk meningkatkan
profesionalitas kerja, khususnya pengabdian Anda dalam mengajar.
Untuk membantu Anda
menguasai kemampuan di atas, dalam modul ini akan disajikan pembahasan dalam
dua Kegiatan Belajar (KB) sebagai berikut:
Kegiatan Belajar 1 : Graph
Planar dan Graph Sebidang.
Kegiatan Belajar 2 : Genus
suatu Graph dan Graph Dual.
Agar Anda berhasil
dengan baik dalam mempelajari modul ini, ikuti petunjuk belajar sebagai
berikut:
1. Bacalah dengan cermat bagian
Pendahuluan modul ini sampai Anda memahami apa, untuk apa, dan bagaimana
mempelajari modul ini.
2. Baca
sepintas bagian demi bagian dan temukan kata-kata kunci dan kata-kata yang Anda anggap baru.
Jangan terkejut jika Anda belum memahami pada pembacaan yang pertama.
3. Tangkaplah pengertian demi pengertian dari isi modul ini
melalui pemahaman sendiri dan tukar pikiran dengan mahasiswa/guru
lain atau dengan tutor Anda.
4. Jika pada pembacaan yang pertama dan Anda
belum paham adalah kejadian yang wajar. Coba ulangi lagi. Gunakan
alat-alat bantu pensil dan kertas untuk coret-coret bilamana diperlukan.
5. Mantapkan pemahaman Anda melalui diskusi
mengenai hasil pemahaman Anda dalam kelompok kecil atau bersama tutor.
Kegiatan Belajar 1
Graph Planar dan Graph
Sebidang
K
|
onsep utama dalam teori
graph adalah planaritas dan bilangan kromatik. Kombinasi kedua konsep itu
memunculkan permasalahan pelik yang terkenal dengan: Masalah Empat Warna. Pada
Kegiatan Belajar 1 ini akan didiskusikan konsep planaritas.
GRAPH PLANAR DAN GRAPH SEBIDANG
Suatu graph planar G(p,q) adalah graph yang
dapat digambarkan di bidang datar sehingga tidak ada dua rusuknya yang
berpotongan kecuali pada simpul-simpulnya.
Contoh 1
Diberikan
suatu graph G(5,9), sebagai berikut
Gambar 5.1
Graph
G di atas, dapat digambarkan pada bidang datar dengan beberapa bentuk. Gambar
5.1 (a) merupakan salah satu gambar graph G dengan rusuk-rusuk yang berpotongan.
Namun demikian, G dapat digambarkan pada bidang datar tanpa adanya perpotongan
rusuk-rusuknya kecuali pada simpul-simpulnya, sebagaimana terlihat pada Gambar
5.1 (b). Menurut definisi diketahui bahwa G adalah graph planar.
Graph planar yang telah digambar di
bidang datar sedemikian rupa sehingga tidak ada dua rusuknya yang berpotongan
disebut graph sebidang.
Jadi,
graph pada Gambar 5.1 (a) adalah bukan graph sebidang, akan tetapi graph
pada Gambar 5.1 (b) adalah graph sebidang.
Misalkan G adalah graph
sebidang dan perhatikanlah bagian-bagian bidang datar yang ditinggalkan setelah
kita mengangkat rusuk-rusuk dan simpul-simpul dari G (boleh dibayangkan bahwa
bidang tempat gambar di buat dari tanah liat). Potongan-potongan bidang
terhubung ini disebut daerah (region) dari G. Daerah dalam G terdiri
atas 2 jenis yaitu daerah dalam dan daerah luar. Setiap graph
sebidang senantiasa mempunyai satu daerah luar.
Simpul-simpul
dan rusuk-rusuk dari G yang bertemu dengan daerah R membangun suatu batas dari
R. Banyaknya rusuk yang dilalui dalam menetapkan batas suatu daerah R, yang
dimulai dari suatu simpul dan kembali ke simpul tersebut dinamakan derajat
daerah R ditulis der(R).
Untuk memberi gambaran
tentang pengertian batas, daerah dan derajat R, marilah kita bahas graph
berikut.
|
|||||||
|
|||||||
|
|||||||
|
|||||||
Gambar 5.2
Dalam Gambar 5.2, graph G1
mempunyai tiga daerah, yakni dua daerah dalam dan satu daerah luar. Graph G2
mempunyai satu daerah luar dan G3 mempunyai enam daerah. Batas-batas
daerah R1 di G3 terdiri atas simpul-simpul b, c, dan d dan
rusuk-rusuk bc, bd, dan cd sehingga der (R1) = 3. Dengan cara yang sama
diperoleh der(R2) = der(R3) = der(R4) = der(R5)
= 3. Sedangkan batas-batas daerah luar R6, terdiri atas
simpul-simpul a, b, c, e, f, dan g dan rusuk-rusuk ab, bc, ce, ef, fg, dan gb. Dalam
menentukan der(R6) proses penghitungan dapat dilakukan dari simpul a
dan didapat rusuk-rusuk yang dilalui
adalah ab, bc, ce, ef, fg, gb dan ab sehingga der(R6) = 7. Berdasarkan hasil penghitungan
der(Ri) dalam G3 didapat hubungan antara jumlahan derajat
dari daerah G3 adalah sama dengan 2 kali banyak rusuk, yaitu
3+3+3+3+3+7 = 2 . 11. Fakta ini ternyata berlaku secara umum, yaitu jika G(p,q)
suatu graph sebidang, terhubung dan memiliki r daerah maka berlaku ∑ der(R) = 2
q.
Graph sebidang G1 pada Gambar 5.2 mempunyai p
= 4 simpul, q = 5 rusuk, dan r = 3 daerah; G2 mempunyai p = 7, q =
11, dan r = 6. Perhatikanlah bahwa dalam
ketiga kasus itu berlaku p - q + r = 2.
Kondisi ini bukan suatu
kebetulan, sebab setiap graph
sebidang G(p,q) dengan r daerah berlaku hubungan p – q + r = 2. Persamaan tersebut merupakan temuan Matematikawan Leonard Euler
yang dikenal dengan Teorema Euler untuk graph sebidang.
RUMUS
EULER DAN PERLUASANNYA
Teorema 5.1. (Rumus Euler)
Jika G(p,q) adalah graph sebidang terhubung yang mempunyai
r daerah maka p - q + r = 2.
Catatan
Graph G(p,q) sebidang terhubung
adalah syarat perlu untuk berlakunya p - q + r = 2, tetapi bukan syarat perlu
dan cukup. Maksudnya, jika berlaku p - q + r = 2, belum tentu graph G(p,q)
sebidang terhubung. Kita buktikan rumus Euler tersebut.
Bukti
Kita gunakan induksi
matematik atas banyaknya rusuk q.
(i) Jika G graph sebidang terhubung dengan
banyak rusuk q = 1, maka G adalah pohon sehingga banyaknya simpul p = 2 (ingat
p = q+1) dan memiliki banyaknya daerah r = 1. Akibatnya, diperoleh p - q + r = 2 - 1 + 1 = 2. Jadi rumus benar
untuk q = 1.
(ii) Diasumsikan rumus benar untuk graph terhubung
dengan banyak simpul p, banyak rusuk q = k dan banyak daerah r, yakni, p - k + r = 2.
(iii) Akan dibuktikan rumus juga benar untuk q = k +
1. Ambillah sebarang graph terhubung
sebidang G dengan banyak simpul p, banyak rusuk q = k + 1, dan banyak daerah r. Akan
dibuktikan bahwa p - (k + 1) + r = 2.
Ada dua kasus yang mungkin, yaitu untuk G pohon dan G bukan pohon.
Kasus
1.
Jika
G pohon maka berlaku rumus p = q + 1 sehingga didapat p = k + 1 + 1 = k + 2 dan memiliki r = 1. Dengan
demikian diperoleh p - (k+1) + r = (k+2) - (k+1) + 1 = 2. Jadi rumus benar
untuk q = k + 1.
Kasus
2.
Misalkan
G bukan pohon. Karena G terhubung dan bukan pohon maka G mempunyai sikel S.
Pilih salah satu rusuk e pada S. Pandang G - e adalah graph terhubung dengan
banyak simpul p, dan banyak rusuk (k+1) - 1 = k, dan banyak daerah r - 1, sebab
sebuah rusuk adalah batas dua daerah. Karena G - e mempunyai rusuk sebanyak k,
menurut asumsi pada (ii), rumus benar untuk graph G - e, sehingga: p - k + (r -
1) = 2 menjadi p - (k+1) + r = 2. Jadi, berlaku untuk G bukan suatu pohon.
Berdasarkan bukti
tersebut, diperoleh kesimpulan bahwa persamaan p + q – r = 2 berlaku untuk
setiap banyak rusuk q dan terbuktilah Teorema 5.1.
Teorema 5.2.
Jika G adalah graph sebidang terhubung dengan banyak
simpul p, p > 3, dan banyak rusuk q maka berlaku q < 3p -
6.
Catatan.
Kontra positif dari teorema
ini adalah jika q > 3p - 6 maka graph G(p, q) tidak terhubung planar.
Konversnya belum tentu benar; artinya, jika dalam graph G(p,q) berlaku q <
3p-6, maka G(p,q) belum tentu planar terhubung. Sekarang kita buktikan
Teorema 5.2.
Bukti
Bukti
dengan teknik langsung. Untuk p = 3, q paling banyak 3. Jadi rumus benar.
Misalkan G adalah graph terhubung sebidang dengan p > 4. Misalkan
banyak daerah adalah r. Setiap daerah paling sedikit dibatasi oleh 3 rusuk,
jadi r daerah paling sedikit dibatasi oleh 2/3 banyaknya rusuk (setiap rusuk
menjadi batas 2 daerah). Karena banyaknya rusuk adalah q, maka
q
³ 3r/2 atau r £ 2q/3 (1)
Menurut Teorema
5.1, p
- q + r = 2, (2)
(1) masuk (2), menjadi p - q + 2q/3 ³ 2
yakni 3p
- 3q + 2q > 6
atau q
< 3p - 6.
Teorema
5.3.
Graph bipartit lengkap K3,3 adalah non planar
Bukti
Andaikan K3,3 planar.
Lihat Gambar 5.3(a). Banyaknya simpul p = 6, banyaknya rusuk q = (3.6)/2 = 9.
Menurut Teorema 5.1, p - q + r = 2, sehingga r = 2 - 6 + 9 = 5. Jika K3,3 planar, maka satu daerah yang terjadi paling
sedikit dibatasi oleh 4 rusuk. Jadi 2q > 4r dan karena q = 9, maka 18 £ 4r atau r £ 9/2, yang tentu saja kontradiksi dengan r = 5.
Pengandaian harus diingkar.
Teorema 5.4.
Graph lengkap K5 adalah non planar.
Bukti
Karena G adalah graph lengkap K5 maka dipeorleh p = 5 dan q = 5 (5-1)/2
= 10. Akibatnya, didapat 3p – 6 = 3. 5 – 6 = 9 < q = 10. Menurut
kontrapositif dari Teorema 5.2 didapat jika q > 3p – 6 maka G bukan graph terhubung planar. Jadi, K5
adalah graph non planar .
Teorema 5.5.
Setiap graph planar G memuat
suatu simpul v sedemikian rupa sehingga deg v < 5.
Catatan
Kontra positif dari Teorema 5.5. adalah jika setiap
simpul dalam G berderajat 6 atau lebih maka G adalah graph non planar.
Bukti
Andaikan semua simpul
dalam G(p,q) berderajat 6 atau lebih maka menurut Teorema Jabat tangan didapat
2 q = ∑ der(v) ≥ ∑ 6 = 6p sehingga q ≥ 3p. Pada sisi lain, menurut Teorema 5.2
diperoleh q £ 3p – 6, sehingga q < 3p. Hal Ini kontradiksi dengan q
≥ 3p. Akibatnya, pengandaian salah, sehingga tidak semua simpul berderajat 6
atau lebih. Dengan kata lain, terdapat suatu simpul v dalam G dengan deg v £ 5.
SUBDIVISI SUATU GRAPH
Misalkan G suatu graph. Graph subdivisi G adalah suatu graph yang diperoleh dari G
dengan memasukkan simpul-simpul berderajat 2 ke dalam rusuk-rusuk dari G
(beberapa pengarang menyebutnya dengan konfigurasi atau kontraksi).
Contoh 2
Diberikan
3 graph, yaitu graph G, H dan F, sebagaimana pada Gambar 5.4. Graph H adalah
suatu graph yang diperoleh dari G dengan memasukkan dua simpul berderajat dua,
yakni u dan v. Menurut definisi, H merupakan graph subdivisi dari G, sedangkan
F bukan graph subdivisi dari G.
|
||||
|
||||
Sekarang akan dibicarakan
teorema yang sangat terkenal dalam teori graph, yakni Teorema Kuratovski. Akan
tetapi, buktinya terlalu panjang untuk disajikan di sini. Bukti teorema dapat
dilihat, antara lain pada Berge, C. dalam “The Theory of Graph and Its
Applications”, John Wiley and Sons, New York, 1962 atau pada Liu, C.L, “Introduction to Combinatorical Mathematics”,
McGraw-Hill Company, New York, 1966.
Teorema 5.6 (Teorema Kuratovski)
Suatu graph G adalah planar jika dan
hanya jika G tidak memuat subgraph yang isomorphik dengan K3,3 atau K5 atau sebarang subdivisi dari K3,3 atau K5.
Contoh 3
Graph bipartet lengkap
3,4, yakni K3,4 adalah graph non planar karena K3,4
memuat K3,3.
GRAPH PLATONIK (GRAPH POLIHEDRAL)
Graph platonik adalah graph planar yang memiliki
sifat : semua simpulnya berderajat sama, yakni d1, dan semua
daerahnya dibatasi oleh banyak rusuk
yang sama, yakni d2, dengan ketentuan d1 > 3, d2 > 3. Graph platonik adalah “kerangka” dari polihedral
pejal atau masif. Nama-nama seperti: polihedral, polihedron, benda platonik,
dan bidang banyak teratur sering dipakai secara sinonim.
Marilah kita analisis
apa saja polihedral itu. Misalkan G(p,q) adalah graph platonik dengan banyak
daerah r.
1. Berdasarkan Teorema Jabat tangan, diperoleh
bahwa jumlahan dari derajat simpul-simpul yaitu pd1 sama dengan 2 banyaknya rusuk, yaitu 2q. ( ingat : ∑ deg (v)
= 2 q). Jadi pd1 = 2q atau q = (pd1)/2
2. Banyaknya daerah adalah r, dan setiap
daerah dibatasi oleh d2 rusuk. Maka
banyaknya rusuk adalah rd2/2.
Jadi kita peroleh q = rd2/2.
Jika kita gunakan hasil pada (1), maka (pd1)/2 =
rd2/2 atau r = (d1/d2)p.
3. Menurut Rumus Euler (Teorema 5.1), p - q +
r = 2. Jika hasil-hasil pada (1) dan (2) kita substitusikan di sini, maka
diperoleh
p – (d1p)/2 + (d1/d2)p
= 2.
Kedua ruas dikalikan
dengan 2d2 sehingga
2d2 p – d1p d2 + 2d1p = 4d2
atau (2d1
+ 2d2 – d1d2)p = 4d2
4. Karena p dan 4d2 adalah bilangan bulat positif, maka dari hasil
dalam (3) dapat disimpulkan bahwa 2d1 + 2d2 - d1d2 > 0.
Ketaksamaan ini dapat dianalisis selanjutnya sebagai berikut:
d1d2 - 2d1 - 2d2 + 4 < 4
(d1 - 2) (d2 - 2) <
4.
5. Karena d1 > 3, d2 > 3, maka ada pasangan-pasangan d1 dan d2 tertentu
saja yang memenuhi ketaksamaan itu. Perhatikanlah Tabel di bawah ini untuk
berbagai nilai d1 dan d2 yang memenuhi (4) beserta nilai p,q dan r yang
terkait.
d1
|
d2
|
(3)
p=4d2/(2d1+2d2-d1d2)
|
(1)
q=d1p/2
|
(2)
r=(d1/d2)p
|
Nama
Polihedron
|
3
|
3
|
p
= 12/3 = 4
|
q
= 6
|
r
= 4
|
Tetrahedron = bidang 4 teratur
|
3
|
4
|
p
= 16/2 = 8
|
q
= 12
|
r
= 6
|
Heksahedron = bid. 6 teratur = kubus
|
3
|
5
|
p
= 20/1 = 20
|
q
= 30
|
r
= 12
|
Dodekahedron = bidang 12 teratur
|
4
|
3
|
p
= 12/2 = 6
|
q
= 12
|
r
= 8
|
Oktahedron = bidang 8 teratur
|
5
|
3
|
p
= 12/1 = 12
|
q
= 30
|
r
= 20
|
Ikosahedron = bidang 20 teratur
|
Benda-benda platonik
diberi nama menurut banyaknya daerah. Sebagai catatan, jika benda platonik
masif atau dimensi 3 maka daerah ini adalah ‘sisi’ dinotasikan S, simpul
disebut ‘titik-sudut’, dilambangkan T, dan rusuk tetap diberi nama ‘rusuk’
benda itu, dilambangkan dengan R. Akibatnya, Rumus Euler menjadi: T - R + S = 2. Graph
platonik pada tabel di atas, masing-masing disajikan pada Gambar 5.5.
berikut :
Gambar polihedral pejal
diperlihatkan pada Gambar 5.6. di bawah ini
|
Contoh
4
Buktikanlah bahwa graph
terhubung planar G dengan banyak simpul kurang dari 12 mempunyai suatu simpul
dengan derajat paling banyak 4.
Catatan
Kontra positif dari Contoh 4
adalah jika G suatu graph dengan banyak simpul kurang dari 12 dan setiap
simpulnya berderajat 5 atau lebih.
Penyelesaian
Akan dibuktikan dengan
teknik kontra positif. Berdasarkan ketentuan diketahui bahwa graph G(p,q),
dengan p £ 11. Andaikan untuk
setiap simpul v di G berderajat 5 atau lebih, yakni, deg v > 5 untuk
setiap v di G. Akibatnya, banyaknya rusuk di G lebih dari 5.11 = 55. Menurut
Teorema Jabat tangan diperoleh 2q > 55 atau q > 28. Dari
pihak lain, menurut Teorema 5.2, didapat q < 3p - 6 = 33 - 6 = 26.
Kontradiksi. Pengandaian harus diingkar, yaitu tidak semua simpul berderajat 5 atau lebih. Dengan kata lain,
terdapat simpul dalam G dengan derajat 4 atau kurang.
Contoh
4
Selidikilah, apakah graph pada Gambar 5.7.(a)
merupakan graph planar?
Penyelesaian
Mula-mula carilah
sirkuit yang terpanjang. Kita peroleh sirkuit itu adalah a, f, c, h, d,
g, e, a yang memuat semua ke delapan simpul. Sekarang cobalah menambahkan
keempat rusuk-rusuk yang lain, ah, bf, cg, dan de. Dengan cara mengambil
simetri dalam-dan-luar, kita dapat
memulai dengan menggambar ah, di sebelah dalam. Lihat Gambar 5.7(b). Kemudian,
bf dan cg harus berada di sebelah luar. Artinya, G dapat digambarkan dalam
bidang datar sehingga tidak terdapat rusuk-rusuk yang berpotongan kecuali pada
simpul-simpul. Jadi, G adalah graph planar.
Contoh
5
Buktikanlah bahwa graph
Petersen (yakni graph reguler-3 dengan 10 simpul) adalah non planar. Lihat
Gambar 5.8(a).
Bukti
Graph dalam Gambar 5.8
mempunyai p = 10, q = (10.3)/2 = 15.
Menurut Teorema 5.2, q < 3p - 6 atau 15 < 3.10 - 6 = 24.
Jadi memenuhi Teorema 5.2. Maka graph Petersen planar. Bukti ini salah.
Sebab konvers dari teorema tidak berlaku. Mohon Anda amati lagi Teorema 5.2
dengan teliti. Bukti yang benar adalah sebagai berikut.
Kita coba mencari
subdivisi K3,3 atau K5
(Teorema Kuratovski). Perhatikan dua himpunan simpul M = {1, 2, 3} dan N = {a,
b, c}. Himpunan simpul membentuk K3,3 . Ternyata terdapat H suatu
graph bagian dari graph Peterson dan merupakan graph subdivisi K3,3.
Tepatnya, H diperoleh dari K3,3 dengan memasukkan 4 simpul
berderajat dua, yaitu simpul u, v, w dan y. (Perhatikan Gambar 5.8 (b)). Berdasarkan
Teorema Kuratovski disimpulkan bahwa graph Peterson merupakan graph nonplanar.
Alternatif. Andaikan graph tersebut terhubung planar. Daerah-daerah yang
terbentuk dibatasi oleh paling sedikit 4 rusuk. Jika banyaknya daerah adalah r
maka banyaknya rusuk 4r/2 = 2q, atau r = q. Jadi r = q = 15. Menurut Teorema
5.1 (Rumus Euler), r = 2 - p + q = 2 - 10 + 15 = 7. Kontradiksi dengan r = 15 sehingga pengandaian harus diingkar,
yaitu graph Peterson adalah graph non planar.
Contoh 6
Tentukan banyaknya diagonal ruang
pada ikosahedron dimensi 3?
Penyelesaian :
Dalam ikosahedron (bidang-20 teratur) dimensi 3 didapat
r = 20 dan setiap daerah (sisi) merupakan ‘segitiga’ sehingga q = 20 . 3/2 = 30.
Dengan Teorema Euler, diperoleh p = q – r + 2 = 30 – 20 + 2 = 12. Kemudian,
banyaknya garis yang menghubungkan dua simpul adalah 12 . 11 / 2 = 66. Jadi, banyaknya
garis diagonal = 66 - 30 = 36.
Cara lain.
Sebuah simpul v berdekatan (berikatan) dengan 5
simpul yang merupakan ‘rusuk’. Hal itu berakibat, banyaknya simpul yang
berjauhan (merupakan rusuk tetapi jauh) adalah 12 - 1 - 5 = 6. Karena p = 12 simpul(titik)
maka banyaknya diagonal = 12 . 6/2 = 36.
 |
1) Apakah perbedaan antara graph planar dan
graph sebidang?
2) Berdasarkan graph H, pada Gambar 5.4,
buktikan bahwa jumlahan dari derajat daerah-daerah dalam H sama dengan 2 kali
banyaknya rusuknya.
3) Jika graph G(p,q) terhubung dan q ≤ 3p – 6,
maka G(p,q) planar. Benarkah? Jelaskan jawaban Anda!
4) Buktikan, jika G(p,q) suatu graph planar,
terhubung dengan p ≥ 4 dan tidak memuat sikel segitiga maka q ≤ 2p – 4.
5) Tunjukkan bahwa K2,14 adalah
suatu subdivisi dari K2,10.
Periksa dan teliti
kembali jawaban Anda, sekarang cocokkan jawaban dengan kunci jawaban berikut
ini.
Petunjuk Jawaban Latihan
1) Graph planar adalah graph yang dapat
digambar dalam bidang datar dengan cara demikian sehingga tidak ada dua rusuk
yang berpotongan, sedangkan graph sebidang adalah graph planar yang telah
digambar di bidang datar tanpa ada dua rusuk yang berpotongan. Setiap graph
sebidang merupakan graph planar dan tidak berlaku sebaliknya.
2) Graph H(7,7) dan memiliki 2 daerah yaitu daerah
dalam R1 dan daerah luar R2, der(R1) = 9 serta
der(R2) = 5 sehingga 9 + 5 = 14 = 2 . 7.
3) Salah. Konversnya belum tentu benar,
contohnya graph sebagai berikut: Lihat graph di bawah ini (Gambar 5.9). p = 7,
q = 14, jadi q £ 3p – 6 benar, akan tetapi G tidak planar, sebab memuat
subgraph K5.
 |
Gambar 5.9.
4) Karena G(p, q) tidak memuat sikel segitiga
maka setiap daerah dalam G dibatasi paling sedikit 4 rusuk. Untuk r daerah maka
didapat 4r ≤ 2q atau r ≤ ½ q. Dari sisi
lain, berdasarkan Teorema 5.2. didapat p
- q + r = 2 sehingga r = q – p + 2. Dengan mensubstitusikan r diperoleh q - p + 2 ≤ ½ q sehingga q - ½ q ≤ p – 2. Jadi, berlaku q ≤ 2p
– 4.
5) Ambillah 4 simpul yang berderajat dua pada K2,14,
maka menjadi K2,10.
Graph planar adalah graph
yang dapat digambar pada bidang datar sedemikian hingga tidak ada dua rusuk
saling berpotongan, kecuali pada simpul, sedang graph sebidang adalah graph planar
yang telah digambar pada bidang datar. Graph bipartet lengkap K3,3
dan graph lengkap K5 adalah graph non planar. Semua graph yang
memuat graph yang isomorfik dengan K5 atau K3,3 atau
graph subdivisi dari K5 atau K3,3 adalah non planar.
Jika graph G(p,q) terhubung
sebidang, maka berlaku rumus Euler yaitu p – q + r = 2, dengan r adalah
banyaknya ‘daerah’ dalam graph sebidang itu. Perluasan Teorema Euler adalah
jika graph G(p,q) terhubung dan planar maka berlaku q < 3p – 6. Untuk
meneliti planaritas suatu graph G(p,q)
dapat digunakan kontra positif Teorema 5.2. Selain itu, dapat pula dengan
menggambar langsung dengan langkah-langkah sebagai berikut:
1. Carilah sirkuit terpanjang di G yang memuat
semua simpulnya.
2. Gambarlah rusuk-rusuk yang belum dipakai
dengan cara simetri-dalam-dan-luar.
 |
1) Tentukan banyaknya simpul dan derajat daerah
R dari graph G pada Gambar 5.10, di bawah ini.
 |
 |
 |
|
 |
Gambar 5.10
A. 9 simpul,
der(R) = 4
B. 11 simpul, der(R) = 12
C. 9 simpul,
der(R) = 12
D. 9 simpul,
der(R) = 10
2) Manakah di antara graph-graph G, H, dan K
dalam Gambar 5.11 yang merupakan graph non planar?
A. G dan H
B. G dan K
C. H dan K
D. tidak ada
3) Berapakah nilai der(Ri), i = 1, 2,
3, 4 dari graph G berikut
 |
A. der(R1)=8, der(R2)=12,
der(R3)=4, der(R4)=5
B. der(R1)=9, der(R2)=11,
der(R3)=4, der(R4)=5
C. der(R1)=9, der(R2)=12,
der(R3)=4, der(R4)=5
D. der(R1)=8, der(R2)=11,
der(R3)=4, der(R4)=5
4) Perhatikan pernyataan-pernyataan berikut :
1. Setiap subgraph dari graph planar adalah planar
2. Setiap subgraph dari graph non planar adalah non planar
3. Setiap graph yang memuat subgraph planar adalah planar
4. Setiap graph yang memuat subgraph non planar adalah non
planar.
Pernyataan
yang benar adalah
A.
1 dan 2
B.
1 dan 4
C.
2 dan 3
D.
3 dan 4
5) Jika G(p,q) adalah graph terhubung planar,
maka gambar penyajian graph sebidangnya ada bermacam-macam bentuk yang mungkin.
Banyaknya daerah r dari graph sebidang yang disajikan adalah:
A. tergantung cara penggambaran
B. tergantung dapat digambar atau tidaknya
C. banyak daerahnya sama
D. tergantung sirkuitnya
6)
Perhatikanlah
graph sebidang pada Gambar 5.13. Segi-n adalah daerah dalam graph
sebidang yang batasannya ada sebanyak n rusuk. Banyaknya segi-3, segi-4 dan
segi-5 dalam graph G adalah
 |
Gambar 5.13
A. 1 segi-3, 1 segi-4 dan 1 segi-5
B. 1 segi-3, 1 segi-4 dan 2 segi-5
C. 2 segi-3, 1 segi-4 dan 1 segi-5
D. 2 segi-3, 1 segi-4 dan 2 segi-5
7) Bilangan pemotongan dari graph G, dinotasikan
c(G) adalah bilangan minimum dari pasangan-pasangan rusuk yang berpotongan jika
G digambar dalam bidang datar. Akibatnya, jika G suatu graph planar maka c(G) = 0. Besarnya nilai dari c(K5)
adalah ...
A. 1
B. 2
C. 3
D. 5
8) Graph G disebut graph kritis jika G graph
nonplanar tetapi subgraphnya G – v adalah planar, untuk sebarang simpul v di G.
Diantara graph berikut yang merupakan graph kritis adalah ..
A. K6
B. K3,3 dan K5
C. K3,4 dan K6
D. Setiap graph subdivisi dari K5 atau
K3,3
9) Berapakah banyaknya diagonal ruang pada
dodekahedron dimensi 3?
A. 10
B. 40
C. 36
D. 100
10) Berapakah banyaknya diagonal ruang terpanjang
pada dodekahedron dimensi 3?
A. 10
B. 40
C. 55
D. 100
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
(TIDAK USAH)
Genus suatu Graph, Graph
Dual,
dan Graph Infinit
PEMANCANGAN
Beberapa aspek dalam teori
graph terkait sangat erat dengan beberapa cabang matematika seperti topologi,
khususnya pada pokok bahasan ‘permukaan atau luasan topologi’. Sebenarnya, kita
telah mendiskusikan hubungan antara graph dan permukaan tersebut pada Kegiatan
Belajar 1, yaitu ketika kita mempelajari graph planar. Namun demikian, kita
akan perluas dan perdalam hubungan antara graph planar dengan luasan bola dan
sejenisnya.
Telah kita ketahui bahwa hanya kelompok graph
tertentu yang dapat kita gambar di bidang datar sedemikian rupa sehingga tidak
ada rusuk-rusuknya yang berpotongan
terkecuali pada simpul-simpulnya. Kelompok inilah yang disebut graph
planar. Penggambaran yang demikian itu disebut suatu pemancangan (embedding) dari graph itu di bidang
datar. Tidaklah terlalu sulit untuk memahami bahwa graph-graph planar mana yang
dapat dipancangkan pada pemukaan suatu bola. Graph bola adalah
graph-graph yang dapat dipancangkan pada permukaan sebuah bola tanpa ada dua
rusuk yang berpotongan.
Contoh 1
Gambar 5.14(a) menunjukkan graph bola yang dihasilkan
dari pemancangan graph K4 pada pemukaan bola.
 |
|||
 |
|||
(a) (b)
Berdasarkan pengertiannya, dapat difahami bahwa
graph-graph bola dan graph-graph planar adalah tepat sama (ekuivalen). Secara
umum, setiap graph dapat dipancangkan pada ruang dimensi-3.
Torus
Bentuk permukaan lain
yang memainkan peran cukup penting dalam topologi adalah permukaan bentuk donat
yang disebut torus. Suatu permasalah yang menarik untuk dijawab yaitu
apakah suatu graph planar dapat dipancangkan pada torus dan sifat-sifat apakah
yang dimilikinya. Jawaban dari permasalahan ini dijelaskan dalam bentuk contoh
2.
Contoh 2
Gambar
5.14(b) di atas, menunjukkan pemancangkan
graph lengkap K4 pada torus.
Jika G adalah graph yang
dipancangkan pada suatu torus, maka daerah-daerah dari G adalah
potongan-potongan terhubung dari torus yang tertinggal setelah simpul-simpul
dan rusuk-rusuk dari G diangkat. (Ingat kembali definisi ‘daerah’ dalam kasus
graph sebidang). Dalam kasus K4 yang dipancangkan pada Gambar
5.14(b), terdapat 4 daerah.
Menurut definisinya,
semua daerah adalah terhubung, apakah graph-graph itu dipancangkan pada bola
atau pun pada torus. Akan tetapi, suatu daerah dapat juga memiliki sifat
penting lainnya. Suatu daerah disebut terhubung
sederhana (simply connected) jika
sebarang kurva tertutup sederhana (seperti elips atau lingkaran) dapat ‘secara
kontinu disusut’ dalam daerah itu sehingga menjadi sebuah titik di daerah
itu Daerah yang demikian juga disebut 2-sel.
Daerah 2-sel ini secara topologik ekuivalen dengan ruang dimensi-2 pada ruang
Euclid. Umpamanya, daerah R dalam Gambar 5,14(b), adalah bukan daerah
terhubung sederhana, sebab jika kita mempunyai kurva tertutup sederhana C
seperti tampak pada daerah R, maka C tidak dapat secara kontinu disusut untuk
menjadi sebuah titik di R. Ketiga daerah
lainnya dari K4 dalam Gambar 5.14(b) adalah daerah terhubung
sederhana.
Toroidal
Jika suatu graph
(planar) terhubung dipancangkan pada permukaan bola, maka setiap daerah adalah
(perlu) terhubung. Akan tetapi tidak
demikian halnya bagi graph-graph terhubung yang dipancangkan pada permukaan
torus. Artinya, tidak setiap graph
planar terhubung yang dipancangkan pada torus selalu menghasilkan daerah yang
terhubung. Suatu graph disebut toroidal apabila graph itu dapat
dipanjangkan pada torus.
Contoh
3
Graph
planar K4 adalah toroidal,
sebagaimana terlihat pada Gambar 5.14 (b).
Secara
umum berlaku bahwa setiap graph planar adalah toroidal. Akan tetapi konvers
pernyataan ini adalah salah. Maksudnya terdapat graph-graph nonplanar yang tidak
dapat dipancangkan pada permukaan torus. Salah satu contohnya adalah K5
(yang nonplanar) dapat dipancangkan pada torus seperti diperlihatkan pada Gambar 5.15.
Menggambar
pada Torus
Cara lain menggambar
graph pada torus sering terbukti menyenangkan. Pertama-tama perhatikan
bagaimana mengonstruksi torus. Kita mulai dengan persegi panjang, dan kemudian
kita gulung dalam bentuk tabung. Kemudian kita tekuk bidang alas dan atas ini
sehingga melekat lagi, sehingga akhirnya diperoleh suatu torus. Gambar 5.16
menjelaskan masalah ini.
Gambar 5.16.
Sekarang menggambar
graph yang akan dipancangkan. Pada persegi panjang dalam Gambar 5.17(a),
titik-titik yang berlabel A, nanti pada torus akan menjadi titik yang sama,
demikian juga titik berlabel B. Jadi, K5 dapat dipancangkan pada
torus seperti dalam Gambar 5.17(b).
Gambar 5.17.
Genus
Dalam topologi, suatu
torus juga dikenal sebagai bola dengan satu ‘pegangan’ (handle), seperti ditunjukkan dalam
Gambar 5.18(a). Kita mengatakan bahwa torus dan bola dengan satu
pegangan adalah ‘ekuivalen secara topologis’ atau ‘homeomorphik’. Banyaknya pegangan suatu permukaan (bola) disebut genus
dari permukaan itu. Dengan genus g (G) dari graph G mempunyai genus bilangan
g, dimaksudkan genus
terkecil dari semua permukaan di mana graph G dapat dipancangkan. Karena
permukaan bola dan bidang datar adalah ekuivalen topologis, maka graph-graph
genus 0 adalah graph-graph planar. Graph dengan genus 1 adalah graph-graph
nonplanar yang dapat dipancangkan pada torus.
Contoh
4
Graph non planar K5 merupakan graph dengan genus 1,
sebagaimana disajikan pemancangannya pada gambar 5.18 berikut.
Berdasarkan definisi
genus maka K5 akan dapat dipancangkan pada permukaan yang mempunyai
genus lebih dari 1. Dapat dengan mudah Anda menunjukkan bahwa K3,3
dapat dipancangkan pada permukaan genus 1, dan tentu saja berlaku untuk permukaan bergenus 2, seperti
ditunjukkan dalam Gambar 5.18(b).
Anda telah mengetahui
rumus Euler yang menyatakan hubungan antara banyaknya simpul p, banyaknya rusuk
q dan banyaknya daerah r dari graph sebidang G(p,q). Rumus-rumus ini untuk
graph-graph yang dapat dipancangkan pada
luasan dengan genus tertentu. Dari sisi penulisan rumus mirip dengan
rumus-rumus pada graph sebidang, hanya sedikit berubah sehingga mudah untuk
dimengerti. Berikut ini didaftar rumus-rumus ini tanpa bukti dan diungkapkan
dalam teorema-teorema. Bagi Anda yang ingin mempelajari tentang bukti-buktinya,
dapat Anda pelajari dalam buku “Graphs an Introductory Approach, A First Course
in Discrete Mathematics”, karangan Robin J. Wilson dan John J. Watkins, John
Wiley & Sons, Inc.
Teorema 1
Jika G(p,q) adalah graph
terhubung dengan suatu 2-sel (daerah terhubung sederhana), dapat dipancangkan
pada permukaan dari genus n dan mempunyai r daerah, maka
p - q + r = 2 - 2n.
Untuk n = 0, yaitu permukaan bergenus 0 maka berlaku Teorema
Euler untuk graph pada bidang datar.
Teorema 2
Jika G(p,q) adalah graph
terhubung yang dipancangkan pada permukaan dengan genus g (G), maka setiap daerah dari G adalah 2-sel.
Teorema 3
Jika G(p,q) adalah graph
terhubung yang dipancangkan pada
permukaan dengan genus g (G) dan banyaknya daerah adalah r, maka
p - q + r = 2 – 2 g (G).
Teorema 4
Jika G(p,q) adalah graph
terhubung dengan p > 3, maka
g(G) > q/6
– p/2 + 1
Teorema 5
Genus dari graph lengkap
Kp, g (Kp), p > 4, dinyatakan dengan
rumus:
g(Kp) =
,
,
dengan pembulatan ke atas jika nilainya g(G) > 0.
Contoh 5
Graph K6 mempunyai
genus 1 sebab g(K5)
= (5-3)(5-4)/12 = 1/6 > 0 sehingga nilainya dibulatkan ke atas, yaitu g(K5)
= 1.
Teorema 6
Genus dari graph
bipartit lengkap Km,n, g(Km,n), dinyatakan dengan rumus:
g(Km,n)
= 
dengan pembulatan ke atas jika
nilainya > 0.
Contoh 6
Graph K4,4 mempunyai
genus 1 sebab g(K5)
= (4-3)(4-2)/4 = 1/2 > 0 sehingga nilainya dibulatkan ke atas, yaitu g(K4,4)
= 1.
Graph Dual
Multigraph sebidang M
disebut juga sebagai peta. Dua daerah di M dikatakan berdekatan
jika kedua daerah itu mempunyai sebuah rusuk persekutuan.
Contoh
7
Perhatikan graph
pada Gambar 5.19(a), daerah r1 dan r2 berdekatan,
sedangkan r1 dan r3 tidak.
Perhatikan
multigraph sebidang M. Dalam setiap daerah
di M kita pilih sebuah titik, dan jika dua buah daerah mempunyai
rusuk persekutuan, kedua titik yang
telah dipilih itu hubungkan dengan sebuah kurva melalui (memotong) rusuk
persekutuan itu. Kurva-kurva ini dapat digambar dengan cara demikian rupa sehingga setiap dua kurva tidak
berpotongan. Maka kita peroleh peta (multigraph) baru M*, yang disebut dual
dari M, sedemikian sehingga setiap simpul dari M* bersesuaian dengan tepat satu
daerah di M. Gambar 5.19(b) menunjukkan dual dari peta M pada Gambar 5.19(a).
Mudah dilihat bahwa setiap daerah di M* tepat memuat sebuah simpul di M dan
setiap rusuk di M* akan berpotongan tepat pada simpul di M dan sebaliknya. Maka
peta M adalah dual dari peta M*
 |
Graph dual mempunyai
banyak penerapan misalnya pada permasalahan graph euler, permasalahan pewarnaan
(simpul, rusuk atau daerah). Masalah pewarnaan graph akan dibicarakan pada Modul 6.
Graph
Latis Takberhingga (Infinit)
Pada subbabb ini akan
dibicarakan sebuah jenis graph, yaitu graph latis takberhingga (infinit). Definisi graph infinit L2,
adalah sebagai berikut. Simpul-simpul adalah titik-titik dalam bidang datar
yang absis dan ordinatnya bilangan bulat. Dua buah simpul dikatakan berdekatan
jika kedua simpul itu mempunyai jarak geometrik sama dengan satu satuan
panjang. Sebagian dari graph L2 dilukiskan pada Gambar 5.20. Hal itu karena banyaknya simpul
dalam L2 adalah takberhingga sehingga tidak mampu melukis seluruh
gambar graphnya.
Dalam graph infinit kita
tidak dapat mempunyai sikel Hamilton seperti didefinisikan dalam Modul 3, Kegiatan
Belajar 1, sebab sikel hanyalah mempunyai simpul-simpul yang banyaknya finit.
Akan tetapi, jika kita memikirkan sikel Hamilton sebagai ‘faktor-2’ terhubung
dari suatu graph, hal ini dapat bermakna bagi graph infinit seperti halnya
untuk graph finit. Untuk graph finit, suatu faktor-2 terhubung adalah sikel
hamilton, dan untuk graph infinit, faktor-2 itu adalah lintasan terentang tanpa
batas. Dengan kata lain, lintasan itu adalah infinit di kedua arahnya. Kita
akan menamakan lintasan terentang demikian ini sebagai garis Hamilton.
Dalam suatu graph infinit terdapat beberapa garis Hamilton. Dengan kata lain,
eksistensi garis Hamilton dalam suatu graph infinit adalah tidak tunggal.
Contoh
8
Diberikan graph infinit L2 sebagaimana
tertuang pada Gambar 5.21 berikut. Salah satu garis Hamilton dari L2
adalah lintasan yang digambarkan dengan garis tebal. Sedangkan Gambar 5.22 memperlihatkan
penguraian atau dekomposisi L2 ke dalam dua garis.
Untuk memperluas definisi
sirkuit Euler dalam graph infinit maka diperlukan suatu modifikasi. Suatu sirkuit
Euler adalah jalur Euler yang infinit pada kedua arahnya. Dengan kata lain,
sirkuit euler adalah jalur yang memuat setiap rusuk dan setiap simpul dari
graph infinit dan tidak mempunyai simpul permulaan atau simpul akhir. Dengan
istilah yang lebih praktis, graph infinit dengan garis Euler dapat
dibuat dari sepotong kawat yang panjangnya tak berhingga.
Gambar 5.23
memperlihatkan contoh sederhana dari suatu garis Euler dalam L2. Gambar
garis Euler dalam Gambar 5.24, semakin komplek atau sangat ruwet. Namun
demikian, kedua garis Euler ini memiliki keteraturan sehingga masing-masing
membentuk simetri-putar. Berdasarkan
Gambar 5.23 diperoleh pusatnya adalah titik tengah dari rusuk di tengah. Hal ini
berakibat bahwa jika Anda memutar gambar
itu 180o mengelilingi pusatnya, gambar itu tetap kelihatan sama. Pada
Gambar 5.24 pusat dari simetri-putar adalah simpul dimana kedua garis hamilton
berpotongan. Artinya, jika Anda memutar 90o maka kedua garis hamilton
itu bertukar tempat.
Sirkuit Euler dan jalur
Euler kedua-duanya telah didefinisikan untuk graph finit. Telah kita lihat
bagaimana memodifikasi definisi keduanya dalam graph infinit. Pertama, dalam
graph finit, lintasan Euler mempunyai dua titik ujung, sedangkan dalam graph
infinit kita dapat membuangnya salah satu. Kedua, suatu jalur dalam graph
infinit memuat setiap rusuk dari graph itu tepat satu kali, disebut jalur
Euler satu-arah. Jelaslah bahwa y sebagai simpul ujung harus mempunyai
derajat ganjil, dan simpul-simpul lainnya harus berderajat genap. Tetapi, hal
ini tidaklah cukup. Anda hendaknya mencari jalur Euler satu-arah dalam graph
sarang labah-labah infinit pada Gambar 5.25.
Suatu jalur Hamilton
satu-arah dalam graph infinit adalah lintasan yang panjangnya infinit, bermula pada suatu
simpul z dan melalui setiap simpul dari graph itu. Derajat dari z tidak menjadi
masalah.
|
1) Apakah yang dimaksud dengan pemancangan (embedding) suatu graph? dan gambarkan
pemancangan dari K3,2 pada torus
2) Apakah yang dimaksud dengan ‘graph bola’.
3) Apakah graph toroidal itu? Apakah graph G3,4
yang merupakan subdivisi dari K3,3 merupakan toroidal.
4) Apakah yang dimaksud dengan ‘daerah
terhubung sederhana’ atau daerah 2-sel itu?
5) Apakah yang dimaksud dengan ‘homeomorphik’
dua atau lebih permukaan?
6) Apakah genus suatu permukaan itu? Apa pula
genus graph G?
7) Apakah
graph dual dari graph G? dan tentukan graph dual dari K4
8) Dalam graph L2, suatu garis Hamilton
adalah pohon terentang yang setiap simpul-simpulnya hanya berderajat dua.
Carilah pohon terentang T dari L2 sedemikian rupa sehingga T tidak
mempunyai simpul-simpul berderajat 2.
9) Carilah subgraph terentang dalam L2
di mana setiap simpulnya berderajat 3.
10) Cari penguraian atau dekomposisi dari L2
ke dalam empat faktor-1.
11) Carilah penguraian atau dekomposisi dari L2
ke dalam subgraph-subgraph yang isomorphik dengan
a. graph segi-4 atau C4
b. Cg
c. C12
d. Umumnya C4t
12) Buktikanlah bahwa tidaklah mungkin menguraikan
L2 ke dalam subgraph-subgraph yang isomorphik dengan C6.
13) Ditentukan bilangan bulat t > 1,
buktikanlah bahwa L2 dapat diuraikan ke dalam subgraph-subgraph yang
isomorphik dengan Jt, yaitu yang panjangnya t.
14) Uraikan L2 ke dalam
a. tiga subgraph terhubung
b. tiga subgraph terhubung isomorphik
15) Kita definisikan M2 adalah latis
terdiri atas titik-titik dengan koordinat bulat di dalam bidang datar
sedemikian rupa sehingga titik-titik yang jarak geometrinya Ö2 adalah berdekatan.
Apakah N2 terhubung?
16) Kita definisikan N2 sebagai latis
yang terdiri titik-titik dengan koodinat bulat di dalam bidang datar sedemikian
rupa sehingga titik-titik dengan jarak geometri Ö5 adalah berdekatan. Apakah N2
terhubung?
Petunjuk Jawaban Latihan
1)
Pemancangan
suatu graph adalah penggambaran suatu graph pada permukaan bidang datar atau
permukaan bola dengan syarat tidak ada dua rusuk berpotongan (terkecuali pada
simpul).
Pemancangan
K3,2 pada torus, tersaji pada Gambar 5.27 di bawah ini
 |
Gambar
5.28
2)
Graph bola
adalah graph-graph yang dapat dipancangkan pada permukaan sebuah bola tanpa ada
dua rusuk yang berpotongan.
3)
Suatu graph
disebut toroidal apabila graph itu dapat dipancangkan pada torus.
Graph bipartet lengkap K3,3
adalah troidal sebab dapat
dipancangkan pada torus, seperti terlihat pada Gambar 5.28 berikut.
 |
Gambar 5.28
4)
Daerah terhubung
sederhana adalah daerah pada pemancangan graph pada permukaan dengan sifat
setiap kurva tertutup sederhana dapat disusut menjadi sebuah titik yang berada
di titik itu.
5)
Homeomorphik
dua atau lebih permukaan adalah dua permukaan atau lebih yang secara topologi
ekuivalen
6)
Genus suatu
permukaan adalah banyaknya pegangan pada suatu permukaan. Genus suatu graph
adalah banyaknya pegangan minimal suatu permukaan sehingga G dapat dipancangkan
pada permukaan itu.
7)
Graph dual
dari G adalah graph G* sedemikian rupa sehingga setiap daerah di G bersesuaian
dengan setiap simpul G*, setiap dua daerah berdekatan pada G bersesuaian dengan
dua simpul berdekatan pada G* dan sebaliknya. Dual dari K4 yaitu K4*
seperti terlukis pada Gambar
5.29 berikut.
 |
|||
 |
|||
K4 K4*
Gambar
5.29
8)
Perhatikan Gambar
5.21. Pohon terentang T dari L2 yang memiliki simpul-simpul yang
tidak berderajat dua dapat dilukis seperti pada Gambar 5.21, tetapi setiap kali
berbelok melewati dua baris atau kolom. Hal itu berakibat titik-titik pada
baris dan kolom menjadi berderajat 4.
9)
Dengan cara
yang analog, sebagaimana Gambar 5.21, tetapi setiap kali berbelok melewati satu
baris/atau kolom.
10)
Perhatikan
Gambar 5.22 yang menjelaskan tentang dekomposisi L2 kedalam dua
garis Hamilton. Untuk menguraikan L2 ke dalan 4 faktor-1 dapat
dilakukan secara analog, bedanya dengan loncat ‘dua’.
11)
Bentuk
dekomposisi dari L2 terhadap subgraph yang isomorphik dengan C4 akan berbentuk bujursangkar
berisi satu. Sedangkan dekomposisi L2 yang isomorphik dengan C8
akan berbentuk bujursangkar berisi dua. Dengan cara yang sama (analog),
dekomposisi L2 terhadap subgraph yang isomorphik dengan C4t
akan berbentuk bujursangkar yang berisi t, untuk suatu t bilangan cacah.
12)
Karena
dekomposisi L2 akan berupa bujursangkar maka tidak akan kita temukan
suatu bujursangkar berisi 4t yang mempunyai keliling 6, t bilangan cacah.
13)
a. Untuk
menguraikan L2 kedalam bentuk tiga subgraph terhubung maka dapat
dilakukan dengan melukis dua garis Hamilton.
b.
Sedangkan
untuk menguraikan (dekomposisi) L2 kedalam bentuk tiga subgraph
terhubung isomorphik maka dapat dilakukan dengan melukis tiga garis Hamilton
14)
Benar. Anda
dapat membuktikan dengan mendefinisian N2 dengan simpul-simpul
sebagai titik-titik pada bidang Euclid dan dua simpul dikatakan berdekatan jika
kedua simpul berjarak Ö2. Maka setiap dua simpul pada N2 akan
terdapat jalur yang menghubungkannya.
15)
Benar,
analog soal no. 14.
Graph infinit atau latis
infinit adalah graph sebidang dengan banyak simpul infinit atau takhingga. Definisi lintasan, jalur, sikel dan sirkuit
untuk graph infinit ada sedikit perubahan dari
yang didefinisikan pada graph finit.
Setiap graph sebidang dapat
dipancangkan pada permukaan sebuah bola. Bidang datar dan permukaan bola adalah
homeomorphik. Graph-graph nonplanar tak dapat dipancangkan pada permukaan bola,
akan tetapi dapat dipancangkan pada permukaan bola yang diberi ‘pegangan’.
Banyaknya pegangan pada permukaan bola disebut genus permukaan itu. Permukaan
bola dan bidang datar adalah permukaan dengan genus 0 (nol). Torus adalah permukaan berbentuk kue donat
dan permukaan ini homeomorphik dengan permukaan bergenus 1. Genus graph
terhubung G adalah banyaknya pegangan
minimal sedemikian sehingga graph G dapat dipancangkan di permukaan itu. Graph
bipartit K3,3, graph-graph lengkap K5, K6, dan
K7 adalah graph bergenus 1 sehingga dapat dipancangkan pada torus
atau pada permukaan bola berpegangan 1.
1) Misalkan K5 dipancangkan pada
sebuah torus. Banyaknya daerah terhubung sederhana pada K5 adalah
A. 3
B. 4
C. 5
D. 6
2) Jika K3,3 dipancangkan pada
permukaan bola dengan genus 1, maka banyaknya daerah -2 sel adalah ....
A. 3
B. 4
C. 5
D. 6
3) Jika K3,3 dipancangkan pada
permukaan bola genus 2, maka banyaknya daerah terhubung sederhana adalah ....
A. 2
B. 3
C. 4
D. 5
4) Misalkan G adalah graph planar terhubung. Banyaknya
daerah yang diperoleh jika G dipancangkan pada permukaan dan banyaknya daerah
jika G dipancangkan pada suatu torus adalah ....
A. sama banyak
B. tidak sama
C. lebih banyak pada bola
D. lebih sedikit pada bola
5) Jika G(p,q) adalah graph terhubung dapat
dipancangkan pada sebuah bidang dan banyaknya daerah yang terjadi adalah r,
maka p - q + r = 2. Jika G(p,q) adalah graph terhubung dan dapat dipancangkan
pada sebuah torus sedemikian rupa sehingga setiap daerah dari r daerah yang
terjadi adalah terhubung tunggal, berapakah nilai p + q - r?
A. 3
B. 2
C. 1
D. 0
6) Menurut
Teorema 1, jika G(p, q) adalah graph terhubung yang dapat dipancangkan pada
permukaan bola, dan mempunyai daerah sebanyak r, maka nilai p - q + r adalah
....
A. 0
B. 1
C. 2
D. 3
7) Menurut Teorema 5, genus graph lengkap K8
adalah ....
A. 1
B. 2
C. 3
D. 4
8) Menurut Teorema 6, genus graph bipartit K6,6
adalah ....
A. 1
B. 2
C. 3
D. 4
9) Jika genus graph lengkap Kn
yaitu g(Kn) = 7 maka nilai n adalah
A. 10
B. 11
C. 12
D. tidak ada
10) Menurut Teorema 3 dan Teorema 6, banyaknya
daerah jika graph bipartit lengkap K5,5 dipancangkan pada permukaan
bergenus adalah ....
A. 11
B. 10
C. 9
D. 8
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. p = 5 simpul dan der(R) = 12
2) D. tidak ada
3) C. der(R1)=9, der(R2)=12,
der(R3)=4, der(R4)=5,
4) B. 1 dan 4
5) C. banyak daerahnya sama, yaitu r = q – p + 2
6) D. 2 segi-3, 1 segi-4 dan 2 segi-5
7) A,
1
8) B. K3,3 dan K5
9) D. 100. Dalam dodekahedron, r = 12, setiap
daerah (sisi) merupakan ‘segilima’ sehingga q = 12.5/2 = 30, p = 2 + q - r =
20. Banyaknya garis hubung antara dua
titik = 20.19/2 = 19/2 = 190. Setiap sisi mempunyai (5 - 3).5/2 = 5 diagonal
sisi. Banyaknya diagonal sisi = 12.5 =
60. Jadi banyaknya diagonal ruang = 190 - 30 - 60 = 100.
Cara lain
Setiap
titik ‘berdekatan dengan 9 titik lain (ini menjadi rusuk atau diagonal sisi.
Jadi setiap titik ‘berjauhan’ dengan 10 titik lainnya (merupakan diagonal ruang).
Banyaknya diagonal ruang = 10.20/2 =
100.
10) A. 10. Diagonal terpanjang diperoleh dari dua
titik yang ‘berhadapan’. Karena banyaknya titik = 20, jadi yang berhadapan = 10 pasang.
Tes Formatif 2
1) C 5. Daerah terhubung sederhana dari hasil
pemancangan K5 pada torus
adalah daerah yang melekat pada bola. Perhatikan dengan seksama Gambar
5.27 (a).
2) B. 3. Permukaan bola dengan
genus 1 adalah permukaan bola yang memiliki pegangan 1. Maka pemancangan K5
pada permukaan bola bergenus 1 adalah daerah-daerah yang melekat pada
bola. Detailnya tersaji pada Gambar 5.27(b).
3) B. 2. Pemancangan K3,3 pada
permukaan bola bergenus 2, terlukis pada Gambar 5.28. Banyaknya daerah
terhubung sederhananya adalah 2.
Gambar
5.28
4) A. Karena G suatu graph planar terhubung maka
banyaknya daerah terhubung sederhana pada pemancangan graph G pada permukaan
bola dan torus adalah sama.
5) D. 0. Anda gunakan Teorema 3 dan karena G(p,q)
bergenus 1 maka didapat p – q + r = 2 – 2 g(G) = 2 – 2.1= 0
6) C. 2. Berdasarkan Teorema 1 didapat p – q + r = 2 – 2 n, dengan n banyaknya
genus. Karena permukaan bola adalah permukaan bergenus 0 maka diperoleh p-q+r = 2 – 2.0 = 2
7) B. 2. Karena
K8 sehingga didapat p
=8 maka diperoleh
g(K8) == (8-3)(8-4)/12 = 5/3 > 0.
= (8-3)(8-4)/12 = 5/3 > 0.
Dengan menggunakan Teorema
5, dan mengingat g(K8)= 5/3 > 0
sehingga dibulatkan keatas, yaitu g(K8)= 2.
8) C. 3. Dengan menggunakan Teorema 6 didapat
g(K5,7)
= 
= (5-3)(7-2) / 4 = 5/2.
Karena g(K5,7) =
5/2 > 0 maka g(K5,7) = 3. (pembulatan keatas).
9) D. tidak ada, karena g(Kn) = 7 maka menurut Teorema 5
didapat
7
= (n-4)(n-3)/12 sehingga 84 = (n-4)(n-3). Karena jika g(Kn) > 0 maka pembulatan ke atas
sehingga persamaan menjadi 84 72 ≤
(n-4)(n-3) ≤ 84. Hal ini berakibat, tidak ada nilai n cacah yang memenuhi
pertidaksamaan ini.
10) B. 10. Menurut Teorema 6, diperoleh g(K5,5) = (5-3)(5-2) / 4 = 3/2 sehingga
g(K5,5) =
2. Kemudian, substitusi g(K5,5) = 2 ke Teorema 3 dan
diperoleh r = 2 – p + q - g(K5,5) =
2 – 10 + 20 – 2 = 10.
Daftar Pustaka
Chartrand, Gary, and
Lesniak, Linda. (1986). Graph & Digraph. Second Edition. Belmont,
California: Wadsworth. Inc.
Lipschutz, Seymour.
(1976). Discrete Mathematics. Schaum’s Outline Series. New York:
McGraw-Hill.
Liu, C.L. (1985). Elements
of Discrete Mathematics. New York: McGraw-Hill.
Robin, RW, John, JW.
(1990), Graphs An Introductory Approach, A First Course in Discrete
Mathematics, New York : John Wiley and Sons, Inc.
Tucker, Alan. (1984). Applied
Combinatorics. New York: John Wiley.
GLOSARIUM
Daerah
dari suatu graph G adalah potongan-potongan daerah terhubung pada bidang datar
dari G
Daerah
Terhubung Sederhana (daerah 2-sel) adalah suatu daerah yang jika sebarang kurva
tertutup sederhana (seperti elips atau lingkaran) dapat ‘secara kontinu
disusut’ dalam daerah itu sehingga menjadi sebuah titik di daerah itu
Dodekahedron adalah suatu bidang 4 teratur
Euler (sirkuit)
adalah suatu sirkuit yang
memuat semua simpul dan semua rusuk dari multigraph M.
Euler
(graph) suatu graph yang memuat
semua sirkuit Euler disebut graph Euler (multigraph) adalah suatu graph yang memuat sirkuit Euler
Euler Teorema : Jika G(p,q) adalah
graph sebidang terhubung yang terdiri r daerah maka p – q + r = 2.
Graph G(V,E) adalah suatu himpunan berhingga G yang
dilengkapi dengan himpunan simpul-simpul V dalam G dan himpunan rusuk-rusuk
dalam G sehingga V(G) bukan himpunan
kosong.
Graph Bipartet G adalah suatu
graph yang memiliki sifat bahwa himpunan simpul-simpulnya dibagi menjadi dua
bagian sehingga setiap simpul pada salahsatu bagian hanya berikatan/berdekatan dengan simpul pada
bagian lain.
Graph Peterson adalah suatu
graph teratur-3 dengan 10 simpul.
Graph planar G adalah suatu graph yang dapat
digambarkan di bidang datar sehingga tidak ada dua rusuknya yang berpotongan
kecuali pada simpul-simpulnya
Graph
sebidang adalah suatu planar yang telah digambar di bidang datar
sedemikian rupa sehingga tidak ada dua rusuknya yang berpotongan.
Graph
subdivisi dari G adalah subgraph yang diperoleh (dikonstruksi)
dari graph G dengan menyisipkan berhingga simpul berderajat dua kepada G.
Graph Hamilton adalah suatu graph
yang memuat sikel Hamilton dari simpul di G.
Graph bola adalah graph-graph yang dapat dipancangkan pada
permukaan sebuah bola tanpa ada dua rusuk yang berpotongan.
Graph
Dual dari G adalah suatu graph yang diperoleh dengan
mendefini-sikan simpul adalah daerah-daerah terhubung dan setiap dua simpul
berikatan jika keduanya memiliki rusuk persekutuan
Genus
dari suatu
permukaan adalah banyaknya pegangan dalam permukaan bola.
Genus
dari graph
terhubung G adalah banyaknya pegangan (genus) terkecil dari semua permukaan
dimana graph G dapat dipancangkan pada permukaan tersebut.
Heksahedron adalah suatu bidang 6 teratur
Homeomorphik adalah ekiuvalen secara
topologi
Ikosahedron adalah suatu bidang 4 teratur
Kuratovski (teorema) : Suatu graph G
adalah planar jika dan hanya jika G tidak memuat subgraph yang isomorphik
dengan K5 atau K3,3 atau sebarang subdivisi dari K3,3
dan K5.
Latis
(infinity)
adalah suatu graph (V,E) dengan V(G) :himpunan simpul-simpulnya adalah himpunan
titik-titik dalam Euclid yang absis yang ordinatnya bilangan cacah dan E(G) adalah himpunan rusuk dan setiap dua
simpul berikatan jika kedua simpul memiliki jarak geometri sama dengan satu
satuan panjang.
Oktahedron adalah suatu bidang 8 teratur
Pemancangan (embedding)
adalah gambar di bidang datar sedemikian rupa sehingga tidak ada rusuk-rusuknya
yang berpotongan terkecuali pada
simpul-simpulnya.
Polihedral (graph platonik ) adalah
graph planar yang memiliki sifat : semua simpulnya berderajat sama, yakni d1
, dan semua daerahnya dibatasi oleh banyak rusuk yang sama, yakni d2 , dengan ketentuan d1 >
3, d2 > 3.
Tetrahedron adalah suatu bidang 4 teratur
Sirkuit adalah lintasan tertutup
Sikel
Hamilton adalah sikel yang
memuat semua simpul di G
Torus adalah suatu permukaan berbentuk
donat.
Toroidal (graph) adalah suatu graph yang
dapat dipancangkan pada torus.
.jpg)
0 komentar:
Posting Komentar