Kuis Teori Graf part 1

Awal mula teori graf dikaitkan dengan permasalahan yang diajukan oleh Leonhard Euler pada abad ke-18. Permasalahan tersebut dikenal dengan nama Jembatan Königsberg. Tujuan utama dari permasalahan ini adalah...

• Menentukan jarak terpendek antara dua kota di Prusia Timur

• Menemukan lintasan yang melalui semua jembatan tepat satu kali

• Menghitung banyaknya kombinasi lintasan di seluruh kota Königsberg

• Membuat model jaringan transportasi yang paling efisien

• Membedakan antara graf terhubung dan graf tidak terhubung

Pernyataan berikut yang paling tepat menggambarkan definisi graf adalah...

• Graf adalah struktur data linear yang terdiri dari simpul-simpul berarah.

• Graf adalah representasi fungsi matematis yang memetakan titik-titik dalam bidang koordinat.

• Graf adalah diagram batang atau garis yang menunjukkan hubungan antar data numerik.

• Graf adalah pohon biner dengan simpul-simpul yang saling terhubung satu arah.

Sebuah jaringan komputer yang memiliki hubungan komunikasi dua arah antara setiap pasang komputer dapat dimodelkan sebagai...

• Graf berarah sederhana

• Graf tak berarah lengkap

• Graf teratur berderajat 1

• Pohon biner berakar

• Graf sirkuit Hamilton

Graf yang semua sisinya memiliki arah tertentu disebut sebagai...

• Graf sederhana

• Graf terhubung

• Graf berarah (directed graph)

• Graf tak berarah (undirected graph)

• Graf lengkap

Graf yang tidak memiliki sisi ganda maupun gelang disebut...

• Multigraf

• Graf sederhana

• Graf berarah

• Graf beraturan

• Graf terhubung

Diketahui sebuah graf tak berarah dengan 5 simpul dan 6 sisi. Jumlah seluruh derajat simpul pada graf tersebut adalah...

• 6

• 10

• 12

• 15

• 24

Manakah pernyataan berikut yang benar?

• Dalam graf tak berarah, setiap sisi direpresentasikan sebagai pasangan berurutan.

• Dalam graf berarah, derajat masuk dan derajat keluar setiap simpul selalu sama.

• Dalam graf tak berarah, arah sisi tidak diperhatikan.

• Graf berarah tidak dapat memiliki gelang.

• Graf tak berarah tidak dapat direpresentasikan dalam bentuk matriks.

Dalam media sosial, hubungan pertemanan antar pengguna yang saling mengikuti (mutual) dapat dimodelkan sebagai...

• Graf berarah

• Graf tak berarah

• Multigraf

• Pohon berakar

• Graf berbobot

Pernyataan berikut yang paling tepat menjelaskan mengapa permasalahan Jembatan Königsberg dianggap sebagai awal teori graf adalah...

• Karena Euler menggunakan konsep aljabar untuk menghitung jumlah jembatan

• Karena Euler memodelkan permasalahan dunia nyata dalam bentuk titik dan garis yang mewakili struktur hubungan

• Karena Euler menemukan algoritma untuk mencari rute terpendek

• Karena graf yang digunakan Euler bersifat berarah dan berbobot

• Karena Euler menggambarkan semua kemungkinan lintasan dalam bentuk tabel

Manakah pernyataan berikut yang tidak sesuai dengan definisi graf G = (V, E)?

• Setiap elemen dalam V disebut simpul atau verteks.

• Setiap elemen dalam E merupakan pasangan simpul.

• Dua simpul dapat dihubungkan oleh lebih dari satu sisi pada graf sederhana.

• Himpunan V tidak boleh kosong.

• Himpunan E dapat kosong.