A pszeudoerdő (pseudoforest) gráfelméleti fogalom, olyan irányítatlan gráf,Az itt használt irányítatlan gráfot gyakran multigráfnak vagy pszeudográfnak nevezik, az egyszerű gráfoktól megkülönböztetendő. 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: .
Definíciók és struktúra Definiáljuk az irányítatlan (multi)gráfot csúcsok és élek halmazaként, ahol az éleket mindkét végpontja a csúcsok halmazában található. Megengedjük, hogy két csúcs között több él húzódjon, és azt is, hogy egy élhez tartozó két csúcs egybeessen (hurokél). Egy gráf részgráfja a csúcsok és élek részhalmazaiból alkotott gráf, ahol az élek részhalmazába tartozó minden él végpontjai szerepelnek a csúcsok részhalmazában. Az irányítatlan gráf összefüggő komponense az a részgráf, ami valamely kiindulásként választott csúcsból az éleken keresztül elérhető csúcsokból és élekből áll. Egy gráf összefüggő, ha minden csúcs és él elérhető minden csúcsból és élből. Egy kör olyan összefüggő részgráf, melyben minden csúcs pontosan két éllel szomszédos, vagy hurkot alkot.A definíciók megtalálhatók a hivatkozott cikkekben és azok további hivatkozásaiban.
Egy pszeudoerdő olyan irányítatlan gráf, melynek összefüggő komponenseiben legfeljebb 1-1 kör lehet.Ezt a definíciót használta pl. . Ezzel ekvivalens, hogy olyan irányítatlan gráf, melynek összefüggő komponenseinek egyikében sincsen több él, mint csúcs.Ez definíciója. Azok a komponensek, melyek nem tartalmaznak köröket, egyszerűen fák, míg az egyetlen kört tartalmazó komponensek az 1-fák (1-trees vagy unicyclic graphs). Tehát egy 1-fa olyan összefüggő gráf, ami pontosan egy kört tartalmaz. Az egyetlen összefüggő komponensből (amit általában pszeudofának neveznek, bár egyes szerzőknél a pszeudofa mindig 1-fa) álló pszeudoerdő vagy fa, vagy 1-fa; általában egy pszeudoerdő több összefüggő komponensből állhat, amennyiben azok mindegyike fa vagy 1-fa.
Ha egy 1-fa köréből valamely élt eltávolítjuk, az eredmény fa lesz. Megfordítva, egy fa két csúcsát új éllel összekötve 1-fát kapunk; a hozzáadott él két végpontját a fában összekötő élek és a hozzáadott él együttesen alkotják az 1-fa egyetlen körét. Ha egy 1-fához hozzáadunk egy olyan élt, ami valamely csúcsot egy újonnan hozzáadott csúcshoz köti, eredményül 1-fát kapunk, ami egy csúccsal nagyobb az eredetinél: az 1-fák konstrukciójának lehetséges módszere egy körből kiindulva újra és újra csúcsokat adni a gráfhoz. Az 1-fa élei egyedi módon oszthatók fel két részgráfra, melyek egyike egy kör, a maradék pedig egy erdő, melynek minden fája pontosan a kör egy csúcsát tartalmazza.Lásd pl. a Lemma 4 bizonyítását itt: .
A pszeudoerdők néhány típusát mélyebben is megvizsgálták. Egy 1-erdő (1-forest) vagy maximális pszeudoerdő (maximal pseudoforest) olyan pszeudoerdő, ami nem bővíthető új éllel anélkül, hogy a gráf valamely komponensében ne legyen egynél több kör. Ha egy pszeudoerdő valamely komponense fa, nem lehet 1-erdő, hiszen a fa-komponenshez adva az új élt két eset lehetséges: vagy 1-fa keletkezik a komponensből, vagy összekötjük egy másik komponenssel. Tehát az 1-erdők pontosan azok a pszeudoerdők, melyekben minden komponens 1-fa.
Egy irányítatlan G gráf feszítő pszeudoerdői (spanning pseudoforests) a G olyan pszeudoerdő részgráfjai, melyek G minden csúcsát tartalmazzák. Egy ilyen pszeudoerdő nem feltétlenül rendelkezik élekkel, hiszen akár az a részgráf is megfelelő, ami tartalmazza G összes csúcsát és egyetlen éllel sem rendelkezik (tehát összefüggő komponensei mind egyetlen csúcsból álló fák).
Egy irányítatlan G gráf maximális pszeudoerdői (maximal pseudoforests) a G olyan pszeudoerdő-részgráfjai, melyeket nem tartalmazza G egyetlen nagyobb pszeudoerdője sem. Egy gráf maximális pszeudoerdője mindig feszítő pszeudoerdő is, fordítva ez nem feltétlenül igaz. Ha G-nek egyik összefüggő komponense sem fa, akkor maximális pszeudoerdői 1-erdők, ha pedig G valamely komponense fa, maximális pszeudoerdői nem 1-erdők. Precízebben, bármely G gráf maximális pszeudoerdői felbonthatók G összes fa komponensére plusz a G maradék csúcsát lefedő egy vagy több diszjunkt 1-fára.
Irányított pszeudoerdők Az előbbi definíciók némi változtatással irányított gráfokra is használhatók. Az irányított gráfok és csúcsokból és élekből állnak, de minden él rendelkezik az egyik végpontjától a másikig mutató irányítással. Egy irányított pszeudoerdő olyan irányított gráf, melyben a csúcsok legfeljebb egy kimenő éllel rendelkeznek, tehát a ki-fok legfeljebb egy. Egy irányított 1-erdő – gyakoribb nevén függvénygráf (functional graph) (lásd lent) vagy maximális irányított pszeudoerdő – olyan irányított gráf, melyben minden csúcs ki-foka pontosan egy. a fordított definíciót használja, amiben minden csúcs be-foka egy; az eredményül kapott, általa unicycular-nak nevezett gráfok az itt használt definíció szerinti gráfok transzponáltjai. Ha D egy irányított pszeudoerdő, a D éleiből az irányítást eltávolítva egy irányítatlan pszeudoerdőt kapunk.
Élek száma Egy n csúcsú pszeudoerdőnek legfeljebb n éle lehet, minden n csúcsú maximális pszeudoerdőnek pedig pontosan n éle. Fordítva, ha egy G gráfra igaz, hogy csúcsainak bármely S részhalmazát tekintve S feszített részgráfjában az élek száma legfeljebb S csúcsainak számával egyezik meg, akkor G egy pszeudoerdő. Az 1-fák pedig úgy is definiálhatók, mint azok az összefüggő gráfok, melyekben a csúcsok és az élek száma megegyezik.
Az egyes gráfoktól áttérve a gráfcsaládokra, ha egy gráfcsalád rendelkezik azzal a tulajdonsággal, hogy a családba tartozó gráf minden részgráfja szintén a család tagja, és minden gráf a családban legfeljebb annyi éllel rendelkezik, mint csúccsal, akkor a család kizárólag pszeudoerdőket tartalmaz. Például egy thrackle minden részgráfja (a thrackle vagy gubanc egy gráf olyan lerajzolása, ahol minden élpárnak egy közös pontja van) szintén thrackle, ezért Conway thrackle-sejtése, miszerint egy thrackle-nek legfeljebb annyi éle lehet, mint csúcsa úgy is megfogalmazható, hogy minden thrackle pszeudoerdő. Egy precízebb jellemzés szerint, ha a sejtés igaz, akkor a thrackle-ök pontosan megegyeznek az olyan pszeudoerdőkkel, melyekben nincsen négy csúcsból álló kör és legfeljebb egy páratlan körük van.; .
Streinu és Theran. általánosítják a pszeudoerdőket definiáló ritkasági feltételeket: definíciójuk egy gráf (k,l)-ritka, ha minden nem üres részgráfjának n csúcsa között legfeljebb kn − l él húzódik, a (k,l)-éles gráf (tight graph)az „éles” szó itt a matematikai zsargonban használt éles, tovább már nem javítható eredményre utal pedig olyan (k,l)-ritka gráf, mely pontosan kn − l éllel rendelkezik. A pszeudoerdők tehát az (1,0)-ritka gráfok, a maximális pszeudoerdők pedig az (1,0)-éles gráfok. Számos fontos gráfcsalád meghatározható a k és l értékei alapján, és ha l ≤ k, akkor a (k,l)-ritka gráfok éppen azok a gráfok, melyek l erdő és k − l pszeudoerdő éldiszjunkt uniójával állnak elő..
Majdnem minden elegendően ritka véletlen gráf pszeudoerdő.. Lásd a 120. oldalon a Corollary 24-et a véletlen gráf 1-fa komponenseibe tartozó csúcsok számára vonatkozó korláthoz, illetve a 113. oldalon a Corollary 19-et a különböző címkézett 1-fa gráfok számára vonatkozó korláthoz. Tehát, ha c konstansra igaz, hogy 0 < c < 1/2, Pc(n) pedig annak valószínűsége, hogy az n csúccsal és cn éllel rendelkező gráfok közül egyenletes eloszlás szerint véletlenszerűen választva pszeudoerdőt kapunk, akkor Pc(n) az n növekedésével 1-hez tart. Ha azonban a c > 1/2, csaknem minden cn éllel rendelkező véletlen gráf rendelkezik olyan nagyméretű komponenssel, ami nem 1-fa.
Leszámlálás Egy gráf egyszerű, ha nem rendelkezik sem többszörös, sem hurokéllel. Az n címkézett csúccsal rendelkező egyszerű 1-fák száma; lásd in the On-Line Encyclopedia of Integer Sequences.
Az n-hez tartozó értékek 18-ig megtalálhatók itt: .
Az n csúcsú maximális irányított pszeudoerdők száma, a hurokéleket megengedve éppen nn, mivel minden csúcs kimenő éle n lehetséges végponthoz csatlakozhat. André Joyal ezt a tényt használta fel a Cayley-formula (azaz hogy az n csúcsú irányítatlan fák száma nn − 2) bijektív bizonyítására; kölcsönösen egyértelmű megfeleltetést talált a maximális irányított pszeudoerdők és a két megkülönböztetett csúccsal bíró irányítatlan fák között.. Ha a hurokélek nem megengedettek, a maximális irányított pszeudoerdők száma (n − 1)n.
Függvények gráfjai
Az irányított pszeudoerdők és az endofüggvények (azok a függvények, melyek értelmezési tartománya és értékkészlete megegyezik) bizonyos értelemben matematikailag egyenértékűek. Bármely, az X halmazt magára leképező ƒ függvény (X bármely endomorfizmusa) felfogható olyan irányított pszeudoerdőként, melyben x-ből y-ba pontosan akkor mutat él, ha ƒ(x) = y. Az eredményül kapott irányított pszeudoerdő maximális, és tartalmazhat hurokéleket, ha valamely x-re ƒ(x) = x. Ha nem engedjük meg a hurkokat, a nem maximális pszeudoerdőket kapjuk. A másik irányban, bármely maximális irányított pszeudoerdő meghatároz egy olyan ƒ függvényt, melyben ƒ(x) az x-ből kiinduló él végpontja, továbbá bármely nem maximális irányított pszeudoerdő maximálissá tehető hurkok hozzáadásával, majd ugyanilyen függvénnyé konvertálásával. Emiatt a maximális irányított pszeudoerdőket néha függvénygráfoknak (functional graphs) is hívják. Egy függvény gráfként történő kezelése kényelmesebb lehet olyan tulajdonságok leírására, amikre a függvényelméleti keret nem alkalmas; különösen így van ez az iteratív függvények esetében, melyek a függvénygráfokban szereplő utaknak felelnek meg.
A függvénygráfokban történő kördetektálásnak a kriptográfia és az algoritmikus számelmélet területén vannak alkalmazásai, például a prímfelbontásra szolgáló Pollard-féle módszer vagy a kriptográfiai hashfüggvényekben található ütközések keresése. Ezekben az alkalmazásokban az ƒ-től véletlenszerű viselkedést várnak el; Flajolet és Odlyzko. tanulmányozták a véletlenszerű összerendelésekkel kialakított függvénygráfok gráfelméleti tulajdonságait. A születésnap-paradoxon egy formájából következik, hogy egy n csúcsú véletlen függvénygráfban tetszőlegesen kiválasztott csúcsból kiindulva jellemzően O(√n) lépésben körbeérünk. Konyagin et al. a gráfstatisztika területén analitikus és számítási előrelépéseket tettek..
Martin, Odlyzko és Wolfram. a sejtautomaták dinamikáját modellező pszeudoerdőket vizsgálták. Ezeknek az állapotátmenet-diagramnak (state transition diagrams) nevezett függvénygráfok csúcsai a sejtautomata egy-egy lehetséges állapotának felelnek meg, két csúcs között pedig akkor húzódik él, ha a nekik megfelelő automata-állapotok között lehetséges átmenet. A diagramok szerkezetéből következtetni lehet az automaták tulajdonságaira; például a komponensek számára, a limitáló körök hosszára, ezen körök nem limitáló állapotaihoz csatlakozó fák mélységére stb. Például egy bejövő éllel nem rendelkező csúcs egy édenkert-, a hurokél pedig egy csendélet-konfigurációnak felel meg.