Suuntaamattoman graafin G Tremaux-puu on G : n erottuva-juurinen virittävä puu , jolla on ominaisuus, että mitkä tahansa kaksi vierekkäistä G :n kärkeä liittyvät toisiinsa esi- ja jälkeläisten suhteen. Kaikki syvyyden etsintäpuut ja kaikki Hamiltonin polut ovat Tremo-puita. Tremaux-puut on nimetty Charles Pierre Tremaux'n mukaan, 1800-luvulla eläneen ranskalaisen kirjailijan mukaan, joka käytti syvyyshaun muunnelmaa labyrinttipoistumisstrategiana [1] [2] . Tremaux-puita kutsutaan myös normaaleiksi virittäviksi puiksi , erityisesti äärettömien graafien yhteydessä [3] .
Vaikka äärellisissä kaavioissa itse syvyyshaku on luonnostaan peräkkäinen, Tremo-puita voidaan rakentaa satunnaistetulla rinnakkaisalgoritmilla RNC :n kompleksisuusluokassa . Tremopuita voidaan käyttää graafin puun syvyyden määrittämiseen ja osana tasomaisuustestiä testata, onko kuvaaja tasomainen . Tremo-puiden kuvaaminen toisen kertaluvun unaarigrafiikkalogiikalla tekee mahdolliseksi tunnistaa tehokkaasti orientaatiosta riippuvat graafin ominaisuudet graafisille , joilla on rajoitettu puunleveys Courcellen lauseen avulla .
Jokaisella äärettömällä graafilla ei ole Tremo-puuta, ja kielletyt alaikäiset voivat kuvata graafit, joissa tällaista puuta ei ole . Tremo-puu on olemassa missä tahansa graafissa, jossa on laskettava määrä pisteitä, vaikka ääretön syvyys-ensimmäinen hakumuunnos ei pystyisi testaamaan graafin kaikkia pisteitä. Äärettömässä graafissa Tremaux-puulla täytyy olla täsmälleen yksi ääretön polku jokaiselle graafin säteelle , ja Tremaux-puun olemassaolo luonnehtii graafia, joiden topologiset täydennykset, jotka muodostetaan lisäämällä piste äärettömyyteen kullekin säteelle, ovat metrinen . tilat .
Alla olevassa kaaviossa puu, jonka reunat ovat 1–3, 2–3 ja 3–4, on Tremaux-puu, jos sen juuri on kärki 1 tai kärki 2 – mikä tahansa graafin reuna kuuluu puuhun paitsi reuna 1–2 , joka (valittaessa määritettyä juuria) yhdistää esi-isän ja jälkeläisen parin.
Jos kuitenkin valitsemme saman puun juureksi solmun 3 tai 4, saadaan juurtunut puu, joka ei ole Tremo-puu, koska näillä juurilla solmut 1 ja 2 eivät ole enää esi- tai jälkeläisiä.
Jokaisella äärellisellä yhdistetyllä suuntaamattomalla graafilla on vähintään yksi Tremo-puu. Tällainen puu voidaan rakentaa käyttämällä syväyshakua ja yhdistämällä jokainen kärkipiste (muu kuin haun alkupiste) aikaisempaan kärkeen, josta nykyiseen kärkipisteeseen haettiin. Tällä tavalla rakennettu puu tunnetaan syvyysetsintäpuuna. Jos uv on mielivaltainen reuna graafissa ja u on aikaisempi kahdesta haun saavuttamasta pisteestä, niin v :n tulee kuulua u :n jälkeläisten alipuuhun syvyysensimmäisessä hakupuussa , koska haku löytää kärjen. v tarvittaessa katsomalla kyseistä puuta joko yhdestä kärkien alipuusta tai suoraan kärjestä u . Mikä tahansa äärellinen Tremo-puu voidaan muodostaa Depth-First-First -puuna – jos T on äärellisen graafin Tremo-puu ja Syvyys -ensimmäinen Tutki kunkin kärjen T :n jälkeläisiä ennen kuin harkitset muita kärkeä, tämä on välttämättä luo T graafin Syvyys-ensimmäisenä-puuna.
Tremo- puuhakutehtävä on P-täydellinen , jos sitä etsitään käyttämällä peräkkäistä syvyys-ensimmäistä hakualgoritmia, jossa kunkin kärjen naapurit etsitään numeerisessa järjestyksessä [4] . On kuitenkin mahdollista löytää toinen Tremo-puu käyttämällä satunnaistettua rinnakkaisalgoritmia , joka osoittaa, että Tremo-puiden rakenne kuuluu RNC :n kompleksisuusluokkaan [5] . On edelleen epäselvää, voidaanko Tremo-puu rakentaa deterministisellä rinnakkaisalgoritmilla, joka kuuluu NC -luokkaan [6] .
On mahdollista ilmaista ominaisuus, että reunojen joukko T valitulla juuripisteellä r muodostaa Tremaux-puun, toisen kertaluvun graafien yksipaikkalogiikassa , ja tällaista lauseketta kutsutaan nimellä MSO 2 . Tämä ominaisuus voidaan ilmaista seuraavien ominaisuuksien yhdistelmänä:
Kun Tremo-puu on tunnistettu tällä tavalla, voidaan kuvata tietyn graafin suuntausta yksipaikkaisessa toisen kertaluvun logiikassa määrittämällä joukko reunoja, jotka on suunnattu vanhemmalta lapselle. Reunat, jotka eivät sisälly tähän sarjaan, on suunnattava vastakkaiseen suuntaan. Tämä tekniikka mahdollistaa graafin ominaisuuksien kuvaamisen orientaatiolla yksipaikkaisessa toisen kertaluvun logiikassa, mikä mahdollistaa näiden ominaisuuksien tehokkaan testaamisen rajallisella puunleveydellä Courcellen lauseen [7] avulla .
Jos graafissa on Hamiltonin polku , niin tämä polku (jossa on yksi pää) on myös Tremaux-puu. Suuntaamattomien graafien joukko, jolle millä tahansa Tremaux-puulla on tämä muoto, koostuu sykleistä , täydellisistä kaavioista ja tasapainotetuista täydellisistä kaksiosaisista graafista [8] .
Tremopuut liittyvät läheisesti puun syvyyden käsitteeseen . G :n puun syvyys voidaan määritellä pienimmäksi luvuksi d siten, että G voidaan upottaa H :n aligraafiksi, jolla on Tremaux-puu T , jonka syvyys on d . Graafiperheen puun rajattu syvyys vastaa sellaisen polun olemassaoloa, joka ei voi esiintyä graafin sivuarvona suvussa. Monissa monimutkaisissa graafien laskentaongelmissa on kiinteäparametriset ratkaistavissa olevat -algoritmit, jos ne parametroidaan puun syvyyden mukaan [9] .
Tremaux-puilla on myös keskeinen rooli De Freysex-Rosenstil tasomaisuustestissä , jolla testataan, onko graafi tasomainen . Tämän kriteerin mukaan graafi G on tasomainen, jos missä tahansa graafin G Tremo-puussa T loput reunat voidaan sijoittaa puun vasemmalle ja oikealle puolelle, mikä estää reunojen risteämisen (tästä syystä voit joskus katso nimi "LP-algoritmi" - lyhenne sanoista Left / Right) [10] [11] .
Jokaisella äärettömällä graafilla ei ole normaalia virittävää puuta. Esimerkiksi täydellisellä graafilla lukemattomalla joukolla pisteitä ei ole normaalia virittävää puuta - tällainen puu täydellisessä graafissa voi olla vain polku, mutta polulla on vain laskettava määrä pisteitä. Kuitenkin millä tahansa graafilla laskettavassa pistejoukossa on normaali virittävä puu [3] .
Jopa laskettavissa kaavioissa syvyysensimmäinen haku voi epäonnistua, kun tarkastellaan koko kuvaajaa [3] , eikä jokaista normaalia virittävää puuta voida luoda syvyys-ensimmäisellä haulla - ollakseen syvyys-ensin hakupuu, laskettava normaali virittävä puu. on oltava vain yksi ääretön polku tai yksi solmu, jolla on ääretön määrä naapureita (mutta ei molempia tapauksia samanaikaisesti).
Jos äärettömällä graafilla G on normaali virittävä puu, niin on myös millä tahansa G :n yhdistetyllä mollilla . Tämä tarkoittaa, että kielletyt alaikäiset voivat kuvata kaavioita, joissa on normaaleja virittäviä puita . Toinen kahdesta kiellettyjen alaikäisten luokasta koostuu kaksiosaisista graafista , joissa yksi osa on laskettava ja toinen laskematon ja millä tahansa kärjellä on ääretön aste. Toinen kiellettyjen alaikäisten luokka koostuu tietyistä Aronshine-puista johdetuista kaavioista [12] .
Tämän kuvauksen yksityiskohdat riippuvat matematiikan formalisoinnissa käytetyn joukkoteoria-aksiomatian valinnasta. Erityisesti joukkoteorian malleissa, joissa Martinin aksiooma on totta, mutta jatkumohypoteesi ei pidä paikkaansa, kaksiosaisten graafien luokka voidaan korvata yhdellä kielletyllä mollilla. Kuitenkin malleissa, joissa jatkumohypoteesi pitää paikkansa, tämä luokka sisältää graafit, jotka ovat verrattavissa alaikäisten järjestykseen [13] .
Normaalit virittävät puut liittyvät läheisesti äärettömän graafin säteisiin samaan suuntaan kulkevien äärettömien polkujen ekvivalenssiluokkiin. Jos graafissa on normaali virittävä puu, sillä on oltava täsmälleen yksi ääretön polku kutakin graafin sädettä kohden [14] .
Ääretöntä graafia voidaan käyttää topologisen avaruuden muodostamiseen käsittelemällä itse graafia yksinkertaisena kompleksina ja lisäämällä pisteen äärettömyyteen jokaiselle graafin säteelle. Tällaisella topologialla graafilla on normaali virittävä puu, jos ja vain jos sen kärkijoukko voidaan osioida laskettavaksi suljettujen joukkojen liitoksi . Lisäksi tämä topologinen avaruus voidaan esittää metrisellä avaruudella, jos ja vain jos graafissa on normaali virittävä puu [14] .