Pseudoforest - Pseudoforest

1-les (maximální pseud les), tvořený třemi 1-stromy

v teorie grafů, a pseudoforest je neorientovaný graf^[1] ve kterém každý připojená součást má maximálně jednu cyklus. To znamená, že se jedná o systém vrcholy a hrany spojující páry vrcholů, takže žádné dva cykly po sobě jdoucích hran nesdílejí mezi sebou žádný vrchol, ani nemohou být dva cykly vzájemně spojeny cestou po sobě jdoucích hran. A pseudotree je propojený pseud les.

Názvy jsou odůvodněny analogií k běžněji studovaným stromy a lesy. (Strom je propojený graf bez cyklů; les je nesouvislé spojení stromů.) Gabow a Tarjan^[2] připisuje studium pseudolesů Dantzigově knize z roku 1963 lineární programování, ve kterém vznikají pseudolesy při řešení jistých tok sítě problémy.^[3] Pseudoforests také tvoří graf-teoretické modely funkcí a vyskytují se v několika algoritmické problémy. Pseudolesy jsou řídké grafy - jejich počet hran je lineárně omezen, pokud jde o jejich počet vrcholů (ve skutečnosti mají maximálně tolik hran, kolik mají vrcholy) - a jejich matroid Struktura umožňuje rozložení několika dalších rodin řídkých grafů jako svazů lesů a pseud lesů. Název „pseudoforest“ pochází z Picard & Queyranne (1982).

Definice a struktura

Definujeme nepřímý graf jako množinu vrcholy a hrany tak, že každá hrana má dva vrcholy (které se mohou shodovat) jako koncové body. To znamená, že povolíme více hran (hrany se stejnou dvojicí koncových bodů) a smyček (hrany, jejichž dva koncové body jsou stejný vrchol).^[1] A podgraf grafu je graf tvořený libovolnými podmnožinami jeho vrcholů a hran tak, že každá hrana v podmnožině hran má oba koncové body v podmnožině vrcholů. připojená součást neorientovaného grafu je podgraf sestávající z vrcholů a hran, kterých lze dosáhnout sledováním hran z jediného daného počátečního vrcholu. Graf je připojen, pokud je každý vrchol nebo hrana dosažitelná ze všech ostatních vrcholů nebo hran. A cyklus v neorientovaném grafu je připojený podgraf, ve kterém každý vrchol dopadá přesně na dvě hrany nebo je smyčkou.^[4]

21 jednicyklických grafů s maximálně šesti vrcholy

Pseudoforest je neorientovaný graf, ve kterém každá připojená součást obsahuje maximálně jeden cyklus.^[5] Ekvivalentně se jedná o neorientovaný graf, ve kterém každá připojená součást nemá více hran než vrcholů.^[6] Komponenty, které nemají cykly, jsou jen stromy, zatímco jsou volány komponenty, které mají v sobě jeden cyklus 1-stromy nebo unicyklické grafy. To znamená, že 1-strom je připojený graf obsahující přesně jeden cyklus. Pseudoforest s jednou připojenou komponentou (obvykle nazývanou a pseudotree, ačkoli někteří autoři definují pseudotree jako 1-strom) je buď strom nebo 1-strom; Obecně může mít pseudoforest více připojených komponent, pokud jsou všechny stromy nebo 1-stromy.

Pokud jeden odstraní z 1-stromu jednu z hran ve svém cyklu, výsledkem je strom. Při obrácení tohoto procesu, pokud jeden zvětší strom spojením libovolných dvou jeho vrcholů o nový okraj, výsledkem je 1 strom; cesta ve stromu spojující dva koncové body přidané hrany spolu se samotnou přidanou hranou tvoří jedinečný cyklus jednoho stromu. Pokud jeden rozšiřuje 1-strom přidáním hrany, která spojuje jeden z jeho vrcholů s nově přidaným vrcholem, výsledkem je opět 1-strom s jedním dalším vrcholem; alternativní metodou pro konstrukci 1-stromů je začít s jediným cyklem a poté opakovat tuto operaci zvětšení několikrát. Okraje libovolného 1-stromu lze jedinečným způsobem rozdělit na dva podgrafy, z nichž jeden je cyklus a druhý les, takže každý strom lesa obsahuje přesně jeden vrchol cyklu.^[7]

