A matematika, azon belül a gráfelmélet területén egy 4-reguláris gráf (angol nyelvterületen még: quartic graph) olyan reguláris gráf, melyben minden csúcs fokszáma 4..

Példák

Számos jól ismert gráf 4-reguláris. Közéjük tartoznak: A K5 teljes gráf, ami a legkisebb lehetséges 4-reguláris gráf. A 12 csúcsú Chvátal-gráf, a legkisebb 4-reguláris gráf, mely nem tartalmaz háromszöget és nem színezhető ki három színnel.. A 20 csúcsú Folkman-gráf, ami a legkisebb félszimmetrikus gráf.. A 70 csúcsú Meredith-gráf, ami egyben 4-szeresen összefüggő is, de nincs Hamilton-köre, cáfolva ezzel Crispin Nash-Williams egy sejtését..

Minden mediális gráf 4-reguláris síkbarajzolható gráf, és minden 4-reguláris síkbarajzolható gráf egy duális síkgráfok vagy multigráfok mediális gráfja.. A csomódiagramok és láncdiagramok szintén 4-reguláris, síkba rajzolható multigráfok, melyek csúcsai a diagram metszéspontjainak felelnek meg és további információt tartalmaznak azzal kapcsolatban, hogy a csomó két ága közül melyik metszi a másik ágat az adott ponton..

Tulajdonságok Mivel egy 4-reguláris gráf minden csúcsának fokszáma páros, ezért minden összefüggő 4-reguláris gráfnak van Euler-köre. Minden páros gráfhoz tartozik teljes párosítás; a 4-reguláris páros gráfok esetében ennek megkeresése sokkal egyszerűbb és gyorsabb algoritmussal történhet: egy Euler-séta minden második élét kiválasztva megkapjuk a gráf 2-faktorát, ami ebben az esetben páros hosszúságú körök olyan gyűjteménye, melyre igaz, hogy a gráf minden csúcsa pontosan egy körben szerepel. Ezen körökön belül újra minden második élt kiválasztva lineáris időben megkapható a teljes párosítás. Ugyanez a módszer használható a gráf négy színnel történő élszínezésének lineáris idejű előállítására..

A 4-reguláris gráfok páros számú Hamilton-körökre felbontással rendelkeznek..

Megoldatlan problémák Nyitott kérdés, hogy vajon az összes 4-reguláris Hamilton-körű gráfnak páros számú Hamilton-kör van-e, vagy egyáltalán egynél több Hamilton-köre van-e. A válasz 4-reguláris multigráfok esetében nemleges..

Kapcsolódó szócikkek

3-reguláris gráf

Fordítás

Jegyzetek

További információk

Kategória:Gráfcsaládok Kategória:Reguláris gráfok