Soal Pengantar Teori Graph

TUGAS MANDIRI

PENGANTAR TEORI GRAPH

(PAMA4208)

PETUNJUK: UNTUK SOAL NOMOR   1  SAMPAI  DENGAN 51,  PILIHLAH SATU JAWABAN YANG PALING TEPAT!

1.   Masalah jembatan koningberg di daratan Eropa merupakan awal lahirnya teori Graf pada tahun ....           

A.   1895

B.   1868

C.   1821

D.   1736

2.   Sehubungan dengan perkembangan teori graf Sir W. R. Hamilton tahun 1859 berhasil menemukan suatu permainan teori graf dengan menggunakan kayu yang berbentuk ....          

A.   polihedron beraturan

B.   dodecohedron beraturan

C.   pentagon beraturan

D.   hexagon beraturan

     

3.   Teori pohon merupakan bagian yang penting dari Teori Graf yang digunakan dalam persoalan jaringan listrik. Hal tersebut dikembangkan oleh ....

A.   Euler

B.   GR Kirchoff

C.   A. Coyley

D.   A.F. Mobius

4.   Masalah empat warna sangat terkenal setelah dipublikasikan pada tahun 1879 dalam proceding of the Royal Geographic society oleh ....

A.   A. F Mobius

B.   De Morgan

C.   Coyley

D.   Kirchoff

5.   Diantara orang-orang terkenal yang banyak berkecimpung dalam aktivitas pengembangan teori graf baik murni maupun terapan adalah ....

A.   Claude Berge, Oysten Coyley, William Tutte

B.   William Tutte, Frank Harry, Konig, Paul Erdon

C.   Paul Erdon, Claude Berge, De Morgan, Frank Harary

D.   Claude Berge, Oysten, Paul Erdon, Frank Harary

6.   Sebuah Graf 6 = (V, E) dengan himpunan sisi E merupakan himpunan kosong disebut ....

A.   hingga

B.   tak hingga

C.   null

D.   sederhana

7.   Sebuah titik dalam graf G yang berderajat nol disebut titik ....

A.   anting

B.   ujung

C.   terisolasi

D.   ajasen

8.   Sebuah graf yang tidak memiliki loop dan sisi-sisi paralel disebut graf ....

A.   Null

B.   Teratur

C.   sederhana

D.   lengkap

9.   Diagram di bawah merupakan suatu graf yang mempunyai ....

A.   4 titik dan 7 sisi

B.   5 titik dan 6 sisi

C.   5 titik dan 4 sisi

D.   5 titik dan 8 sisi

10.   Jika dua titik v1 dan v2 dalam sebuah graf

        G = (V,E) merupakan titik-titik ujung dari sebuah sisi e, maka kedua titik tersebut merupakan titik-titik yang saling ....

A.   insiden

B.   ajasen

C.   paralel

D.   seri

11.   Sebuah graf berarah D adalah suatu himpunan hingga yang tidak kosong dengan sebuah relasi R pada V dengan R yang bersifat ....

A.   transitif

B.   reflektif

C.   tidak reflektif

D.   tidak simetris

12.   Gambar di bawah ini merupakan diagram dari graf ....

A.   berarah

B.   berarah simetri

C.   berarah sama

D.   berarah berlawanan

13.   Jaringan kerja yang merupakan sebuah graf disebut jaringan kerja ....

A.   biasa

B.   bersemu

C.   berarah

D.   tidak berarah

14.   Misalkan M adalah sebuah multigraf dengan himpunan sisi E dan fungsi f. Jika u v Î E dan f (uv) = n (n adalah bilangan bulat positif), maka u dan v dihubungkan oleh n sisi. Sisi-sisi seperti ini disebut sisi ....

A.   multipel

B.   paralel

C.   insiden

D.   ajasen

15.   Apabila G = (V, E) adalah sebuah multigraf, dan G memuat (u,v) dengan v anggota V, maka G disebut ....

A.   loop

B.   multigraf

C.   graf berarah

