Himpunan bebas (teori graf)
Dalam teori graf, himpunan bebas () adalah serangkaian simpul (vertex) dalam graf, tanpa ada dua simpul di antaranya saling bertetangga. Dengan kata lain, ada himpunan yang berisi simpul-simpul, dan untuk setiap dua simpul dalam tidak ada sisi yang menghubungkan keduanya. Selain itu, setiap sisi dalam graf memiliki paling banyak satu simpul ujung yang berada di dalam . Suatu himpunan dapat dikatakan bebas jika dan hanya jika himpunan tersebut merupakan klika dalam komplemen graf tersebut.
Himpunan BEB maksimum
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
Sumber dan atribusi
Konten artikel ini diadaptasi dari Wikipedia bahasa Indonesia, revisi 29238256 (2026-05-17T04:03:56Z), yang tersedia berdasarkan lisensi Creative Commons Atribusi-BerbagiSerupa (CC BY-SA). Gambar pada artikel ini bersumber dari Wikimedia Commons dan mengikuti ketentuan lisensi masing-masing berkas. Mohon gunakan konten dan media secara bijak serta sesuai dengan ketentuan lisensi yang berlaku.