A pszeudoerdő (pseudoforest) gráfelméleti fogalom, olyan irányítatlan gráf,^[1] 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^[2] 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.^[3] 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: (Picard & Queyranne 1982).

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).^[1] 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.^[4]

Egy pszeudoerdő olyan irányítatlan gráf, melynek összefüggő komponenseiben legfeljebb 1-1 kör lehet.^[5] Ezzel ekvivalens, hogy olyan irányítatlan gráf, melynek összefüggő komponenseinek egyikében sincsen több él, mint csúcs.^[6] 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.^[7]

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.

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.^[8] 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.

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.^[2]

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.^[9]

Streinu és Theran^[10] á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)^[11] 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ő.^[12]

Majdnem minden elegendően ritka véletlen gráf pszeudoerdő.^[13] Tehát, ha c konstansra igaz, hogy 0 < c < 1/2, P_c(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 P_c(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.

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^[14]

${\displaystyle n\sum _{k=1}^{n}{\frac {(-1)^{k-1}}{k}}\sum _{n_{1}+\cdots +n_{k}=n}{\frac {n!}{n_{1}!\cdots n_{k}!}}{\binom {{\binom {n_{1}}{2}}+\cdots +{\binom {n_{k}}{2}}}{n}}.}$

Az n-hez tartozó értékek 18-ig megtalálhatók itt:  A057500.

Az n csúcsú maximális irányított pszeudoerdők száma, a hurokéleket megengedve éppen nⁿ, 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 n^n − 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.^[15] Ha a hurokélek nem megengedettek, a maximális irányított pszeudoerdők száma (n − 1)ⁿ.

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.^[2] 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 hash fü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^[16] 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.^[17]

Martin, Odlyzko és Wolfram^[18] 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.

A függvénygráfok korai alkalmazása a Steiner-hármasrendszerek tanulmányozására szolgáló train-ek voltak.^[19] Egy hármasrendszer train-je egy függvénygráf, melynek csúcsai a lehetséges szimbólumhármasoknak felelnek meg; minden pqr triplettet az ƒ stu-ba visz át, ahol pqs, prt és qru azok a triplettek, melyek a rendszerbe tartoznak és tartalmazzák a pq, pr, illetve qr párosokat. A train-ekről megmutatták, hogy a hármasrendszerek hatékony invariánsai, még ha kiszámításuk körülményes is.

Egy matroid olyan matematikai struktúra, melynek elemeiből képezett bizonyos halmazok függetlenként vannak meghatározva, oly módon, hogy a független halmazok a vektortérbeli lineáris függetlenség tulajdonságai alapján modellezett tulajdonságoknak tegyenek eleget. A matroid klasszikus példája a grafikus matroid, ahol a független halmazok egy gráf erdőinek élhalmazai; az erdők matroidstruktúrája fontos a gráf minimális feszítőfáját meghatározó algoritmusokban. A grafikus matroidok analógiájára pszeudoerdőkből is definiálhatók matroidok.

Adott G = (V,E) gráfra definiálunk G élein egy matroidot, melyben élek egy halmaza akkor és csak akkor független, ha pszeudoerdőt alkot; ezt a matroidot a G gráf bicirkuláris matroidja (vagy bicycle matroidja) néven ismerjük.^[20][21] Ezen matroid legkisebb független halmazai a G olyan minimális összefüggő részgráfjai, melyekben egynél több kör van, és ezeket a részgráfokat hívják néha bicycle-öknek. Három lehetséges bicycle-típus van: a théta-gráfban két végponti csúcsot három belsőleg diszjunkt út köt össze; a 8-as alak két kör, melyek egy közös csúccsal rendelkeznek, a bilincsgráf pedig két diszjunkt kör, amit egy út köt össze.^[22] Egy gráf pontosan akkor pszeudoerdő, ha nem tartalmaz bicycle-t részgráfként.^[10]

Ha élek összehúzásával és törlésével egy pszeudoerdő minorát képezzük, újabb pszeudoerdőt kapunk. Ezért a pszeudoerdők családja a minorképzés műveletére nézve zárt, és a Robertson–Seymour-tétel alapján a pszeudoerdők jellemezhetők tiltott minorjaik véges halmaza alapján, ahogy a Wagner-tétel karakterizálja a síkbarajzolható gráfokat, mint a sem a K₅ teljes gráfot, sem a K_3,3 teljes páros gráfot minorként nem tartalmazó gráfokat. Ahogy feljebb is olvasható, bármely nem-pszeudoerdő gráf részgráfként tartalmazza a bilincs-, 8-as alak vagy thétagráfot; bármely bilincs- vagy 8-as alak összehúzható pillangógráffá (öt csúcsú 8-as alak), bármely thétagráf pedig összehúzható gyémántgráffá (négy csúcsú thétagráf),^[23] tehát bármely nem pszeudoerdő gráf minorként tartalmazza a pillangógráfot vagy a gyémántgráfot, és ezek az egyedüli minor-minimális nem pszeudoerdők. Más megfogalmazásban, egy gráf pontosan akkor pszeudoerdő, ha nem tartalmazza minorként sem a pillangó-, sem a gyémántgráfot. Ha csak a gyémántgráfot tiltjuk, az így meghatározott bővebb gráfcsalád a kaktuszgráfokból, illetve kaktuszgráfok diszjunkt unióiból áll.^[24]

Ha viszont multigráfokat tekintünk és a hurokéleket is megengedjük, egyetlen tiltott minor marad, a két hurokéllel rendelkező csúcs.

A pszeudoerdők egyik korai felhasználása a hálózati szimplex (network simplex) algoritmus alkalmazása volt a különböző fajta termékek közötti konverziót modellező általánosított folyam-problémákra.^[3][25] Ezeknek a problémáknak a bemenete egy olyan folyam, melyben a csúcsok az egyes árucikkeknek felelnek meg, az élek pedig az árucikkek közötti lehetséges konverziókat modellezik. Az egyes élekhez különböző mennyiségek tartoznak: a kapacitás (mennyi árucikk konvertálható egységnyi idő alatt); a folyamszorzó (flow multiplier) (az árucikkek közötti konverziós arány); és a költség (mennyi veszteséggel, vagy negatív érték esetén haszonnal jár egységnyi árucikk konvertálása). A feladat annak meghatározása, hogy a folyam egyes élein mennyi árucikket érdemes konvertálni akár a költség minimalizálása, akár a haszon maximalizálása érdekében, közben figyelembe véve a kapacitáskorlátozásokat és nem engedve, hogy bármely fajta árucikk felhasználatlanul felhalmozódjon. Ez a fajta probléma megfogalmazható lineáris optimalizálási problémaként, ami a szimplex algoritmussal megoldható. Az algoritmus köztes megoldásai, ahogy az eredményül kapott optimális megoldás is, speciális szerkezettel rendelkeznek: a bemeneti hálózat éleit vagy nem használják vagy teljes kapacitását kihasználják – kivéve az élek egy részhalmazát, melyek a bemeneti hálózat feszítő pszeudoerdőjét alkotják, melyekre a folyam kapacitásértékei nulla és a teljes kapacitás közé esnek. Ezen az alkalmazási területen az 1-fákat néha augmented tree-knek („javított fa”), a maximális pszeudoerdőket pedig néha augmented forest-eknek („javított erdőknek”) nevezik.^[25]

A minimális feszítő pszeudoerdő-probléma egy élsúlyozott G gráf minimális súlyú feszítő pszeudoerdőjének megkereséséből áll. A pszeudoerdők matroidszerkezetéből következően a minimális súlyú maximális pszeudoerdők a minimális feszítőfa problémájához hasonlóan mohó algoritmussal megtalálhatók. Gabow és Tarjan erre az esetre még hatékonyabb, lineáris idejű megközelítést találtak.^[2]

A G gráf pszeudoarboricitása, az arboricitás analógiájára, a pszeudoerdők minimális száma, amire a gráf élei felbonthatók; ezzel ekvivalens definíció szerint az a minimális k, amire G (k,0)-ritka, vagy az a minimális k, amire G élei úgy orientálhatók, hogy legfeljebb k ki-fokú irányított gráfot alkossanak. A pszeudoerdők matroidszerkezete miatt a pszeudoarboricitás polinom időben számítható.^[26]

Egy véletlen páros gráf, ahol a párosítás mindkét oldalán n csúcs van, és a lehetséges n² számú élből egymástól függetlenül, véletlenszerűen cn él kerül behúzásra, nagy valószínűséggel pszeudoerdő, amennyiben a c konstans kisebb egynél. Ez a tény kap fontos szerepet a kakukk hash (cuckoo hashing) analízisében; ez egy adatszerkezet, melynek segítségével kulcs-érték párok kérdezhetők le két hashtábla a kulcsból kinyert helyéről: megalkotható az a kakukkgráf (cuckoo graph), melynek csúcsai a hashtábla helyeinek felelnek meg, élei pedig a két helyet kötik össze, ahol a kulcsok egyike megtalálható. A kakukk hash algoritmus pontosan akkor jár sikerrel az összes kulcs helyének megkeresésében, ha a kakukkgráf pszeudoerdő.^[27]

A pszeudoerdők kulcsfontosságú szerepet játszanak a gráfszínezési és kapcsolódó problémák párhuzamos algoritmusaiban.^[28]

• Ez a szócikk részben vagy egészben a Pseudoforest című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

• Weisstein, Eric W.: Unicyclic Graph (angol nyelven). Wolfram MathWorld