TEORI GRAF DAN OTOMATA
TUGAS INDIVIDU
OLEH :
NAMA : TAUFIK
ARI ARNANDAN
NIM : 14.11.0110
KELAS :
TI 14 B
1)
Mungkinkah dibuat graf-sederhana 5 simpul dengan derajat
masing-masing simpul adalah:
a) 5, 2, 3, 2, 4
Jawab:
-
Tidak mungkin, karena
ada satu simpul yang berderajat 5, jadi di perlukan looping atau gelang.
b) 4, 4, 3, 2, 3
Jawab:
-
mungkin
-
Karena 4+4+3+2+3 = 16
(Genap)
-
Jumlah sisi yang
terbentuk adalah 16:2 = 8 sisi
c) 3, 3, 2, 3, 2
Jawab:
-
Tidak mungkin
-
Karena 3+3+2+3+2 = 13 (Derajat Ganjil)
-
13 jika di bagi 2 tidak akan membentuk
sisi yang utuh
-
Karena jumlah sisi ganjilnya ada 3
(ganjil)
d) 4, 4, 1, 3, 2
Jawab:
-
Tidak mungkin
-
Karena 4+4+1+3+2 = 14 (7
sisi)
-
Simpul 1 & 2 harus
bertetangga, dengan simpul yang ke 3 mempunyai derajat 2 dan simpul lainya
berderajat 1.
2) Soal
E-Book Halaman 56
Jawab :
(a) False
(b) True
(c) True
(d) True
Jawab :
Graf tersebut memenuhi korespondensi satu per
satu.
Jawab :
(a) (1,1,2,3,3,4,4,6)
1+1+2+3+3+4+4+6 = 24
(Genap)
Jumlah sisi yang
terbentuk adalah 24:2 = 12 sisi
(b) (3,3,3,3,3,5,5,5)
3+3+3+3+3+5+5+5 = 30
(Genap)
Jumlah sisi yang
terbentuk adalah 30:2 = 15 sisi
EmoticonEmoticon