Független ponthalmaz probléma: Adott G gráf, keressünk meg egy maximális elemszámú független ponthalmazát.
Sokkal könnyebb az alábbi relaxált kérdésen gondolkozni: Adott G gráf, keressünk minál nagyobb elemszámú független ponthalmazt.
Független ponthalmazok
Ötlettár Megoldások
A független ponthalmazok fogalma analóg a független élhalmazok fogalmával, sőt még egyszerűbbnek is tűnik. Ennek ellenére sokkal nehezebben kezelhető és sokkal kevesebbet tudunk róla.
Független ponthalmaz: ha a ponthalmaz által feszített részgráf üres, vagyis ha a ponthalmaz semely két pontja között nem fut él, akkor a ponthalmazt függetlennek nevezzük ...
1 Független és lefogó halmazok
2 Lefogó és független ponthalmaz viszonya
2.1 Bizonyítás
3 Független és lefogó élhalmaz viszonya ...
 See also: Gráf, Teljes gráf, Halmaz, Definíció, Fokszám
  
|
RSS
