Reconstructibility of Tree Graphs

Bartha, Dénes

Reconstructibility of Tree Graphs

Subject: Műszaki tudományok/Informatikai tudományok
trees
tree reconstruction
Parikh vectors
jumbled strings
labeled trees
weighted trees
subtree size frequencies
rooted directed trees
Informatika D. I./Numerikus és szimbolikus számítások
fák
fák rekonstrukciója
Parikh vektor
összekevert sztringek
címkézett fák
súlyozott fák
részfa-méret gyakoriság
gyökeres irányított fák

URI: http://hdl.handle.net/10831/85503

Link to Library Catalogue: https://opac.elte.hu/Record/opac-EUL01-1107617

MTMT: 33880556

DOI: 10.15476/ELTE.2021.095

Abstract:

Az általunk megadott STF-vektor polinom reprezentációját használva algoritmusokat adunk meg az STF-vektor kiszámítására gyökérmentes fák esetén. Megmutatjuk hogy nem-izomorf, címkézetlen gyökérmentes fák esetén találhatóak STF-ekvivalens párok, mely fák STF-polinomja megegyezik. Számítógépes keresés segítségével az összes kis méretű fa párosok közül megkerestük az STF-ekvivalenseket, melyekről statisztikát közlünk. Megmutatjuk hogy végtelenül sok STF-ekvivalens pár található az általunk konstruált végtelen családok példáin keresztül. Továbbá mutatunk néhány speciális fát, ahol a fák rekonstruálhatóak az STF-vektoraikból.

Megvizsgáljuk, hogy egy T fa mikor rekonstruálható a Parikh-vektorainak multihalmazából részfák, utak illetve maximális hosszúságú utak esetén. Algoritmusokat adunk meg a Parikh-vektorok multihalmazainak kiszámítására részfák, utak, maximális utak esetén, címkézetlen, címkézett valamint súlyozott esetekben. Végtelen nem-izomorf (Parikh-vektorainak multihalmazain értelmezve) ekvivalens családokat keresünk részfa, utak illetve maximális hosszúságú utakra, címkézetlen, címkézett és súlyozott esetekben. Számítógéppel kis csúcsszámú fákra az összes ilyen ekvivalens példát megkerestük. Rekonstrukciós algoritmusokat, valamint nem rekonstruálhatósági eredményeket mutatunk be és kiterjesztjük a polinomos eljárást általános és speciális fa-osztályokra, melyet korábban "jumbled string"-ekre illetve súlyozott stringekre alkalmaztak.

Az RSTF-vektor (részfa-méret gyakoriság vektora) kiszámításához algoritmusokat adunk meg, melyek a (jól-formált) RSTF-polinomok reprezentációján alapszanak. Megmutatjuk hogy léteznek nem-izomorf gyökeres, irányított fa párok, melyek RSTF-ekvivalensek, azaz a hozzájuk tartozó RSTF-vektor megegyeznek. Számítógéppel az összes ilyen RSTF-ekvivalens párt felkutattuk kis méretű, gyökeres, irányított fák esetén. Végtelen RSTF-ekvivalens családokat mutatunk valamint megadunk egy módszert, mellyel bármely RSTF-ekvivalens nem-izomorf gyökeres, irányított fa párosból tudunk végtelen RSTF-ekvivalens családokat alkotni. Bemutatjuk az RRDT algoritmust, melynek segítségével gyökeres, irányított fákat tudunk rekonstruálni a hozzájuk tartozó RSTF-polinomokból.

Abstract:

We present a polynomial representation of the STF-vector (subtree size frequencies) that we use for creating algorithms to calculate the vector from free trees. We show that there exist examples of non-isomorphic pairs of unlabeled free trees that are STF-equivalent. Using exhaustive computer search, we determine all such pairs for small sizes. We show that there are infinitely many non-isomorphic STF-equivalent pairs of trees by constructing infinite families of examples. We present reconstructibility results for special kinds of trees. We investigate when tree T can be reconstructed from the multiset of Parikh vectors of all of its subtrees, or all of its paths, or all of its maximal paths. We present algorithms to calculate the multiset of Parikh vectors based on subree, path and maximal path information for unlabeled, labeled and weighted cases. We present infinite families of non-isomorphic equivalent (multisets of Parikh vector) trees for subtree, path and maximal path information in unlabeled, labeled and weighted cases. We also determined all such pairs for small sizes using exhaustive computer search. We present reconstruction algorithms and non-reconstructibility results, and extend the polynomial method, previously applied to jumbled and weighted strings. We present a polynomial representation of the RSTF-vector (rooted subtree size frequencies) and well-formed polynomial representation of the vector that we use for creating algorithms to calculate the vector from free trees. We show that there exist examples of non-isomorphic pairs of rooted directed trees that are RSTF-equivalent. Using exhaustive computer search, we determine all such pairs for small sizes. We present infinite families of RSTF-equivalent rooted directed trees and show a method to create such families from any non-isomorphic rooted directed RSTF-equivalent trees. We present the RRDT algorithm for reconstructing rooted directed trees from their RSTF-polynomial.

Show full item record