|
Kleitman–Wang Algorithms
The Kleitman–Wang algorithms are two different algorithms in graph theory solving the digraph realization problem, i.e. the question if there exists for a finite list of nonnegative integer pairs a simple directed graph such that its degree sequence is exactly this list. For a positive answer the list of integer pairs is called ''digraphic''. Both algorithms construct a special solution if one exists or prove that one cannot find a positive answer. These constructions are based on recursive algorithms. Kleitman and Wang gave these algorithms in 1973. Kleitman–Wang algorithm (arbitrary choice of pairs) The algorithm is based on the following theorem. Let S=((a_1,b_1),\dots,(a_n,b_n)) be a finite list of nonnegative integers that is in nonincreasing lexicographical order and let (a_i,b_i) be a pair of nonnegative integers with b_i >0. List S is digraphic if and only if the finite list S'=((a_1-1,b_1),\dots,(a_-1,b_),(a_,0),(a_,b_),(a_,b_),\dots,(a_n,b_n)) has nonnegative int ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Graph Theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph theory), vertices'' (also called ''nodes'' or ''points'') which are connected by ''Glossary of graph theory terms#edge, edges'' (also called ''arcs'', ''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 (mathematics), set of vertices (also called nodes or points); * ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Digraph Realization Problem
The digraph realization problem is a decision problem in graph theory. Given pairs of nonnegative integers ((a_1,b_1),\ldots,(a_n,b_n)), the problem asks whether there is a labeled directed graph, simple directed graph such that each vertex (graph theory), vertex v_i has directed graph, indegree a_i and directed graph, outdegree b_i. Solutions The problem belongs to the complexity class P (complexity), P. Two algorithms are known to prove that. The first approach is given by the Kleitman–Wang algorithms constructing a special solution with the use of a Recursion (computer science), recursive algorithm. The second one is a characterization by the Fulkerson–Chen–Anstee theorem, i.e. one has to validate the correctness of n inequalities. Other Notations The problem can also be stated in terms of zero-one matrix (mathematics), matrices. The connection can be seen if one realizes that each directed graph has an adjacency matrix where the column sums and row sums correspond to (a_ ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
