Himpunan bebas (teori graf)

Berkas:Graf - independent set.jpg 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.

Perhatikan gambar berikut ini yang menjelaskan simpul yang adalah Himpinan bebas dan yang bukan tergolong himpunan bebas : Berdasarkan komposisi graf diatas jika dipilih Himpunan Bebas = { c } maka yang bukan termasuk Himpunan bebas = { b, e, d}

Pengembangan

Berkas:Graf - independent set vc.jpg 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 diatas, jika didapati Himpunan Bebas = { 1,5,4,3} maka VC yang didapat berdasarkan aturan VC = C - IS adalah { 2,6}