Byly také studovány určité konkrétnější typy pseudolesů.

A 1-les, někdy nazývané a maximální pseudoles, je pseud les, ke kterému nelze přidat další hrany, aniž by některá součást grafu obsahovala více cyklů. Pokud pseudoforest obsahuje strom jako jednu ze svých složek, nemůže to být 1-les, protože lze přidat buď hranu spojující dva vrcholy v rámci tohoto stromu, tvořící jeden cyklus, nebo hranu spojující tento strom s nějakou jinou komponentou. Tedy 1-lesy jsou přesně pseudolesy, ve kterých je každá složka 1-strom.

The klenout se nad lesy neorientovaného grafu G jsou pseud lesy podgrafy z G které mají všechny vrcholy G. Takový pseudoforest nemusí mít žádné hrany, protože například podgraf, který má všechny vrcholy G a žádná hrana není pseudoforest (jehož součástí jsou stromy skládající se z jediného vrcholu).

The maximální pseud lesy v G jsou podgrafy pod lesem G které nejsou obsaženy v žádném větším pseudolesu z G. Maximum pseudoforest of G je vždy překlenující pseudoles, ale ne naopak. Li G nemá žádné připojené komponenty, kterými jsou stromy, pak jsou jeho maximálními lesy 1 lesy, ale pokud G má stromovou složku, její maximální pseudolesy nejsou 1-lesy. Uvedeno přesně v každém grafu G jeho maximální pseud lesy se skládají z každé stromové složky G, společně s jedním nebo více nesouvislými 1-stromy pokrývajícími zbývající vrcholy G.

Řízené pseud lesy

Verze těchto definic se také používají pro řízené grafy. Stejně jako neorientovaný graf se i orientovaný graf skládá z vrcholů a hran, ale každá hrana je směrována z jednoho ze svých koncových bodů do druhého koncového bodu. A řízený pseud les je směrovaný graf, ve kterém má každý vrchol nejvýše jednu odchozí hranu; to znamená, že má překonat nanejvýš jeden. A řízený 1-les - nejčastěji se nazývá a funkční graf (vidět níže ), někdy maximální směrovaný pseudoles - je směrovaný graf, ve kterém každý vrchol překročil přesně jeden.^[8] Li D je směrovaný pseudoforest, neorientovaný graf vytvořený odstraněním směru od každého okraje D je neorientovaný pseudoles.

Počet hran

Každý pseudoales na množině n vrcholy má maximálně n hrany a každý maximální pseudoales na množině n vrcholy má přesně n hrany. Naopak, pokud graf G má vlastnost, která pro každou podmnožinu S z jeho vrcholů počet hran v indukovaný podgraf z S je nanejvýš počet vrcholů v S, pak G je pseudoforest. 1-stromy lze definovat jako spojené grafy se stejným počtem vrcholů a hran.^[2]

Při přechodu z jednotlivých grafů na rodiny grafů má rodina grafů tu vlastnost, že každý podgraf grafu v rodině je také v rodině a každý graf v rodině má maximálně tolik hran jako vrcholy, pak rodina obsahuje jen pseudolesy. Například každý podgraf a thrackle (graf tažené takže každá dvojice hran má jeden průsečík) je také thrackle, takže Conwayova domněnka že každá oblast má nanejvýš tolik hran jako vrcholy, lze vyjádřit slovy, že každá oblast je pseudoforestem. Přesnější charakterizace spočívá v tom, že pokud je domněnka pravdivá, pak jsou závody přesně pseudoalesy bez cyklu čtyř vrcholů a maximálně jednoho lichého cyklu.^[9]

