| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén egy élperfekt gráf (line perfect graph) olyan gráf, melynek élgráfja perfekt gráf. Ezzel egyenértékű definíció szerint azok a gráfok élperfektek, melyek minden páratlan hosszúságú egyszerű köre háromszög. Egy gráf pontosan akkor élperfekt, ha minden kétszeresen összefüggő komponense teljes páros gráf, a teljes gráf vagy egy alakú háromszögű (teljes háromrészes gráf). Mivel mindháromfajta kétszeresen összefüggő komponenens maga is perfekt gráf, ezért az élperfekt gráfok mindig perfekt gráfok is. Hasonló okoskodás alapján minden élperfekt gráf egyben paritásgráf, és is. Az élperfekt gráfok a páros gráfok általánosításai; velük megegyező tulajdonságaik, hogy a maximális elemszámú párosításuk és mérete megegyezik, valamint élkromatikus számuk megegyezik maximális fokszámukkal. (hu)
- A matematika, azon belül a gráfelmélet területén egy élperfekt gráf (line perfect graph) olyan gráf, melynek élgráfja perfekt gráf. Ezzel egyenértékű definíció szerint azok a gráfok élperfektek, melyek minden páratlan hosszúságú egyszerű köre háromszög. Egy gráf pontosan akkor élperfekt, ha minden kétszeresen összefüggő komponense teljes páros gráf, a teljes gráf vagy egy alakú háromszögű (teljes háromrészes gráf). Mivel mindháromfajta kétszeresen összefüggő komponenens maga is perfekt gráf, ezért az élperfekt gráfok mindig perfekt gráfok is. Hasonló okoskodás alapján minden élperfekt gráf egyben paritásgráf, és is. Az élperfekt gráfok a páros gráfok általánosításai; velük megegyező tulajdonságaik, hogy a maximális elemszámú párosításuk és mérete megegyezik, valamint élkromatikus számuk megegyezik maximális fokszámukkal. (hu)
|
