Nama kelompok :
Irman juliansyah
Fahmi
ahmad Habibi
Josen jovianto
Ancer afriyono
Ardy saputro
Ardytyo .pm
Ahmad Fauzan
Indah iksani putri
Risky Agung
Rendy firstdeta renaldy
Risky ade putra
Luthfi ridhoni
1.
Diberikan gambar sebuah graf
seperti di bawah ini.
|
|
(a) Tunjukkan dengan
ketidaksamaan Euler bahwa graf tersebut tidak planar.
(5)
|
(b) Tunjukkan dengan
Teorema Kuratowski bahwa graf tersebut tidak planar.
(10)
|
Jawab :
(a). Dengan ketidaksamaan euler
jika menggunakan rumus
ketidaksamaa euler e ≤ 3n – 6 maka akan terlihat bahwa graf memenuhi
ketidaksamaan tersebut (padahal graf tidak planar)
e ≤ 3n – 6
15 ≤ 3 * 8 – 6
15 ≤ 24 – 6
15 ≤ 18
untuk menunjukkan bahwa graf
tidak planar kita membuat asumsi baru bahwa setiap daerah pada graf planar
dibatasi oleh paling sedikit 4 buah sisi . Dengan demikian total banyaknya sisi
lebih besar atau sama dengan 4f. Tetapi karena suatu sisi berada pada batas
paling banyak 2 wilayah maka total banyaknya sisi lebih kecil atau sama dengan
2e. Jadi :
2e ≤ 4f
dengan rumus euler menjadi
ketidaksamaan
e ≤ 2n – 4
15 ≤ 2 * 8 – 4
15 ≤ 16 – 4
15 ≤ 12 terbukti
(b). Dengan teorema kuratowski
dapat dibuktikan bahwa graf tersebut mengandung
upagraf yang homeomorfik dengan
graf K3,3
atau K5.
G
|
G1 adalah upagraf
dari G
|
G2 yang isomorfik dengan G1
|
G2 homeomorfik dengan K5
(dengan membuang simpul A dan C yang berderajat 2)
|
2.
Dept. IF mempunyai 6 kelompok kerja yang setiap bulannya
masing-masing selalu mengadakan rapat satu kali. Keenam kelompok kerja dengan
masing-masing anggotanya adalah: K1 = {Amir, Budi,
Yanti}, K2 = {Budi, Hasan, Tommy},
K3 = {Amir, Tommy, Yanti}, K4 = {Hasan,
Tommy, Yanti}, K5 = {Amir, Budi},
K6 = {Budi, Tommy, Yanti}.
Berapa banyak waktu rapat berbeda yang harus direncanakan sehingga tidak
ada anggota kelompok kerja yang dijadwalkan rapat pada waktu yang sama.
Gambarkan graf yang merepresentasikan persoalan ini lalu (sisi menyatakan apa,
simpul menyatakan apa) tentukan jumlah waktu rapat ini. (20)
Jawab :
Simpul : menyatakan kelompok
Sisi : menyatakan adanya anggota
kelompok yang sama
Jika ada sisi yang
menghubungkan 2 kelompok berarti kelompok tersebut tidak boleh rapat pada waktu
yang sama.
Dibawah dapat dilihat
gambar graf yang terbentuk. Untuk mencari jumlah minimum waktu rapat yang harus
disediakan kita dapat menggunakan cara yang sama seperti mencari bilangan
kromatis dari graf tersebut. Setiap warna yang berbeda mewakili satu waktu
rapat yang dibutuhkan.
Bilangan kromatis graf
tersebut adalah 5. maka waktu rapat yang harus disediakan adalah 5.
1
waktu untuk K1
1
waktu untuk K2
1
waktu untuk K3
1
waktu untuk K4 dan K5
1
waktu untuk K6
3. Disebuah
pulau terdapat 10 kota, dimana kota-kota tersebut dihubungkan dengan ruas-ruas
jalan. Ada dua kota yang terhubung. Ada juga yang tidak. Suatu rute yang
dimulai dari suatu kota, mengunjungi tepat 8 dari 9 kota lainnya masing-masing
sekali dan kembali ke kota awal dinamakan rute wisata. Tentukan ruas jalan
minimal yang perlu untuk dibuat, sehingga apabila diberikan sembarang kota di
pulau tersebut ada rute wisata yang tidak melewati kota tersebut.
Jawab:
|
graph sebuah pulau
dengan 10 kota
|
Rute
wisata di mulai dari kota 1 melewati 8 kota lainya. Kecuali kota 7. Ruas jalan
yang di butuhkan ada 9 ruas jalan. Antara lain:
R1
: 1-2
R4 :
4-5
R7 : 8-9
R2 :
2-3
R5 :
5-6
R8 : 9-0
R3 :
3-4
R6 :
6-8
R9 : 0-1
4. Apakah graf pada gambar di bawah mempunyai sirkuit
Euler? Jelaskan! Bila jawaban saudara “Ya”, maka berikan sirkuit Euler
tersebut. Lalu, tentukan dua lingkaran Hamilton berbeda pada Geraf B di bawah
ini!
A
B
Jawab:
Untuk
mengetahui apakah graf A di atas
memiliki sirkuit Euler, kita dapat menggunakan suatu teorema yang menyatakan “Jika pseudograf G terhubung dan derajat
setiap titiknya mempunyai derajat genap,
maka G mempunyai sebuah sirkuit Euler” Untuk itu kita periksa bahwa A terhubung dan derajat setiap
titiknya genap. Pertama kita beri label setiap titik dan sisi pada graf A sebagai berikut:
A
Graf A terhubung karena terdapat sebuah
lintasan dari titik x dan y jika diketahui sembarang titik x dan y. Dan jika
kita periksa sebagai berikut:
a ke b
lintasannya (a, e1, b) ; a ke c lintasannya (a, e1, b, e2, c) ; a ke d lintasannya (a, e12,d) ; a ke e
lintasannya (a, e11, e) ; a ke f
lintasannya (a, e11, e, e10, f) ; b ke c lintasannya (b, e2, c) ; b ke d
lintasannya (b, e4, d) ; b ke e lintasannya (b, e4, d, e8,e) ; b ke f
lintasannya (b, e6, f) ; c ke lintasannya (c, e7, f, e9, d) ; c ke e
lintasannya (c, e5, e) ; c ke f
lintasannya (c, e7, f) ; d ke e lintasannya (d, e8, e) ; d ke f lintasannya
(d, e9, f) ; e ke f lintasannya (e, e10, f) ; sehingga dengan demikian A
terhubung.
d(a) = d(b) = d(c) = d(d) = d(e) = d(f) = 4 ini artinya setiap setiap titik pada graf A berderajat genap.
Karena derajat setiap titik
adalah genap, menurut teorema tersebut di atas maka A mempunyai sebuah sirkuit
Euler.
Jadi
graf A di atas mempunyai Sirkuit
Euler-nya, dan sirkuit Euler-nya yaitu:
(c,
a, b, f, c, e, a, d, e, f, d, b, c)
Untuk
menunjukan lingkaran Hamilton dalam sebuah graf B maka kita beri label terlebih dahulu setiap titik pada graf B seperti yang tampak di bawah ini:
B
Berikut
ini dua lingkaran Hamilton berbeda pada graf B :
(l, h, i, d, c, b, a, j,
k, g, f, e, l)
dan
(i, h, g, f, e, l, b, a,
j, k, c, d, i)
5. Periksalah
apakah kedua graf di bawah ini planar. Berikan alasan
(A) (B)
Jawab:
Untuk
memeriksa graf A planar atau
tidak planar maka kita beri label terlebih dahulu setiap titik pada graf A seperti yang tampak di bawah ini:
(A)
Dalam pemeriksaan
apakah graf A planar atau tidak
planar, dapat menggunakan Teorema Kuratowski yang menyatakan, “Graf G merupakan planar jika dan hanya jika
G tidak mengandung suatu graf-K sebagai subgraf dari G”. Dalam hal ini
sebuah graf-K adalah graf yang didapat dari K5 atau K3,3
dengan melakukan subdivisi pada sisinya. Artinya dalam persoalan
pemeriksaan apakah graf A planar
atau tidak planar kita akan mencoba menemukan K5 atau K3,3 pada graf A..
Pertama
kali kita ingat bahwa titik a, c, d, e dan
f pada graf A yang telah
dilabeli pada gambar di atas, masing – masing mempunyai derajat 4. Untuk itu
kita coba menemukan K5
dalam graf A, karena dalam K5 setiap titik mempunyai
derajat 4, sehingga kita akan melakukannya sebagai berikut:
Graf A kita dapat membentuknya seperti
tampak dibawah ini:
K5 setiap titik mempunyai derajat
4, sehingga kita dapat menghapus sisi (d, h) dan (g, h) agar semua sisi
mempunyai derajat 4, tampak pada gambar dibawah ini:
Hapus sisi (d, h) dan (g, h)
|
|
K5
Selanjutnya
kita dapat melakukan reduksi seri (Definisi:
Jika sebuah graf G mempunyai sebuah sisi v berderajat 2 dan sisi (v, v1)
dan (v, v2) dengan v1 ¹ v2 kita katakana bahwa rusuk Reduksi seri
(v, v1) dan (v, v2) berada dalam seri. Reduksi
seri terdiri dari penghapusan sisi v graf G dan menggantikan sisi-sisi (v, v1)
dan (v, v2) dengan sisi (v1, v2). Graf yang
dihasilkan G’ dikatakan diperoleh dari G dengan sebuah reduksi seri.
Berdasarkan konvensi, G dikatakan dapat diperoleh dari diri sendiri dengan sebuah
reduksi seri) dan graf yang dihasilkan akan mempunyai sepuluh sisi dan
karena K5 mempunyai
sepuluh sisi, pendekatan ini kelihatan dapat menjanjikan. Dengan coba-coba,
akhirnya kita lihat bahwa jika kita kurangi sisi (d, h) dan (g, h) dan kita
lakukan reduksi seri, kita peroleh sebuah salinan dari K5 seperti tampak pada Gambar 5.1. di atas.
Jadi, graf A pada soal 5. ini tidak planar, karena
graf tersebut mengandung sebuah subgraf yang homeomorfik pada K5.
Untuk
memeriksa graf B planar atau
tidak planar maka kita beri label terlebih dahulu setiap titik pada graf B seperti yang tampak di bawah ini:
(B)
Dalam
pemeriksaan apakah graf B planar
atau tidak planar, dapat menggunakan sama halnya seperti apa yang dilakukan pada
graf A tadi di atas
menggunakan Teorema Kuratowski. Artinya dalam persoalan pemeriksaan apakah
graf B planar atau tidak planar
kita akan mencoba menemukan K5 atau K3,3 pada graf B.
Pertama
kali kita ingat bahwa titik a, b, d, c dan
d pada graf B yang telah
dilabeli pada gambar di atas, masing – masing mempunyai derajat 4. Untuk itu
kita coba menemukan K3,3
dalam graf B, karena dalam K3,3 setiap titik mempunyai
derajat 3, sehingga kita akan melakukannya sebagai berikut:
Graf B kita dapat membentuknya seperti
tampak dibawah ini:
(B)
K3,3 setiap titik mempunyai derajat
3, sehingga kita dapat menghapus sisi (c, h), (e, h) dan (i, h) agar semua sisi
mempunyai derajat 4, tampak pada gambar dibawah ini:
Hapus sisi (c, h), (e, h) dan (i, h)
|
|
K3,3
Selanjutnya
kita dapat melakukan reduksi seri sehingga graf yang dihasilkan akan mempunyai
sembilan sisi dan karena K3,3
mempunyai sembilan sisi, pendekatan ini kelihatan dapat menjanjikan. Dengan
coba-coba, akhirnya kita lihat bahwa jika kita kurangi sisi (c, h), (e, h) dan
(i, h) dan kita lakukan reduksi seri, kita peroleh sebuah salinan dari K3,3 seperti tampak pada Gambar 5.2. di atas.
Jadi, graf B pada soal 5. ini tidak planar, karena
graf tersebut mengandung sebuah subgraf yang homeomorfik pada K3,3.
Nama kelompok :
Irman juliansyah
Fahmi
ahmad Habibi
Josen jovianto
Ancer afriyono
Ardy saputro
Ardytyo .pm
Ahmad Fauzan
Indah iksani putri
Risky Agung
Rendy firstdeta renaldy
Risky ade putra
Luthfi ridhoni
1.
Diberikan gambar sebuah graf
seperti di bawah ini.
|
|
(a) Tunjukkan dengan
ketidaksamaan Euler bahwa graf tersebut tidak planar.
(5)
|
(b) Tunjukkan dengan
Teorema Kuratowski bahwa graf tersebut tidak planar.
(10)
|
Jawab :
(a). Dengan ketidaksamaan euler
jika menggunakan rumus
ketidaksamaa euler e ≤ 3n – 6 maka akan terlihat bahwa graf memenuhi
ketidaksamaan tersebut (padahal graf tidak planar)
e ≤ 3n – 6
15 ≤ 3 * 8 – 6
15 ≤ 24 – 6
15 ≤ 18
untuk menunjukkan bahwa graf
tidak planar kita membuat asumsi baru bahwa setiap daerah pada graf planar
dibatasi oleh paling sedikit 4 buah sisi . Dengan demikian total banyaknya sisi
lebih besar atau sama dengan 4f. Tetapi karena suatu sisi berada pada batas
paling banyak 2 wilayah maka total banyaknya sisi lebih kecil atau sama dengan
2e. Jadi :
2e ≤ 4f
dengan rumus euler menjadi
ketidaksamaan
e ≤ 2n – 4
15 ≤ 2 * 8 – 4
15 ≤ 16 – 4
15 ≤ 12 terbukti
(b). Dengan teorema kuratowski
dapat dibuktikan bahwa graf tersebut mengandung
upagraf yang homeomorfik dengan
graf K3,3
atau K5.
|
G
|
G1 adalah upagraf
dari G
|
G2 yang isomorfik dengan G1
|
G2 homeomorfik dengan K5
(dengan membuang simpul A dan C yang berderajat 2)
|
2.
Dept. IF mempunyai 6 kelompok kerja yang setiap bulannya
masing-masing selalu mengadakan rapat satu kali. Keenam kelompok kerja dengan
masing-masing anggotanya adalah: K1 = {Amir, Budi,
Yanti}, K2 = {Budi, Hasan, Tommy},
K3 = {Amir, Tommy, Yanti}, K4 = {Hasan,
Tommy, Yanti}, K5 = {Amir, Budi},
K6 = {Budi, Tommy, Yanti}.
Berapa banyak waktu rapat berbeda yang harus direncanakan sehingga tidak
ada anggota kelompok kerja yang dijadwalkan rapat pada waktu yang sama.
Gambarkan graf yang merepresentasikan persoalan ini lalu (sisi menyatakan apa,
simpul menyatakan apa) tentukan jumlah waktu rapat ini. (20)
Jawab :
Simpul : menyatakan kelompok
Sisi : menyatakan adanya anggota
kelompok yang sama
Jika ada sisi yang
menghubungkan 2 kelompok berarti kelompok tersebut tidak boleh rapat pada waktu
yang sama.
Dibawah dapat dilihat
gambar graf yang terbentuk. Untuk mencari jumlah minimum waktu rapat yang harus
disediakan kita dapat menggunakan cara yang sama seperti mencari bilangan
kromatis dari graf tersebut. Setiap warna yang berbeda mewakili satu waktu
rapat yang dibutuhkan.
Bilangan kromatis graf
tersebut adalah 5. maka waktu rapat yang harus disediakan adalah 5.
1
waktu untuk K1
1
waktu untuk K2
1
waktu untuk K3
1
waktu untuk K4 dan K5
1
waktu untuk K6
3. Disebuah
pulau terdapat 10 kota, dimana kota-kota tersebut dihubungkan dengan ruas-ruas
jalan. Ada dua kota yang terhubung. Ada juga yang tidak. Suatu rute yang
dimulai dari suatu kota, mengunjungi tepat 8 dari 9 kota lainnya masing-masing
sekali dan kembali ke kota awal dinamakan rute wisata. Tentukan ruas jalan
minimal yang perlu untuk dibuat, sehingga apabila diberikan sembarang kota di
pulau tersebut ada rute wisata yang tidak melewati kota tersebut.
Jawab:
|
|
graph sebuah pulau
dengan 10 kota
|
Rute
wisata di mulai dari kota 1 melewati 8 kota lainya. Kecuali kota 7. Ruas jalan
yang di butuhkan ada 9 ruas jalan. Antara lain:
R1
: 1-2
R4 :
4-5
R7 : 8-9
R2 :
2-3
R5 :
5-6
R8 : 9-0
R3 :
3-4
R6 :
6-8
R9 : 0-1
4. Apakah graf pada gambar di bawah mempunyai sirkuit
Euler? Jelaskan! Bila jawaban saudara “Ya”, maka berikan sirkuit Euler
tersebut. Lalu, tentukan dua lingkaran Hamilton berbeda pada Geraf B di bawah
ini!
A
B
Jawab:
Untuk
mengetahui apakah graf A di atas
memiliki sirkuit Euler, kita dapat menggunakan suatu teorema yang menyatakan “Jika pseudograf G terhubung dan derajat
setiap titiknya mempunyai derajat genap,
maka G mempunyai sebuah sirkuit Euler” Untuk itu kita periksa bahwa A terhubung dan derajat setiap
titiknya genap. Pertama kita beri label setiap titik dan sisi pada graf A sebagai berikut:
A
Graf A terhubung karena terdapat sebuah
lintasan dari titik x dan y jika diketahui sembarang titik x dan y. Dan jika
kita periksa sebagai berikut:
a ke b
lintasannya (a, e1, b) ; a ke c lintasannya (a, e1, b, e2, c) ; a ke d lintasannya (a, e12,d) ; a ke e
lintasannya (a, e11, e) ; a ke f
lintasannya (a, e11, e, e10, f) ; b ke c lintasannya (b, e2, c) ; b ke d
lintasannya (b, e4, d) ; b ke e lintasannya (b, e4, d, e8,e) ; b ke f
lintasannya (b, e6, f) ; c ke lintasannya (c, e7, f, e9, d) ; c ke e
lintasannya (c, e5, e) ; c ke f
lintasannya (c, e7, f) ; d ke e lintasannya (d, e8, e) ; d ke f lintasannya
(d, e9, f) ; e ke f lintasannya (e, e10, f) ; sehingga dengan demikian A
terhubung.
d(a) = d(b) = d(c) = d(d) = d(e) = d(f) = 4 ini artinya setiap setiap titik pada graf A berderajat genap.
Karena derajat setiap titik
adalah genap, menurut teorema tersebut di atas maka A mempunyai sebuah sirkuit
Euler.
Jadi
graf A di atas mempunyai Sirkuit
Euler-nya, dan sirkuit Euler-nya yaitu:
(c,
a, b, f, c, e, a, d, e, f, d, b, c)
Untuk
menunjukan lingkaran Hamilton dalam sebuah graf B maka kita beri label terlebih dahulu setiap titik pada graf B seperti yang tampak di bawah ini:
B
Berikut
ini dua lingkaran Hamilton berbeda pada graf B :
(l, h, i, d, c, b, a, j,
k, g, f, e, l)
dan
(i, h, g, f, e, l, b, a,
j, k, c, d, i)
5. Periksalah
apakah kedua graf di bawah ini planar. Berikan alasan
(A) (B)
Jawab:
Untuk
memeriksa graf A planar atau
tidak planar maka kita beri label terlebih dahulu setiap titik pada graf A seperti yang tampak di bawah ini:
(A)
Dalam pemeriksaan
apakah graf A planar atau tidak
planar, dapat menggunakan Teorema Kuratowski yang menyatakan, “Graf G merupakan planar jika dan hanya jika
G tidak mengandung suatu graf-K sebagai subgraf dari G”. Dalam hal ini
sebuah graf-K adalah graf yang didapat dari K5 atau K3,3
dengan melakukan subdivisi pada sisinya. Artinya dalam persoalan
pemeriksaan apakah graf A planar
atau tidak planar kita akan mencoba menemukan K5 atau K3,3 pada graf A..
Pertama
kali kita ingat bahwa titik a, c, d, e dan
f pada graf A yang telah
dilabeli pada gambar di atas, masing – masing mempunyai derajat 4. Untuk itu
kita coba menemukan K5
dalam graf A, karena dalam K5 setiap titik mempunyai
derajat 4, sehingga kita akan melakukannya sebagai berikut:
Graf A kita dapat membentuknya seperti
tampak dibawah ini:
K5 setiap titik mempunyai derajat
4, sehingga kita dapat menghapus sisi (d, h) dan (g, h) agar semua sisi
mempunyai derajat 4, tampak pada gambar dibawah ini:
Hapus sisi (d, h) dan (g, h)
|
|
K5
Selanjutnya
kita dapat melakukan reduksi seri (Definisi:
Jika sebuah graf G mempunyai sebuah sisi v berderajat 2 dan sisi (v, v1)
dan (v, v2) dengan v1 ¹ v2 kita katakana bahwa rusuk Reduksi seri
(v, v1) dan (v, v2) berada dalam seri. Reduksi
seri terdiri dari penghapusan sisi v graf G dan menggantikan sisi-sisi (v, v1)
dan (v, v2) dengan sisi (v1, v2). Graf yang
dihasilkan G’ dikatakan diperoleh dari G dengan sebuah reduksi seri.
Berdasarkan konvensi, G dikatakan dapat diperoleh dari diri sendiri dengan sebuah
reduksi seri) dan graf yang dihasilkan akan mempunyai sepuluh sisi dan
karena K5 mempunyai
sepuluh sisi, pendekatan ini kelihatan dapat menjanjikan. Dengan coba-coba,
akhirnya kita lihat bahwa jika kita kurangi sisi (d, h) dan (g, h) dan kita
lakukan reduksi seri, kita peroleh sebuah salinan dari K5 seperti tampak pada Gambar 5.1. di atas.
Jadi, graf A pada soal 5. ini tidak planar, karena
graf tersebut mengandung sebuah subgraf yang homeomorfik pada K5.
Untuk
memeriksa graf B planar atau
tidak planar maka kita beri label terlebih dahulu setiap titik pada graf B seperti yang tampak di bawah ini:
(B)
Dalam
pemeriksaan apakah graf B planar
atau tidak planar, dapat menggunakan sama halnya seperti apa yang dilakukan pada
graf A tadi di atas
menggunakan Teorema Kuratowski. Artinya dalam persoalan pemeriksaan apakah
graf B planar atau tidak planar
kita akan mencoba menemukan K5 atau K3,3 pada graf B.
Pertama
kali kita ingat bahwa titik a, b, d, c dan
d pada graf B yang telah
dilabeli pada gambar di atas, masing – masing mempunyai derajat 4. Untuk itu
kita coba menemukan K3,3
dalam graf B, karena dalam K3,3 setiap titik mempunyai
derajat 3, sehingga kita akan melakukannya sebagai berikut:
Graf B kita dapat membentuknya seperti
tampak dibawah ini:
(B)
K3,3 setiap titik mempunyai derajat
3, sehingga kita dapat menghapus sisi (c, h), (e, h) dan (i, h) agar semua sisi
mempunyai derajat 4, tampak pada gambar dibawah ini:
Hapus sisi (c, h), (e, h) dan (i, h)
|
|
K3,3
Selanjutnya
kita dapat melakukan reduksi seri sehingga graf yang dihasilkan akan mempunyai
sembilan sisi dan karena K3,3
mempunyai sembilan sisi, pendekatan ini kelihatan dapat menjanjikan. Dengan
coba-coba, akhirnya kita lihat bahwa jika kita kurangi sisi (c, h), (e, h) dan
(i, h) dan kita lakukan reduksi seri, kita peroleh sebuah salinan dari K3,3 seperti tampak pada Gambar 5.2. di atas.
Jadi, graf B pada soal 5. ini tidak planar, karena
graf tersebut mengandung sebuah subgraf yang homeomorfik pada K3,3.
