|
In mathematics, and more specifically in graph theory, a tree is an undirected graph in which any two vertices are connected by ''exactly one'' path. In other words, any connected graph without simple cycles is a tree. A forest is a disjoint union of trees. The various kinds of data structures referred to as trees in computer science have underlying graphs that are trees in graph theory, although such data structures are generally rooted trees, thus in fact being directed graphs, and may also have additional ordering of branches. Rooted trees in their directed graph form may be called directed rooted trees. Other terms for this include〔In particular, some authors consider that ''directed rooted trees'' are not descriptive enough as to the direction of the arcs, for instance 〕 arborescence,〔 out-arborescence, out-tree,〔 and even branching. The term "tree" was coined in 1857 by the British mathematician Arthur Cayley.〔Cayley (1857) ("On the theory of the analytical forms called trees," ) ''Philosophical Magazine'', 4th series, 13 : 172–176. However it should be mentioned that in 1847, K.G.C. von Staudt, in his book ''Geometrie der Lage'' (Nürnberg, (Germany): Bauer und Raspe, 1847), presented a proof of Euler's polyhedron theorem which relies on trees on (pages 20–21 ). Also in 1847, the German physicist Gustav Kirchhoff 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) ("Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird" ) (On the solution of equations to which one is led by the investigation of the linear distribution of galvanic currents), ''Annalen der Physik und Chemie'', 72 (12) : 497–508.〕 == Definitions == A tree is an undirected simple graph ''G'' that satisfies any of the following equivalent conditions: *''G'' is connected and has no cycles. *''G'' has no cycles, and a simple cycle is formed if any edge is added to ''G''. *''G'' is connected, but is not connected if any single edge is removed from ''G''. *''G'' is connected and the 3-vertex complete graph is not a minor of ''G''. *Any two vertices in ''G'' can be connected by a unique simple path. If ''G'' has finitely many vertices, say ''n'' of them, then the above statements are also equivalent to any of the following conditions: *''G'' is connected and has ''n'' − 1 edges. *''G'' has no simple cycles and has ''n'' − 1 edges. As elsewhere in graph theory, the order-zero graph (graph with no vertices) is generally excluded from consideration: while it is vacuously connected as a graph (any two vertices can be connected by a path), it is not 0-connected (or even (−1)-connected) in algebraic topology, unlike non-empty trees, and violates the "one more node than edges" relation. A leaf is a vertex of degree 1. An internal vertex is a vertex of degree at least 2. An irreducible (or ''series-reduced'') tree is a tree in which there is no vertex of degree 2. A forest is an undirected graph, all of whose connected components are trees; in other words, the graph consists of a disjoint union of trees. Equivalently, a forest is an undirected cycle-free graph. As special cases, an empty graph, a single tree, and the discrete graph on a set of vertices (that is, the graph with these vertices that has no edges), all are examples of forests. The term hedge sometimes refers to an ordered sequence of trees. A polytree〔See .〕 (also known as oriented tree〔See .〕〔See .〕 or singly connected network〔See .〕) is a directed acyclic graph (DAG) whose underlying undirected graph is a tree. In other words, if we replace its directed arcs with undirected edges, we obtain an undirected graph that is both connected and acyclic. A directed tree is a directed graph which would be a tree if the directions on the edges were ignored, i.e. a polytree. Some authors restrict the phrase to the case where the edges are all directed towards a particular vertex, or all directed away from a particular vertex (see arborescence). A tree is called a rooted tree if one vertex has been designated the root, in which case the edges have a natural orientation, ''towards'' or ''away'' from the root. The ''tree-order'' is the partial ordering on the vertices of a tree with ''u'' ≤ ''v'' if and only if the unique path from the root to ''v'' passes through ''u''. A rooted tree which is a subgraph of some graph ''G'' is a normal tree if the ends of every edge in ''G'' are comparable in this tree-order whenever those ends are vertices of the tree . Rooted trees, often with additional structure such as ordering of the neighbors at each vertex, are a key data structure in computer science; see tree data structure. In a context where trees are supposed to have a root, a tree without any designated root is called a free tree. In a rooted tree, the parent of a vertex is the vertex connected to it on the path to the root; every vertex except the root has a unique parent. A child of a vertex ''v'' is a vertex of which ''v'' is the parent. A descendent of any vertex ''v'' is any vertex which is either the child of ''v'' or is (recursively) the descendent of any of the children of ''v''. A sibling to a vertex ''v'' is any other vertex on the tree which has the same parent as ''v''. A labeled tree is a tree in which each vertex is given a unique label. The vertices of a labeled tree on ''n'' vertices are typically given the labels 1, 2, ..., ''n''. A recursive tree is a labeled rooted tree where the vertex labels respect the tree order (''i.e.'', if ''u'' < ''v'' for two vertices ''u'' and ''v'', then the label of ''u'' is smaller than the label of ''v''). A k-ary tree is a rooted tree for which each vertex has at most ''k'' children.〔See 〕 ''2-ary trees'' are sometimes called binary trees, while ''3-ary trees'' are sometimes called ternary trees. A terminal vertex of a tree is a vertex of degree 1. In a rooted tree, the leaves are all terminal vertices; additionally, the root, if not a leaf itself, is a terminal vertex if it has precisely one child. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Tree (graph theory)」の詳細全文を読む スポンサード リンク
|