|
Nash-Williams Theorem
In graph theory, the Nash-Williams theorem is a tree-packing theorem that describes how many edge-disjoint spanning trees (and more generally forests) a graph can have:A graph ''G'' has ''t'' edge-disjoint spanning trees iff for every partition V_1, \ldots, V_k \subset V(G) where V_i \neq \emptyset there are at least ''t''(''k'' − 1) crossing edges ( Tutte 1961, Nash-Williams 1961).For this article, we will say that such a graph has arboricity ''t'' or is ''t''-arboric. (The actual definition of arboricity is slightly different and applies to forests rather than trees.) Related tree-packing properties A ''k''-arboric graph is necessarily ''k''-edge connected. The converse is not true. As a corollary of NW, every 2''k''-edge connected graph is ''k''-arboric. Both NW and Menger's theorem characterize when a graph has ''k'' edge-disjoint paths between two vertices. Nash-Williams theorem for forests NW (1964) generalized the above result to forests:G can be ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Theory
In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are connected by ''edges'' (also called ''links'' or ''lines''). A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges link two vertices asymmetrically. Graphs are one of the principal objects of study in discrete mathematics. Definitions Definitions in graph theory vary. The following are some of the more basic ways of defining graphs and related mathematical structures. Graph In one restricted but very common sense of the term, a graph is an ordered pair G=(V,E) comprising: * V, a set of vertices (also called nodes or points); * E \subseteq \, a set of edges (also called links or lines), which are unordered pairs of vertices (that is, an edge is associated with t ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Spanning Tree
In the mathematical field of graph theory, a spanning tree ''T'' of an undirected graph ''G'' is a subgraph that is a tree which includes all of the vertices of ''G''. In general, a graph may have several spanning trees, but a graph that is not connected will not contain a spanning tree (see about spanning forests below). If all of the edges of ''G'' are also edges of a spanning tree ''T'' of ''G'', then ''G'' is a tree and is identical to ''T'' (that is, a tree has a unique spanning tree and it is itself). Applications Several pathfinding algorithms, including Dijkstra's algorithm and the A* search algorithm, internally build a spanning tree as an intermediate step in solving the problem. In order to minimize the cost of power networks, wiring connections, piping, automatic speech recognition, etc., people often use algorithms that gradually build a spanning tree (or many such trees) as intermediate steps in the process of finding the minimum spanning tree. The Interne ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Forest (graph Theory)
In graph theory, a tree is an undirected graph in which any two vertices are connected by ''exactly one'' path, or equivalently a connected acyclic undirected graph. A forest is an undirected graph in which any two vertices are connected by ''at most one'' path, or equivalently an acyclic undirected graph, or equivalently a disjoint union of trees. A polytreeSee . (or directed tree or oriented treeSee .See . or singly connected networkSee .) is a directed acyclic graph (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. 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. 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 ca ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Crispin Nash-Williams
Crispin St John Alvah Nash-Williams FRSE (19 December 1932 – 20 January 2001) was a British mathematician. His research interest was in the field of discrete mathematics, especially graph theory. Biography Nash-Williams was born on 19 December 1932 in Cardiff, Wales. His father, Victor Erle Nash-Williams ( Williams), was an archaeologist at University College Cardiff, and his mother had studied classics at Oxford. As a small boy, Nash-Williams attended Christ Church Cathedral School in Oxford, which was then headed by Wilfrid Oldaker. A biographer has said that Oldaker was a formative influence on Nash-Williams.D. J. A. Welsh"Crispin St J. A. Nash-Williams (1932–2001)"in ''Bulletin of the London Mathematical Society'', Vol. 35, Issue 6, November 2003, Pages 829–844 After studying mathematics at the University of Cambridge, earning the title of Senior Wrangler in 1953, he remained at Cambridge for his graduate studies, under the supervision of Shaun Wylie and David Re ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Arboricity
The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash-Williams theorem provides necessary and sufficient conditions for when a graph is ''k''-arboric. Example The figure shows the complete bipartite graph ''K''4,4, with the colors indicating a partition of its edges into three forests. ''K''4,4 cannot be partitioned into fewer forests, because any forest on its eight vertices has at most seven edges, while the overall graph has sixteen edges, more than double the number of edges in a single forest. Therefore, the arboricity of ''K''4,4 is three. Arboricity as a measure of density The arboricity of a graph is a measure of how dense the graph is: graphs with many edges have high arboricity, and graphs with high arboricity must have a dense subgraph. In more detail, as any n-vertex forest has at most n-1 edge ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
K-edge-connected Graph
In graph theory, a connected graph is -edge-connected if it remains connected whenever fewer than edges are removed. The edge-connectivity of a graph is the largest for which the graph is -edge-connected. Edge connectivity and the enumeration of -edge-connected graphs was studied by Camille Jordan in 1869. Formal definition Let G = (V, E) be an arbitrary graph. If subgraph G' = (V, E \setminus X) is connected for all X \subseteq E where , X, < k, then ''G'' is ''k''-edge-connected. The edge connectivity of is the maximum value ''k'' such that ''G'' is ''k''-edge-connected. The smallest set ''X'' whose removal disconnects ''G'' is a minimum cut in ''G''. The edge connectivity version of Menger's theorem provides an alternative and equivalent characterization, in term ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Menger's Theorem
In the mathematical discipline of graph theory, Menger's theorem says that in a finite graph, the size of a minimum cut set is equal to the maximum number of disjoint paths that can be found between any pair of vertices. Proved by Karl Menger in 1927, it characterizes the connectivity of a graph. It is generalized by the max-flow min-cut theorem, which is a weighted, edge version, and which in turn is a special case of the strong duality theorem for linear programs. Edge connectivity The edge-connectivity version of Menger's theorem is as follows: :Let ''G'' be a finite undirected graph and ''x'' and ''y'' two distinct vertices. Then the size of the minimum edge cut for ''x'' and ''y'' (the minimum number of edges whose removal disconnects ''x'' and ''y'') is equal to the maximum number of pairwise edge-independent paths from ''x'' to ''y''. :Extended to all pairs: a graph is ''k''-edge-connected (it remains connected after removing fewer than ''k'' edges) if and only if e ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Induced Subgraph
In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Definition Formally, let G=(V,E) be any graph, and let S\subset V be any subset of vertices of . Then the induced subgraph G is the graph whose vertex set is S and whose edge set consists of all of the edges in E that have both endpoints in S . That is, for any two vertices u,v\in S , u and v are adjacent in G if and only if they are adjacent in G . The same definition works for undirected graphs, directed graphs, and even multigraphs. The induced subgraph G may also be called the subgraph induced in G by S , or (if context makes the choice of G unambiguous) the induced subgraph of S . Examples Important types of induced subgraphs include the following. * Induced paths are induced subgraphs that are paths. The shortest path betwe ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Arboricity
The arboricity of an undirected graph is the minimum number of forests into which its edges can be partitioned. Equivalently it is the minimum number of spanning forests needed to cover all the edges of the graph. The Nash-Williams theorem provides necessary and sufficient conditions for when a graph is ''k''-arboric. Example The figure shows the complete bipartite graph ''K''4,4, with the colors indicating a partition of its edges into three forests. ''K''4,4 cannot be partitioned into fewer forests, because any forest on its eight vertices has at most seven edges, while the overall graph has sixteen edges, more than double the number of edges in a single forest. Therefore, the arboricity of ''K''4,4 is three. Arboricity as a measure of density The arboricity of a graph is a measure of how dense the graph is: graphs with many edges have high arboricity, and graphs with high arboricity must have a dense subgraph. In more detail, as any n-vertex forest has at most n-1 edge ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bridge (graph Theory)
In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges. This type of bridge should be distinguished from an unrelated meaning of "bridge" in graph theory, a subgraph separated from the rest of the graph by a specified subset of vertices; see . Trees and forests A graph with n nodes can contain at most n-1 bridges, since adding additional edges must create a cycle. The graphs with exactly n-1 bridges are exactly the trees, and the graphs in which every edge is a bridge are exactly the forests. In every undirected graph, there is an equivalence relation on the vertices according to which two vertices are related to each other whenever there are two edge-disjoint paths c ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Lawrence Paulson
Lawrence Charles Paulson (born 1955) is an American computer scientist. He is a Professor of Computational Logic at the University of Cambridge Computer Laboratory and a Fellow of Clare College, Cambridge. Education Paulson graduated from the California Institute of Technology in 1977,Lawrence Paulson and obtained his PhD in Computer Science from Stanford University in 1981 for research on programming languages and compiler-compilers supervised by John L. Hennessy. Research Paulson came to the University of Cambridge in 1983 and became a Fellow of Clare College, Cambridge in 1987. He is best known for the cornerstone text on the programming language ML, ''ML for the Working Programmer''. His research is based around the interactive theorem prover Isabelle, which he introduced in 1986. He has worked on the verification of cryptographic protocols using inductive definitions, and he has also formalised the constructible universe of Kurt Gödel. Recently he has built a new ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
