Matematika Diskrit : Subgraf dan Komplemen

Subgraf

Misalkan G = (V,E) adalah sebuah graf.

G1 = (V1, E1) adalah subgraf dari G jika V1 โŠ† V dan E1 โŠ† E.

Beberapa hal yang dapat diturunkan dari definisi:

a. Sebuah titik dalam G merupakan subgraf G

b. Sebuah garis dalam G bersama-sama titik ujungnya merupakan subgraf G

c. Setiap graf merupakan subgraf dari dirinya sendiri.

d. Dalam subgraf berlaku sifat transitif : jika H adalah subgraf G dan G subgraf K, maka H adalah subgraf dari K


Subgraf Rentang (Spanning Subgraph)

Subgraf G1 = (V1, E1) dari G = (V, E) dikatakan subgraf rentang jika V1 =V (yaitu G1 mengandung semua simpul dari G).


Komplemen

Komplemen dari subgraf G1 terhadap graf G adalah graf G2 = (V2, E2) sedemikian sehingga E2 = E – E1 dan V2 adalah himpunan simpul yang anggota-anggota E2 bersisian dengannya.

Notasi komplemen dari suatu graf A โ†’ ฤ€

Komponen graf (connected component) adalah jumlah maksimum subgraf terhubung dalam graf G.

Graf G di bawah ini mempunyai 4 buah komponen:

Pada graf berarah, komponen terhubung kuat (strongly connected component) adalah jumlah maksimum subgraf yang terhubung kuat.

Graf di bawah ini mempunyai 2 buah komponen terhubung kuat:


Cut-Set

Cut-set dari graf terhubung G adalah himpunan sisi yang bila dibuang dari G menyebabkan G tidak terhubung. Jadi, cut-set selalu menghasilkan dua buah komponen.

Pada graf di bawah, {(1,2), (1,5), (3,5), (3,4)} adalah cut-set. Terdapat banyak cut-set pada sebuah graf terhubung.

Himpunan {(1,2), (2,5)} juga adalah cut-set, {(1,3), (1,5), (1,2)} adalah cut-set, {(2,6)} juga cut-set, tetapi {(1,2), (2,5), (4,5)} bukan cut-set sebab himpunan bagiannya, {(1,2), (2,5)} adalah cut-set.


Graf Berbobot (Weighted Graph)

Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga (bobot).


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