797:) is a rooted tree in which an ordering is specified for the children of each vertex. This is called a "plane tree" because an ordering of the children is equivalent to an embedding of the tree in the plane, with the root at the top and the children of each vertex lower than that vertex. Given an embedding of a rooted tree in the plane, if one fixes a direction of children, say left to right, then an embedding gives an ordering of the children. Conversely, given an ordered tree, and conventionally drawing the root at the top, then the child vertices in an ordered tree can be drawn left-to-right, yielding an essentially unique planar embedding.
40:
896:
For any three vertices in a tree, the three paths between them have exactly one vertex in common. More generally, a vertex in a graph that belongs to three shortest paths among three vertices is called a median of these vertices. Because every three vertices in a tree have a unique median, every tree
174:
or out-tree—or making all its edges point towards the root—in which case it is called an anti-arborescence or in-tree. A rooted tree itself has been defined by some authors as a directed graph. A rooted forest is a disjoint union of rooted trees. A rooted forest may be directed, called a directed
506:
is a tree in which one vertex has been designated the root. The edges of a rooted tree can be assigned a natural orientation, either away from or towards the root, in which case the structure becomes a directed rooted tree. When a directed rooted tree has an orientation away from the root, it is
2164:
investigated electrical circuits and found a relation between the number (n) of wires/resistors (branches), the number (m) of junctions (vertices), and the number (μ) of loops (faces) in the circuit. He proved the relation via an argument relying on trees. See: Kirchhoff, G. R. (1847)
744:
in particular. The root has depth zero, leaves have height zero, and a tree with only a single vertex (hence both a root and leaf) has depth and height zero. Conventionally, an empty tree (a tree with no vertices, if such are allowed) has depth and height −1.
169:
that are trees in graph theory, although such data structures are generally rooted trees. A rooted tree may be directed, called a directed rooted tree, either making all its edges point away from the root—in which case it is called an
486:(or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is acyclic.
410:
of trees. Trivially so, each connected component of a forest is a tree. As special cases, the order-zero graph (a forest consisting of zero trees), a single tree, and an edgeless graph, are examples of forests. Since for every tree
489:
As with directed trees, some authors restrict the phrase "directed forest" to the case where the edges of each connected component are all directed towards a particular vertex, or all directed away from a particular vertex (see
1509:
1277:
1404:
1101:
364:(or even (−1)-connected) in algebraic topology, unlike non-empty trees, and violates the "one more vertex than edges" relation. It may, however, be considered as a forest consisting of zero trees.
467:(DAG) whose underlying undirected graph is a tree. In other words, if we replace its directed edges with undirected edges, we obtain an undirected graph that is both connected and acyclic.
150:(DAG) whose underlying undirected graph is a tree. A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest.
470:
Some authors restrict the phrase "directed tree" to the case where the edges are all directed towards a particular vertex, or all directed away from a particular vertex (see
573:, p. 15). Rooted trees, often with an additional structure such as an ordering of the neighbors at each vertex, are a key data structure in computer science; see
360:(graph with no vertices) is generally not considered to be a tree: while it is vacuously connected as a graph (any two vertices can be connected by a path), it is not
912:-vertex tree has a centroid consisting of one vertex or two adjacent vertices. In the first case removal of the vertex splits the tree into subtrees of fewer than
2169:
1430:
1198:
908:
consisting of one vertex or two adjacent vertices. The center is the middle vertex or middle two vertices in every longest path. Similarly, every
2041:
1316:
2412:
740:). The depth of a tree is the maximum depth of any vertex. Depth is commonly needed in the manipulation of the various self-balancing trees,
179:
or out-forest—or making all its edges point towards the root in each rooted tree—in which case it is called an anti-branching or in-forest.
422:, we can easily count the number of trees that are within a forest by subtracting the difference between total vertices and total edges.
916:/2 vertices. In the second case, removal of the edge between the two centroidal vertices splits the tree into two subtrees of exactly
2562:
1555:
1303:
1182:
2167:"Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird"
997:
810:. A graph is bipartite if and only if it contains no cycles of odd length. Since a tree contains no cycles at all, it is bipartite.
1617:
and several path graphs attached to it. More formally, a tree is starlike if it has exactly one vertex of degree greater than 2.
379:(or outer vertex, terminal vertex or leaf) is a vertex of degree 1. A branch vertex in a tree is a vertex of degree at least 3.
2743:
2729:
2718:
2095:
2070:
2035:
1998:
1970:
1922:
1897:
1872:
2369:
89:
2233:
2176:(On the solution of equations to which one is led by the investigation of the linear distribution of galvanic currents),
247:
2156:(Nürnberg, (Germany): Bauer und Raspe, 1847), presented a proof of Euler's polyhedron theorem which relies on trees on
2018:
2556:
2462:
2406:
2120:
175:
rooted forest, either making all its edges point away from the root in each rooted tree—in which case it is called a
2639:
in Proc. 8th
International Joint Conference on Artificial Intelligence (IJCAI 1983), Karlsruhe, Germany, August 1983
2636:
Kim, Jin H.; Pearl, Judea (1983), "A computational model for causal and diagnostic reasoning in inference engines",
2530:
in Proc. 15th
Conference on Uncertainty in Artificial Intelligence (UAI 1999), Stockholm, Sweden, July–August 1999
2306:
Tran, Ngoc Mai; Buck, Johannes; Klüppelberg, Claudia (February 2024), "Estimating a directed tree for extremes",
2149:
2849:
2762:
2166:
550:
2434:
2757:
1958:
829:
491:
471:
176:
171:
728:
of a vertex in a rooted tree is the length of the longest downward path to a leaf from that vertex. The
17:
2022:
2854:
2392:
336:
2457:, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, p. 573,
407:
386:(or series-reduced tree) is a tree in which there is no vertex of degree 2 (enumerated at sequence
136:
1138:
Counting the number of unlabeled free trees is a harder problem. No closed formula for the number
878:, has at least two terminal vertices (leaves). This minimal number of leaves is characteristic of
924:
324:
2733:
2652:
1683:
848:
trees. Generalizing the existence of depth-first-search trees, every connected graph with only
580:
In a context where trees typically have a root, a tree without any designated root is called a
464:
147:
2452:
2136:
2157:
1732:
1687:
372:
158:
110:
50:
923:
The maximal cliques of a tree are precisely its edges, implying that the class of trees has
2692:
2628:
2543:
2292:
2254:
1737:
845:
303:
of them, then the above statements are also equivalent to any of the following conditions:
273:
223:
124:
2752:
591:
is a tree in which each vertex is given a unique label. The vertices of a labeled tree on
8:
1622:
1115:
989:
941:
654:
574:
288:
233:
117:
62:
2637:
840:. More specific types spanning trees, existing in every connected finite graph, include
2828:
2448:
2428:
2311:
2195:
1655:
841:
955:
2799:
2795:
2739:
2714:
2683:
2601:
2552:
2458:
2402:
2391:
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2022).
2116:
2091:
2066:
2031:
1994:
1966:
1918:
1893:
1868:
1157:
2194:
DeBiasio, Louis; Lo, Allan (2019-10-09). "Spanning trees with few branch vertices".
2820:
2791:
2678:
2591:
2582:
2577:
2528:
2321:
2280:
2242:
2161:
1646:
1123:
1111:
861:
524:
357:
166:
162:
106:
75:
612:
is a labeled rooted tree where the vertex labels respect the tree order (i.e., if
2770:
2688:
2624:
2518:
2365:
2288:
2250:
2173:
1659:
is a tree in which all vertices are within distance 2 of a central path subgraph.
1650:
is a tree in which all vertices are within distance 1 of a central path subgraph.
857:
807:
219:
154:
121:
853:
657:
to the root; every vertex has a unique parent, except the root has no parent. A
2058:
1986:
1726:
1119:
608:
261:
2843:
2803:
2708:
2666:
2605:
2325:
2014:
1706:
1692:
1609:
1107:
849:
814:
187:
1548:
1, 1, 2, 4, 9, 20, 48, 115, 286, 719, 1842, 4766, 12486, 32973, … (sequence
1504:{\displaystyle r(n)\sim D\alpha ^{n}n^{-3/2}\quad {\text{as }}n\to \infty ,}
1272:{\displaystyle t(n)\sim C\alpha ^{n}n^{-5/2}\quad {\text{as }}n\to \infty ,}
958:, which naturally show a stronger result: the number of trees with vertices
2612:
2573:
2284:
1721:
1675:
1399:{\displaystyle \lim _{n\to \infty }{\frac {t(n)}{C\alpha ^{n}n^{-5/2}}}=1.}
905:
898:
818:
773:
98:
2654:
M.S. Thesis, Dept. of
Computer Science, University of Victoria, BC, Canada
2308:
Journal of the Royal
Statistical Society Series B: Statistical Methodology
1122:.) The similar problem of counting all the subtrees regardless of size is
767:
558:
361:
1175:
1, 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159, … (sequence
331:
includes at least one vertex with zero or one incident edges. (That is,
2832:
2596:
1679:
1570:
890:
879:
750:
2615:; Sumner, David (1980), "The dichromatic number of an oriented tree",
2578:"The number of homeomorphically irreducible trees, and other species"
1956:
1716:
1711:
135:
path, or equivalently an acyclic undirected graph, or equivalently a
2824:
2246:
2316:
2200:
1993:(5th ed.). Springer Science & Business Media. p. 28.
741:
442:
143:
2545:
Graph Theory with
Applications to Engineering and Computer Science
2346:
2344:
2342:
2340:
2338:
2336:
2334:
131:
is an undirected graph in which any two vertices are connected by
2782:
Jerrum, Mark (1994), "Counting trees in a graph is #P-complete",
2775:
The Art of
Computer Programming Volume 1: Fundamental Algorithms
2520:
Lists, Decisions and Graphs. With an
Introduction to Probability
1409:
This is a consequence of his asymptotic estimate for the number
2331:
1118:. (Cayley's formula is the special case of spanning trees in a
515:; when it has an orientation towards the root, it is called an
2651:
Li, Gang (1996), "Generation of Rooted Trees and Free Trees",
2482:
2470:
1912:
1887:
1761:
1749:
1096:{\displaystyle {n-2 \choose d_{1}-1,d_{2}-1,\ldots ,d_{n}-1}.}
1154:
893:. The number of leaves is at least the maximum vertex degree.
39:
2617:
2065:. Springer Science & Business Media. pp. 167–168.
1550:
1298:
1177:
391:
387:
211:
that satisfies any of the following equivalent conditions:
2390:
2208:
2013:
1626:
is a tree which consists of a single internal vertex (and
709:
is any other vertex on the tree that shares a parent with
2271:
Kozlov, Dmitry N. (1999). "Complexes of directed trees".
1985:
2368:. U.S. National Institute of Standards and Technology.
1862:
2227:
Chen, Wai-kai (1966). "On directed trees and directed
2088:
1917:. Springer Science & Business Media. p. 108.
2137:"On the theory of the analytical forms called trees,"
2030:. Springer Science & Business Media. p. 52.
1940:
1938:
1936:
1934:
1433:
1319:
1201:
1000:
2113:
1782:
1780:
1778:
1776:
761:) is a rooted tree in which each vertex has at most
2713:(3rd ed.), Berlin, New York: Springer-Verlag,
2669:(1991), "Trees with 1-factors and oriented trees",
2305:
2110:
2007:
736:
of a vertex is the length of the path to its root (
1931:
1503:
1398:
1271:
1095:
2727:
2024:Algorithms and Data Structures: The Basic Toolbox
1991:Combinatorial Optimization: Theory and Algorithms
1773:
1527:
1084:
1004:
406:is an undirected acyclic graph or equivalently a
2841:
2516:
2350:
1767:
1755:
1321:
832:, which is a tree that contains every vertex of
681:or is (recursively) an ascendant of a parent of
537:if and only if the unique path from the root to
232:is acyclic, and a simple cycle is formed if any
186:was coined in 1857 by the British mathematician
2527:Dasgupta, Sanjoy (1999), "Learning polytrees",
2517:Bender, Edward A.; Williamson, S. Gill (2010),
1979:
1950:
1915:Design and Analysis of Approximation Algorithms
697:or is (recursively) a descendant of a child of
2811:Otter, Richard (1948), "The Number of Trees",
2057:
1890:Graph Theoretic Methods in Multiagent Networks
1633:leaves). In other words, a star tree of order
1582:vertices arranged in a line, so that vertices
2148:However it should be mentioned that in 1847,
2104:
2085:
1856:
1797:
1795:
2611:
2051:
1802:
2777:(3rd ed.), Addison-Wesley Professional
2572:
2231:-trees of a digraph and their generation".
2214:
1913:Ding-Zhu Du; Ker-I Ko; Xiaodong Hu (2011).
1867:. Courier Dover Publications. p. 288.
732:of the tree is the height of the root. The
677:is any vertex that is either the parent of
44:A labeled tree with 6 vertices and 5 edges.
2193:
1892:. Princeton University Press. p. 38.
1792:
2682:
2595:
2315:
2266:
2264:
2199:
1888:Mehran Mesbahi; Magnus Egerstedt (2010).
1674:edges at each vertex. These arise as the
771:, while 3-ary trees are sometimes called
2635:
2551:, Englewood, New Jersey: Prentice-Hall,
2526:
1963:Handbook of Graph Theory, Second Edition
1906:
1850:
1834:
693:is any vertex that is either a child of
2706:
2488:
2476:
2447:
954:labeled vertices. A classic proof uses
765:children. 2-ary trees are often called
570:
27:Undirected, connected and acyclic graph
14:
2842:
2781:
2665:
2270:
2261:
1845:
1843:
1818:
1127:
2810:
2769:
2363:
2160:. Also in 1847, the German physicist
1829:
1827:
1813:
1811:
1523:
1189:
2372:from the original on 8 February 2015
2226:
2090:. McGraw-Hill Science. p. 747.
1881:
1613:consists of a central vertex called
2541:
2234:SIAM Journal on Applied Mathematics
2063:Sets, Logic and Maths for Computing
1944:
1840:
1786:
1106:A more general problem is to count
595:vertices (for nonnegative integers
569:are comparable in this tree-order (
250:if any single edge is removed from
146:, or singly connected network is a
24:
2700:
2650:
2501:
1865:Combinatorics for Computer Science
1824:
1808:
1495:
1331:
1263:
1160:is known. The first few values of
1133:
1008:
356:As elsewhere in graph theory, the
25:
2866:
2454:Enumerative Combinatorics, Vol. I
2415:from the original on 16 July 2023
1562:
717:is a vertex with no children. An
599:) are typically given the labels
371:(or inner vertex) is a vertex of
2047:from the original on 2015-09-08.
1863:Stanley Gill Williamson (1985).
1641:with as many leaves as possible.
936:
721:is a vertex that is not a leaf.
299:has finitely many vertices, say
142:A directed tree, oriented tree,
38:
2568:from the original on 2019-05-17
2494:
2441:
2397:(4th ed.). Section B.5.3,
2384:
2356:
2299:
2273:Journal of Combinatorial Theory
2220:
2187:
2129:
2079:
1957:Jonathan L. Gross; Jay Yellen;
1528:Flajolet & Sedgewick (2009)
1483:
1420:of unlabeled rooted trees with
1251:
1192:proved the asymptotic estimate
864:graphs do not have such a tree.
780:
527:on the vertices of a tree with
246:is connected, but would become
2784:Information Processing Letters
2738:, Cambridge University Press,
1492:
1443:
1437:
1348:
1342:
1328:
1260:
1211:
1205:
931:
497:
193:
90:Table of graphs and parameters
13:
1:
2510:
2364:Black, Paul E. (4 May 2007).
2178:Annalen der Physik und Chemie
1593:are connected by an edge for
1530:, chap. VII.5, p. 475).
836:and whose edges are edges of
800:
634:is smaller than the label of
477:
433:number of trees in a forest.
345:has no simple cycles and has
287:can be connected by a unique
2796:10.1016/0020-0190(94)00085-9
2684:10.1016/0012-365X(91)90061-6
2351:Bender & Williamson 2010
2111:Alexander Schrijver (2003).
1768:Bender & Williamson 2010
1756:Bender & Williamson 2010
1114:, which is addressed by the
7:
2758:Encyclopedia of Mathematics
2401:: MIT Press. p. 1174.
2399:Binary and positional trees
1700:
649:is the vertex connected to
436:
10:
2871:
2707:Diestel, Reinhard (2005),
2394:Introduction to Algorithms
1965:. CRC Press. p. 116.
1803:Harary & Sumner (1980)
1670:is the infinite tree with
757:(for nonnegative integers
440:
375:at least 2. Similarly, an
397:
88:
74:
61:
49:
37:
32:
2433:: CS1 maint: location (
2115:. Springer. p. 34.
1743:
1533:The first few values of
523:. The tree-order is the
461:singly connected network
323:is connected, and every
2576:; Prins, Geert (1959),
2215:Harary & Prins 1959
1682:, and in the theory of
990:multinomial coefficient
867:Every finite tree with
207:is an undirected graph
198:
2735:Analytic Combinatorics
2542:Deo, Narsingh (1974),
2326:10.1093/jrsssb/qkad165
2285:10.1006/jcta.1999.2984
2140:Philosophical Magazine
2086:Kenneth Rosen (2011).
1851:Kim & Pearl (1983)
1505:
1400:
1273:
1097:
944:states that there are
889:, is attained only by
882:; the maximal number,
824:Every connected graph
641:In a rooted tree, the
465:directed acyclic graph
148:directed acyclic graph
2813:Annals of Mathematics
2773:(November 14, 1997),
1989:; Jens Vygen (2012).
1733:Tree (data structure)
1688:statistical mechanics
1506:
1401:
1274:
1126:in the general case (
1098:
988:respectively, is the
813:Every tree with only
665:is a vertex of which
561:if the ends of every
310:is connected and has
260:is connected and the
226:(contains no cycles).
153:The various kinds of
2850:Trees (graph theory)
2728:Flajolet, Philippe;
2671:Discrete Mathematics
2184:(12) : 497–508.
1738:Unrooted binary tree
1526:, chap. 2.3.4.4 and
1516:D ≈ 0.43992401257...
1431:
1317:
1199:
998:
852:many vertices has a
846:breadth-first search
630:, then the label of
283:Any two vertices in
127:undirected graph. A
120:, or equivalently a
2449:Stanley, Richard P.
1637:is a tree of order
1310:symbol means that
1116:matrix tree theorem
817:many vertices is a
575:tree data structure
2645:, pp. 190–193
2597:10.1007/BF02559543
2536:, pp. 134–141
2172:2023-07-20 at the
2154:Geometrie der Lage
1690:they are known as
1501:
1396:
1335:
1294:≈ 2.95576528565...
1269:
1093:
842:depth-first search
669:is the parent. An
2815:, Second Series,
2745:978-0-521-89806-5
2730:Sedgewick, Robert
2720:978-3-540-26183-4
2150:K.G.C. von Staudt
2097:978-0-07-338309-5
2072:978-1-4471-2499-3
2037:978-3-540-77978-0
2000:978-3-642-24488-9
1972:978-1-4398-8018-0
1924:978-1-4614-1701-9
1899:978-1-4008-3535-5
1874:978-0-486-42076-9
1487:
1388:
1320:
1255:
1158:graph isomorphism
1082:
904:Every tree has a
622:for two vertices
517:anti-arborescence
335:is connected and
167:underlying graphs
113:are connected by
109:in which any two
95:
94:
16:(Redirected from
2862:
2855:Bipartite graphs
2835:
2806:
2778:
2771:Knuth, Donald E.
2766:
2748:
2723:
2695:
2686:
2661:
2659:
2646:
2644:
2631:
2608:
2599:
2590:(1–2): 141–162,
2583:Acta Mathematica
2569:
2567:
2550:
2537:
2535:
2523:
2505:
2498:
2492:
2486:
2480:
2474:
2468:
2467:
2445:
2439:
2438:
2432:
2424:
2422:
2420:
2388:
2382:
2381:
2379:
2377:
2360:
2354:
2348:
2329:
2328:
2319:
2303:
2297:
2296:
2268:
2259:
2258:
2230:
2224:
2218:
2212:
2206:
2205:
2203:
2191:
2185:
2162:Gustav Kirchhoff
2146: : 172–176.
2133:
2127:
2126:
2108:
2102:
2101:
2083:
2077:
2076:
2055:
2049:
2048:
2046:
2029:
2011:
2005:
2004:
1983:
1977:
1976:
1954:
1948:
1942:
1929:
1928:
1910:
1904:
1903:
1885:
1879:
1878:
1860:
1854:
1847:
1838:
1831:
1822:
1815:
1806:
1799:
1790:
1784:
1771:
1765:
1759:
1753:
1673:
1669:
1647:caterpillar tree
1640:
1636:
1632:
1603:
1592:
1585:
1581:
1553:
1543:
1521:
1517:
1510:
1508:
1507:
1502:
1488:
1485:
1482:
1481:
1477:
1461:
1460:
1423:
1419:
1405:
1403:
1402:
1397:
1389:
1387:
1386:
1385:
1381:
1365:
1364:
1351:
1337:
1334:
1309:
1301:
1295:
1288:
1287:≈ 0.534949606...
1278:
1276:
1275:
1270:
1256:
1253:
1250:
1249:
1245:
1229:
1228:
1180:
1170:
1152:
1148:
1112:undirected graph
1102:
1100:
1099:
1094:
1089:
1088:
1087:
1081:
1074:
1073:
1049:
1048:
1030:
1029:
1019:
1007:
987:
964:
956:Prüfer sequences
953:
949:
942:Cayley's formula
888:
877:
856:. However, some
806:Every tree is a
789:(alternatively,
764:
760:
753:
712:
708:
700:
696:
692:
684:
680:
676:
668:
664:
652:
648:
637:
633:
629:
625:
621:
605:
598:
594:
568:
564:
556:
548:
545:. A rooted tree
544:
540:
536:
525:partial ordering
432:
421:
384:irreducible tree
358:order-zero graph
351:
344:
334:
330:
322:
316:
309:
302:
298:
286:
279:
271:
259:
253:
245:
239:
231:
217:
210:
163:computer science
107:undirected graph
76:Chromatic number
42:
30:
29:
21:
2870:
2869:
2865:
2864:
2863:
2861:
2860:
2859:
2840:
2839:
2825:10.2307/1969046
2751:
2746:
2721:
2703:
2701:Further reading
2657:
2642:
2565:
2559:
2548:
2533:
2513:
2508:
2499:
2495:
2487:
2483:
2475:
2471:
2465:
2446:
2442:
2426:
2425:
2418:
2416:
2409:
2389:
2385:
2375:
2373:
2361:
2357:
2349:
2332:
2304:
2300:
2269:
2262:
2247:10.1137/0114048
2228:
2225:
2221:
2213:
2209:
2192:
2188:
2174:Wayback Machine
2147:
2134:
2130:
2123:
2109:
2105:
2098:
2084:
2080:
2073:
2056:
2052:
2044:
2038:
2027:
2012:
2008:
2001:
1984:
1980:
1973:
1955:
1951:
1943:
1932:
1925:
1911:
1907:
1900:
1886:
1882:
1875:
1861:
1857:
1848:
1841:
1835:Dasgupta (1999)
1832:
1825:
1816:
1809:
1800:
1793:
1785:
1774:
1766:
1762:
1754:
1750:
1746:
1703:
1671:
1667:
1638:
1634:
1627:
1594:
1587:
1583:
1579:
1565:
1549:
1534:
1519:
1515:
1484:
1473:
1466:
1462:
1456:
1452:
1432:
1429:
1428:
1421:
1410:
1377:
1370:
1366:
1360:
1356:
1352:
1338:
1336:
1324:
1318:
1315:
1314:
1307:
1297:
1290:
1283:
1252:
1241:
1234:
1230:
1224:
1220:
1200:
1197:
1196:
1176:
1161:
1150:
1139:
1136:
1134:Unlabeled trees
1083:
1069:
1065:
1044:
1040:
1025:
1021:
1020:
1009:
1003:
1002:
1001:
999:
996:
995:
985:
979:
972:
966:
959:
951:
945:
939:
934:
883:
872:
871:vertices, with
808:bipartite graph
803:
795:positional tree
783:
762:
758:
751:
719:internal vertex
710:
706:
698:
694:
690:
682:
678:
674:
666:
662:
650:
646:
635:
631:
627:
623:
613:
600:
596:
592:
566:
562:
554:
546:
542:
541:passes through
538:
528:
500:
480:
445:
439:
423:
412:
400:
377:external vertex
369:internal vertex
346:
342:
332:
328:
320:
311:
307:
300:
296:
284:
277:
270:
264:
257:
251:
243:
237:
229:
215:
208:
201:
196:
157:referred to as
155:data structures
45:
28:
23:
22:
15:
12:
11:
5:
2868:
2858:
2857:
2852:
2838:
2837:
2819:(3): 583–599,
2808:
2790:(3): 111–116,
2779:
2767:
2749:
2744:
2725:
2719:
2702:
2699:
2698:
2697:
2667:Simion, Rodica
2663:
2648:
2633:
2623:(3): 184–187,
2609:
2570:
2557:
2539:
2524:
2512:
2509:
2507:
2506:
2493:
2491:, Prop. 8.5.2.
2489:Diestel (2005)
2481:
2479:, Prop. 8.2.4.
2477:Diestel (2005)
2469:
2463:
2440:
2407:
2383:
2355:
2353:, p. 173.
2330:
2298:
2279:(1): 112–122.
2260:
2219:
2217:, p. 150.
2207:
2186:
2152:, in his book
2142:, 4th series,
2135:Cayley (1857)
2128:
2121:
2103:
2096:
2078:
2071:
2059:David Makinson
2050:
2036:
2006:
1999:
1987:Bernhard Korte
1978:
1971:
1949:
1947:, p. 207.
1930:
1923:
1905:
1898:
1880:
1873:
1855:
1839:
1823:
1807:
1791:
1789:, p. 206.
1772:
1770:, p. 172.
1760:
1758:, p. 171.
1747:
1745:
1742:
1741:
1740:
1735:
1730:
1727:Tree structure
1724:
1719:
1714:
1709:
1702:
1699:
1698:
1697:
1693:Bethe lattices
1684:Tits buildings
1660:
1651:
1642:
1618:
1605:
1578:) consists of
1564:
1563:Types of trees
1561:
1560:
1559:
1522:as above (cf.
1512:
1511:
1500:
1497:
1494:
1491:
1480:
1476:
1472:
1469:
1465:
1459:
1455:
1451:
1448:
1445:
1442:
1439:
1436:
1407:
1406:
1395:
1392:
1384:
1380:
1376:
1373:
1369:
1363:
1359:
1355:
1350:
1347:
1344:
1341:
1333:
1330:
1327:
1323:
1280:
1279:
1268:
1265:
1262:
1259:
1248:
1244:
1240:
1237:
1233:
1227:
1223:
1219:
1216:
1213:
1210:
1207:
1204:
1187:
1186:
1149:of trees with
1135:
1132:
1120:complete graph
1108:spanning trees
1104:
1103:
1092:
1086:
1080:
1077:
1072:
1068:
1064:
1061:
1058:
1055:
1052:
1047:
1043:
1039:
1036:
1033:
1028:
1024:
1018:
1015:
1012:
1006:
983:
977:
970:
938:
935:
933:
930:
929:
928:
921:
902:
894:
865:
822:
811:
802:
799:
782:
779:
609:recursive tree
553:of some graph
505:
499:
496:
485:
479:
476:
450:
441:Main article:
438:
435:
408:disjoint union
405:
399:
396:
385:
378:
370:
354:
353:
340:
318:
293:
292:
281:
268:
262:complete graph
255:
241:
227:
200:
197:
195:
192:
185:
137:disjoint union
134:
116:
93:
92:
86:
85:
78:
72:
71:
70: − 1
65:
59:
58:
53:
47:
46:
43:
35:
34:
26:
9:
6:
4:
3:
2:
2867:
2856:
2853:
2851:
2848:
2847:
2845:
2834:
2830:
2826:
2822:
2818:
2814:
2809:
2805:
2801:
2797:
2793:
2789:
2785:
2780:
2776:
2772:
2768:
2764:
2760:
2759:
2754:
2750:
2747:
2741:
2737:
2736:
2731:
2726:
2722:
2716:
2712:
2711:
2705:
2704:
2694:
2690:
2685:
2680:
2677:(1): 93–104,
2676:
2672:
2668:
2664:
2656:
2655:
2649:
2641:
2640:
2634:
2630:
2626:
2622:
2618:
2614:
2613:Harary, Frank
2610:
2607:
2603:
2598:
2593:
2589:
2585:
2584:
2579:
2575:
2574:Harary, Frank
2571:
2564:
2560:
2558:0-13-363473-6
2554:
2547:
2546:
2540:
2532:
2531:
2525:
2522:
2521:
2515:
2514:
2503:
2497:
2490:
2485:
2478:
2473:
2466:
2464:9781107015425
2460:
2456:
2455:
2450:
2444:
2436:
2430:
2414:
2410:
2408:9780262046305
2404:
2400:
2396:
2395:
2387:
2371:
2367:
2359:
2352:
2347:
2345:
2343:
2341:
2339:
2337:
2335:
2327:
2323:
2318:
2313:
2309:
2302:
2294:
2290:
2286:
2282:
2278:
2274:
2267:
2265:
2256:
2252:
2248:
2244:
2240:
2236:
2235:
2223:
2216:
2211:
2202:
2197:
2190:
2183:
2179:
2175:
2171:
2168:
2163:
2159:
2155:
2151:
2145:
2141:
2138:
2132:
2124:
2122:3-540-44389-4
2118:
2114:
2107:
2099:
2093:
2089:
2082:
2074:
2068:
2064:
2060:
2054:
2043:
2039:
2033:
2026:
2025:
2020:
2019:Peter Sanders
2016:
2015:Kurt Mehlhorn
2010:
2002:
1996:
1992:
1988:
1982:
1974:
1968:
1964:
1960:
1953:
1946:
1941:
1939:
1937:
1935:
1926:
1920:
1916:
1909:
1901:
1895:
1891:
1884:
1876:
1870:
1866:
1859:
1852:
1846:
1844:
1836:
1830:
1828:
1820:
1819:Simion (1991)
1814:
1812:
1804:
1798:
1796:
1788:
1783:
1781:
1779:
1777:
1769:
1764:
1757:
1752:
1748:
1739:
1736:
1734:
1731:
1728:
1725:
1723:
1720:
1718:
1715:
1713:
1710:
1708:
1707:Decision tree
1705:
1704:
1695:
1694:
1689:
1685:
1681:
1677:
1676:Cayley graphs
1665:
1661:
1658:
1657:
1652:
1649:
1648:
1643:
1630:
1625:
1624:
1619:
1616:
1612:
1611:
1610:starlike tree
1606:
1601:
1597:
1590:
1577:
1573:
1572:
1567:
1566:
1557:
1552:
1547:
1546:
1545:
1541:
1537:
1531:
1529:
1525:
1518:and the same
1498:
1489:
1478:
1474:
1470:
1467:
1463:
1457:
1453:
1449:
1446:
1440:
1434:
1427:
1426:
1425:
1417:
1413:
1393:
1390:
1382:
1378:
1374:
1371:
1367:
1361:
1357:
1353:
1345:
1339:
1325:
1313:
1312:
1311:
1306:). Here, the
1305:
1300:
1293:
1286:
1266:
1257:
1246:
1242:
1238:
1235:
1231:
1225:
1221:
1217:
1214:
1208:
1202:
1195:
1194:
1193:
1191:
1184:
1179:
1174:
1173:
1172:
1168:
1164:
1159:
1156:
1146:
1142:
1131:
1129:
1128:Jerrum (1994)
1125:
1121:
1117:
1113:
1109:
1090:
1078:
1075:
1070:
1066:
1062:
1059:
1056:
1053:
1050:
1045:
1041:
1037:
1034:
1031:
1026:
1022:
1016:
1013:
1010:
994:
993:
992:
991:
986:
976:
969:
963:
957:
948:
943:
937:Labeled trees
926:
922:
919:
915:
911:
907:
903:
900:
895:
892:
886:
881:
875:
870:
866:
863:
859:
855:
851:
847:
843:
839:
835:
831:
830:spanning tree
827:
823:
820:
816:
812:
809:
805:
804:
798:
796:
792:
788:
778:
776:
775:
774:ternary trees
770:
769:
756:
755:
746:
743:
739:
735:
731:
727:
722:
720:
716:
704:
688:
672:
660:
656:
644:
639:
620:
616:
611:
610:
604:
590:
585:
583:
578:
576:
572:
560:
552:
535:
531:
526:
522:
518:
514:
510:
503:
495:
493:
487:
483:
475:
473:
468:
466:
462:
458:
457:oriented tree
454:
453:directed tree
448:
444:
434:
430:
426:
419:
415:
409:
403:
395:
393:
389:
383:
380:
376:
374:
368:
365:
363:
359:
349:
341:
338:
326:
319:
314:
306:
305:
304:
290:
282:
275:
267:
263:
256:
249:
242:
235:
228:
225:
221:
214:
213:
212:
206:
191:
189:
188:Arthur Cayley
183:
180:
178:
173:
168:
164:
160:
156:
151:
149:
145:
140:
138:
132:
130:
126:
123:
119:
114:
112:
108:
104:
100:
91:
87:
83:
79:
77:
73:
69:
66:
64:
60:
57:
54:
52:
48:
41:
36:
31:
19:
2816:
2812:
2787:
2783:
2774:
2756:
2734:
2710:Graph Theory
2709:
2674:
2670:
2653:
2638:
2620:
2616:
2587:
2581:
2544:
2529:
2519:
2496:
2484:
2472:
2453:
2443:
2417:. Retrieved
2398:
2393:
2386:
2374:. Retrieved
2366:"k-ary tree"
2358:
2307:
2301:
2276:
2275:. Series A.
2272:
2238:
2232:
2222:
2210:
2189:
2181:
2177:
2153:
2143:
2139:
2131:
2112:
2106:
2087:
2081:
2062:
2053:
2023:
2009:
1990:
1981:
1962:
1952:
1914:
1908:
1889:
1883:
1864:
1858:
1763:
1751:
1722:Pseudoforest
1691:
1664:regular tree
1663:
1656:lobster tree
1654:
1645:
1628:
1621:
1614:
1608:
1599:
1595:
1588:
1576:linear graph
1575:
1569:
1539:
1535:
1532:
1524:Knuth (1997)
1513:
1415:
1411:
1408:
1291:
1284:
1281:
1190:Otter (1948)
1188:
1166:
1162:
1144:
1140:
1137:
1105:
981:
974:
967:
961:
946:
940:
920:/2 vertices.
917:
913:
909:
899:median graph
884:
873:
868:
854:Trémaux tree
837:
833:
825:
819:planar graph
794:
790:
787:ordered tree
786:
784:
781:Ordered tree
772:
768:binary trees
766:
749:
747:
737:
733:
729:
725:
723:
718:
714:
705:to a vertex
702:
689:of a vertex
686:
673:of a vertex
670:
661:of a vertex
658:
645:of a vertex
642:
640:
618:
614:
607:
602:
589:labeled tree
588:
586:
581:
579:
571:Diestel 2005
533:
529:
520:
516:
512:
509:arborescence
508:
501:
488:
481:
472:arborescence
469:
460:
456:
452:
446:
428:
424:
417:
413:
401:
381:
366:
355:
347:
337:1-degenerate
312:
294:
265:
248:disconnected
236:is added to
204:
202:
181:
172:arborescence
152:
141:
128:
102:
99:graph theory
96:
81:
67:
55:
2660:, p. 9
2241:: 550–560.
2158:pages 20–21
1680:free groups
1124:#P-complete
965:of degrees
932:Enumeration
925:few cliques
891:star graphs
880:path graphs
858:uncountable
559:normal tree
504:rooted tree
498:Rooted tree
362:0-connected
289:simple path
194:Definitions
133:at most one
115:exactly one
2844:Categories
2511:References
2376:8 February
2317:2102.06197
2201:1709.04937
1959:Ping Zhang
1666:of degree
1571:path graph
1424:vertices:
1296:(sequence
844:trees and
801:Properties
791:plane tree
687:descendant
549:that is a
507:called an
484:polyforest
478:Polyforest
139:of trees.
18:Tree graph
2804:0020-0190
2763:EMS Press
2606:0001-5962
2502:Li (1996)
2429:cite book
1729:(general)
1717:Multitree
1712:Hypertree
1623:star tree
1496:∞
1493:→
1468:−
1454:α
1447:∼
1372:−
1358:α
1332:∞
1329:→
1264:∞
1261:→
1236:−
1222:α
1215:∼
1153:vertices
1076:−
1060:…
1051:−
1032:−
1014:−
960:1, 2, …,
950:trees on
850:countably
828:admits a
815:countably
754:-ary tree
742:AVL trees
738:root path
671:ascendant
601:1, 2, …,
582:free tree
565:-path in
492:branching
272:is not a
220:connected
182:The term
177:branching
122:connected
2732:(2009),
2563:archived
2451:(2012),
2413:Archived
2370:Archived
2170:Archived
2061:(2012).
2042:Archived
2021:(2008).
1961:(2013).
1945:Deo 1974
1787:Deo 1974
1701:See also
1598:= 1, …,
1486:as
1254:as
551:subgraph
513:out-tree
449:polytree
443:Polytree
437:Polytree
325:subgraph
144:polytree
111:vertices
51:Vertices
2833:1969046
2765:, 2001
2693:1099270
2629:0603363
2419:20 July
2293:1713484
2255:0209064
1554:in the
1551:A000081
1302:in the
1299:A051491
1181:in the
1178:A000055
703:sibling
653:on the
521:in-tree
463:) is a
390:in the
388:A000014
224:acyclic
125:acyclic
2831:
2802:
2753:"Tree"
2742:
2717:
2691:
2627:
2604:
2555:
2461:
2405:
2291:
2253:
2119:
2094:
2069:
2034:
1997:
1969:
1921:
1896:
1871:
1110:in an
906:center
876:> 1
730:height
726:height
643:parent
404:forest
398:Forest
373:degree
352:edges.
317:edges.
129:forest
105:is an
84:> 1
2829:JSTOR
2658:(PDF)
2643:(PDF)
2566:(PDF)
2549:(PDF)
2534:(PDF)
2312:arXiv
2196:arXiv
2045:(PDF)
2028:(PDF)
1744:Notes
1686:. In
1514:with
1282:with
1155:up to
980:, …,
897:is a
862:order
734:depth
659:child
617:<
557:is a
532:<
274:minor
165:have
159:trees
80:2 if
63:Edges
33:Trees
2800:ISSN
2740:ISBN
2715:ISBN
2602:ISSN
2553:ISBN
2500:See
2459:ISBN
2435:link
2421:2023
2403:ISBN
2378:2015
2362:See
2117:ISBN
2092:ISBN
2067:ISBN
2032:ISBN
1995:ISBN
1967:ISBN
1919:ISBN
1894:ISBN
1869:ISBN
1849:See
1833:See
1817:See
1801:See
1615:root
1586:and
1574:(or
1556:OEIS
1544:are
1304:OEIS
1289:and
1183:OEIS
1171:are
724:The
715:leaf
713:. A
701:. A
685:. A
655:path
626:and
606:. A
451:(or
392:OEIS
234:edge
222:and
205:tree
199:Tree
184:tree
118:path
103:tree
101:, a
2821:doi
2792:doi
2679:doi
2592:doi
2588:101
2322:doi
2281:doi
2243:doi
1678:of
1631:– 1
1602:– 1
1591:+ 1
1322:lim
1130:).
887:− 1
793:or
785:An
638:).
519:or
511:or
494:).
474:).
459:or
455:or
420:= 1
394:).
382:An
367:An
350:− 1
327:of
315:− 1
295:If
276:of
218:is
161:in
97:In
2846::
2827:,
2817:49
2798:,
2788:51
2786:,
2761:,
2755:,
2689:MR
2687:,
2675:88
2673:,
2625:MR
2619:,
2600:,
2586:,
2580:,
2561:,
2431:}}
2427:{{
2411:.
2333:^
2320:,
2310:,
2289:MR
2287:.
2277:88
2263:^
2251:MR
2249:.
2239:14
2237:.
2182:72
2180:,
2144:13
2040:.
2017:;
1933:^
1842:^
1826:^
1810:^
1794:^
1775:^
1662:A
1653:A
1644:A
1620:A
1607:A
1568:A
1558:).
1394:1.
1185:).
973:,
777:.
748:A
587:A
584:.
577:.
502:A
482:A
447:A
427:−
416:−
402:A
339:.)
203:A
190:.
2836:.
2823::
2807:.
2794::
2724:.
2696:.
2681::
2662:.
2647:.
2632:.
2621:5
2594::
2538:.
2504:.
2437:)
2423:.
2380:.
2324::
2314::
2295:.
2283::
2257:.
2245::
2229:k
2204:.
2198::
2125:.
2100:.
2075:.
2003:.
1975:.
1927:.
1902:.
1877:.
1853:.
1837:.
1821:.
1805:.
1696:.
1672:d
1668:d
1639:n
1635:n
1629:n
1604:.
1600:n
1596:i
1589:i
1584:i
1580:n
1542:)
1540:n
1538:(
1536:r
1520:α
1499:,
1490:n
1479:2
1475:/
1471:3
1464:n
1458:n
1450:D
1444:)
1441:n
1438:(
1435:r
1422:n
1418:)
1416:n
1414:(
1412:r
1391:=
1383:2
1379:/
1375:5
1368:n
1362:n
1354:C
1349:)
1346:n
1343:(
1340:t
1326:n
1308:~
1292:α
1285:C
1267:,
1258:n
1247:2
1243:/
1239:5
1232:n
1226:n
1218:C
1212:)
1209:n
1206:(
1203:t
1169:)
1167:n
1165:(
1163:t
1151:n
1147:)
1145:n
1143:(
1141:t
1091:.
1085:)
1079:1
1071:n
1067:d
1063:,
1057:,
1054:1
1046:2
1042:d
1038:,
1035:1
1027:1
1023:d
1017:2
1011:n
1005:(
984:n
982:d
978:2
975:d
971:1
968:d
962:n
952:n
947:n
927:.
918:n
914:n
910:n
901:.
885:n
874:n
869:n
860:-
838:G
834:G
826:G
821:.
763:k
759:k
752:k
711:v
707:v
699:v
695:v
691:v
683:v
679:v
675:v
667:v
663:v
651:v
647:v
636:v
632:u
628:v
624:u
619:v
615:u
603:n
597:n
593:n
567:G
563:T
555:G
547:T
543:u
539:v
534:v
530:u
431:=
429:E
425:V
418:E
414:V
348:n
343:G
333:G
329:G
321:G
313:n
308:G
301:n
297:G
291:.
285:G
280:.
278:G
269:3
266:K
258:G
254:.
252:G
244:G
240:.
238:G
230:G
216:G
209:G
82:v
68:v
56:v
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