D.   multigraf dengan loop

16.   Silsilah keluarga dapat dibuat atau dinyatakan dalam bentuk graf sederhana. Graf tersebut berbentuk ....

A.   loop

B.   pohon

C.   jaringan tidak berarah

D.   jaringan silsilah

17.   Gambar di bawah merupakan graf yang mempresentasikan banyaknya pintu yang terdapat dalam suatu ruangan sama dengan ....

A.   banyaknya sisi

B.   banyaknya sisi berarah

C.   banyaknya loop

D.   derajat titik

18.   Untuk mengubah signal dari suatu sirkuit ke sirkuit lainnya dan juga untuk memproses data digunakan ....

A.   komputer mikro

B.   komputer mini

C.   internet

D.   intercom

19.   Suatu sistem yang dapat digunakan untuk mengirim pesan antar komputer mikro atau untuk melakukan proses pengolahan data termasuk ....

A.   desain artitektur

B.   jaringan transportasi

C.   jaringan silsilah

D.   sistem komunikasi

20.   Dalam sebuah graf G, tiap elemen dari E disebut sisi dan E sendiri disebut himpunan sisi dari G. Banyaknya sisi dalam G disebut ....

A.   ukuran dari G

B.   ukuran dari E

C.   orde dari G

D.   orde dari E

21.   Dalam sebuah graf G, V merupakan sebuah himpunan titik dan tiap elemen dari V disebut titik. Banyaknya titik dalam G ditulis ....

A.   ½E½

B.   ½V½

C.   E (G)

D.   V (G)

22.   Himpunan sisi dari suatu graf bisa berupa himpunan kosong atau suatu graf mungkin tidak memiliki sisi, karena relasi R pada V memenuhi sifat ....

A.   reflektif dan tidak antisimetris

B.   tidak reflektif dan tidak antisemetris

C.   reflektif dan antisimetris

D.   tidak reflektif dan antisimetris

23.   Diagram di bawah sebuah graf yang menyatakan ....

A.   titik v₃ bukan ujung v₂ v₃

B.   titik v₄ bukan ujung v₂ v₃

C.   sisi v₁v_­3 dan v₃v₄ dua sisi tidak berbatasan

D.   sisi v₁v₂ dan v₂v₄ dua sisi berbatasan

24.   Jika u v ÏE (G), e menghubungkan titik u dan v, maka u dan v merupakan dua titik yang ....

A.   saling berbatasan

B.   saling berpotongan

C.   tidak saling berbatasan

D.   tidak saling berpotongan

25.   Jika A(G) merupakan sebuah matriks indidensi dari suatu graf terhubung G dengan n titik, maka rank dari A(G) adalah ....

A.   n

B.   n - 1

C.   n + 1

D.   n x n

26.   Matriks ajasensi dari graf gambar di bawah, elemen-elemen diagonal utamanya adalah ....

A.   0 0 0 0

B.   1 1 1 1

C.   1 1 0 0

D.   0 0 1 1

27.   Matriks dari graf G dengan n titik dan tidak memuat sisi paralel merupakan matriks ....

A.   insidensi

B.   ajasensi

C.   biner

D.   (0,1)

28.   Jika sebuah graf G tidak terhubung dan terdiri atas dua komponen g, dan g₂ maka matriks ajasensinya adalah x (G) = ....

A.  

B.  

C.  

D.  

29.   Graf G = (V,E) adalah sebuah graf lengkap dengan 4 titik, maka banyaknya sisi dalam G adalah ....

A.   4

B.   6

C.   10

D.   12

30.   Karena tiap titik dalam graf lengkap selalu dihubungkan dengan titik lain melalui satu sisi, maka derajat tiap titik dalam sebuah graf lengkap G dengan n titik dirumuskan sebagai ....

A.   n - 1

B.   n + 1

C.   n (n+1)/2

D.   n ( n - 1)/2

31.   Sebuah graf G = (V,E) semua titiknya berderajat sama, maka graf tersebut disebut graf  ....

