Himpunan bebas (teori graf): Perbedaan antara revisi

Konten dihapus Konten ditambahkan

Sebaris

Revisi terkini sejak 14 Juli 2024 05.29

Dalam teori graf, himpunan bebas (bahasa Inggris: independent set) adalah serangkaian simpul (vertex) dalam graf, tidak ada dua yang berdekatan. Artinya, ada himpunan I dari simpul tersebut di mana untuk setiap dua simpul dalam I, tidak ada tepi yang menghubungkan keduanya. Hal ini Ekuivalen dengan pernyataan bahwa masing-masing sisi (edge) dalam grafik memiliki paling banyak satu titik akhir di I.

Himpunan BEB maksimum

Contoh (2) Graf Kubikal yang memiliki enam himpunan bebas maksimum yang ditandai dengan simpul berwarna merah.

Untuk mendapatkan himpunan bebas maksimum, mana digunakan pendekatan dengan Teorema untuk setiapp graf G (V,E) dengan Minimum Vertex Cover dan Himpunan set maksimum sedemikian:

Vertex cover (minimum) U Himpunan bebas = Himpunan hingga Simpul
Vertex cover (minimum) ∩ Maksimum Himpunan bebas = ø

Pengembangan

Dengan keberadaan himpunan bebas, dapat dicari korelasi dan kombinasi lainnya dari Graf yang secara langsung akan mengungkapkan temuan-temuan lain pada graf, hal ini di tuangkan pada klaim dan sejumlah teorema

Klaim VC = V - IS

Keberadaan Himpunan Bebas merumuskan sejumlah aturan lain sehubungan dengan komposisi graf yang diformulasikan sedemikian: VC = V - IS

VC = Vertex cover
V = Himpunan vertex
IS = Himpunan Bebas

Mengacu pada Graf pada contoh ke 3, jika didapati Himpunan Bebas = { 1,5,4,3} maka VC yang didapat berdasarkan aturan VC = C - IS adalah { 2,6}

Klaim IS U VC = V

Dengan diketahuinya Himpunan bebas maka akan diketahui pula Vertex Covernya dengan rumus: VC = V -IS Mengacu pada gambar graf ke tiga,ama jika didapati Himpunan bebas = { 1,5,4,3} maka vertex cover dihitung dari sisa jumlah vertex dikurangi Himpunan bebas sehingga didapat = {2,6}

CLIQUE

Clique adalah himpunan hingga Vertex CL ⊆ V di mana setiap pasang vertex U, V ∈ CL maka (U, V) ∈ E Dengan kondisi demikian, CLIQUE secara total merupakan kebalikan dari Himpinan Bebas (IS) dan CLIQUE (CL) membentuk graf komplet. Jadi jika CLIQUE pada graf diketahui, maka didapatkan himpunan bebasnya.

Langkah yang dilakukan untuk mendapatkan Himpunan bebas dari CLIQUE yaitu membuat graf komplemen G', di mana:

G' = (V',E')
V' = V
E' = {(U,V) | (U,V) bukan bagian dari E}

Dari graf yang menjadi aksen dari graf sebelumnya dapat disimbulkan sebuah Teorema: IS ⊆ V, CL ⊆ V, IS = CL berdasarkan Teorema tersebut dapat dibuktikan:

IS = U, V ∈ IS -> (U,V) bukan bagian dari E
CL = U,V ∈ CL -> (U,V) ∈ E

Artikel bertopik matematika ini adalah sebuah rintisan. Anda dapat membantu Wikipedia dengan mengembangkannya.

@@ Baris 1: / Baris 1: @@
+{{Tanpa referensi|date=Februari 2022}}{{Periksa terjemahan|en|Independent set (graph theory)}}{{Copy edit}}<!-- Catata: Bagian pembuka diterjemahkan kaku. Beberapa kalimat  ada yang diterjemahkan, dan sisanya tanpa menerjemahkan. -->
-[[Berkas:Graf_-_independent_set.jpg|thumb|right|]]
-'''Himpunan Bebas''' atau [[Independent Set]]  dalam teori grafik adalah  sebuah set independen atau set stabil adalah serangkaian simpul (vertex) dalam graf, tidak ada dua yang berdekatan. Artinya,ada  himpunan  I dari simpul tersebut dimana  untuk setiap dua simpul dalam I, tidak ada tepi yang menghubungkan keduanya. Hal ini Ekuivalen dengan  pernyataan bahwa masing-masing sisi (edge) dalam grafik memiliki paling banyak satu titik akhir di I.
+[[Berkas:Independent set graph.svg|jmpl|Sembilan verteks biru membentuk himpunan bebas maksimum, yaitu [[graf Petersen rampat]] {{Math|GP(12,4)}}]]
-Perhatikan gambar berikut ini yang menjelaskan simpul yang adalah Himpinan bebas dan yang bukan tergolong himpunan bebas :
+Dalam teori [[graf]], '''himpunan bebas''' ({{Lang-en|independent set}}) adalah serangkaian simpul (vertex) dalam graf, tidak ada dua yang berdekatan. Artinya, ada himpunan I dari simpul tersebut di mana untuk setiap dua simpul dalam I, tidak ada tepi yang menghubungkan keduanya. Hal ini Ekuivalen dengan pernyataan bahwa masing-masing sisi (edge) dalam grafik memiliki paling banyak satu titik akhir di I.
-Berdasarkan komposisi graf diatas jika dipilih Himpunan Bebas = { c } maka yang bukan termasuk Himpunan bebas = { b, e, d}
-== Himpunan Set maksimum ==
+== Himpunan BEB maksimum ==
+[[Berkas:Cube-maximal-independence.svg|jmpl|ka| Contoh (2) Graf Kubikal yang memiliki enam himpunan bebas maksimum yang ditandai dengan simpul berwarna merah.]]
-Untuk mendapatkan himpunan bebas maksimum, mana digunakan pendekatan dengan Teorema untuk setiapp graf G (V,E) dengan Minimum [[Vertex Cover]] dan Himpunan set maksimum sedemikian :
+Untuk mendapatkan himpunan bebas maksimum, mana digunakan pendekatan dengan Teorema untuk setiapp graf G (V,E) dengan Minimum [[Vertex Cover]] dan Himpunan set maksimum sedemikian:
-* [[Vertex Cover]] (minimum)  U  Himpunan bebas = Himpunan hingga Simpul
-* [[Vertex Cover]] (minimum)  ∩ Maksimum Himpunan bebas = ø
+* [[Vertex cover]] (minimum) U Himpunan bebas = Himpunan hingga Simpul
+* [[Vertex cover]] (minimum) ∩ Maksimum Himpunan bebas = ø
 == Pengembangan ==
 Dengan keberadaan himpunan bebas, dapat dicari korelasi dan kombinasi lainnya dari Graf yang secara langsung akan mengungkapkan temuan-temuan lain pada graf, hal ini di tuangkan pada klaim dan sejumlah teorema
