| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén a karommentes gráf (claw-free graph) olyan gráf, mely nem tartalmazza a karomgráfot feszített részgráfként. A karom a K1,3 teljes páros gráf másik neve (tehát arról a csillaggráfról van szó, ami három éllel, három levéllel és egy csomóponttal rendelkezik). Egy karommentes gráf onnan ismerszik meg, hogy egyetlen feszített részgráfja sem karom; tehát semelyik négy csúcspontja között nincs ilyen módon csatlakozó három él. Ezzel egyenértékű megfogalmazás, hogy a karommentes gráf olyan gráf, melyben bármely csúcs szomszédsága egy háromszögmentes gráf komplementere. A karommentes gráfokat eredetileg az élgráfok általánosításaként vizsgálták, de három fő felfedezést tettek velük kapcsolatban, melyek indokolták a további vizsgálódást: hogy bármely páros rendű karommentes összefüggő gráf rendelkezik teljes párosítással; a karommentes gráfok független csúcshalmazait megtaláló algoritmusok felfedezése; a karommentes perfekt gráfok karakterizációja. Több száz matematikai tanulmány és áttekintő munka foglalkozik velük. (hu)
- A matematika, azon belül a gráfelmélet területén a karommentes gráf (claw-free graph) olyan gráf, mely nem tartalmazza a karomgráfot feszített részgráfként. A karom a K1,3 teljes páros gráf másik neve (tehát arról a csillaggráfról van szó, ami három éllel, három levéllel és egy csomóponttal rendelkezik). Egy karommentes gráf onnan ismerszik meg, hogy egyetlen feszített részgráfja sem karom; tehát semelyik négy csúcspontja között nincs ilyen módon csatlakozó három él. Ezzel egyenértékű megfogalmazás, hogy a karommentes gráf olyan gráf, melyben bármely csúcs szomszédsága egy háromszögmentes gráf komplementere. A karommentes gráfokat eredetileg az élgráfok általánosításaként vizsgálták, de három fő felfedezést tettek velük kapcsolatban, melyek indokolták a további vizsgálódást: hogy bármely páros rendű karommentes összefüggő gráf rendelkezik teljes párosítással; a karommentes gráfok független csúcshalmazait megtaláló algoritmusok felfedezése; a karommentes perfekt gráfok karakterizációja. Több száz matematikai tanulmány és áttekintő munka foglalkozik velük. (hu)
|
