Himpunan bebas

Himpunan Bebas atau (bahasa inggris : Independent Set) dalam teori graf 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.