-=== Klaim VC = V - IS===
+=== Klaim VC = V - IS ===
+Keberadaan Himpunan Bebas merumuskan sejumlah aturan lain sehubungan dengan komposisi graf yang diformulasikan sedemikian: '''VC = V - IS'''
-[[Berkas:Graf - independent set vc.jpg|thumb|right|graf]]
+* VC = [[Vertex cover]]
-Keberadaan Himpunan Bebas merumuskan sejumlah aturan lain sehubungan dengan komposisi graf yang diformulasikan sedemikian : '''VC = V - IS'''
+* V = Himpunan vertex
-* VC = [[Vertex Cover]]
-* V  = Himpunan vertex
 * IS = Himpunan Bebas
-Mengacu pada Graf diatas, jika didapati Himpunan Bebas = { 1,5,4,3} maka VC yang didapat berdasarkan aturan VC = C - IS adalah { 2,6}
+Mengacu pada Graf pada contoh ke 3, jika didapati Himpunan Bebas = { 1,5,4,3} maka VC yang didapat berdasarkan aturan VC = C - IS adalah { 2,6}
-=== Klaim VI U VC ===
+=== Klaim IS U VC = V ===
+Dengan diketahuinya Himpunan bebas maka akan diketahui pula Vertex Covernya dengan rumus: VC = V -IS
+Mengacu pada gambar graf ke tiga,ama jika didapati Himpunan bebas = { 1,5,4,3} maka vertex cover dihitung dari sisa jumlah vertex dikurangi Himpunan bebas sehingga didapat = {2,6}
 === CLIQUE ===
+Clique adalah himpunan hingga Vertex CL ⊆ V di mana setiap pasang vertex U, V ∈ CL maka (U, V) ∈ E
+Dengan kondisi demikian, CLIQUE secara total merupakan kebalikan dari Himpinan Bebas (IS) dan CLIQUE (CL) membentuk graf komplet. Jadi jika CLIQUE pada graf diketahui, maka didapatkan himpunan bebasnya.
+Langkah yang dilakukan untuk mendapatkan Himpunan bebas dari CLIQUE yaitu membuat graf komplemen G', di mana:
-Clique adalah himpunan hingga Vertex CL ⊆ V dimana setiap pasang vertex U, V ε CL maka ( U,V) ε E
-Dengan kondisi demikian, CLIQUE secara total merupakan kebalikan dari Himpinan Bebas (IS) dan CLIQUE (CL) membentuk graf komplit. Jadi jika kita mengetahui CLIQUE pada graf, maka akan pula kita dapatkan himpunan bebasnya
-Langkah yang dilakukan untuk mendapatkan Himpunan bebas dari CLIQUE yaitu : Buat graf komplemen G' dimana :
 * G' = (V',E')
-V' = V
+* V' = V
-E' = {(U,V) | (U,V) bukan bagian dari E}
+* E' = {(U,V) | (U,V) bukan bagian dari E}
-Dari graf yang menjadi aksen dari graf sebelumnya dapat disimbulkan sebuah Teorema :
+Dari graf yang menjadi aksen dari graf sebelumnya dapat disimbulkan sebuah Teorema:
 IS ⊆ V, CL ⊆ V, IS = CL
-berdasarkan Teorema tersebut dapat dibuktikan :
+berdasarkan Teorema tersebut dapat dibuktikan:
-* IS = U, V ε IS -> (U,V) bukan bagian dari E
+* IS = U, V ∈ IS -> (U,V) bukan bagian dari E
-* CL = U,V ε CL -> (U,V) ε E
+* CL = U,V ∈ CL -> (U,V) ∈ E
+{{Authority control}}
+[[Kategori:Matematika]]
+{{matematika-stub}}
-[[cs:Nezávislá množina]]
-[[de:Glossar Graphentheorie#Stabile Menge]]
-[[en:Independent set (graph theory)]]
-[[es:Conjunto independiente]]
-[[fa:مجموعه مستقل]]
-[[fr:Stable (théorie des graphes)]]
-[[ko:독립집합]]
-[[he:קבוצה בלתי תלויה (תורת הגרפים)]]
-[[ja:独立集合]]
-[[pl:Zbiór niezależny]]
-[[pt:Conjunto independente]]
-[[ru:Задача о независимом множестве]]
-[[sv:Oberoende mängd]]
-[[th:เซตอิสระ]]
-[[tr:Bağımsız küme problemi]]