Artikel atau sebagian dari artikel ini mungkin diterjemahkan dari Independent set (graph theory) di en.wikipedia.org. Isinya masih belum akurat, karena bagian yang diterjemahkan masih perlu diperhalus dan disempurnakan. Jika Anda menguasai bahasa aslinya, harap pertimbangkan untuk menelusuri referensinya dan menyempurnakan terjemahan ini. Anda juga dapat ikut bergotong royong pada ProyekWiki Perbaikan Terjemahan.
(Pesan ini dapat dihapus jika terjemahan dirasa sudah cukup tepat. Lihat pula: panduan penerjemahan artikel)
Artikel ini membutuhkan penyuntingan lebih lanjut mengenai tata bahasa, gaya penulisan, hubungan antarparagraf, nada penulisan, atau ejaan. Anda dapat membantu untuk menyuntingnya.
Sembilan verteks biru membentuk himpunan bebas maksimum, yaitu graf Petersen rampatGP(12,4)
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
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:
