Himpunan bebas (teori graf): Perbedaan antara revisi
Tidak ada ringkasan suntingan |
Tidak ada ringkasan suntingan |
||
| Baris 1: | Baris 1: | ||
[[Berkas:Graf_-_independent_set.jpg]] |
[[Berkas:Graf_-_independent_set.jpg|thumb|right|]] |
||
'''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. |
'''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. |
||
| Baris 6: | Baris 6: | ||
== Pengembangan == |
== Pengembangan == |
||
[[Berkas:Graf - independent set vc.jpg]] |
[[Berkas:Graf - independent set vc.jpg|thumb|right|]] |
||
Keberadaan Himpunan Bebas merumuskan sejumlah aturan lain sehubungan dengan komposisi graf yang diformulasikan sedemikian : '''VC = V - IS''' |
Keberadaan Himpunan Bebas merumuskan sejumlah aturan lain sehubungan dengan komposisi graf yang diformulasikan sedemikian : '''VC = V - IS''' |
||
* VC = [[Vertex Cover]] |
* VC = [[Vertex Cover]] |
||
Revisi per 25 April 2012 08.58
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
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}