Teori Graf (Tes Formatif 5.1)

Contoh model graf sederhana yang memuat simpul berderajat 1 adalah…

• 
• 
• 
• 
• 

Berdasarkan model graf berikut, simpul yang memiliki derajat tertinggi adalah…

• Simpul b

• Simpul d

• Simpul e

• Simpul g

• Simpul h

Perhatikan model graf di samping.

Misalkan m dan n berturut-turut menyatakan banyak simpul dan sisi pada graf di atas. Nilai dari 2m+n=…

• 12

• 13

• 16

• 17

• 18

Pernyataan yang terkait graf di atas adalah….

• Simpul merupakan simpul terpencil

• Graf tersebut bukan graf sederhana

Misalkan simpul dari suatu graf merepresentasikan kota, sedangkan sisinya merepresentasikan jalur perjalanan yang menghubungkan kota yang satu ke kota yang lain. Jika dimodelkan dalam graf, pernyataan berikut yang tepat adalah…

• Graf yang dibuat merupakan graf sederhana

• Graf yang dibuat memuat gelang

• Graf yang dibuat merupakan multigraf

• Graf yang dibuat pasti memuat simpul terpencil

• Sisi pada graf yang dibuat tidak harus berarah

Dalam sebuah graf berarah, derajat masuk (in-degree) suatu node adalah...

• Jumlah edge yang keluar dari node tersebut

• Jumlah edge yang masuk ke node tersebut

• Jumlah total edge yang terhubung dengan node tersebut

• Jumlah node yang terhubung dengan node tersebut

• Jumlah node yang terhubung dengan simpul

Apa yang dimaksud dengan graf berbobot?

• Graf yang memiliki bobot (nilai numerik) pada setiap edge-nya

• Graf yang memiliki bobot (nilai numerik) pada setiap node-nya

• Graf yang memiliki edge yang saling terhubung dengan bobot yang sama

• Graf yang tidak memiliki bobot pada edge atau node-nya

• Graf yan memiliki bobot pada edge

Kondisi berikut yang tidak mungkin terjadi terkait dengan banyak simpul dan derajatnya adalah…

• Graf A memiliki 7 simpul yang setiap simpulnya berderajat

• Graf B memiliki 11 simpul yang setiap simpulnya berderajat

• Graf C memiliki 10 simpul yang setiap simpulnya berderajat

• Jumlah derajat dari graf D adalah 0

• Banyak simpul dari graf E adalah 5

Misalkan graf G memiliki n ≥ 2 simpul yang semua simpulnya berderajat 0. Dari pernyataan tersebut, dapat kita katakan bahwa G merupakan…

• Graf trivial

• Graf bipartit lengkap

• Graf taksederhana

• Graf lengkap

• Graf beraturan

Suatu graf sederhana akan dibentuk dari 25 sisi. Tidak ada simpul terpencil pada graf tersebut. Jika n menyatakan banyak simpul pada graf tersebut, maka nilai maksimum dari n adalah….

• 1

• 25

• 26

• 50

• 51