SOAL DAN PEMBAHASAN GRAPH
MATEMATIKA INFORMATIKA 4
KELOMPOK 2
ABDUL ROHMAN 50416018
FIGA RIZFA ZAZILA 52416819
HAWA AMALIA POETRI 53416247
ISAGHRIB AZIZ PRAMONO 53416608
JOSIE LATIF 53416765
KHAIRA YUHARIFALLAH 53416884
LUTHFI RIZKY PERDANA 54416146
MIZANI ZIDQI 54416434
M. AZAM IRFANI 54416742
M. CHAIRULI NUGRAHA 54416761
M. YUSUF HERLAMBANG 55416146
RENALDY DWI JULIANTO 56416169
REVINNA NOVIANTI BR 56416232
1.
1.
Berapa banyak
simpul dan ruas dari graph tersebut?
a.
5 dan 4
b.
4 dan 5
c.
5 dan 5
d.
4 dan 4
Pembahasan:
·
Banyak simpul terdiri
dari 4 simpul, yaitu simpul A, B, C dan D
·
Banyak ruas
terdiri dari 5 ruas, yaitu e1 = (A, B) e2 = (B, D) e3 = (D,C)
e4 = e5 = (B, C)
2.
Berapa
arkus yang terdapat pada graph diatas?
a. 7
b.
6
c.
5
d.
4
Pembahasan:
Graf
tersebut mengandung 7 arkus, yaitu: (1,4), (2,1), (2,1), (2,2), (2,3), (2,4),
(4,3).
3.
3.
Jika order dari G = n, size dari G = e, dan
banyak komponen = k, berapa Rank dari graf G?
A. 6
B. 5
C. 4
D. 3
Pembahasan:
Dik : n = 7
k = 1
Rank (G) = n – k
= 7 – 1
= 6
4.
4.
Pada gambar graf diatas
tentukan himpunan titiknya:
A.
V(G1)
= {a,b,c,d}
V(G2) =
{u,v,w,x,y}
V(G3) =
{1,2,3,4,5,6}
B. V(G1)
= {a,b,c,d}
V(G2)
= {u,v,w,x,y}
V(G3)
= {12,22,23,24,25,26,45,46}
C. V(G1)
= {a,b,c,d}
V(G2)
= {xy,xw,xu,vy,uw,uy,uv,vu}
V(G3)
= {3,2,1,6,5,4}
D. V(G1)
= {ab,ac,bc,ad,bd,cd}
V(G2)
= {u,v,w,x,y}
V(G3)
= {3,2,1,6,5,4}
Pembahasan:
Titik-titik dari suatu
graf yaitu:
V(G1) = {a,b,c,d}
V(G2) =
{u,v,w,x,y}
V(G3) =
{1,2,3,4,5,6}
5.
5.
Berapa derajat graph dari
gambar diatas…
A. 2
B. 4
C. 8
D.
12
Pembahasan:
Order (G) = 4
Size = 6
Derajat graph = 2*size
=2*6
= 12
6. 6. Berapa Komponen dari gambar graph di nomor 5?
A. 2
B. 4
C. 6
D.
1
Pembahasan:
Karena gambar graph di
nomor 3 adalah contoh dari graph terhubung dan saling berkaitan antar ruasnya
7. 7. Graph berarah dibawah ini matriks sirkuitnya adalah....
A.
B.
Pembahasan:
Ada 4
sirkuit pada graf tersebut, masing – masing sirkuit itu adalah
S1 = v4 v6
v4
S2 = v2 v4
v5 v2
S3 = v1 v2
v5 v1
S4 = v1 v2
v4 v5 v1
Misalkan
orientasi yang dipilih pada s2 dan s3 sesuai dengan arah jarum jam, sedangkan
pada s1 dan s4 berlawanan dengan arah jarum jam. Dengan demikian, matriks
sirkuitnya adalah:
88. Nullity dari graf dibawah adalah…
A.
Nullity (G) = 3
B. Nullity (G) = 1
C. Nullity (G) = 2
D. Nullity (G) = 4
Pembahasan:
Diketahui: n= 8; k=1; e=1
Nullity
(G) = e – (n – k)
Nullity
(G) = 1 – (8 – 1)
Nullity
(G) = 3
9 9. Diameter dari graf dibawah
ini adalah…
A. 4
B.
6
C.
8
D.
10
Pembahasan:
Jarak maksimum dalam graf diatas adalah 4 (yaitu
antara A-D, A-H, E-D, E-H), jadi diameter = 4
10.
A. 2
B. 5
C.
6
D. 1
Pembahasan :
Karena panjang walk = banyaknya ruas
