STUDIA UNIVERSITATIS

AMBIENTUM BIOETHICA BIOLOGIA CHEMIA DIGITALIA DRAMATICA EDUCATIO ARTIS GYMNAST. ENGINEERING EPHEMERIDES EUROPAEA GEOGRAPHIA GEOLOGIA HISTORIA HISTORIA ARTIUM INFORMATICA IURISPRUDENTIA MATHEMATICA MUSICA NEGOTIA OECONOMICA PHILOLOGIA PHILOSOPHIA PHYSICA POLITICA PSYCHOLOGIA-PAEDAGOGIA SOCIOLOGIA THEOLOGIA CATHOLICA THEOLOGIA CATHOLICA LATIN THEOLOGIA GR.-CATH. VARAD THEOLOGIA ORTHODOXA THEOLOGIA REF. TRANSYLVAN ROMÂNA ENGLISH INFO PARTENERI ADRESE DE CONTACT ACCES PARTENERI FORMULAR ABONAMENT NEWSLETTER & DOWNLOAD CELE MAI NOI APARITII APARITII ÎN ANUL CURENT TOATA ARHIVA STUDIA CAUTARE ÎN ARHIVA ISTORIE PREZENT SCOP SI OBIECTIVE ECHIPA


	Rezumat articol ediţie STUDIA UNIVERSITATIS BABEŞ-BOLYAI În partea de jos este prezentat rezumatul articolului selectat. Pentru revenire la cuprinsul ediţiei din care face parte acest articol, se accesează linkul din titlu. Pentru vizualizarea tuturor articolelor din arhivă la care este autor/coautor unul din autorii de mai jos, se accesează linkul din numele autorului.


	STUDIA MATHEMATICA - Ediţia nr.4 din 2014

	Articol:	RECONSTRUCTIBILITY OF TREES FROM SUBTREE SIZE FREQUENCIES. Autori: .


	Rezumat: Let T be a tree on n vertices. The subtree frequency vector (STFvector) of T, denoted by stf(T) is a vector of length n whose kth coordinate is thenumber of subtrees of T that have exactly k vertices. We present algorithms for calculating the subtree frequencies.We give a combinatorial interpretation for the first few and last few entries of the STF-vector. The main question we investigate - originally motivated by the problem of determining molecule structure from mass spectrometry data - is whether T can be reconstructed from stf(T). We show that there exist examples of non-isomorphic pairs of unlabeled free (i.e.unrooted) trees that are STF-equivalent, i.e. have identical subtree frequency vectors. 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 also show that for special kinds of trees (e.g. paths, stars and trees containing a single vertex of degree larger than 2), the tree is reconstructible from the subtree frequencies. We consider a version of the problem for rooted trees, where only subtrees containing the root are counted. Finally, we formulate some conjectures and open problems and outline further research directions. Mathematics Subject Classification (2010): 05C05. Keywords: Tree reconstruction, subtree size frequencies.




			Revenire la pagina precedentă