|
Tree-width
In graph theory, the treewidth of an undirected graph is an integer number which specifies, informally, how far the graph is from being a tree. The smallest treewidth is 1; the graphs with treewidth 1 are exactly the trees and the forests. An example of graphs with treewidth at most 2 are the series–parallel graphs. The maximal graphs with treewidth exactly are called '' -trees'', and the graphs with treewidth at most are called '' partial -trees''. Many other well-studied graph families also have bounded treewidth. Treewidth may be formally defined in several equivalent ways: in terms of the size of the largest vertex set in a tree decomposition of the graph, in terms of the size of the largest clique in a chordal completion of the graph, in terms of the maximum order of a haven describing a strategy for a pursuit–evasion game on the graph, or in terms of the maximum order of a bramble, a collection of connected subgraphs that all touch each other. Treewidth is commonly u ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Hadwiger Number
In graph theory, the Hadwiger number of an undirected graph is the size of the largest complete graph that can be obtained by edge contraction, contracting edges of . Equivalently, the Hadwiger number is the largest number for which the complete graph is a graph minor, minor of , a smaller graph obtained from by edge contractions and vertex and edge deletions. The Hadwiger number is also known as the contraction clique number of or the homomorphism degree of . It is named after Hugo Hadwiger, who introduced it in 1943 in conjunction with the Hadwiger conjecture (graph theory), Hadwiger conjecture, which states that the Hadwiger number is always at least as large as the chromatic number of . The graphs that have Hadwiger number at most four have been characterized by . The graphs with any finite bound on the Hadwiger number are sparse, and have small chromatic number. Determining the Hadwiger number of a graph is NP-hard but parameterized complexity, fixed-parameter tra ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tree Decomposition
In graph theory, a tree decomposition is a mapping of a Graph (discrete mathematics), graph into a tree (graph theory), tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. Tree decompositions are also called junction trees, clique trees, or join trees. They play an important role in problems like belief propagation, probabilistic inference, constraint satisfaction, query optimization, and matrix decomposition. The concept of tree decomposition was originally introduced by . Later it was rediscovered by and has since been studied by many other authors. Definition Intuitively, a tree decomposition represents the vertices of a given graph as subtrees of a tree, in such a way that vertices in are adjacent only when the corresponding subtrees intersect. Thus, forms a Glossary of graph theory#Subgraphs, subgraph of the intersection graph of the subtrees. The full intersection graph is a chordal graph. Each ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bramble (graph Theory)
In graph theory, a bramble for an undirected graph is a family of connected subgraphs of that all touch each other: for every pair of disjoint subgraphs, there must exist an edge in that has one endpoint in each subgraph. The ''order'' of a bramble is the smallest size of a hitting set, a set of vertices of that has a nonempty intersection with each of the subgraphs. Brambles may be used to characterize the treewidth of .. In this reference, brambles are called "screens" and their order is called "thickness". Treewidth and havens A haven of order ''k'' in a graph ''G'' is a function ''β'' that maps each set ''X'' of fewer than ''k'' vertices to a connected component of ''G'' − ''X'', in such a way that every two subsets ''β''(''X'') and ''β''(''Y'') touch each other. Thus, the set of images of ''β'' forms a bramble in ''G'', with order ''k''. Conversely, every bramble may be used to determine a haven: for each set ''X'' of size smaller ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Pursuit–evasion
Pursuit–evasion (variants of which are referred to as cops and robbers and graph searching) is a family of problems in mathematics and computer science in which one group attempts to track down members of another group in an environment. Early work on problems of this type modeled the environment geometrically. In 1976, Torrence Parsons introduced a formulation whereby movement is constrained by a graph. The geometric formulation is sometimes called continuous pursuit–evasion, and the graph formulation discrete pursuit–evasion (also called graph searching). Current research is typically limited to one of these two formulations. Discrete formulation In the discrete formulation of the pursuit–evasion problem, the environment is modeled as a graph. Problem definition There are innumerable possible variants of pursuit–evasion, though they tend to share many elements. A typical, basic example is as follows (cops and robber games): Pursuers and evaders occupy nodes of a gra ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Haven (graph Theory)
In graph theory, a haven is a certain type of function on sets of vertices in an undirected graph. If a haven exists, it can be used by an evader to win a pursuit–evasion game on the graph, by consulting the function at each step of the game to determine a safe set of vertices to move into. Havens were first introduced by as a tool for characterizing the treewidth of graphs. Their other applications include proving the existence of small separators on minor-closed families of graphs, and characterizing the ends and clique minors of infinite graphs... Definition If is an undirected graph, and is a set of vertices, then an -flap is a nonempty connected component of the subgraph of formed by deleting . A haven of order in is a function that assigns an -flap to every set of fewer than vertices. This function must also satisfy additional constraints which are given differently by different authors. The number is called the ''order'' of the haven.. In the original ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Tree Decomposition
In graph theory, a tree decomposition is a mapping of a Graph (discrete mathematics), graph into a tree (graph theory), tree that can be used to define the treewidth of the graph and speed up solving certain computational problems on the graph. Tree decompositions are also called junction trees, clique trees, or join trees. They play an important role in problems like belief propagation, probabilistic inference, constraint satisfaction, query optimization, and matrix decomposition. The concept of tree decomposition was originally introduced by . Later it was rediscovered by and has since been studied by many other authors. Definition Intuitively, a tree decomposition represents the vertices of a given graph as subtrees of a tree, in such a way that vertices in are adjacent only when the corresponding subtrees intersect. Thus, forms a Glossary of graph theory#Subgraphs, subgraph of the intersection graph of the subtrees. The full intersection graph is a chordal graph. Each ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Apollonian Network
In combinatorics, combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar graph, planar k-tree, 3-trees, the maximal planar chordal graphs, the uniquely colorable graph, uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction. Definition An Apollonian network may be formed, starting from a single triangle graph embedding, embedded in the Euclidean plane, by repeatedly selecting a triangular face of the embedding, adding a new vertex inside the face, and connecting the new vertex to each vertex of the face containing it. In this way, the triangle containing the new vertex is subdivided into three smaller triangles, which may in turn be subdivided in the same way. Examples The complete graphs on three and four ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
