| dbo:abstract
|
- A matematika, azon belül a gráfelmélet területén egy pszeudoerdő (pseudoforest) olyan irányítatlan gráf, melynek minden összefüggő komponensében legfeljebb egy kör található. Más megfogalmazásban, csúcsok és csúcspárokat összekötő élek olyan rendszere, melyben tetszőleges két kört kiválasztva sem közös csúcsot, sem egymást követő élekből álló utat nem találunk közöttük. Egy pszeudofa (pseudotree) olyan pszeudoerdő, ami összefüggő. Az elnevezéseket az ismert fa és erdő kifejezések analógiájára alkották meg. (A fák összefüggő, körmentes gráfok; az erdők fák diszjunkt uniói.) Gabow és Tarjan a pszeudoerdők vizsgálatát Dantzig 1963-as lineáris programozási könyvéig vezetik vissza, melyben bizonyos hálózati folyam-problémák megoldásaként merülnek föl. A pszeudoerdők függvények gráfelméleti modelljeit alkotják és számos algoritmikus problémában előfordulnak. A pszeudoerdők ritka gráfok – csúcsaik számához képest kevés éllel rendelkeznek – sajátos matroidszerkezetük miatt pedig számos ritkagráf-család felbontható pszeudoerdők és erdők unióira. Bár a fogalmat már korábban vizsgálták, maga a „pszeudoerdő” kifejezés először itt jelent meg: . (hu)
- A matematika, azon belül a gráfelmélet területén egy pszeudoerdő (pseudoforest) olyan irányítatlan gráf, melynek minden összefüggő komponensében legfeljebb egy kör található. Más megfogalmazásban, csúcsok és csúcspárokat összekötő élek olyan rendszere, melyben tetszőleges két kört kiválasztva sem közös csúcsot, sem egymást követő élekből álló utat nem találunk közöttük. Egy pszeudofa (pseudotree) olyan pszeudoerdő, ami összefüggő. Az elnevezéseket az ismert fa és erdő kifejezések analógiájára alkották meg. (A fák összefüggő, körmentes gráfok; az erdők fák diszjunkt uniói.) Gabow és Tarjan a pszeudoerdők vizsgálatát Dantzig 1963-as lineáris programozási könyvéig vezetik vissza, melyben bizonyos hálózati folyam-problémák megoldásaként merülnek föl. A pszeudoerdők függvények gráfelméleti modelljeit alkotják és számos algoritmikus problémában előfordulnak. A pszeudoerdők ritka gráfok – csúcsaik számához képest kevés éllel rendelkeznek – sajátos matroidszerkezetük miatt pedig számos ritkagráf-család felbontható pszeudoerdők és erdők unióira. Bár a fogalmat már korábban vizsgálták, maga a „pszeudoerdő” kifejezés először itt jelent meg: . (hu)
|
