UNIVERSITAS TELKOM
LEDYA NOVAMIZANTI
GRAF No 1
Soal Untuk setiap soal di bawah, sebutkan apakah ada graf sederhana dengan lima simpul (vertex) yang memiliki derajat untuk masing-masing simpul sebagai berikut? Jika ada, gambar grafnya! a) 3,3,2,3,3 b) 4,3,1,4,2 c) 2,1,3,0,2 d) 4,4,3,3,3
2
Mungkinkah dibuat graf-sederhana 5 simpul dengan derajat masing-masing simpul adalah: a) 5, 2, 3, 2, 4 b) 4, 4, 3, 2, 3 c) 3, 3, 2, 3, 2 d) 4, 4, 1, 3, 2 Jika mungkin, berikan satu contohnya, jika tidak mungkin, berikan alasan singkat.
3
Berapa jumlah maksimum dan jumlah minimum simpul pada graf sederhana yang mempunyai 12 buah sisi dan tiap simpul berderajat 3?
4
Mana dari kedua graf di atas yang merupakan graf bipartite? Tentukan mana himpunan simpul V1 dan mana simpul V2 dari graf bipartite tersebut, lalu gambarkan graf bipartite alternatif dengan himpunan V1 di bagian atas dan himpunan V2 di bagian bawah. 5
a) Apakah K14 adalah graf Euler ? Jelaskan! b) Apakah K15 adalah graf Euler ? Jelaskan!
6
Suatu graf memiliki jumlah simpul ganjil. Apabila tiap simpul berderajat sama, tunjukkan bahwa graf tersebut adalah graf Euler!
7
Berapa jumlah maksimum dan jumlah minimum simpul pada graf sederhana yang mempunyai 16 buah sisi dan tiap simpul berderajat sama dan tiap simpul berderajat ≥ 4 ?
8
Berapa jumlah maksimum dan jumlah minimum simpul pada graf sederhana yang mempunyai 12 buah sisi dan tiap simpul berderajat 3?
9
Apakah setiap graf lengkap adalah graf Hamilton ? Jelaskan !
1
UNIVERSITAS TELKOM
LEDYA NOVAMIZANTI
10
a) Apakah setiap graf Hamilton adalah graf Euler? Berikan penjelasan. b) Apakah setiap graf Euler adalah graf Hamilton? Berikan penjelasan. c) Jika a) dan b) keduanya adalah “tidak”, berikan 2 contoh graf Hamilton yang juga merupakan graf Euler (jumlah simpul 2 contoh ini harus berbeda).
11
Gambarkan : a) 2 buah graf yang memiliki lintasan Hamilton tetapi tidak memiliki sirkuit Hamilton b) 2 buah graf yang saling planar menurut Teorema Kuratowski
12
Misalkan graf sederhana planar dan terhubung memiliki 24 buah simpul, masing-masing simpul berderajat 4. Representasi planar dari graf tersebut membagi bidang datar menjadi sejumlah wilayah atau muka. Berapa banyak wilayah yang terbentuk?
13
Apakah graf sederhana yang disajikan oleh pasangan matriks ketetanggaan di bawah ini isomorfik? Jelaskan jawaban, lalu gambarkan grafnya!
0 1 0 1
1 0 0 1
0 0 0 1
1 0 1 1 ; 1 1 0 1
1 0 0 1
1 0 0 1
1 1 1 0
Jawab: Keduanya tidak isomorfik karena jumlah sisi pada graf pertama dan graf kedua tidak sama. Graf pertama (G1) mempunyai 4 buah sisi (hitung jumlah elemen 1 di atas digaonal utama), sedangkan graf kedua (G2) mempunyai 5 buah sisi (hitung jumlah elemen 1 di atas diagonal utama). Gambar kedua graf yang dimaksud:
G1
G2
14
Gambarkan sebuah graf sederhana dengan n buah simpul (n 5) yang tidak memiliki sirkuit Hamilton meskipun derajat setiap simpul paling sedikit (n – 1)/2.
15
Graf yang mewakili masalah jembatan Konigsberg adalah seperti di bawah ini, yang dalam hal ini simpul menyatakan daratan dan sisi menyatakan ruas jembatan.
2
UNIVERSITAS TELKOM
LEDYA NOVAMIZANTI A
D
B
C
Berapa paling sedikit ruas jembatan baru yang perlu ditambahkan agar setiap jembatan dapat dilalui tepat sekali? Gambarkan graf yang baru setelah penambahan jembatan baru tersebut. 16
Ada tiga buah peta jalan di tiga buah komplek perumahan besar (Gambar a, b, dan c di bawah ini). Jalanjalan tersebut ada yang dapat dilalui hanya searah atau dua arah (ditunjukkan dengan arah panah). Mana saja dari ketiga peta jalan tersebut yang dapat dilalui oleh Pak Pos sedemikian sehingga setiap ruas jalan hanya dilewati tepat sekali dan kembali lagi ke titik asal keberangkatan? Jelaskan alasan matematis atas jawaban anda tersebut. Jawab:
(a) 17
(b)
(c)
Diketahui matriks ketetanggaan (adjacency matrices) dari sebuah graf tidak berarah:
0 1 0 0 1
1 0 1 1 1
0 1 1 1 0
0 1 1 0 1
1 1 0 1 0
Gambarkan dua buah graf yang isomorfik yang bersesuaian dengan matriks ketetanggaan di atas.
18
Gambarkan 2 buah graf sederhana yang isomorfik dengan graf teratur berderajat 3 yang mempunyai 8 buah simpul.
3
UNIVERSITAS TELKOM 19
LEDYA NOVAMIZANTI
Apakah pasangan graf dibawah ini isomorfik (kalau iya tentukan simpul-simpul yang berkorespodensi) a)
5
1 a
b
4 2
3 6
d
e
c
f c
b) 1
5
6
2
20
a
e
b
f
4
Diketahui matriks ketetanggaan (adjacency matrices) dari sebuah graf tidak berarah: 0 1 0 0 1
21
d
3
1 0 1 1 1
0 1 1 1 0
0 1 1 0 1
1 1 0 1 0
a. b. c. d.
Apakah graf di atas dapat direpresentasikan sebagai graf planar? Buktikan dengan ketidaksamaan Euler! Jika iya, hitung banyak wilayahnya dengan rumus Euler Hitung jumlah region (wilayah) yang dihasilkan oleh graf tersebut. Gambarkan tiga buah graf yang isomorfik yang bersesuaian dengan matriks di atas.
Perlihatkan dengan ketidaksamaan Euler bahwa graf berikut planar, lalu gambarkan graf planar tersebut sebagai graf bidang. b
c
a
d e
22
f
Gunakan Teorema Kuratowski untuk menentukan apakah graf di bawah ini planar. c
b
a
d g
f
e
4
UNIVERSITAS TELKOM 23
LEDYA NOVAMIZANTI
Diberikan gambar sebuah graf seperti di samping ini. Tunjukkan dengan Teorema Kuratowski bahwa graf tersebut tidak planar. B
A
C
D
E
F
G
H
24
Perlihatkan dengan Teorema Kuratowski bahwa dua buah graf di bawah ini tidak planar! A
E
F
D
B
C
5
