Kuis 1 Teori Graf

Contoh model graf sederhana yang memuat simpul berderajat 1 adalah

• 
• 
• 
• 
• 

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

• b

• d

• e

• g

• h

Perhatikan model graf berikut. Misalkan m dan n berturut-turut menyatakan banyak simpul dan sisi pada graf di atas. Nilai dari 2m+n adalah (a)   (jawab dengan angka, contoh 22)

Pernyataan yang benar terkait graf ini adalah

• 1. Simpul v1 bertetangga dengan v2

• 1. Simpul v4 bertetangga dengan v2 dan v5

• 1. Simpul v2 merupakan simpul terpencil

• 1. Graf tersebut bukan graf sederhana

• 1. Derajat dari v5 adalah deg(v5)=2

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

• 1. Graf yang dibuat merupakan graf sederhana

• 1. Graf yang dibuat memuat gelang

• 1. Graf yang dibuat merupakan multigraf

• 1. Graf yang dibuat pasti memuat simpul terpencil

• 1. Sisi pada graf yang dibuat tidak harus berarah

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

• 1. Graf A memiliki 7 simpul yang setiap simpulnya berderajat 3

• 1. Graf B memiliki 11 simpul yang setiap simpulnya berderajat 2

• 1. Graf C memiliki 10 simpul yang setiap simpulnya berderajat 5

• 1. Jumlah derajat dari graf D adalah 0

• 1. 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 ... (jawab dengan angka)

(a)  

Sebanyak n unit komputer akan dihubungkan dengan sejumlah potongan kabel, baik secara langsung ataupun terhubung melalui komputer lainnya. Banyak potongan kabel minimum yang dibutuhkan adalah ⋯ potongan.

• n+1

• n

• n-1

• 2n

• n-2

Banyak sisi pada graf bipartit lengkap K_10,15 adalah ... (jawab dengan angka)

(a)