Streinu a Theran^[10] zobecnit řídkost podmínky definující pseudolesy: definují graf jako (k,l) -sparse if every unempty subgraph with n vrcholy má maximálně kn − l hrany a (k,l) -těsné, pokud je (k,l) - řídký a má přesně kn − l hrany. Pseudoforests jsou tedy (1,0) řídké grafy a maximální pseudolesy jsou (1,0) těsné grafy. Několik dalších důležitých skupin grafů může být definováno z jiných hodnot k a l,a kdy l ≤ k (k,lŘídké grafy lze charakterizovat jako grafy vytvořené jako spojení hrana-disjunkce l lesy a k − l pseudolesy.^[11]

Téměř každý dostatečně řídký náhodný graf je pseudoforest.^[12] To je, pokud C je konstanta s 0 < C <1/2 a P_C(n) je pravděpodobnost, že se náhodně vybere mezi n-vrcholové grafy s cn edge má za následek pseudoles, pak P_C(n) má tendenci k jedné v limitu pro velké n. Nicméně pro C > 1/2, téměř každý náhodný graf s cn edge má velkou komponentu, která není jednicyklická.

Výčet

Graf je jednoduchý pokud nemá žádné smyčky a více hran se stejnými koncovými body. Počet jednoduchých 1-stromů s n označené vrcholy je^[13]

${displaystyle nsum _ {k = 1} ^ {n} {frac {(-1) ^ {k-1}} {k}} součet _ {n_ {1} + cdots + n_ {k} = n} {frac {n!} {n_ {1}! cdots n_ {k}!}} {jiné {{jiné {n_ {1}} {2}} + cdots + {jiné {n_ {k}} {2}}} { n}}.}$

Hodnoty pro n až 300 lze nalézt postupně OEIS: A057500 z On-line encyklopedie celočíselných sekvencí.

Počet maximálních směrovaných pseudolesů na n vrcholy, umožňující vlastní smyčky, je nⁿ, protože pro každý vrchol existují n možné koncové body pro odchozí hranu. André Joyal využil této skutečnosti k poskytnutí a bijektivní důkaz z Cayleyův vzorec, že počet nepřesměrovaných stromů na n uzly je n^n − 2, nalezením bijekce mezi maximálními směrovanými pseudolesy a neorientovanými stromy se dvěma rozlišujícími uzly.^[14] Pokud nejsou povoleny samostatné smyčky, je místo toho počet maximálních směrovaných pseudoalesů (n − 1)ⁿ.

Grafy funkcí

Funkce od množiny {0,1,2,3,4,5,6,7,8} k sobě a odpovídající funkční graf

Řízené pseud lesy a endofunctions jsou v jistém smyslu matematicky ekvivalentní. Libovolná funkce ƒ ze sady X pro sebe (tj endomorfismus z X) lze interpretovat tak, že definuje cílený pseud les, který má výhodu před X na y kdykoli ƒ (X) = y. Výsledný cílený pseudoles je maximální a může zahrnovat vlastní smyčky kdykoli nějakou hodnotu X má ƒ (X) = X. Alternativně může vynechání smyček vést k ne-maximálnímu pralesu. V opačném směru určuje jakýkoli maximální směrovaný pseudoales funkci ƒ takovou, že ƒ (X) je cíl hrany, ze které jde ven X, a jakýkoli ne-maximální směrovaný pseudoforest lze dosáhnout maxima přidáním samostatných smyček a následným převedením na funkci stejným způsobem. Z tohoto důvodu se někdy nazývají maximální řízené pseudolesy funkční grafy.^[2] Prohlížení funkce jako funkčního grafu poskytuje vhodný jazyk pro popis vlastností, které nejsou z hlediska funkce a teorie tak snadno popsatelné; tato technika je obzvláště použitelná při řešení problémů iterované funkce, které odpovídají cesty ve funkčních grafech.

Detekce cyklu, problém sledování cesty ve funkčním grafu k nalezení cyklu v něm, má aplikace v kryptografie a výpočetní teorie čísel, jako část Pollardův rho algoritmus pro celočíselná faktorizace a jako metoda pro zjištění kolizí v kryptografické hashovací funkce. V těchto aplikacích se očekává, že se ƒ bude chovat náhodně; Flajolet a Odlyzko^[15] studujte graficko-teoretické vlastnosti funkčních grafů vyplývajících z náhodně vybraných zobrazení. Zejména forma narozeninový paradox znamená, že v náhodném funkčním grafu s n vrcholy, cesta začínající od náhodně vybraného vrcholu se obvykle smyčí zpět na sebe a vytvoří cyklus v O (√n) kroky. Konyagin et al. dosáhly analytického a výpočetního pokroku ve statistikách grafů.^[16]

Martin, Odlyzko, a Wolfram^[17] vyšetřovat pseudolesy, které modelují dynamiku mobilní automaty. Tyto funkční grafy, které nazývají stavové přechodové diagramy, mít jeden vrchol pro každou možnou konfiguraci, ve které může být soubor buněk automatu, a hranu spojující každou konfiguraci s konfigurací, která ji následuje podle pravidla automatu. Ze struktury těchto diagramů lze odvodit vlastnosti automatu, jako je počet komponent, délka omezujících cyklů, hloubka stromů spojujících neomezující stavy s těmito cykly nebo symetrie diagramu. Například jakýkoli vrchol bez příchozí hrany odpovídá a Rajská zahrada vzor a vrchol s vlastní smyčkou odpovídá a vzor zátiší.

Další časná aplikace funkčních grafů je v vlaky zvyklý studovat Trojité systémy Steiner.^[18] Vlak trojitého systému je funkční graf, který má vrchol pro každou možnou trojici symbolů; každý trojitý pqr je namapováno ƒ na stu, kde pqs, prt, a qru jsou trojice, které patří do trojitého systému a obsahují páry pq, pr, a qr resp. Ukázalo se, že vlaky jsou mocným invariantem trojitých systémů, i když je výpočetně poněkud těžkopádný.

Půlkruhový matroid

A matroid je matematická struktura, ve které jsou definovány určité sady prvků nezávislý, takovým způsobem, aby nezávislé množiny uspokojily vlastnosti po vzoru vlastností lineární nezávislost v vektorový prostor. Jedním ze standardních příkladů matroidu je grafický matroid ve kterém jsou nezávislé množiny množiny hran v lesích grafu; struktura matroidů lesů je důležitá v algoritmech pro výpočet minimální kostra grafu. Analogicky můžeme definovat matroidy z pseudolesů.

Pro jakýkoli graf G = (PROTI,E), můžeme definovat matroid na okrajích G, ve kterém je množina okrajů nezávislá právě tehdy, když tvoří pseud les; tento matroid je znám jako dvoukruhový matroid (nebo matroid kola) z G.^[19][20] Nejmenší závislé množiny pro tento matroid jsou minimální spojené podgrafy G které mají více než jeden cyklus, a tyto podgrafy se někdy nazývají jízdní kola. Existují tři možné typy jízdních kol: a theta graf má dva vrcholy, které jsou spojeny třemi vnitřně disjunktními cestami, graf na obrázku 8 sestává ze dvou cyklů sdílejících jeden vrchol a graf pout je tvořen dvěma disjunktními cykly spojenými cestou.^[21]Graf je pseudoforest, právě když neobsahuje kolo jako podgraf.^[10]

Zakázané nezletilé

The motýlí graf (vlevo) a diamantový graf (vpravo), zakázáno nezletilí pro pseudolesy

Formování a Méně důležitý smrštěním některých jeho okrajů a odstraněním dalších vytvoří další les. Proto je rodina pseud lesů Zavřeno pod nezletilými a Věta Robertson – Seymour znamená, že pseudolesy lze charakterizovat jako konečný soubor zakázané nezletilé, analogicky k Wagnerova věta charakterizující rovinné grafy protože grafy nemají ani kompletní graf K.₅ ani kompletní bipartitní graf K._3,3 jak bylo popsáno výše, jakýkoli graf, který není pseudoforestem, obsahuje jako podgraf pouta, obrázek 8 nebo graf theta; jakýkoli graf pouta nebo obrázek 8 může být smluvně vytvořen a motýlí graf (pětvertexový obrázek 8) a jakýkoli graf theta může být smluvně vytvořen a diamantový graf (čtyřvrcholový theta graf),^[22] takže jakýkoli jiný než pseudoforest obsahuje jako menší buď motýla nebo diamant, a to jsou jediné méně-minimální nepseudoforestové grafy. Graf je tedy pseud lesem, právě když nemá motýla nebo diamant jako nezletilého. Pokud zakážete pouze diamant, ale ne motýla, výsledná větší rodina grafů se skládá z kaktusové grafy a disjunktní svazky několika kaktusových grafů.^[23]

Jednodušší, pokud multigrafy s vlastní smyčky jsou považovány, existuje pouze jeden zakázaný moll, vrchol se dvěma smyčkami.

Algoritmy

Časné algoritmické použití pseudolesů zahrnuje síť simplex algoritmus a jeho aplikace na generalizované problémy toku modelování převodu mezi komodity různých typů.^[3][24] V těchto problémech je jeden uveden jako vstup a toková síť ve kterém vrcholy modelují každou komoditu a hrany modelují povolené převody mezi jednou komoditou a druhou. Každá hrana je označena a kapacita (kolik komodity lze převést za jednotku času), a multiplikátor toku (směnný kurz mezi komoditami) a náklady (kolik ztráty nebo, pokud je záporné, zisku na jednotku převodu). Úkolem je určit, kolik z každé komodity se má převést na každém okraji tokové sítě, aby se minimalizovaly náklady nebo maximalizoval zisk, přičemž se musí dodržovat kapacitní omezení a nedovolit, aby se komodity jakéhokoli typu hromadily nevyužité. Tento typ problému lze formulovat jako a lineární program a vyřešen pomocí simplexní algoritmus. Mezilehlá řešení vyplývající z tohoto algoritmu, jakož i případné optimální řešení, mají speciální strukturu: každá hrana ve vstupní síti je buď nevyužita, nebo je plně využita, s výjimkou podmnožiny hran, které tvoří překlenující se vstupní síť, pro kterou může množství toku ležet mezi nulou a plnou kapacitou. V této aplikaci se také někdy nazývají unicyklické grafy rozšířené stromy a někdy se také nazývají maximální pseudolesy rozšířené lesy.^[24]

The problém s minimálním překlenovacím lesem zahrnuje nalezení překlenujícího se pseudolesu o minimální hmotnosti ve větším grafu s váženým okrajem G.Vzhledem k matroidní struktuře pseudolesů lze najít minimální hmotnostní maximální pseudoalesy od chamtivé algoritmy podobné těm pro minimální kostra problém. Gabow a Tarjan však v tomto případě našli efektivnější lineární přístup.^[2]

The pseudoarboricita grafu G je definován analogicky k arboricita jako minimální počet pseud lesů, do kterých lze rozdělit jeho okraje; ekvivalentně je to minimum k takhle G je (k, 0) - řídký nebo minimální k tak, že hrany G lze orientovat tak, aby tvořil směrovaný graf s maximálním přesahem k. Vzhledem k matroidní struktuře pseudolesů lze pseudoarboricitu vypočítat v polynomiálním čase.^[25]

A náhodný bipartitní graf s n vrcholy na každé straně jeho bipartice a s cn okraje vybrané náhodně nezávisle od každého z n² možných párů vrcholů, je kdykoli pseudoforest s vysokou pravděpodobností C je konstanta přísně menší než jedna. Tato skutečnost hraje při analýze klíčovou roli kukačka hash, datová struktura pro vyhledávání párů klíč – hodnota hledáním v jedné ze dvou hash tabulek na místech určených z klíče: lze vytvořit graf, „kukačkový graf“, jehož vrcholy odpovídají umístěním hash tabulky a jejichž hrany spojují dvě místa, kde lze jeden z klíčů najít, a algoritmus hašování kukačky uspěl při hledání umístění všech svých klíčů právě tehdy, je-li kukačkový graf pseud lesem.^[26]

Pseudoforests také hrají klíčovou roli v paralelní algoritmy pro zbarvení grafu a související problémy.^[27]

Poznámky

Reference

externí odkazy

• Weisstein, Eric W., „Jednicyklický graf“, MathWorld