Egy irányítatlan G gráf Tremaux fája G megkülönböztetett gyökerű feszítőfája , azzal a tulajdonsággal, hogy G bármely két szomszédos csúcsa ős/leszármazó kapcsolaton keresztül kapcsolódik egymáshoz. Minden mélységben kereső fa és minden Hamiltoni ösvény Tremo fa. A Tremaux-fák Charles Pierre Tremaux nevéhez fűződik, egy 19. századi francia szerzőről, aki a mélységi keresés egy változatát használta labirintusból való kilépési stratégiaként [1] [2] . A Tremaux-fákat normál feszítőfáknak is nevezik , különösen a végtelen gráfok kontextusában [3] .
A véges gráfokban, bár maga a mélységi keresés eleve szekvenciális, a Tremo fákat véletlenszerű párhuzamos algoritmussal is fel lehet építeni RNC komplexitási osztályú . Tremo fák használhatók egy gráf famélységének meghatározására, és a síksági teszt részeként annak tesztelésére, hogy egy gráf sík -e . A Tremo fák másodrendű unáris gráflogikával [en] történő leírása lehetővé a korlátozott faszélességű gráfok orientációfüggő gráftulajdonságainak hatékony felismerését a Courcelle-tétel segítségével .
Nem minden végtelen gráfnak van Tremo fája, és az ilyen fával nem rendelkező gráfokat tiltott kiskorúak leírhatják . A Tremo-fa minden megszámlálható számú csúcsot tartalmazó gráfban létezik, még akkor is, ha a végtelen mélység-első keresési változat nem tudja sikeresen tesztelni a gráf összes csúcsát. Egy végtelen gráfban egy Tremaux-fának pontosan egy végtelen úttal kell rendelkeznie a gráf minden egyes sugarához [ , és egy Tremaux-fa létezése jellemzi azokat a gráfokat, amelyek topológiai befejezései, amelyeket úgy hoznak létre, hogy minden sugárhoz hozzáadunk egy pontot a végtelenben, metrikusak . terek .
Az alábbi grafikonon az 1-3, 2-3 és 3-4 élű fa Tremaux-fa, ha a gyökere az 1-es vagy a 2-es csúcsú – a gráf bármely éle a fához tartozik, kivéve az 1-2 élt. , amely (a megadott gyökér kiválasztásakor) egy ős-utód párost köt össze.
Ha azonban ugyanannak a fának a 3. vagy 4. csomópontot választjuk gyökérként, akkor egy olyan gyökeres fát kapunk, amely nem Tremo fa, mert ezekkel a gyökerekkel az 1. és 2. csomópont már nem lesz őse/leszármazottja.
Minden véges összekapcsolt irányítatlan gráfnak legalább egy Tremo fája van. Egy ilyen fát úgy lehet létrehozni, hogy mélységi keresést használunk , és minden csúcsot (a keresés kezdeti csúcsán kívül) összekapcsolunk egy korábbi csúcsgal, amelyből az aktuális csúcsot elértük. Az így épített fát mélységi keresőfának nevezik. Ha uv egy tetszőleges él a gráfban, és u a keresés által elért két csúcs közül a korábbi, akkor v -nek az u leszármazottjainak egyik részfájához kell tartoznia a mélység-első keresési fában, mivel a keresés megtalálja a csúcsot. v szükség szerint úgy, hogy a fát vagy az egyik csúcsrészfából, vagy közvetlenül az u csúcsból nézzük . Bármely véges Tremo fa létrehozható mélység-első-faként – ha T egy véges gráf Tremo-fája, és a mélység -első-először Fedezze fel az egyes csúcsok T leszármazottait, mielőtt bármilyen másik csúcsot figyelembe venne, akkor ez szükségszerűen generálja a T -t a grafikon Mélység-Első-First-fájaként.
Egy Tremo-fa keresési probléma P-teljes , ha egy szekvenciális mélység-első keresési algoritmussal keresik, amelyben az egyes csúcsok szomszédait számsorrendben keresik [4] . Lehetséges azonban találni egy másik Tremo fát egy véletlenszerű párhuzamos algoritmus segítségével , amely azt mutatja, hogy a Tremo fák felépítése az RNC komplexitási osztályba tartozik [5] . Továbbra sem ismert, hogy a Tremo fa megszerkeszthető-e az NC osztályba tartozó determinisztikus párhuzamos algoritmussal [6] .
gráfok egyhelyes logikájában kifejezhető az a tulajdonság, hogy a kiválasztott r gyökércsúcsot tartalmazó T élhalmaz egy Tremaux-fát alkot , és egy ilyen kifejezést MSO 2 -nek nevezünk . Ez a tulajdonság a következő tulajdonságok kombinációjaként fejezhető ki:
Ha egy Tremo-fát ily módon azonosítottunk, leírhatjuk egy adott gráf orientációját egy egyhelyes másodrendű logikában, ha megadunk egy sor élt, amelyek szülőtől gyermek felé orientálódnak. A készletben nem szereplő éleket az ellenkező irányba kell elhelyezni. Ez a technika lehetővé teszi egy gráf tulajdonságainak orientációval történő leírását egy egyhelyes másodrendű logikában, ami lehetővé teszi ezen tulajdonságok hatékony tesztelését korlátozott faszélességű gráfokon a Courcelle-tétel [7] segítségével .
Ha egy gráfnak van Hamilton-útvonala , akkor ez az út (amelynek egyik vége a gyökér) is egy Tremaux-fa. Az irányítatlan gráfok halmaza, amelyre bármely Tremaux-fa ilyen formájú, ciklusokból , teljes gráfokból és kiegyensúlyozott teljes kétrészes gráfokból áll [8] .
A tremo fák szorosan kapcsolódnak a famélység fogalmához . G fa mélysége a legkisebb d számként definiálható úgy , hogy G beágyazható H részgráfjaként, amelynek d mélységű T Tremaux fája van . Egy fa korlátos mélysége egy gráfcsaládban egyenértékű egy olyan út létezésével, amely nem jelenhet meg gráf minorként a családban. Sok bonyolult számítási feladat gráfokon fix paraméterű megoldható algoritmusokkal rendelkezik, ha famélységgel paraméterezzük [9] .
A Tremaux fák kulcsszerepet játszanak a De Freysex-Rosenstil síksági tesztben is, amely azt vizsgálja, hogy egy gráf sík -e . E kritérium szerint egy G gráf sík, ha a G gráf bármely T Tremo fájára a fennmaradó élek a fa bal és jobb oldalára helyezhetők, ami megakadályozza az élek keresztezését (ezért néha előfordulhat lásd az "LP algoritmus" nevet – a Left/Right szavak rövidítése) [10] [11] .
Nem minden végtelen gráfnak van normál feszítőfája. Például egy megszámlálhatatlan csúcshalmazon lévő teljes gráfnak nincs normál feszítőfája – egy ilyen fa egy teljes gráfban csak egy útvonal lehet, de egy útvonalnak csak megszámlálható számú csúcsa van. Azonban minden gráfnak megszámlálható csúcshalmazon van egy normál feszítőfája [3] .
Még a megszámlálható gráfokban is előfordulhat, hogy a mélység-első keresés meghiúsul, ha a teljes gráfot nézzük [3] , és nem minden normál feszítőfa generálható mélységi kereséssel – hogy legyen mélység-első keresési fa, megszámlálható normál feszítőfa. csak egy végtelen útnak kell lennie, vagy egy csomópontnak végtelen számú szomszéddal (de nem mindkét esetben egyszerre).
Ha egy végtelen G gráfnak van normál feszítőfája, akkor G bármely összefüggő mollja is . Ez azt jelenti, hogy a normál feszítőfákkal rendelkező gráfokat tiltott kiskorúak is leírhatják . A tiltott minorok két osztálya közül az egyik kétrészes gráfokból áll , amelyekben az egyik rész megszámlálható, a másik megszámlálhatatlan, és bármely csúcsnak végtelen foka van. A tiltott kiskorúak egy másik osztálya bizonyos Aronshine fákból [12] származó gráfokból áll .
Ennek a leírásnak a részletei a matematika formalizálásában használt halmazelméleti axiomatika megválasztásától függenek. Különösen azokban a halmazelméleti modellekben, amelyekben Martin axiómája igaz, de a kontinuumhipotézis nem igaz, a bipartit gráfok osztálya egyetlen tiltott mollra cserélhető. Azoknál a modelleknél azonban, amelyekben a kontinuumhipotézis igaz, ez az osztály olyan gráfokat tartalmaz, amelyek összehasonlíthatatlanok a kiskorúak sorrendjében [13] .
A normál feszítőfák szorosan összefüggenek a végtelen gráf sugaraival a végtelen utak azonos irányú ekvivalenciaosztályaival. Ha egy gráfnak van egy normál feszítőfája, akkor ennek a fának pontosan egy végtelen útvonala kell legyen a gráf minden sugarához [14] .
Egy végtelen gráf felhasználható topológiai tér kialakítására úgy, hogy magát a gráfot egyszerű komplexként kezeljük, és a gráf minden sugarához hozzáadunk egy pontot a végtelenben . Egy ilyen topológiával egy gráfnak akkor és csak akkor van normál feszítőfája, ha csúcshalmaza zárt halmazok megszámlálható uniójává particionálható . Sőt, ez a topológiai tér akkor és csak akkor reprezentálható metrikus térrel , ha a gráfnak van normál feszítőfája [14] .