Steven Skiena: "Implementing Discrete Mathematics: Combinatorics
and Graph Theory with Mathematica",
Addison-Wesley Publishing Co.
*)
(* :Mathematica Version: 2.0
*)
BeginPackage["DiscreteMath`Combinatorica`"]
Graph::usage = "Graph[g,v] is the header for a graph object where g is an adjacency matrix and v is a list of vertices."
Directed::usage = "Directed is an option to inform certain functions that the graph is directed."
Undirected::usage = "Undirected is an option to inform certain functions that the graph is undirected."
Edge::usage = "Edge is an option to inform certain functions to work with edges instead of vertices."
All::usage = "All is an option to inform certain functions to return all solutions, instead of just the first one."
AcyclicQ::usage = "AcyclicQ[g] returns True if graph g is acyclic. AcyclicQ[g,Directed] returns True if g is a directed acyclic graph."
AddEdge::usage = "AddEdge[g,{x,y}] returns graph g with a new undirected edge {x,y}, while AddEdge[g,{x,y},Directed] returns graph g with a new directed edge {x,y}."
AddVertex::usage = "AddVertex[g] adds a disconnected vertex to graph g."
AllPairsShortestPath::usage = "AllPairsShortestPath[g] returns a matrix, where the (i,j)th entry is the length of the shortest path in g between vertices i and j."
ArticulationVertices::usage = "ArticulationVertices[g] returns a list of all articulation vertices in graph g, vertices whose removal will disconnect the graph."
Automorphisms::usage = "Automorphisms[g] finds the automorphism group of a graph g, the set of isomorphisms of g with itself."
Backtrack::usage = "Backtrack[s,partialQ,solutionQ] performs a backtrack search of the state space s, expanding a partial solution so long as partialQ is True and returning the first complete solution, as identified by solutionQ."
BiconnectedComponents::usage = "BiconnectedComponents[g] returns a list of all the biconnected components of graph g."
BiconnectedComponents::usage = "BiconnectedComponents[g] returns a list of the biconnected components of graph g."
BiconnectedQ::usage = "BiconnectedQ[g] returns True if graph g is biconnected."
BinarySearch::usage = "BinarySearch[l,k,f] searches sorted list l for key k and returns the the position of l containing k, with f a function which extracts the key from an element of l."
BinarySubsets::usage = "BinarySubsets[l] returns all subsets of l ordered according to the binary string defining each subset."
BipartiteMatching::usage = "BipartiteMatching[g] returns the list of edges associated with a maximum matching in bipartite graph g."
BipartiteQ::usage = "BipartiteQ[g] returns True if graph g is bipartite."
BreadthFirstTraversal::usage = "BreadthFirstTraversal[g,v] performs a breadth-first traversal of graph g starting from vertex v, and returns a list of vertices in the order in which they were encountered."
Bridges::usage = "Bridges[g] returns a list of the bridges of graph g, the edges whose removal disconnects the graph."
CartesianProduct::usage = "CartesianProduct[l1,l2] returns the Cartesian product of lists l1 and l2."
CatalanNumber::usage = "CatalanNumber[n] computes the nth Catalan number, for a positive integer n."
ChangeEdges::usage = "ChangeEdges[g,e] constructs a graph with the adjacency matrix e and the embedding of graph g."
ChangeVertices::usage = "ChangeVertices[g,v] constructs a graph with the adjacency matrix of graph g and the list v as its embedding."
ChromaticNumber::usage = "ChromaticNumber[g] computes the chromatic number of the graph, the fewest number of colors necessary to color the graph."
ChromaticPolynomial::usage = "ChromaticPolynomial[g,z] returns the chromatic polynomial P(z) of graph g, which counts the number of ways to color g with exactly z colors."
CirculantGraph::usage = "CirculantGraph[n,l] constructs a circulant graph on n vertices, meaning the ith vertex is adjacent to the (i+j)th and (i-j)th vertex, for each j in list l."
CircularVertices::usage = "CircularVertices[n] constructs a list of n points equally spaced on a circle."
CliqueQ::usage = "CliqueQ[g,c] returns True if the list of vertices c defines a clique in graph g."
CodeToLabeledTree::usage = "CodeToLabeledTree[l] constructs the unique labeled tree on n vertices from the Prufer code l, which consists of a list of n-2 integers from 1 to n."
Cofactor::usage = "Cofactor[m,{i,j}] calculates the (i,j)th cofactor of matrix m."
CompleteQ::usage = "CompleteQ[g] returns True if graph g is complete."
Compositions::usage = "Compositions[n,k] returns a list of all compositions of integer n into k parts."
ConnectedComponents::usage = "ConnectedComponents[g] returns the vertices of graph g partitioned into connected components."
ConnectedQ::usage = "ConnectedQ[g] returns True if undirected graph g is connected. ConnectedQ[g,Directed] and ConnectedQ[g,Undirected] returns True if g is strongly or weakly connected, respectively."
ConstructTableau::usage = "ConstructTableau[p] performs the bumping algorithm repeatedly on each element of permutation p, resulting in a distinct Young tableau."
Contract::usage = "Contract[g,{x,y}] gives the graph resulting from contracting edge {x,y} of graph g."
CostOfPath::usage = "CostOfPath[g,p] sums up the weights of the edges in graph g defined by the path p."
Cycle::usage = "Cycle[n] constructs the cycle on n vertices, a 2-regular connected graph."
DeBruijnSequence::usage = "DeBruijnSequence[a,n] constructs a de Bruijn sequence on the alphabet described by list a, the shortest sequence such that every string of length n on a occurs as a contiguous subrange of the sequence."
DegreeSequence::usage = "DegreeSequence[g] returns the sorted degree sequence of graph g."
DeleteCycle::usage = "DeleteCycle[g,c] deletes undirected cycle c from graph g. DeleteCycle[g,c,Directed] deletes directed cycle c from graph g."
DeleteEdge::usage = "DeleteEdge[g,{x,y}] returns graph g minus undirected edge {x,y}, while DeleteEdge[g,{x,y},Directed] returns graph g minus directed edge {x,y}."
DeleteFromTableau::usage = "DeleteFromTableau[t,r] deletes the last element of row r from Young tableaux t."
DeleteVertex::usage = "DeleteVertex[g,v] deletes vertex v from graph g."
DepthFirstTraversal::usage = "DepthFirstTraversal[g,v] performs a depth-first traversal of graph g starting from vertex v, and returns a list of vertices in the order in which they were encountered."
DerangementQ::usage = "DerangementQ[p] tests whether permutation p is a derangement, a permutation without a fixed point."
Derangements::usage = "Derangements[p] constructs all derangements of permutation p."
Diameter::usage = "Diameter[g] computes the diameter of graph g, the length of the longest shortest path between two vertices of g."
Dijkstra::usage = "Dijkstra[g,v] returns the shortest path spanning tree and associated distances from vertex v of graph g."
DilateVertices::usage = "DilateVertices[v,d] multiplies each coordinate of each vertex position in list l by d, thus dilating the embedding."
DistinctPermutations::usage = "DistinctPermutations[l] returns all permutations of the multiset described by list l."
Distribution::usage = "Distribution[l,set] lists the frequency of occurrence of each element of set in list l."
DurfeeSquare::usage = "DurfeeSquare[p] computes the number of rows involved in the Durfee square of partition p, the side of the largest sized square contained within the Ferrers diagram of p."
Eccentricity::usage = "Eccentricity[g] computes the eccentricity of each vertex v of graph g, the length of the longest shortest path from v."
EdgeChromaticNumber::usage = "EdgeChromaticNumber[g] computes the fewest number of colors necessary to color each edge of graph g, so that no two edges incident on the same vertex have the same color."
EdgeColoring::usage = "EdgeColoring[g] uses Brelaz's heuristic to find a good, but not necessarily minimal, edge coloring of graph g."
EdgeConnectivity::usage = "EdgeConnectivity[g] computes the minimum number of edges whose deletion from graph g disconnects it."
Edges::usage = "Edges[g] returns the adjacency matrix of graph g."
Element::usage = "Element[a,l] returns the lth element of nested list a, where l is a list of indices"
EmptyGraph::usage = "EmptyGraph[n] generates an empty graph on n vertices."
EmptyQ::usage = "EmptyQ[g] returns True if graph g contains no edges."
EncroachingListSet::usage = "EncroachingListSet[p] constructs the encroaching list set associated with permutation p."
EquivalenceClasses::usage = "EquivalenceClasses[r] identifies the equivalence classes among the elements of matrix r."
EquivalenceRelationQ::usage = "EquivalenceRelationQ[r] returns True if the matrix r defines an equivalence relation. EquivalenceRelationQ[g] tests whether the adjacency matrix of graph g defines an equivalence relation."
Equivalences::usage = "Equivalences[g,h] lists the vertex equivalence classes between graphs g and h defined by the all-pairs shortest path heuristic."
EulerianCycle::usage = "EulerianCycle[g] finds an Eulerian circuit of undirected graph g if one exists. EulerianCycle[g,Directed] finds an Eulerian circuit of directed graph g if one exists."
EulerianQ::usage = "EulerianQ[g] returns True if graph g is Eulerian, meaning there exists a tour which includes each edge exactly once. EulerianQ[g,Directed] returns True if directed graph g is Eulerian."
Eulerian::usage = "Eulerian[n,k] computes the number of permutations of length n with k runs."
ExactRandomGraph::usage = "ExactRandomGraph[n,e] constructs a random labeled graph of exactly e edges and n vertices."
ExpandGraph::usage = "ExpandGraph[g,n] expands graph g to n vertices by adding disconnected vertices."
ExtractCycles::usage = "ExtractCycles[g] returns a list of edge disjoint cycles in graph g."
FerrersDiagram::usage = "FerrersDiagram[p] draws a Ferrers diagram of integer partition p."
FindCycle::usage = "FindCycle[g] finds a list of vertices which define an undirected cycle in graph g. FindCycle[g,Directed] finds a directed cycle in graph g."
FindSet::usage = "FindSet[n,s] returns the root of the set containing n in union-find data structure s."
FirstLexicographicTableau::usage = "FirstLexicographicTableau[p] constructs the first Young tableau with shape described by partition p."
FromAdjacencyLists::usage = "FromAdjacencyLists[l] constructs an adjacency matrix representation for a graph with adjacency lists l, using a circular embedding. FromAdjacencyLists[l,v] uses v as the embedding for the resulting graph."
FromCycles::usage = "FromCycles[c] restores a cycle structure c to the original permutation."
FromInversionVector::usage = "FromInversionVector[v] reconstructs the unique permutation with inversion vector v."
FromOrderedPairs::usage = "FromOrderedPairs[l] constructs an adjacency matrix representation from a list of ordered pairs l, using a circular embedding. FromOrderedPairs[l,v] uses v as the embedding for the resulting graph."
FromUnorderedPairs::usage = "FromUnorderedPairs[l] constructs an adjacency matrix representation from a list of unordered pairs l, using a circular embedding. FromUnorderedPairs[l,v] uses v as the embedding for the resulting graph."
FunctionalGraph::usage = "FunctionalGraph[f,n] constructs the functional digraph on n vertices defined by integer function f."
Girth::usage = "Girth[g] computes the length of the shortest cycle in unweighted graph g."
GraphCenter::usage = "GraphCenter[g] returns a list of the vertices of graph g with minimum eccentricity."
GraphComplement::usage = "GraphComplement[g] returns the complement of graph g."
GraphDifference::usage = "GraphDifference[g,h] constructs the graph resulting from subtracting the adjacency matrix of graph g from that of graph h."
GraphIntersection::usage = "GraphIntersection[g,h] constructs the graph defined by the edges which are in both graph g and graph h."
GraphJoin::usage = "GraphJoin[g,h] constructs the join of graphs g and h."
GraphPower::usage = "GraphPower[g,k] computes the kth power of graph g, meaning there is an edge between any pair of vertices of g with a path between them of length at most k."
GraphProduct::usage = "GraphProduct[g,h] constructs the product of graphs g and h."
GraphSum::usage = "GraphSum[g,h] constructs the graph resulting from adding the adjacency matrices of graphs g and h."
GraphUnion::usage = "GraphUnion[g,h] constructs the union of graphs g and h. GraphUnion[n,g] constructs n copies of graph g, where n is an integer."
GraphicQ::usage = "GraphicQ[s] returns True if the list of integers s is graphic, and thus represents a degree sequence of some graph."
GrayCode::usage = "GrayCode[l] constructs a binary reflected Gray code on set l."
GridGraph::usage = "GridGraph[n,m] constructs an n*m grid graph, the product of paths on n and m vertices."
HamiltonianCycle::usage = "HamiltonianCycle[g] finds a Hamiltonian cycle in graph g if one exists. HamiltonianCycle[g,All] returns all Hamiltonian cycles of graph g."
HamiltonianQ::usage = "HamiltonianQ[g] returns True if there exists a Hamiltonian cycle in graph g, in other words, if there exists a cycle which visits each vertex exactly once."
Harary::usage = "Harary[k,n] constructs the minimal k-connected graph on n vertices."
HasseDiagram::usage = "HasseDiagram[g] constructs a Hasse diagram of the relation defined by directed acyclic graph g."
HeapSort::usage = "HeapSort[l] performs a heap sort on the items of list l."
Heapify::usage = "Heapify[p] builds a heap from permutation p."
HideCycles::usage = "HideCycles[c] canonically encodes the cycle structure c into a unique permutation."
Hypercube::usage = "Hypercube[n] constructs an n-dimensional hypercube."
IdenticalQ::usage = "IdenticalQ[g,h] returns True if graphs g and h have identical adjacency matrices."
IncidenceMatrix::usage = "IncidenceMatrix[g] returns the (0,1) incidence matrix of graph g, which has a row for each vertex and column for each edge and (v,e)=1 if and only if vertex v is incident upon edge e."
IndependentSetQ::usage = "IndependentSetQ[g,i] returns True if the vertices in list i define an independent set in graph g."
Index::usage = "Index[p] returns the index of permutation p, the sum of all subscripts j such that p[j] is greater than p[j+1]."
InduceSubgraph::usage = "InduceSubgraph[g,s] constructs the subgraph of graph g induced by the list of vertices s."
InitializeUnionFind::usage = "InitializeUnionFind[n] initializes a union-find data structure for n elements."
InsertIntoTableau::usage = "InsertIntoTableau[e,t] inserts integer e into Young tableau t using the bumping algorithm."
IntervalGraph::usage = "IntervalGraph[l] constructs the interval graph defined by the list of intervals l."
InversePermutation::usage = "InversePermutation[p] yields the multiplicative inverse of permutation p."
Inversions::usage = "Inversions[p] counts the number of inversions in permutation p."
InvolutionQ::usage = "InvolutionQ[p] returns True if permutation p is its own inverse."
IsomorphicQ::usage = "IsomorphicQ[g,h] returns True if graphs g and h are isomorphic."
IsomorphismQ::usage = "IsomorphismQ[g,h,p] tests if permutation p defines an isomorphism between graphs g and h."
Isomorphism::usage = "Isomorphism[g,h] returns an isomorphism between graphs g and h if one exists."
Josephus::usage = "Josephus[n,m] generates the inverse of the permutation defined by executing every mth member in a circle of n men."
KSubsets::usage = "KSubsets[l,k] returns all subsets of set l containing exactly k elements, ordered lexicographically."
K::usage = "K[n] creates a complete graph on n vertices. K[a,b,c,...,k] creates a complete k-partite graph of the prescribed shape."
LabeledTreeToCode::usage = "LabeledTreeToCode[g] reduces the tree g to its Prufer code."
LastLexicographicTableau::usage = "LastLexicographicTableau[p] constructs the last Young tableau with shape described by partition p."
LexicographicPermutations::usage = "LexicographicPermutations[l] constructs all permutations of list l in lexicographic order."
LexicographicSubsets::usage = "LexicographicSubsets[l] returns all subsets of set l in lexicographic order."
LineGraph::usage = "LineGraph[g] constructs the line graph of graph g."
LongestIncreasingSubsequence::usage = "LongestIncreasingSubsequence[p] find the longest increasing scattered subsequence of permutation p."
M::usage = "M[g] gives the number of edges in undirected graph g."
MakeGraph::usage = "MakeGraph[v,f] constructs the binary relation defined by function f on all pairs of elements of list v."
MakeSimple::usage = "MakeSimple[g] returns an undirected, unweighted graph derived from directed graph g."
MakeUndirected::usage = "MakeUndirected[g] returns a graph with an undirected edge for each directed edge of graph g."
MaximalMatching::usage = "MaximalMatching[g] returns the list of edges associated with a maximal matching of graph g."
MaximumAntichain::usage = "MaximumAntichain[g] returns a largest set of unrelated vertices in partial order g."
MaximumClique::usage = "MaximumClique[g] finds the largest clique in graph g."
MaximumIndependentSet::usage = "MaximumIndependentSet[g] finds the largest independent set of graph g."
MaximumSpanningTree::usage = "MaximumSpanningTree[g] uses Kruskal's algorithm to find a maximum spanning tree of graph g."
MinimumChainPartition::usage = "MinimumChainPartition[g] partitions partial order g into a minimum number of chains."
MinimumChangePermutations::usage = "MinimumChangePermutations[l] constructs all permutations of list l such that adjacent permutations differ by only one transposition."
MinimumSpanningTree::usage = "MinimumSpanningTree[g] uses Kruskal's algorithm to find a minimum spanning tree of graph g."
MinimumVertexCover::usage = "MinimumVertexCover[g] finds the minimum vertex cover of graph g."
MultiplicationTable::usage = "MultiplicationTable[l,f] constructs the complete transition table defined by the binary relation function f on the elements of list l."
NetworkFlowEdges::usage = "NetworkFlowEdges[g,source,sink] returns the adjacency matrix showing the distribution of the maximum flow from source to sink in graph g."
NetworkFlow::usage = "NetworkFlow[g,source,sink] finds the maximum flow through directed graph g from source to sink."
NextComposition::usage = "NextComposition[l] constructs the integer composition which follows l in a canonical order."
NextKSubset::usage = "NextKSubset[l,s] computes the k-subset of list l which appears after k-subsets s in lexicographic order."
NextPartition::usage = "NextPartition[p] returns the integer partition following p in reverse lexicographic order."
NextPermutation::usage = "NextPermutation[p] returns the permutation following p in lexicographic order"
NextSubset::usage = "NextSubset[l,s] constructs the subset of l following subset s in canonical order."
NextTableau::usage = "NextTableau[t] returns the tableau of shape t which follows t in lexicographic order."
NormalizeVertices::usage = "NormalizeVertices[v] returns a list of vertices with the same structure as v but with all coordinates of all points between 0 and 1."
NthPair::usage = "NthPair[n] returns the nth unordered pair of positive integers, when sequenced to minimize the size of the larger integer."
NthPermutation::usage = "NthPermutation[n,l] returns the nth lexicographic permutation of list l."
NthSubset::usage = "NthSubset[n,l] returns the nth subset of list l in canonical order."
NumberOfCompositions::usage = "NumberOfCompositions[n,k] counts the number of distinct compositions of integer n into k parts."
NumberOfDerangements::usage = "NumberOfDerangements[n] counts the derangements on n elements, the permutations without any fixed points."
NumberOfInvolutions::usage = "NumberOfInvolutions[n] counts the number of involutions on n elements."
NumberOfPartitions::usage = "NumberOfPartitions[n] counts the number of distinct integer partitions of n."
NumberOfPermutationsByCycles::usage = "NumberOfPermutationsByCycles[n,m] returns the number of permutations of length n with exactly m cycles."
NumberOfSpanningTrees::usage = "NumberOfSpanningTrees[g] computes the number of distinct labeled spanning trees of graph g."
NumberOfTableaux::usage = "NumberOfTableaux[p] uses the hook length formula to count the number of Young tableaux with shape defined by partition p."
OrientGraph::usage = "OrientGraph[g] assigns a direction to each edge of a bridgeless, undirected graph g, so that the graph is strongly connected."
PartialOrderQ::usage = "PartialOrderQ[g] returns True if the binary relation defined by the adjacency matrix of graph g is a partial order, meaning it is transitive, reflexive, and anti-symmetric."
PartitionQ::usage = "PartitionQ[p] returns True if p is an integer partition."
Partitions::usage = "Partitions[n] constructs all partitions of integer n in reverse lexicographic order."
PathConditionGraph::usage = "PathConditionGraph[g] replaces each non-edge of a graph by an infinite cost, so shortest path algorithms work correctly"
Path::usage = "Path[n] constructs a tree consisting only of a path on n vertices."
PerfectQ::usage = "PerfectQ[g] returns true is g is a perfect graph, meaning that for every induced subgraph of g the size of the largest clique equals the chromatic number."
PermutationGroupQ::usage = "PermutationGroupQ[l] returns True if the list of permutations l forms a permutation group."
PermutationQ::usage = "PermutationQ[p] returns True if p represents a permutation and False otherwise."
Permute::usage = "Permute[l,p] permutes list l according to permutation p."
PlanarQ::usage = "PlanarQ[g] returns True if graph g is planar, meaning it can be drawn in the plane so no two edges cross."
PointsAndLines::usage = "PointsAndLines[g] constructs a partial graphics representation of a graph g."
Polya::usage = "Polya[g,m] returns the polynomial giving the number of colorings, with m colors, of a structure defined by the permutation group g."
PseudographQ::usage = "PseudographQ[g] returns True if graph g is a pseudograph, meaning it contains self-loops."
RadialEmbedding::usage = "RadialEmbedding[g] constructs a radial embedding of graph g, radiating from the center of the graph."
Radius::usage = "Radius[g] computes the radius of graph g, the minimum eccentricity of any vertex of g."
RandomComposition::usage = "RandomComposition[n,k] constructs a random composition of integer n into k parts."
RandomGraph::usage = "RandomGraph[n,p,{l,h}] constructs a random labeled graph on n vertices with an edge probability of p and edge weights of integers drawn uniformly at random from the range (l,h). RandomGraph[n,p,{l,h},Directed] similarly constructs a random directed graph."
RandomHeap::usage = "RandomHeap[n] constructs a random heap on n elements."
RandomKSubset::usage = "RandomKSubset[l,k] returns a random subset of set l with exactly k elements."
RandomPartition::usage = "RandomPartition[n] constructs a random partition of integer n."
RandomPermutation1::usage = "RandomPermutation1[n] sorts random numbers to generate a random permutation."
RandomPermutation2::usage = "RandomPermutation2[n] uses random transpositions to generate random permutations."
RandomPermutation::usage = "RandomPermutation[n] returns a random permutation of length n."
RandomSubset::usage = "RandomSubset[l] creates a random subset of set l."
RandomTableau::usage = "RandomTableau[p] constructs a random Young tableau of shape p."
RandomTree::usage = "RandomTree[n] constructs a random labeled tree on n vertices."
RandomVertices::usage = "RandomVertices[g] assigns a random embedding to graph g."
RankGraph::usage = "RankGraph[g,l] partitions the vertices into classes based on the shortest geodesic distance to a member of list l."
RankPermutation::usage = "RankPermutation[p] computes the rank of permutation p in lexicographic order."
RankSubset::usage = "RankSubset[l,s] computes the rank, in canonical order, of subset s of set l."
RankedEmbedding::usage = "RankedEmbedding[g,l] performs a ranked embedding of graph g, with the vertices ranked in terms of geodesic distance from a member of list l."
ReadGraph::usage = "ReadGraph[f] reads a graph represented as edge lists from file f, and returns the graph as a graph object."
RealizeDegreeSequence::usage = "RealizeDegreeSequence[s] constructs a semirandom graph with degree sequence s."
RegularGraph::usage = "RegularGraph[k,n] constructs a semirandom k-regular graph on n vertices, if such a graph exists."
RegularQ::usage = "RegularQ[g] returns True if g is a regular graph."
RemoveSelfLoops::usage = "RemoveSelfLoops[g] constructs a graph g with the same edges except for any self-loops."
RevealCycles::usage = "RevealCycles[p] unveils the canonical hidden cycle structure of permutation p."
RootedEmbedding::usage = "RootedEmbedding[g,v] constructs a rooted embedding of graph g with vertex v as the root."
RotateVertices::usage = "RotateVertices[v,theta] rotates each vertex position in list v by theta radians around the origin (0,0)."
Runs::usage = "Runs[p] partitions p into contiguous increasing subsequences."
SamenessRelation::usage = "SamenessRelation[l] constructs a binary relation from a list of permutations l which is an equivalence relation if l is a permutation group."
SelectionSort::usage = "SelectionSort[l,f] sorts list l using ordering function f."
SelfComplementaryQ::usage = "SelfComplementaryQ[g] returns True if graph g is self-complementary, meaning it is isomorphic to its complement."
ShakeGraph::usage = "ShakeGraph[g,d] performs a random perturbation of the vertices of graph g, with each vertex moving at most a distance d from its original position."
ShortestPathSpanningTree::usage = "ShortestPathSpanningTree[g,v] constructs the shortest-path spanning tree originating from v, so that the shortest path in graph g from v to any other vertex is the path in the tree."
ShortestPath::usage = "ShortestPath[g,start,end] finds the shortest path between vertices start and end in graph g."
ShowGraph::usage = "ShowGraph[g] displays graph g according to its embedding. ShowGraph[g,Directed] displays directed graph g according to its embedding, with arrows illustrating the orientation of each edge."
ShowLabeledGraph::usage = "ShowLabeledGraph[g] displays graph g according to its embedding, with each vertex labeled with its vertex number. ShowLabeledGraph[g,l] uses the ith element of list l as the label for vertex i."
SignaturePermutation::usage = "SignaturePermutation[p] gives the signature of permutation p."
SimpleQ::usage = "SimpleQ[g] returns True if g is a simple graph, meaning it is unweighted and contains no self-loops."
Spectrum::usage = "Spectrum[g] gives the eigenvalues of graph g."
SpringEmbedding::usage = "SpringEmbedding[g] beautifies the embedding of graph g by modeling the embedding as a system of springs."
StableMarriage::usage = "StableMarriage[mpref,fpref] finds the male optimal stable marriage defined by lists of permutations describing male and female preferences."
Star::usage = "Star[n] constructs a star on n vertices, which is a tree with one vertex of degree n-1."
StirlingFirst::usage = "StirlingFirst[n,k] computes the Stirling numbers of the first kind."
StirlingSecond::usage = "StirlingSecond[n,k] computes the Stirling numbers of the second kind."
Strings::usage = "Strings[l,n] constructs all possible strings of length n from the elements of list l."
StronglyConnectedComponents::usage = "StronglyConnectedComponents[g] returns the strongly connected components of directed graph g."
Subsets::usage = "Subsets[l] returns all subsets of set l."
TableauClasses::usage = "TableauClasses[p] partitions the elements of permutation p into classes according to their initial columns during Young tableaux construction."
TableauQ::usage = "TableauQ[t] returns True if and only if t represents a Young tableau."
TableauxToPermutation::usage = "TableauxToPermutation[t1,t2] constructs the unique permutation associated with Young tableaux t1 and t2, where both tableaux have the same shape. "
Tableaux::usage = "Tableaux[p] constructs all tableaux whose shape is given by integer partition p."
ToAdjacencyLists::usage = "ToAdjacencyLists[g] constructs an adjacency list representation for graph g."
ToCycles::usage = "ToCycles[p] returns the cycle structure of permutation p."
ToInversionVector::usage = "ToInversionVector[p] computes the inversion vector associated with permutation p."
ToOrderedPairs::usage = "ToOrderedPairs[g] constructs a list of ordered pairs representing the edges of undirected graph g."
ToUnorderedPairs::usage = "ToUnorderedPairs[g] constructs a list of vertex pairs representing graph g, with one pair per undirected edge."
TopologicalSort::usage = "TopologicalSort[g] returns a permutation of the vertices of directed acyclic graph g such that an edge (i,j) implies vertex i appears before vertex j."
TransitiveClosure::usage = "TransitiveClosure[g] finds the transitive closure of graph g, the superset of g which contains edge {x,y} iff there is a path from x to y."
TransitiveQ::usage = "TransitiveQ[g] returns True if graph g defines a transitive relation."
TransitiveReduction::usage = "TransitiveReduction[g] finds the smallest graph which has the same transitive closure as g."
TranslateVertices::usage = "TranslateVertices[v,{x,y}] adds the vector {x,y} to each vertex in list v."
TransposePartition::usage = "TransposePartition[p] reflects a partition p of k parts along the main diagonal, creating a partition with maximum part k."
TransposeTableau::usage = "TransposeTableau[t] reflects a Young tableau t along the main diagonal, creating a different tableau."
TravelingSalesmanBounds::usage = "TravelingSalesmanBounds[g] computes upper and lower bounds on the minimum cost traveling salesman tour of graph g."
TravelingSalesman::usage = "TravelingSalesman[g] finds the optimal traveling salesman tour in graph g."
TreeQ::usage = "TreeQ[g] returns True if graph g is a tree."
TriangleInequalityQ::usage = "TriangleInequalityQ[g] returns True if the weight function defined by the adjacency matrix of graph g satisfies the triangle inequality."
Turan::usage = "Turan[n,p] constructs the Turan graph, the extremal graph on n vertices which does not contain K[p]."
TwoColoring::usage = "TwoColoring[g] finds a two-coloring of graph g if g is bipartite."
UndirectedQ::usage = "UndirectedQ[g] returns True if graph g is undirected."
UnionSet::usage = "UnionSet[a,b,s] merges the sets containing a and b in union-find data structure s."
UnweightedQ::usage = "UnweightedQ[g] returns True if all entries in the adjacency matrix of graph g are zero or one."
V::usage = "V[g] gives the order or number of vertices of graph g."
VertexColoring::usage = "VertexColoring[g] uses Brelaz's heuristic to find a good, but not necessarily minimal, vertex coloring of graph g."
VertexConnectivity::usage = "VertexConnectivity[g] computes the minimum number of vertices whose deletion from graph g disconnects it."
VertexCoverQ::usage = "VertexCoverQ[g,c] returns True if the vertices in list c define a vertex cover of graph g."
Vertices::usage = "Vertices[g] returns the embedding of graph g."
WeaklyConnectedComponents::usage = "WeaklyConnectedComponents[g] returns the weakly connected components of directed graph g."
Wheel::usage = "Wheel[n] constructs a wheel on n vertices, which is the join of K[1] and Cycle[n-1]."
WriteGraph::usage = "WriteGraph[g,f] writes graph g to file f using an edge list representation."
