| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén a H irányítatlan gráf a G gráf minora, ha H előállítható G-ből élek és csúcsok törlésével, valamint élösszehúzás segítségével. A gráfminorok elmélete a kezdődött, miszerint egy gráf pontosan akkor síkbarajzolható, ha minorai között nem található meg sem a K5 teljes gráf, sem a K3,3 teljes páros gráf. A szerint ezzel analóg módon, a törlések és élösszehúzások által nem befolyásolt minden gráftulajdonsághoz tartozik tiltott minorok szerinti karakterizáció.Adott H gráfra alatt tesztelhető, hogy az a bemeneti G gráf minora-e; ebből a tiltott minorok szerinti osztályozást is tekintve az következik, hogy minden, törlések és élösszehúzások mellett is megmaradó gráftulajdonság polinom időben felismerhető. További, a gráfminorokat érintő eredmények és sejtések közé tartozik a , ami szerint a H-t minorként nem tartalmazó gráfok előállíthatók egyszerűbb darabok összeragasztásával, továbbá a mély Hadwiger-sejtés, ami a gráfok színezésének problémáját összeköti a nagyméretű teljes gráfminorok létezésével. A gráfminorok fajtái közül megemlítendők a topologikus minorok és az immerziós minorok. (hu)
- A matematika, azon belül a gráfelmélet területén a H irányítatlan gráf a G gráf minora, ha H előállítható G-ből élek és csúcsok törlésével, valamint élösszehúzás segítségével. A gráfminorok elmélete a kezdődött, miszerint egy gráf pontosan akkor síkbarajzolható, ha minorai között nem található meg sem a K5 teljes gráf, sem a K3,3 teljes páros gráf. A szerint ezzel analóg módon, a törlések és élösszehúzások által nem befolyásolt minden gráftulajdonsághoz tartozik tiltott minorok szerinti karakterizáció.Adott H gráfra alatt tesztelhető, hogy az a bemeneti G gráf minora-e; ebből a tiltott minorok szerinti osztályozást is tekintve az következik, hogy minden, törlések és élösszehúzások mellett is megmaradó gráftulajdonság polinom időben felismerhető. További, a gráfminorokat érintő eredmények és sejtések közé tartozik a , ami szerint a H-t minorként nem tartalmazó gráfok előállíthatók egyszerűbb darabok összeragasztásával, továbbá a mély Hadwiger-sejtés, ami a gráfok színezésének problémáját összeköti a nagyméretű teljes gráfminorok létezésével. A gráfminorok fajtái közül megemlítendők a topologikus minorok és az immerziós minorok. (hu)
|
