| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén egy maximális független csúcshalmaz, maximális független ponthalmaz, maximális független halmaz (MFH) vagy maximális stabil halmaz (angol nyelvterületen: maximal independent set = MIS vagy maximal stable set) olyan független csúcshalmaz, ami nem valódi részhalmaza egyetlen független csúcshalmaznak sem. Más szavakkal, nincs olyan rajta kívül eső csúcs, amit a halmazhoz hozzá lehetne venni anélkül, hogy megszűnne független csúcshalmaznak lenni. Például a három csúcsú útgráf esetén, melyet az , és csúcsok, valamint az és élek alkotnak, mind a , mind az maximális független csúcshalmaz. Az halmaz független, de nem maximális, mivel valódi részhalmaza a nagyobb független csúcshalmaznak. Ugyanennek a gráfnak a maximális klikkjei az és halmazok. Egy MFH egyben a gráf is, és minden domináló halmaz, ami független, egyben maximális független is, ezért a maximális független halmazokat gyakran független domináló halmazoknak (independent dominating sets) is nevezik. Egy gráf nagyon különböző méretű MFH-kkal rendelkezhet; közülük a legnagyobb MFH-t vagy MFH-kat maximális elemszámú független csúcshalmaznak (maximum independent set) nevezzük. Az olyan gráfok, melyekben a maximális független csúcshalmazok mind azonos méretűek, a (well-covered graph). Két algoritmikus probléma köthető az MFH-khoz: , illetve az . (hu)
- A matematika, azon belül a gráfelmélet területén egy maximális független csúcshalmaz, maximális független ponthalmaz, maximális független halmaz (MFH) vagy maximális stabil halmaz (angol nyelvterületen: maximal independent set = MIS vagy maximal stable set) olyan független csúcshalmaz, ami nem valódi részhalmaza egyetlen független csúcshalmaznak sem. Más szavakkal, nincs olyan rajta kívül eső csúcs, amit a halmazhoz hozzá lehetne venni anélkül, hogy megszűnne független csúcshalmaznak lenni. Például a három csúcsú útgráf esetén, melyet az , és csúcsok, valamint az és élek alkotnak, mind a , mind az maximális független csúcshalmaz. Az halmaz független, de nem maximális, mivel valódi részhalmaza a nagyobb független csúcshalmaznak. Ugyanennek a gráfnak a maximális klikkjei az és halmazok. Egy MFH egyben a gráf is, és minden domináló halmaz, ami független, egyben maximális független is, ezért a maximális független halmazokat gyakran független domináló halmazoknak (independent dominating sets) is nevezik. Egy gráf nagyon különböző méretű MFH-kkal rendelkezhet; közülük a legnagyobb MFH-t vagy MFH-kat maximális elemszámú független csúcshalmaznak (maximum independent set) nevezzük. Az olyan gráfok, melyekben a maximális független csúcshalmazok mind azonos méretűek, a (well-covered graph). Két algoritmikus probléma köthető az MFH-khoz: , illetve az . (hu)
|
