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