Graf tak berarah

Graf Tak Berarah dan Graf Berarah

​

Komplemen Graf

Multiple Choice

Sisi pada $$\overline{G}$$ merupakan komplemen sisi pada G terhadap ...

• graf teratur

• graf lingkaran

• graf lengkap

• graf bipartit

Multiple Choice

Komplemen dari graph di samping adalah ...

Graf Bagian/Sub Graf

Multiple Choice

Terdapat dua buah graf yaitu graf G dan graf H. Pernyataan berikut yang dapat menggambarkan kedua graf adalah ...

• graf H merupakan graf bagian dari graf G

• graf H bukan merupakan graf bagian dari graf G

• Graf G dan graf H saling bertolak belakang

• Graf G bukan merupakan graf bagian dari graf H

Multiple Choice

Banyak graf bagian yang dapat dibuat dari graf tersebut adalah ...

• 4

• 5

• 6

• 7

Derajat

Misalkan V adalah suatu titik dalam graf G. Derajat titik V adalah jumlah sisi yang berhubungan dengan titik v dan loop dihitung 2 kali.

Simbol dari derajat titik V adalah d(v).

Derajat total G adalah jumlah derajat semua titik dalam G.

Jumlah derajat semua simpul pada suatu graf adalah genap, yaitu dua kali jumlah sisi pada graph tersebut.

Multiple Choice

Derajat dari titik q adalah ...

• 1

• 2

• 3

• 4

Multiple Choice

Jumlah derajat semua simpul pada suatu graf selalu ...

• ganjil

• genap

• kadang genap kadang ganjil

• sama

Walk, Path, Sirkuit

Misalkan G adalah suatu graf. Misalkan pula v dan w adalah 2 titik dalam G.

Suatu walk dari v ke w adalah barisan titik-titik berhubungan dan garis secara berselang-seling, diawali dari titik v dan diakhiri pada titik w.

Path dengan panjang n dari v ke w adalah walk dari v ke w yang semua garisnya berbeda.

Path sederhana dengan panjang n dari v ke w adalah path dari v ke w yang semua titiknya berbeda.

Sirkuit dengan panjang n adalah path yang dimulai dan diakhiri pada titik yang sama.

Sirkuit sederhana dengan panjang n adalah sirkuit yang semua titiknya berbeda.

Multiple Choice

Rute v1 e1 v2 e3 v3 e4 v3 e5 v4 pada gambar graf di atas merupakan ...

• walk

• path

• path sederhana

• sirkuit

Multiple Choice

Suatu rute yang diawali dan diakhir dengan titik yang sama disebut ...

• walk

• path

• derajat

• sirkuit

Graf Terhubung

G disebut graph terhubung jika untuk setiap pasang simpul v_i dan v_j dalam himpunan V terdapat lintasan (path) dari v_i ke v_j.

Jika tidak, maka G disebut graph tak-terhubung.

Derajat pada Graf Berarah

Multiple Choice

Derajat masuk titik V3 pada gambar graf terdapat ... buah

• 1

• 2

• 3

• 4

Multiple Choice

Jumlah derajat keluar semua titik pada graf tersebut adalah ...

• 4

• 5

• 6

• 7

WALK BERARAH, PATH BERARAH DAN SIRKUIT BERARAH

Pengertian walk, path dan sirkuit dalam graf berarah sama dengan pengertian dalam graf tak berarah. Hanya saja dalam graf berarah suatu perjalanan harus mengikuti arah sisi.

Suatu graf berarah yang tidak memuat sirkuit berarah disebut Asiklik.

Multiple Choice

Banyak path berarah yang dapat dibuat dari v1 ke v6 adalah ....

• 1

• 2

• 3

• 4

Multiple Choice

Manakah yang merupakan path berarah terpanjang dari v5 ke v2 berikut ini ....

• v5-v1-v2

• v5-v6-v2

• v5-v1-v3-v7-v8-v6-v2

• v5-v1-v3-v4-v2

Graf Berarah Terhubung

Suatu graf tak berarah dikatakan terhubung jika ada path yang menghubungkan tiap 2 titiknya. Pengertian itupun berlaku untuk graf berarah. Berdasarkan arah sisinya, dalam graf berarah dikenal 2 jenis keterhubungan, yaitu terhubung kuat dan terhubung lemah.

Misalkan G adalah suatu graph berarah dan v,w adalah sembarang 2 titik dalam G.

G disebut terhubung kuat jika ada path berarah dari v ke w. Dimana dapat dibuat path dari titik awal menuju ke semua titik.

G disebut terhubung lemah jika G tida terhubung kuat.

Multiple Choice

Graf berikut merupakan termasuk ke dalam graf terhubung ....

• kuat

• lemah

Multiple Choice

Suatu graf dikatakan terhubung kuat jika terdapat .... dari titik v ke titik w

• walk berarah

• path berarah

• sirkuit berarah

• derajat