Himpunan bebas (teori graf): Perbedaan antara revisi
Konten dihapus Konten ditambahkan
Tidak ada ringkasan suntingan |
|||
| (29 revisi perantara oleh 13 pengguna tidak ditampilkan) | |||
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. -->
'''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)}}]]
▲
== Himpunan
[[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
* [[Vertex Cover]] (minimum) U Himpunan bebas = Himpunan hingga Simpul▼
* [[Vertex
== 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
▲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
=== Klaim
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
Dengan kondisi demikian, CLIQUE secara total merupakan kebalikan dari Himpinan Bebas (IS) dan CLIQUE (CL) membentuk graf
Langkah yang dilakukan untuk mendapatkan Himpunan bebas dari CLIQUE yaitu
▲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
* 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
* CL = U,V
{{Authority control}}
[[Kategori:Matematika]]
{{matematika-stub}}
| |||