A.   sederhana

B.   lengkap

C.   teratur

D.   iso morfik

32.   Misalkan G = (V, E) adalah sebuah graf sederhana. Jika tiap pasangan titik v_i,v_j, terdapat sebuah sisi yang menghubungkannya, maka G disebut graf  ....

A.   sederhana

B.   lengkap

C.   universal

D.   teratur

33.   Jika dua (atau lebih) subgraf g1 dan g2 dari graf G tidak memiliki sisi sekutu, maka disebut ....

A.   Bipartit

B.   Isomorfik

C.   Disjoin sisi

D.   Universal

34.   Diagram di bawah merupakan graf ....

A.   bipartit

B.   isomorfik

C.   lengkap

D.   teratur

35.   Sebuah graf G dengan u dan v adalah titik dari graf. Perjalanan u - v dengan tidak ada satu sisipun yang di ulang disebut ....

A.   terhubung u - v

B.   penelusuran u - v

C.   perjalanan u - v

D.   pemetaan u - v

36.   Jika R simetris untuk setiap pasangan berurutan (u,v) ÎR pasangan terurut (v,u) juga elemen R, maka yang dinotasikan dengan E adalah himpunan pasangan ....

A.   terurut tidak simetris

B.   terurut simetris

C.   tidak terurut tidak simetris

D.   tidak terurut simetris

37.   Suatu perjalanan yang digambarkan dalam suatu graf hanya diperlukan daftar ....

A.   simpul dan rusuk

B.   rusuk dan titik

C.   simpul-simpul saja

D.   rusuk-rusuk saja

38.   Dari gambar graf G berikut yang menunjukkan sirkuit adalah barisan simpul ....

	A

 

D

E

F

B

C

       

A.   A, B, E, C, D, E, F

B.   A, C, D, B, E, F, C

C.   C, A, B, D, E, C, F

D.   C, E, B, D, E, F, C

39.   Dua buah simpul u dan v dalam suatu graf G, jika u = v atau jika u ¹ v, terdapatlah jalur u - v di G. Maka graf G dikatakan ....

A.   tak terhubung

B.   terhubung

C.   lintasan

D.   jalur

     

40.   Suatu graf dikatakan terhubung bila graf tersebut hanya mempunyai ....

A.   empat buah komponen

B.   tiga buah komponen

C.   dua buah komponen

D.   satu buah komponen

41.   Graf G pada gambar di bawah merupakan sirkuit apabila ....

A.   a, b, c, e, b, f, a

B.   a, b, c, e, d, b, f

C.   a, f, b, e, d, c, e

D.   a, f, b, c, e, d, b

42.   Sub graf H dari G dengan V(H) = { a, b, e, c, f) dan E (H) = { ab, bc, ec, eb, bf } maka H termasuk suatu ....

A.   sirkuit dalam G

B.   lintasan dalam G

C.   sikel dalam G

D.   komponen dalam G

43.   Suatu simpul v di dalam graf terhubung G disebut simpul pemotongan apabila ....

A.   G - v terhubung

B.   G - v tak terhubung

C.   G - v himpunan rusuk

D.   G - v jaringan rusuk

44.   Multigraf yang memuat sirkuit Euler disebut ....

A.   sirkuit Euler

B.   graf Euler

C.   multigraf Euler

D.   lintasan Euler

45.   Gambar graf di bawah termasuk graf ....

A.   Hamilton

B.   Euler

C.   terlacak

D.   sebarang

46.   Multigraf G dikatakan terlacak jika dan hanya jika G terhubung dan tepat mempunyai ....

A.   dua simpul ganjil

B.   tiga simpul ganjil

C.   dua simpul genap

D.   tiga simpul genap

47.   Jika graf G mempunyai simpul p ³ 3 dan derajat tiap simpul di G ³ P/2, maka graf G adalah graf ....

A.   Euler

B.   Hamilton

C.   Multigraf

D.   terlacak

