| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén egy független csúcshalmaz, független ponthalmaz, független halmaz (independent set) vagy stabil halmaz (stable set) egy gráf olyan csúcsainak halmaza, melyek közül semelyik kettő sem szomszédos egymással. Tehát a csúcsok olyan S halmaza, hogy bármelyik két S-beli csúcsot tekintve állítható, hogy nincs közöttük él. Ezzel ekvivalens állítás, hogy a gráf minden élének pontosan egy végpontja található S-ben. A független halmaz méretén az azt alkotó csúcsok számát értjük. A független halmazokat nevezik belsőleg stabil halmazoknak (internally stable sets) is. Egy maximális független halmaz (maximal independent set) olyan halmaz, melyhez vagy bármely csúcsot hozzáadva biztosan tartalmazni fog egy élet is, vagy az üres gráf összes csúcsát tartalmazza. Egy adott G gráfhoz tartozó maximális független halmazok nevükkel ellentétben nagyon különböző méretűek lehetnek. A maximális független halmazok közül a maximális elemszámú független halmaz az adott G gráfhoz tartozó legnagyobb lehetséges méretű halmaz. Ezt a méretet nevezik G függetlenségi számának (independence number), jelölése α(G). Az ilyen halmaz előállításának a problémája, a maximális elemszámú független csúcshalmaz-probléma (maximum independent set problem) optimalizálási feladat. Így hát valószínűtlen, hogy létezik hatékony algoritmus egy gráf maximális elemszámú független csúcshalmazának meghatározására. A maximális elemszámú független csúcshalmazok (maximum independent set) minden esetben maximális független csúcshalmazok is (maximal independent set), az állítás megfordítása azonban nem áll fenn. (hu)
- A matematika, azon belül a gráfelmélet területén egy független csúcshalmaz, független ponthalmaz, független halmaz (independent set) vagy stabil halmaz (stable set) egy gráf olyan csúcsainak halmaza, melyek közül semelyik kettő sem szomszédos egymással. Tehát a csúcsok olyan S halmaza, hogy bármelyik két S-beli csúcsot tekintve állítható, hogy nincs közöttük él. Ezzel ekvivalens állítás, hogy a gráf minden élének pontosan egy végpontja található S-ben. A független halmaz méretén az azt alkotó csúcsok számát értjük. A független halmazokat nevezik belsőleg stabil halmazoknak (internally stable sets) is. Egy maximális független halmaz (maximal independent set) olyan halmaz, melyhez vagy bármely csúcsot hozzáadva biztosan tartalmazni fog egy élet is, vagy az üres gráf összes csúcsát tartalmazza. Egy adott G gráfhoz tartozó maximális független halmazok nevükkel ellentétben nagyon különböző méretűek lehetnek. A maximális független halmazok közül a maximális elemszámú független halmaz az adott G gráfhoz tartozó legnagyobb lehetséges méretű halmaz. Ezt a méretet nevezik G függetlenségi számának (independence number), jelölése α(G). Az ilyen halmaz előállításának a problémája, a maximális elemszámú független csúcshalmaz-probléma (maximum independent set problem) optimalizálási feladat. Így hát valószínűtlen, hogy létezik hatékony algoritmus egy gráf maximális elemszámú független csúcshalmazának meghatározására. A maximális elemszámú független csúcshalmazok (maximum independent set) minden esetben maximális független csúcshalmazok is (maximal independent set), az állítás megfordítása azonban nem áll fenn. (hu)
|
