Concept
Tree (graph theory)
Related concepts (39)
Polytree
In mathematics, and more specifically in graph theory, a polytree (also called directed tree, oriented tree or singly connected network) is a directed acyclic graph 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. A polyforest (or directed forest or oriented forest) is a directed acyclic graph whose underlying undirected graph is a forest.
Multitree
In combinatorics and order theory, a multitree may describe either of two equivalent structures: a directed acyclic graph (DAG) in which there is at most one directed path between any two vertices, or equivalently in which the subgraph reachable from any vertex induces an undirected tree, or a partially ordered set (poset) that does not have four items a, b, c, and d forming a diamond suborder with a ≤ b ≤ d and a ≤ c ≤ d but with b and c incomparable to each other (also called a diamond-free poset).
Random graph
In mathematics, random graph is the general term to refer to probability distributions over graphs. Random graphs may be described simply by a probability distribution, or by a random process which generates them. The theory of random graphs lies at the intersection between graph theory and probability theory. From a mathematical perspective, random graphs are used to answer questions about the properties of typical graphs.
Kirchhoff's theorem
In the mathematical field of graph theory, Kirchhoff's theorem or Kirchhoff's matrix tree theorem named after Gustav Kirchhoff is a theorem about the number of spanning trees in a graph, showing that this number can be computed in polynomial time from the determinant of a submatrix of the Laplacian matrix of the graph; specifically, the number is equal to any cofactor of the Laplacian matrix. Kirchhoff's theorem is a generalization of Cayley's formula which provides the number of spanning trees in a complete graph.
Prüfer sequence
In combinatorial mathematics, the Prüfer sequence (also Prüfer code or Prüfer numbers) of a labeled tree is a unique sequence associated with the tree. The sequence for a tree on n vertices has length n − 2, and can be generated by a simple iterative algorithm. Prüfer sequences were first used by Heinz Prüfer to prove Cayley's formula in 1918. One can generate a labeled tree's Prüfer sequence by iteratively removing vertices from the tree until only two vertices remain. Specifically, consider a labeled tree T with vertices {1, 2, .
Star (graph theory)
In graph theory, a star S_k is the complete bipartite graph K_1,k : a tree with one internal node and k leaves (but no internal nodes and k + 1 leaves when k ≤ 1). Alternatively, some authors define S_k to be the tree of order k with maximum diameter 2; in which case a star of k > 2 has k − 1 leaves. A star with 3 edges is called a claw. The star S_k is edge-graceful when k is even and not when k is odd. It is an edge-transitive matchstick graph, and has diameter 2 (when l > 1), girth ∞ (it has no cycles), chromatic index k, and chromatic number 2 (when k > 0).
Maze-solving algorithm
A maze-solving algorithm is an automated method for solving a maze. The random mouse, wall follower, Pledge, and Trémaux's algorithms are designed to be used inside the maze by a traveler with no prior knowledge of the maze, whereas the dead-end filling and shortest path algorithms are designed to be used by a person or computer program that can see the whole maze at once. Mazes containing no loops are known as "simply connected", or "perfect" mazes, and are equivalent to a tree in graph theory.
Caterpillar tree
In graph theory, a caterpillar or caterpillar tree is a tree in which all the vertices are within distance 1 of a central path. Caterpillars were first studied in a series of papers by Harary and Schwenk. The name was suggested by Arthur Hobbs. As colorfully write, "A caterpillar is a tree which metamorphoses into a path when its cocoon of endpoints is removed." The following characterizations all describe the caterpillar trees: They are the trees for which removing the leaves and incident edges produces a path graph.
List of graphs
This partial list of graphs contains definitions of graphs and graph families. For collected definitions of graph theory terms that do not refer to individual graph types, such as vertex and path, see Glossary of graph theory. For links to existing articles about particular kinds of graphs, see . Some of the finite structures considered in graph theory have names, sometimes inspired by the graph's topology, and sometimes after their discoverer.