48.   Gambar di bawah graf G adalah graf Hamilton sebab graf itu memuat sikel Hamilton. Hal ini dapat dituliskan sebagai ....

A.   a, c, b, d, e, b

B.   a, c, b, e, d, a

C.   a, b, c, d, e, a

D.   a, b, e, d, c, a

49.   Graf G₁ dan G₂ adalah graf Euler yang tidak bersekutu satu simpulpun. Jika v₁ simpul di G₁, v₂ simpul di G₂ dan G adalah graf yang terdiri dari G₁ dan G₂ bersama-sama dengan rusuk v₁v₂ maka graf G adalah ....

A.   graf terlacak

B.   graf sebarang

C.   graf Euler

D.   graf Hamilton

50.   Jika di dalam graf diperkenankan adanya dua simpul yang dihubungkan lebih dari satu rusuk, maka disebut ....

A.   Euler

B.   Hamilton

C.   terlacak

D.   multigraf

51.   Seluruh multigraf M adalah multigraf Euler jika dan hanya jika M terhubung dan setiap simpulnya berderajat ....

A.   nol

B.   bulat

C.   ganjil

D.   genap

PETUNJUK:  UNTUK SOAL NOMOR   52   SAMPAI   60,   PILIHLAH:

A.   JIKA 1) DAN 2) BENAR!

B.   JIKA 1) DAN 3) BENAR!

C.   JIKA 2) DAN 3) BENAR!

D.   JIKA 1), 2), DAN 3) SEMUANYA BENAR!    

52.   Gambar graf di bawah menyatakan v₁, v₂, v₃ adalah tiga kota. Tiap dua kota dihubungkan oleh satu jalan yang jaraknya tidak sama dan ditempuh dengan jalan kaki, maka lama perjalanannya adalah ....

1)   antara v₁ dan v₂ tiga hari

2)   antara v₁ dan v₃ satu hari

3)   antara v₂ dan v₃ satu hari

53.   Graf G yang didefinisikan sebagai himpunan dan E = { v₁v₂, v₁v₃, v₂v₃, v₃v₄ }, maka graf G dikatakan ....

1)   mempunyai orde 4

2)   mempunyai ukuran 4

3)   mempunyai orde dan ukuran 2

54.   Sebuah matriks insidensi dari suatu graf yang hanya memuat elemen 0 dan 1 disebut matriks ....

1)   (0,1)

2)   biner

3)   ajasensi

55.   Sebuah graf g merupakan bagian dari graf G atau sub graf dari G, maka akan berlaku sifat-sifat berikut ini ....

1)   sebuah titik dalam graf G merupakan sub graf dari G

2)   subgraf dari suatu subgraf dari G adalah subgraf dari G

3)   setiap graf merupakan subgraf dari dirinya sendiri

56.   Jika suatu graf G diketahui V(H) V(G) maka graf H disebut ....

1)   subgraf dari G

2)   subgraf isomorphik dari G

3)   graf bagian dari G

57.   Jika e adalah suatu rusuk dalam graf G, maka G-e adalah subgraf dari G. Rusuk e dalam graf terhubung G disebut ....

1)   simpul pemotongan

2)   jembatan

3)   bridge

58.   E.W. Dijkstra menemukan suatu algoritma jalur terpendek dalam suatu graf. Versi yang diberikan adalah ....

1)   menetapkan m = 1 dan berikan pada simpul a dengan (-,0)

2)   melacak balik untuk sebarang simpul y, jalur terpendek dari simpul a ke y mempunyai panjang k (y)

3)   memberikan label m pada simpul-simpul jalur terpanjangnya dari simpul a

59.   Gambar graf di bawah bukanlah termasuk graf Hamilton karena ....

1)   tidak memuat sikel Hamilton

2)   banyaknya simpul p £ 3

3)   derajat setiap simpul v pada graf maksimal p/2

60.   Gambar graf di bawah merupakan graf terlacak karena ....

1)   mempunyai lintasan

2)   memuat semua simpul dan rusuk

3)   mempunyai sirkuit