| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén egy merev körű gráf vagy húrgráf (chordal graph) olyan gráf, melynek minden négy vagy több csúcsot tartalmazó körének van „húrja”, tehát olyan éle, ami nem része a körnek, de összeköt a körbe tartozó két csúcsot. Ezzel egyenértékű megfogalmazás, hogy a gráf minden feszített köre pontosan három csúcsból állhat. A húrgráfok úgy is jellemezhetők, mint a gráfok, melyek csúcsaira létezik olyan, ún. szimpliciális rendezés (perfect elimination ordering), melyben tetszőleges v csúcs környezetében a rendezésben utána következő csúcsok klikket alkotnak (bármely feszített részgráf tartalmaz szimpliciális csúcsot); a gráfok, melyben minden minimális elvágó csúcshalmaz klikket alkot; illetve amely egy fa részfáinak metszetgráfja. Ismert elnevezéseik közé tartoznak még: kordális gráfok, merev körű gráfok (rigid circuit graphs), háromszögelt gráfok (triangulated graphs), felbontható gráfok (decomposable graphs) vagy átlós gráfok. A merev körű gráfok a perfekt gráfok részhalmazát alkotják. felismerhetők, és számos olyan problémát, ami más gráfosztályokon nehézséget okoz (pl. gráfszínezés) merev körű gráfokon polinom időben meg lehet oldani. Tetszőleges gráf favastagságát jellemzi az őt tartalmazó húrgráfok klikkjeinek mérete. (hu)
- A matematika, azon belül a gráfelmélet területén egy merev körű gráf vagy húrgráf (chordal graph) olyan gráf, melynek minden négy vagy több csúcsot tartalmazó körének van „húrja”, tehát olyan éle, ami nem része a körnek, de összeköt a körbe tartozó két csúcsot. Ezzel egyenértékű megfogalmazás, hogy a gráf minden feszített köre pontosan három csúcsból állhat. A húrgráfok úgy is jellemezhetők, mint a gráfok, melyek csúcsaira létezik olyan, ún. szimpliciális rendezés (perfect elimination ordering), melyben tetszőleges v csúcs környezetében a rendezésben utána következő csúcsok klikket alkotnak (bármely feszített részgráf tartalmaz szimpliciális csúcsot); a gráfok, melyben minden minimális elvágó csúcshalmaz klikket alkot; illetve amely egy fa részfáinak metszetgráfja. Ismert elnevezéseik közé tartoznak még: kordális gráfok, merev körű gráfok (rigid circuit graphs), háromszögelt gráfok (triangulated graphs), felbontható gráfok (decomposable graphs) vagy átlós gráfok. A merev körű gráfok a perfekt gráfok részhalmazát alkotják. felismerhetők, és számos olyan problémát, ami más gráfosztályokon nehézséget okoz (pl. gráfszínezés) merev körű gráfokon polinom időben meg lehet oldani. Tetszőleges gráf favastagságát jellemzi az őt tartalmazó húrgráfok klikkjeinek mérete. (hu)
|
