Matematika Diskrit : Terminologi Graf

Ketetanggan (Adjacent)

Dua buah simpul dikatakan bertetangga bila keduanya terhubung langsung.

Tinjau graf G1 :

  • Simpul 1 bertetangga dengan simpul 2 dan 3
  • Simpul 1 tidak bertetangga dengan simpul 4

Bersisian (Incidency)

Untuk sembarang sisi e = (vj, vk) dikatakan :

  • e bersisian dengan simpul vj
  • e bersisian dengan simpul vk

Tinjau graf G1:

  • Sisi (2, 3) bersisian dengan simpul 2 dan simpul 3
  • Sisi (2, 4) bersisian dengan simpul 2 dan simpul 4
  • Tetapi sisi (1, 2) tidak bersisian dengan simpul 4.

Simpul Terpencil (Isolated Vertex)

Simpul terpencil ialah simpul yang tidak mempunyai sisi yang bersisian dengannya.

Tinjau graf G3:

  • Simpul 5 adalah simpul terpencil.

Graf Kosong (Null graph atau Empty graph)

Graf yang himpunan sisinya merupakan himpunan kosong (Nn).

Graf N5 :


Derajat (Degree)

Derajat suatu simpul adalah jumlah sisi yang bersisian dengan simpul tersebut.

Notasi: d(v)

Tinjau graf G1:

  • d(1) = d(4) = 2
  • d(2) = d(3) = 3

Tinjau graf G2:

  • d(1) = 3 โ†’ bersisian dengan sisi ganda
  • d(3) = 4 โ†’ bersisian dengan sisi gelang (loop)

Tinjau graf G3:

  • d(5) = 0 โ†’ simpul terpencil
  • d(4) = 1 โ†’ simpul anting-anting (pendant vertex)

Pada graf berarah,

din(v) = derajat-masuk (in-degree)

= jumlah busur yang masuk ke simpul v

dout(v) = derajat-keluar (out-degree)

= jumlah busur yang keluar dari simpul v

d(v) = din(v) + dout(v)

Tinjau graf G4:

din(1) = 2; dout(1) = 1

din(2) = 2; dout(2) = 3

din(3) = 2; dout(3) = 1

din(4) = 1; dout(3) = 2


Lemma Jabat Tangan

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

Dengan kata lain, jika G = (V, E), maka

\[ \sum_{v=V}d(v)=2|E| \]


Tinjau graf G1: d(1) + d(2) + d(3) + d(4) = 2 + 3 + 3 + 2 = 10 = 2 ร— jumlah sisi = 2 ร— 5

Tinjau graf G2: d(1) + d(2) + d(3) = 3 + 3 + 4 = 10 = 2 ร— jumlah sisi = 2 ร— 5

Tinjau graf G3: d(1) + d(2) + d(3) + d(4) + d(5) = 2 + 2 + 3 + 1 + 0 = 8 = 2 ร— jumlah sisi = 2 ร— 4

Akibat dari lemma (corollary):

Untuk sembarang graf G, banyaknya simpul berderajat ganjil selalu genap

Contoh

Diketahui graf dengan lima buah simpul. Dapatkah kita menggambar graf tersebut jika derajat masing-masing simpul adalah:

  1. 2, 3, 1, 1, 2
  2. 2, 3, 3, 4, 4

Penyelesaian:

  1. Tidak dapat, karena jumlah derajat semua simpulnya ganjil (2 + 3 + 1 + 1 + 2 = 9).
  2. Dapat, karena jumlah derajat semua simpulnya genap (2 + 3 + 3 + 4 + 4 = 16).

Lintasan (Path)

Lintasan yang panjangnya n dari simpul awal v0 ke simpul tujuan vn di dalam graf G ialah barisan berselang-seling simpul-simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2, v2,โ€ฆ , vn โ€“1, en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2), โ€ฆ , en = (vn-1, vn) adalah sisi-sisi dari graf G.

Tinjau graf G1:

  • Lintasan 1, 2, 4, 3 adalah lintasan dengan barisan sisi (1,2), (2,4), (4,3).

Panjang lintasan adalah jumlah sisi dalam lintasan tersebut. Lintasan 1, 2, 4, 3 pada G1memiliki panjang 3.


Siklus (Cycle) atau Sirkuit (Circuit)

Lintasan yang berawal dan berakhir pada simpul yang sama disebut sirkuit atau siklus.

Tinjau graf G1:

  • 1, 2, 3, 1 adalah sebuah sirkuit.

Panjang sirkuit adalah jumlah sisi dalam sirkuit tersebut. Sirkuit 1, 2, 3, 1 pada G1 memiliki panjang 3.


Terhubung (Connected)

Dua buah simpul v1 dan simpul v2 disebut terhubung jika terdapat lintasan dari v1 ke v2.

G disebut graf terhubung (connected graph) jika untuk setiap pasang simpul vi dan vj dalam himpunan V terdapat lintasan dari vi ke vj.

Jika tidak, maka G disebut graf tak-terhubung (disconnected graph).

Contoh graf tak-terhubung:

Graf berarah G dikatakan terhubung jika graf tidak berarahnya terhubung (graf tidak berarah dari G diperoleh dengan menghilangkan arahnya).

Dua simpul, u dan v, pada graf berarah G disebut terhubung kuat (strongly connected) jika terdapat lintasan berarah dari u ke v dan juga lintasan berarah dari v ke u.

Jika u dan v tidak terhubung kuat tetapi terhubung pada graf tidak berarahnya, maka u dan v dikatakan terhubung lemah (weakly coonected).

Graf berarah G disebut graf terhubung kuat (strongly connected graph) apabila untuk setiap pasang simpul sembarang u dan v di G, terhubung kuat. Kalau tidak, G disebut graf terhubung lemah.


Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Graf, daftar lengkapnya adalah sebagai berikut.


Tonton juga video pilihan dari kami berikut ini

Bagikan ke teman-teman Anda

Contact Us

How to whitelist website on AdBlocker?

How to whitelist website on AdBlocker?

  1. 1 Click on the AdBlock Plus icon on the top right corner of your browser
  2. 2 Click on "Enabled on this site" from the AdBlock Plus option
  3. 3 Refresh the page and start browsing the site
error: Content is protected !!
Up