Soal-soal Graph

Oleh Adinda Syamsudin

22 tayangan
Bagikan artikel

Transkrip Soal-soal Graph

1. Tentukan banyak simpul, jalur dan derajat pada setiap graf dibawah ini. Tentukan simpul
terasing dan simpul pendant dari setiap graf jika ada terdapat dalam setiap graf!
a. a
b

c

d

b. a

b

c

d

e

jawab :
a. Pada graf a, simpulnya atau V = {a, b, c, d}. sedangkan jalurnya atau E = {(a,b),(b,b),(a,c),
(a,d)}. Dalam graf a : der(a)=3, der(b)=3, der(c)=der(d)=1.
Simpul terasing adalah simpul yang berderajat nol atau simpul yang tidak berdekatan
dengan simpul yang lainnya, maka dalam graf a tidak ada simpul terasing.
Simpul pendant adalah simpul yang jika dan hanya jika titik simpul ini berderajat satu, maka
dalam graf a simpul pendant terdapat dalam simpul c dan d.
b. Pada graf b, simpulnya atau V = {a, b, c, d,e}. sedangkan jalurnya atau E = {(a,b),(b,c),(a,c),
(a,d),(b,d),(c,d),(d,e)}. Dalam graf b : der(a)=der(b)=der(c)=, der(d)=4, der(e)=1.
Simpul terasing adalah simpul yang berderajat nol atau simpul yang tidak berdekatan
dengan simpul yang lainnya, maka dalam graf b tidak ada simpul terasing.
Simpul pendant adalah simpul yang jika dan hanya jika titik simpul ini berderajat satu, maka
dalam graf b simpul pendant terdapat dalam simpul e.
2. Gambarlah graf dibawah ini!
a. K8
b. C8
Jawab :
a.

b.

3. Perhatikan graf E dibawah ini. Apakah graf E merupakan graf bipartit? Jelaskan!
2
3
1
5

4
( graf E )

jawab : Graf E dapat direpresentasikan menjadi graf bipartit G(V , V ), dimana V =
1 2
1

{2, 4} dan V = {1, 3, 5}
2
V1

V2

2

1 1

4

3
5

4. Tentukan berapa banyak jalur pada suatu graf yang memiliki 4 simpul dan derajat setiap simpul
adalah 8?
Jawab : karena setiap simpul memiliki derajat = 8, maka jumlah derajat dari 4 simpul tersebut
adalah 8 X 4 = 32.
Menurut rumus mencari jalur 2e = ∑ de (V )
VEV

Sehingga, 2e = 32
e = 16
Jadi banyak jalur yang terdapat dalam graf tersebut adalah 16.
A

B

C

D

5. Gambarlah graf bipartit komplit dibawah ini!
a. K3,6
b. K2,8
Jawab :
a.

b.

Graf lengkap adalah graf yang setiap simpulnya terhubung dengan semua simpul yang lain
dengan hanya satu jalur.
Graf bipartit adalah graf yang simpul-simpulnya dapat dikelompokkan menjadi dua, simpulsimpul dalam satu kelompok tak terhubung dan simpul antar kelompok terhubung lengkap.
Derajat sebuah simpul adalah banyaknya jalur yang incident pada simpul tersebut. Simpul ganjil
adalah simpul yang derajatnya ganjil. Simpul genap adalah simpul yang derajatnya genap.
Jumlah derajat sama dengan dua kali jumlah jalur.
Derajat loop dihitung 2.

Daftar pustaka :
Wibisono, Samuel. 2008. Matematika Diskrit Edisi 2. Yogyakarta: Graha Ilmu

Judul: Soal-soal Graph

Oleh: Adinda Syamsudin


Ikuti kami