Matematika Diskrit : Subgraf dan Komplemen

📋 Daftar Isi

Subgraf

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

G₁ = (V₁, E₁) adalah subgraf dari G jika V₁ ⊆ V dan E₁ ⊆ 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 G₁ = (V₁, E₁) dari G = (V, E) dikatakan subgraf rentang jika V₁ =V (yaitu G₁ mengandung semua simpul dari G).

Komplemen

Komplemen dari subgraf G₁ terhadap graf G adalah graf G₂ = (V₂, E₂) sedemikian sehingga E₂ = E – E₁ dan V₂ adalah himpunan simpul yang anggota-anggota E₂ 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.