CUT SETS DAN CUT VERTEX

Oleh :Sri Widaningsih, MT

Pada bagian ini akan dijelaskan mengenai :Cut sets (himpunan-potong)Edge connectivity (keterhubungan

/konektivitas sisi)Vertex connectivity (keterhubungan

/konektivitas simpul)Separable graph (graph yang dapat

dipisahkan)Cut-vertex (simpul-potong)

Cut-SetsDEFINISICut set dari graf terhubung G adalah

himpunan sisi yang bila dibuang menyebabkan G tidak terhubung.

Cut-set adalah himpunan sisi minimal dalam graf terhubung dimana pengahapusan sisi mengurangi rank graf sebanyak satu.

Cut-set adalah jumlah minimal sisi-sisi yang dihapus dari G yang menghilangkan semua lintasan antara dua himpunan simpul

Cut set selalu menghasilkan dua buah komponen terhubung

Nama lain cut set adalah jembatan (bridge)Jembatan adalah himpunan sisi yang jika

dihapuskan akan menyebabakan graf tidak terhubung (disconnect).

Dalam cut-set tidak boleh mengandung himpunan bagian yang juga cut-set.

Setiap sisi graf pohon merupakan cut-set

G1 G2 G3

G4Grafik G1 dapat dibagi menjadi dua komponen dengan

menghapus salah satu ujung bc atau bd. Oleh karena itu, sisi bc atau bd adalah jembatan.

Grafik G2 di atas dapat diputuskan dengan menghapus tepi tunggal, cd. Oleh karena itu, sisi cd adalah jembatan

Grafik G3 di atas tidak dapat diputuskan dengan menghapus sisi tunggal, tetapi harus menghapus dua sisi (ac dan bc)

 Grafik G4 di atas dapat diputus dengan menghapus dua sisi seperti ac dan dc.

Himpunan sisi {a,c,d,f} adalah cut-set.Cut-set lainnya {a,b,g}, {a,b,e,f}, {a,c,h} dan {h,d,f}Himpunan sisi {a,c,h.d} bukan merupakan cut set

karena {a,c,h} adalah cut set.Rank pada gbr (a) adalah 5 sedangkan pada (b)

adalah 4.Cut-set (a,c,d,f} menghubungkan himpunan simpul

{1,2,6} dengan (3,4,5}.

Pada graf di atas, {(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.

1

3 4

5

2

6

21

3

5

4

6

Sifat-sifat Cut-SetBeberapa sifat (properties) cut-set :Setiap cut-set di dalam graf terhubung, pasti

mengandung sedikitnya satu cabang untuk setiap spanning tree dari G

Penghapusan semua sisi dalam S akan membuat graf G tidak terhubung

Penghapusan beberapa (tetapi tidak semua) sisi S tidak akan membuat graf tidak terhubung G.

Lihat spanning tree yang dibentuk dari {h,f,g,e,d,b,a,c} maka mengandung minimal satu anggota cut set yaitu bd

Kita dapat memutuskan G dengan menghapus tiga tepi bd, be, dan ce, tapi kita tidak bisa memutuskan dengan menghapus hanya dua sisi. 

Edge ConnectivityKonektivitas sisi dari suatu graf terhubung G

adalah jumlah minimum sisi yang dihapuskan untuk memutus G.

Konektivitas sisi dari suatu graf pohon adalah 1.

G1  dan G2 memiliki konektivitas sisi 1.G3 dan G4 memiliki konektivitas sisi 2.

G1 G2 G3 G4

Vertex ConnectivityKonektivitas simpul dari suatu graf terhubung G

adalah jumlah minimum simpul yang dihapuskan untuk memutus G.

G1 G2 G3 G4

Grafik G1 dapat diputus dengan penghilangan simpul tunggal (baik b atau c). G memiliki konektivitas 1.

Graf G2 dapat diputus dengan penghilangan simpul tunggal (baik c atau d). Simpul c atau d adalah cut-vertex. G2 memiliki konektivitas 1.

 Graf G3 dapat diputus dengan menghapus hanya satu yaitu simpul  c. Simpul c adalah cut-vertex. G3 memiliki konektivitas 1.

 Graf G4 tidak dapat diputuskan dengan menghapus satu simpul tunggal, tetapi penghapusan dilakukan pada dua simpul tidak bertetangga (seperti b dan c). G4 memiliki konektivitas 2.

Separable Graph & Cut VertexGraf G disebut separable jika memiliki

konektivitas simpul sebesar 1.Semua graf terhubung yang lain disebut

sebagai nonseparable.Di dalam separable graph, sebuah simpul

yang dihapus dan membuat graf G tidak terhubung disebut cut-vertex

Sehingga cut-vertex adalah sebuah simpul yang apabila dihapuskan akan membuat graf G tidak terhubung.

Graf G dikatakan k-connected jika konektivitas G adalah k,sehingga 1-connected graf sama dengan separable graph

Kedua gambar di atas adalah separable graph dan memiliki konektivitas simpul sebesar 1.

Pada gbr (a) 4 adalah cut-vertex Pada gbr (b) v adalah cut-vertex

Vertex-Cut SetVertex-cut set dari sebuah graf G adalah himpunan

simpul S dengan sifat sebagai berikut :Penghapusan semua simpul pada S akan menyebabkan G

tidak terhubungPengahapusan beberapa (tidak semua) simpul di S tidak

akan menyebabkan G tidak tak terhubung.Kita dapat memutus grafik dengan menghapus dua

simpul b dan e, tapi kita tidak bisa lepaskan dengan hanya menghapus satu simpul. Vertex-cutset dari G adalah {b, e}.

Perbandingan KonektivitasKonektivitas sisi graf G tidak dapat melebihi derajat

simpul yang memiliki derajat terkecil graf GKonektivitas simpul dari graf G tidak dapat

melebihi konektivitas sisi graf G.Jika :

δ (G) adalah derajat terkecil suatu simpul dalam graf G

λ (G) adalah konektivitas sisiK(G) adalah konektivitas simpul,

maka :K (G) ≤ λ (G) ≤ δ (G)

K(G)=1, λ(G) = 3, and δ(G) = 3.K (G) ≤ λ (G) ≤ δ (G)

K(G)=1, λ(G) = 2, and δ(G) = 3.K (G) ≤ λ (G) ≤ δ (G)

Cut-set berperan besar dalam jaringan komunikasi dan transportasi.

Misalkan keenam simpul pada gambar di bawah adalah enam kota yang dihubungkan dengan saluran telepon (sisi). Kita ingin menemukan apakah terdapat titik-titik lemah dalam jaringan yang memerlukan penguatan dengan alat saluran tambahan. Cut-set dengan jumlah sisi paling sedikit (edge connectivity) adalah saluran yang mudah diserang