| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén a rövidségi kitevő vagy rövidségkitevő (shortness exponent) gráfcsaládok olyan numerikus paramétere, ami azt jellemzi, hogy a család gráfjai milyen messze lehetnek attól, hogy Hamilton-körük legyen. Intuitívan, ha az gráfcsalád rövidségi kitevője , akkor a család minden -csúcsú gráfjában van közel hosszúságú kör, de néhány gráfban nincs ennél hosszabb kör. Precízebben, az gráfjainak bármelyik , sorozatba rendezésére, ahol a leghosszabb körének hosszát jelöli, a rövidségkitevő meghatározása a következő: Ez a szám mindig 0 és 1 közé esik; az 1 értéket olyan gráfcsaládokon veszi fel, melyek mindig tartalmaznak Hamilton-kört vagy majdnem Hamilton-kört, a 0 értéket pedig olyan gráfcsaládokon, melyek leghosszabb köre kisebb lehet a csúcsok számának bármely konstans hatványánál. A poliédergráfok rövidségkitevője . Egy -alapú konstrukció segítségével megmutatható, hogy egyes poliédergráfok leghosszabb körének hossza , miközben az is ismert, hogy minden poliédergráf tartalmaz hosszú kört. A poliédergráfok azok a gráfok, melyek egyszerre síkba rajzolhatók és 3-szorosan csúcsösszefüggők; a 3-összefüggőség ezeknek az eredményeknek , hiszen léteznek olyan, 2-összefüggő síkbarajzolható gráfok (például a teljes páros gráfok), melyek rövidségkitevője 0. Számos további eredmény ismert poliédergráfok és síkbarajzolható gráfok korlátozott alosztályainak rövidségkitevőjével kapcsolatban. A 3-összefüggő 3-reguláris gráfok (a síkbarajzolhatóság követelménye nélkül) rövidségkitevője szintén szigorúan 0 és 1 közé esik. (hu)
- A matematika, azon belül a gráfelmélet területén a rövidségi kitevő vagy rövidségkitevő (shortness exponent) gráfcsaládok olyan numerikus paramétere, ami azt jellemzi, hogy a család gráfjai milyen messze lehetnek attól, hogy Hamilton-körük legyen. Intuitívan, ha az gráfcsalád rövidségi kitevője , akkor a család minden -csúcsú gráfjában van közel hosszúságú kör, de néhány gráfban nincs ennél hosszabb kör. Precízebben, az gráfjainak bármelyik , sorozatba rendezésére, ahol a leghosszabb körének hosszát jelöli, a rövidségkitevő meghatározása a következő: Ez a szám mindig 0 és 1 közé esik; az 1 értéket olyan gráfcsaládokon veszi fel, melyek mindig tartalmaznak Hamilton-kört vagy majdnem Hamilton-kört, a 0 értéket pedig olyan gráfcsaládokon, melyek leghosszabb köre kisebb lehet a csúcsok számának bármely konstans hatványánál. A poliédergráfok rövidségkitevője . Egy -alapú konstrukció segítségével megmutatható, hogy egyes poliédergráfok leghosszabb körének hossza , miközben az is ismert, hogy minden poliédergráf tartalmaz hosszú kört. A poliédergráfok azok a gráfok, melyek egyszerre síkba rajzolhatók és 3-szorosan csúcsösszefüggők; a 3-összefüggőség ezeknek az eredményeknek , hiszen léteznek olyan, 2-összefüggő síkbarajzolható gráfok (például a teljes páros gráfok), melyek rövidségkitevője 0. Számos további eredmény ismert poliédergráfok és síkbarajzolható gráfok korlátozott alosztályainak rövidségkitevőjével kapcsolatban. A 3-összefüggő 3-reguláris gráfok (a síkbarajzolhatóság követelménye nélkül) rövidségkitevője szintén szigorúan 0 és 1 közé esik. (hu)
|
