Changes between Initial Version and Version 1 of Mathematica Graph Theory


Ignore:
Timestamp:
02/06/13 12:49:49 (9 years ago)
Author:
azi
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Mathematica Graph Theory

    v1 v1  
     1[[TOC]]
     2
     3
     4= Graph theory features in Mathematica and Sage  =
     5
     6Attached is a spreadsheet listing the Sage graph library functions and the equivalent functions in Combinatorica.  I've also put a few notes in about the implementation differences and other notes suggesting changes to Sage functions.
     7
     8In the following list, I tried to make the functions link to the official documentation at the Wolfram website.  I hope it all worked right.
     9
     10
     11== Construction and representations ==
     12
     13
     14=== Graphs and components ===
     15
     16
     17 * Edges
     18   * Sage
     19     * [http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.edge_iterator graphs.generic_graph.GenericGraph]
     20       * [http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.edge_iterator edge_iterator]
     21       * [http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.edges edges]
     22       * [http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.multiple_edges multiple_edges]
     23     * [http://www.sagemath.org/doc/reference/sage/graphs/base/sparse_graph.html#sage.graphs.base.sparse_graph.SparseGraphBackend graphs.base.sparse_graph.SparseGraphBackend]
     24       * [http://www.sagemath.org/doc/reference/sage/graphs/base/sparse_graph.html#sage.graphs.base.sparse_graph.SparseGraphBackend.iterator_edges iterator_edges]
     25       * [http://www.sagemath.org/doc/reference/sage/graphs/base/sparse_graph.html#sage.graphs.base.sparse_graph.SparseGraphBackend.iterator_in_edges iterator_in_edges]
     26       * [http://www.sagemath.org/doc/reference/sage/graphs/base/sparse_graph.html#sage.graphs.base.sparse_graph.SparseGraphBackend.iterator_out_edges iterator_out_edges]
     27     * [http://www.sagemath.org/doc/reference/sage/graphs/base/dense_graph.html#sage.graphs.base.dense_graph.DenseGraphBackend graphs.base.dense_graph.DenseGraphBackend]
     28       * [http://www.sagemath.org/doc/reference/sage/graphs/base/dense_graph.html#sage.graphs.base.dense_graph.DenseGraphBackend.iterator_edges iterator_edges]
     29       * [http://www.sagemath.org/doc/reference/sage/graphs/base/dense_graph.html#sage.graphs.base.dense_graph.DenseGraphBackend.iterator_in_edges iterator_in_edges]
     30       * [http://www.sagemath.org/doc/reference/sage/graphs/base/dense_graph.html#sage.graphs.base.dense_graph.DenseGraphBackend.iterator_out_edges iterator_out_edges]
     31   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Edges.html Edges][g] gives the list of edges in g.
     32
     33 * Graph
     34   * Sage
     35     * [http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html generic graphs]
     36     * [http://www.sagemath.org/doc/reference/sage/graphs/graph.html undirected graphs]
     37     * [http://www.sagemath.org/doc/reference/sage/graphs/digraph.html directed graphs]
     38     * [http://www.sagemath.org/doc/reference/sage/graphs/base/c_graph.html fast compiled graphs]
     39     * [http://www.sagemath.org/doc/reference/sage/graphs/base/sparse_graph.html fast sparse graphs]
     40     * [http://www.sagemath.org/doc/reference/sage/graphs/base/dense_graph.html fast dense graphs]
     41   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Graph.html Graph][e, v, opts] represents a graph object where e is the list of edges annotated with graphics options, v is a list of vertices annotated with graphics options, and opts is a set of global graph options.
     42
     43 * Number of edges
     44   * Sage
     45     * [http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph graphs.generic_graph.GenericGraph]
     46       * [http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.num_edges num_edges]
     47       * [http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.size size]
     48     * [http://www.sagemath.org/doc/reference/sage/graphs/base/c_graph.html#sage.graphs.base.c_graph.CGraphBackend graphs.base.c_graph.CGraphBackend]
     49       * [http://www.sagemath.org/doc/reference/sage/graphs/base/c_graph.html#sage.graphs.base.c_graph.CGraphBackend.num_edges num_edges]
     50   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/M.html M][g] gives the number of edges in the graph g.
     51
     52 * Number of vertices
     53   * Sage
     54     * [http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph graphs.generic_graph.GenericGraph]
     55       * [http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.num_verts num_verts]
     56       * [http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.order order]
     57     * [http://www.sagemath.org/doc/reference/sage/graphs/base/c_graph.html#sage.graphs.base.c_graph.CGraphBackend graphs.base.c_graph.CGraphBackend]
     58       * [http://www.sagemath.org/doc/reference/sage/graphs/base/c_graph.html#sage.graphs.base.c_graph.CGraphBackend.num_verts num_verts]
     59   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/V.html V][g] gives the order or number of vertices of the graph g.
     60
     61 * Vertices
     62   * Sage
     63     * [http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph graphs.generic_graph.GenericGraph]
     64       * [http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.vertex_iterator vertex_iterator]
     65       * [http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.vertices vertices]
     66     * [http://www.sagemath.org/doc/reference/sage/graphs/base/c_graph.html#sage.graphs.base.c_graph.CGraph graphs.base.c_graph.CGraph]
     67       * [http://www.sagemath.org/doc/reference/sage/graphs/base/c_graph.html#sage.graphs.base.c_graph.CGraph.verts verts]
     68     * [http://www.sagemath.org/doc/reference/sage/graphs/base/c_graph.html#sage.graphs.base.c_graph.CGraphBackend graphs.base.c_graph.CGraphBackend]
     69       * [http://www.sagemath.org/doc/reference/sage/graphs/base/c_graph.html#sage.graphs.base.c_graph.CGraphBackend.iterator_verts iterator_verts]
     70   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Vertices.html Vertices][g] gives the coordinates of each vertex of graph g embedded in a plane.
     71   
     72
     73=== Graph representations ===
     74
     75
     76 * From adjacency lists
     77   * Sage ---
     78   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/FromAdjacencyLists.html FromAdjacencyLists][l] constructs an edge list representation for a graph from the given adjacency lists l, using a circular embedding.
     79
     80 * From adjacency matrix
     81   * Sage ---
     82   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/FromAdjacencyMatrix.html FromAdjacencyMatrix][m] constructs a graph from a given adjacency matrix m, using a circular embedding.
     83
     84 * From ordered pairs
     85   * Sage ---
     86   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/FromOrderedPairs.html FromOrderedPairs][l] constructs an edge list representation from a list of ordered pairs l, using a circular embedding.
     87   
     88 * From unordered pairs
     89   * Sage ---
     90   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/FromUnorderedPairs.html FromUnorderedPairs][l] constructs an edge list representation from a list of unordered pairs l, using a circular embedding.
     91
     92 * Incidence matrix
     93   * Sage ---
     94   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/IncidenceMatrix.html IncidenceMatrix][g] returns the (0,1)-matrix of graph g, which has a row for each vertex and a column for each edge and (v,e)=1 if and only if vertex v is incident upon edge e. For a directed graph, (v,e)=1 if edge e is outgoing from v.
     95
     96 * To adjacency lists
     97   * Sage ---
     98   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ToAdjacencyLists.html ToAdjacencyLists][g] constructs an adjacency list representation for graph g. It allows an option called Type that takes on values All or Simple. Type -> All is the default setting of the option, and this permits self-loops and multiple edges to be reported in the adjacency lists. Type -> Simple deletes self-loops and multiple edges from the constructed adjacency lists. [http://reference.wolfram.com/mathematica/Combinatorica/ref/ToAdjacencyLists.html ToAdjacencyLists][g, [http://reference.wolfram.com/mathematica/Combinatorica/ref/EdgeWeight.html EdgeWeight]] returns an adjacency list representation along with edge weights.
     99
     100 * To adjacency matrix
     101   * Sage ---
     102   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ToAdjacencyMatrix.html ToAdjacencyMatrix][g] constructs an adjacency matrix representation for graph g.
     103
     104 * To ordered pairs
     105   * Sage ---
     106   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ToOrderedPairs.html ToOrderedPairs][g] constructs a list of ordered pairs representing the edges of the graph g. If g is undirected each edge is interpreted as two ordered pairs. An option called Type that takes on values Simple or All can be used to affect the constructed representation. Type -> Simple forces the removal of multiple edges and self-loops. Type -> All keeps all information and is the default option.
     107
     108 * To unordered pairs
     109   * Sage ---
     110   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ToUnorderedPairs.html ToUnorderedPairs][g] constructs a list of unordered pairs representing the edges of graph g. Each edge, directed or undirected, results in a pair in which the smaller vertex appears first. An option called Type that takes on values All or Simple can be used, and All is the default value. Type -> Simple ignores multiple edges and self-loops in g.
     111
     112
     113=== Displaying graphs ===
     114
     115
     116 * Animate graph
     117   * Sage ---
     118   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/AnimateGraph.html AnimateGraph][g, l] displays graph g with each element in the list l successively highlighted. Here l is a list containing vertices and edges of g. An optional flag, which takes on the values All and One, can be used to inform the function about whether objects highlighted earlier will continue to be highlighted or not. The default value of flag is All. All the options allowed by the function Highlight are permitted by [http://reference.wolfram.com/mathematica/Combinatorica/ref/AnimateGraph.html AnimateGraph], as well. See the usage message of Highlight for more details.
     119
     120 * Change edges
     121   * Sage ---
     122   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ChangeEdges.html ChangeEdges][g, e] replaces the edges of graph g with the edges in e. e can have the form {{s1, t1}, {s2, t2}, ...} or the form { {{s1, t1}, gr1}, {{s2, t2}, gr2}, ...}, where {s1, t1}, {s2, t2}, ... are endpoints of edges and gr1, gr2, ... are graphics information associated with edges.
     123
     124 * Change vertices
     125   * Sage ---
     126   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ChangeVertices.html ChangeVertices][g, v] replaces the vertices of graph g with the vertices in the given list v. v can have the form {{x1, y1}, {x2, y2}, ...} or the form {{{x1, y1}, gr1}, {{x2, y2}, gr2}, ...}, where {x1, y1}, {x2, y2}, ... are coordinates of points and gr1, gr2, ... are graphics information associated with vertices.
     127
     128 * Circular embedding
     129   * Sage ---
     130   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/CircularEmbedding.html CircularEmbedding][n] constructs a list of n points equally spaced on a circle. [http://reference.wolfram.com/mathematica/Combinatorica/ref/CircularEmbedding.html CircularEmbedding][g] embeds the vertices of g equally spaced on a circle.
     131
     132 * Edge color
     133   * Sage ---
     134   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/EdgeColor.html EdgeColor] is an option that allows the user to associate colors with edges. Black is the default color. EdgeColor can be set as part of the graph data structure or in ShowGraph.
     135
     136 * Edge direction
     137   * Sage ---
     138   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/EdgeDirection.html EdgeDirection] is an option that takes on values True or False allowing the user to specify whether the graph is directed or not. EdgeDirection can be set as part of the graph data structure or in ShowGraph.
     139
     140 * Edge label
     141   * Sage ---
     142   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/EdgeLabel.html EdgeLabel] is an option that can take on values True or False, allowing the user to associate labels to edges. By default, there are no edge labels. The EdgeLabel option can be set as part of the graph data structure or in ShowGraph.
     143
     144 * Edge label color
     145   * Sage ---
     146   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/EdgeLabelColor.html EdgeLabelColor] is an option that allows the user to associate different colors to edge labels. Black is the default color. EdgeLabelColor can be set as part of the graph data structure or in ShowGraph.
     147
     148 * Edge label position
     149   * Sage ---
     150   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/EdgeLabelPosition.html EdgeLabelPosition] is an option that allows the user to place an edge label in a certain position relative to the midpoint of the edge. LowerLeft is the default value of this option. EdgeLabelPosition can be set as part of the graph data structure or in ShowGraph.
     151
     152 * Edge style
     153   * Sage ---
     154   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/EdgeStyle.html EdgeStyle] is an option that allows the user to associate different sizes and shapes to edges. A line segment is the default edge. EdgeStyle can be set as part of the graph data structure or in ShowGraph.
     155
     156 * Edge weight
     157   * Sage ---
     158   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/EdgeWeight.html EdgeWeight] is an option that allows the user to associate weights with edges. 1 is the default weight. [http://reference.wolfram.com/mathematica/Combinatorica/ref/EdgeWeight.html EdgeWeight] can be set as part of the graph data structure.
     159
     160 * Graph options
     161   * Sage ---
     162   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/GraphOptions.html GraphOptions][g] returns the display options associated with g.
     163
     164 * Highlight
     165   * Sage ---
     166   * Mathematica --- Highlight[g, p] displays g with elements in p highlighted. The second argument p has the form {s1, s2,...}, where the sis are disjoint subsets of vertices and edges of g. The options, [http://reference.wolfram.com/mathematica/Combinatorica/ref/HighlightedVertexStyle.html HighlightedVertexStyle], [http://reference.wolfram.com/mathematica/Combinatorica/ref/HighlightedEdgeStyle.html HighlightedEdgeStyle], [http://reference.wolfram.com/mathematica/Combinatorica/ref/HighlightedVertexColors.html HighlightedVertexColors], and [http://reference.wolfram.com/mathematica/Combinatorica/ref/HighlightedEdgeColors.html HighlightedEdgeColors] are used to determine the appearance of the highlighted elements of the graph. The default settings of the style options are [http://reference.wolfram.com/mathematica/Combinatorica/ref/HighlightedVertexStyle.html HighlightedVertexStyle]->Disk[Large] and [http://reference.wolfram.com/mathematica/Combinatorica/ref/HighlightedEdgeStyle.html HighlightedEdgeStyle]->Thick. The options [http://reference.wolfram.com/mathematica/Combinatorica/ref/HighlightedVertexColors.html HighlightedVertexColors] and [http://reference.wolfram.com/mathematica/Combinatorica/ref/HighlightedEdgeColors.html HighlightedEdgeColors] are both set to {Black, Red, Blue, Green, Yellow, Purple, Brown, Orange, Olive, Pink, [http://reference.wolfram.com/mathematica/Combinatorica/ref/DeepPink.html DeepPink], [http://reference.wolfram.com/mathematica/Combinatorica/ref/DarkGreen.html DarkGreen], Maroon, Navy}. The colors are chosen from the palette of colors with color 1 used for s1, color 2 used for s2, and so on. If there are more parts than colors, then the colors are used cyclically. The function permits all the options that [http://reference.wolfram.com/mathematica/Combinatorica/ref/SetGraphOptions.html SetGraphOptions] permits, for example, [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexColor.html VertexColor], [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexStyle.html VertexStyle], [http://reference.wolfram.com/mathematica/Combinatorica/ref/EdgeColor.html EdgeColor], and [http://reference.wolfram.com/mathematica/Combinatorica/ref/EdgeStyle.html EdgeStyle]. These options can be used to control the appearance of the non-highlighted vertices and edges.
     167
     168 * Highlighted edge colors
     169   * Sage ---
     170   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/HighlightedEdgeColors.html HighlightedEdgeColors] is an option to Highlight that determines which colors are used for the highlighted edges.
     171
     172 * Highlighted edge style
     173   * Sage ---
     174   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/HighlightedEdgeStyle.html HighlightedEdgeStyle] is an option to Highlight that determines how the highlighted edges are drawn.
     175
     176 * Highlighted vertex colors
     177   * Sage ---
     178   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/HighlightedVertexColors.html HighlightedVertexColors] is an option to Highlight that determines which colors are used for the highlighted vertices.
     179
     180 * Highlighted vertex style
     181   * Sage ---
     182   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/HighlightedVertexStyle.html HighlightedVertexStyle] is an option to Highlight that determines how the highlighted vertices are drawn.
     183
     184 * Loop position
     185   * Sage ---
     186   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/LoopPosition.html LoopPosition] is an option to ShowGraph whose values tell ShowGraph where to position a loop around a vertex. This option can take on values UpperLeft, UpperRight, LowerLeft, and LowerRight.
     187
     188 * Ranked embedding
     189   * Sage ---
     190   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/RankedEmbedding.html RankedEmbedding][l] takes a set partition l of vertices {1, 2,..., n} and returns an embedding of the vertices in the plane such that the vertices in each block occur on a vertical line with block 1 vertices on the leftmost line, block 2 vertices in the next line, and so on. [http://reference.wolfram.com/mathematica/Combinatorica/ref/RankedEmbedding.html RankedEmbedding][g, l] takes a graph g and a set partition l of the vertices of g and returns the graph g with vertices embedded according to [http://reference.wolfram.com/mathematica/Combinatorica/ref/RankedEmbedding.html RankedEmbedding][l]. [http://reference.wolfram.com/mathematica/Combinatorica/ref/RankedEmbedding.html RankedEmbedding][g, s] takes a graph g and a set s of vertices of g and returns a ranked embedding of g in which vertices in s are in block 1, vertices at distance 1 from any vertex in block 1 are in block 2, and so on.
     191
     192 * Radial embedding
     193   * Sage ---
     194   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/RadialEmbedding.html RadialEmbedding][g, v] constructs a radial embedding of the graph g in which vertices are placed on concentric circles around v depending on their distance from v. [http://reference.wolfram.com/mathematica/Combinatorica/ref/RadialEmbedding.html RadialEmbedding][g] constructs a radial embedding of graph g, radiating from the center of the graph.
     195
     196 * Rank graph
     197   * Sage ---
     198   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/RankGraph.html RankGraph][g, l] partitions the vertices into classes based on the shortest geodesic distance to a member of list l.
     199
     200 * Rooted embedding
     201   * Sage ---
     202   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/RootedEmbedding.html RootedEmbedding][g, v] constructs a rooted embedding of graph g with vertex v as the root. [http://reference.wolfram.com/mathematica/Combinatorica/ref/RootedEmbedding.html RootedEmbedding][g] constructs a rooted embedding with a center of g as the root.
     203
     204 * Rotate vertices
     205   * Sage ---
     206   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/RotateVertices.html RotateVertices][v, theta] rotates each vertex position in list v by theta radians about the origin (0, 0). [http://reference.wolfram.com/mathematica/Combinatorica/ref/RotateVertices.html RotateVertices][g, theta] rotates the embedding of the graph g by theta radians about the origin (0, 0).
     207
     208 * Set edge labels
     209   * Sage ---
     210   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/SetEdgeLabels.html SetEdgeLabels][g, l] assigns the labels in l to edges of g.
     211
     212 * Set edge weights
     213   * Sage ---
     214   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/SetEdgeWeights.html SetEdgeWeights][g] assigns random real weights in the range [0,1] to edges in g.
     215
     216 * Set graph options
     217   * Sage ---   
     218   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/SetGraphOptions.html SetGraphOptions][g, opts] returns g with the options opts set. [http://reference.wolfram.com/mathematica/Combinatorica/ref/SetGraphOptions.html SetGraphOptions][g, {v1, v2, ..., vopts}, gopts] returns the graph with the options vopts set for vertices v1, v2, ... and the options gopts set for the graph g. [http://reference.wolfram.com/mathematica/Combinatorica/ref/SetGraphOptions.html SetGraphOptions][g, {e1, e2,..., eopts}, gopts], with edges e1, e2,..., works similarly. [http://reference.wolfram.com/mathematica/Combinatorica/ref/SetGraphOptions.html SetGraphOptions][g, {{elements1, opts1}, {elements2, opts2},...}, opts] returns g with the options opts1 set for the elements in the sequence elements1, the options opts2 set for the elements in the sequence elements2, and so on. Here, elements can be a sequence of edges or a sequence of vertices. A tag that takes on values One or All can also be passed in as an argument before any options. The default value of the tag is All and it is useful if the graph has multiple edges. It informs the function about whether all edges that connect a pair of vertices are to be affected or only one edge is affected.
     219
     220 * Set vertex labels
     221   * Sage ---
     222   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/SetVertexLabels.html SetVertexLabels][g, l] assigns the labels in l to vertices of g. If l is shorter than the number of vertices in g, then labels get assigned cyclically. If l is longer than the number of vertices in g, then the extra labels are ignored."
     223
     224 * Set vertex weights
     225   * Sage ---
     226   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/SetVertexWeights.html SetVertexWeights][g] assigns random real weights in the range [0, 1] to vertices in g. [http://reference.wolfram.com/mathematica/Combinatorica/ref/SetVertexWeights.html SetVertexWeights] accepts options [http://reference.wolfram.com/mathematica/Combinatorica/ref/WeightingFunction.html WeightingFunction] and [http://reference.wolfram.com/mathematica/Combinatorica/ref/WeightRange.html WeightRange]. [http://reference.wolfram.com/mathematica/Combinatorica/ref/WeightingFunction.html WeightingFunction] can take values Random, [http://reference.wolfram.com/mathematica/Combinatorica/ref/RandomInteger.html RandomInteger], or any pure function that takes two arguments, an integer as the first argument and a pair {number, number} as the second argument. [http://reference.wolfram.com/mathematica/Combinatorica/ref/WeightRange.html WeightRange] can be an integer range or a real range. The default value for [http://reference.wolfram.com/mathematica/Combinatorica/ref/WeightingFunction.html WeightingFunction] is Random and the default value for [http://reference.wolfram.com/mathematica/Combinatorica/ref/WeightRange.html WeightRange] is [0, 1]. [http://reference.wolfram.com/mathematica/Combinatorica/ref/SetVertexWeights.html SetVertexWeights][g, w] assigns the weights in the weight list w to the vertices of g. [http://reference.wolfram.com/mathematica/Combinatorica/ref/SetVertexWeights.html SetVertexWeights][g, vs, w] assigns the weights in the weight list w to the vertices in the vertex list vs.
     227
     228 * Shake graph
     229   * Sage ---
     230   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ShakeGraph.html 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.
     231
     232 * Show graph
     233   * Sage ---
     234   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ShowGraph.html ShowGraph][g] displays the graph g.
     235
     236 * Show graph array
     237   * Sage ---
     238   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ShowGraphArray.html ShowGraphArray][{g1, g2, ...}] displays a row of graphs.
     239
     240 * Show labeled graph
     241   * Sage ---
     242   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ShowLabeledGraph.html ShowLabeledGraph][g] displays graph g according to its embedding, with each vertex labeled with its vertex number. [http://reference.wolfram.com/mathematica/Combinatorica/ref/ShowLabeledGraph.html ShowLabeledGraph][g, l] uses the ith element of list l as the label for vertex i.
     243
     244 * Spring embedding
     245   * Sage ---
     246   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/SpringEmbedding.html SpringEmbedding][g] beautifies the embedding of graph g by modeling the embedding as a system of springs. [http://reference.wolfram.com/mathematica/Combinatorica/ref/SpringEmbedding.html SpringEmbedding][g, step, increment] can be used to refine the algorithm. The value of step tells the function for how many iterations to run the algorithm. The value of increment tells the function the distance to move the vertices at each step. The default values are 10 and 0.15 for step and increment, respectively.
     247
     248 * Translate vertices
     249   * Sage ---
     250   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/TranslateVertices.html TranslateVertices][v, {x, y}] adds the vector {x, y} to the vertex embedding location of each vertex in list v. [http://reference.wolfram.com/mathematica/Combinatorica/ref/TranslateVertices.html TranslateVertices][g, {x, y}] translates the embedding of the graph g by the vector {x, y}.
     251
     252 * Vertex color
     253   * Sage ---
     254   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexColor.html VertexColor] is an option that allows the user to associate colors with vertices.
     255
     256 * Vertex label
     257   * Sage ---
     258   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexLabel.html VertexLabel] is an option that can take on values True or False, allowing the user to set and display vertex labels.
     259
     260 * Vertex label color
     261   * Sage ---
     262   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexLabelColor.html VertexLabelColor] is an option that allows the user to associate different colors to vertex labels.
     263
     264 * Vertex label position
     265   * Sage ---
     266   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexLabelPosition.html VertexLabelPosition] is an option that allows the user to place a vertex label in a certain position relative to the vertex.
     267
     268 * Vertex number
     269   * Sage ---
     270   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexNumber.html VertexNumber] is an option that can take on values True or False. This can be used in ShowGraph to display or suppress vertex numbers.
     271
     272 * Vertex number color
     273   * Sage ---
     274   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexNumberColor.html VertexNumberColor] is an option that can be used in ShowGraph to associate different colors to vertex numbers.
     275
     276 * Vertex number position
     277   * Sage ---
     278   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexNumberPosition.html VertexNumberPosition] is an option that can be used in ShowGraph to display a vertex number in a certain position relative to the vertex.
     279
     280 * Vertex style
     281   * Sage ---
     282   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexStyle.html VertexStyle] is an option that allows the user to associate different sizes and shapes to vertices.
     283
     284 * Vertex weight
     285   * Sage ---
     286   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexWeight.html VertexWeight] is an option that allows the user to associate weights with vertices. 0 is the default weight. [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexWeight.html VertexWeight] can be set as part of the graph data structure.
     287
     288 * Zoom
     289   * Sage ---   
     290   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Zoom.html Zoom][{i, j, k, ...}] is a value that the [http://reference.wolfram.com/mathematica/Combinatorica/ref/PlotRange.html PlotRange] option can take on in [http://reference.wolfram.com/mathematica/Combinatorica/ref/ShowGraph.html ShowGraph]. Setting [http://reference.wolfram.com/mathematica/Combinatorica/ref/PlotRange.html PlotRange] to this value zooms the display to contain the specified subset of vertices, i, j, k, ....
     291
     292
     293=== Constructing graphs ===
     294
     295
     296 * Add edge
     297   * Sage ---
     298   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/AddEdge.html AddEdge][g, e] returns a graph g with the new edge e added. e can have the form {a,b} or the form {{a,b},options}.
     299
     300 * Add edges
     301   * Sage ---
     302   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/AddEdges.html AddEdges][g, edgeList] gives graph g with the new edges in edgeList added. edgeList can have the form {a,b} to add a single edge {a,b} or the form {{a,b},{c,d},...}, to add edges {a,b},{c,d},... or the form {{{a,b},x},{{c,d},y},...}, where x and y can specify graphics information associated with {a,b} and {c,d}, respectively.
     303
     304 * Add vertex
     305   * Sage ---
     306   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/AddVertex.html AddVertex][g] adds one disconnected vertex to graph g.
     307
     308 * Add vertices
     309   * Sage ---
     310   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/AddVertices.html AddVertices][g, n] adds n disconnected vertices to graph g.
     311
     312 * Approximate vertex cover
     313   * Sage ---
     314   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ApproximateVertexCover.html ApproximateVertexCover][g] produces a vertex cover of graph g whose size is guaranteed to be within twice the optimal size.
     315
     316 * Cartesian product
     317   * Sage ---
     318   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/CartesianProduct.html CartesianProduct][l1, l2] gives the Cartesian product of lists l_1 and l_2.
     319
     320 * Code to labeled tree
     321   * Sage ---
     322   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/CodeToLabeledTree.html CodeToLabeledTree][l] constructs the unique labeled tree on n vertices from the Prufer code l, which consists of a list of n-2 integers between 1 and n.
     323
     324 * Complete binary tree
     325   * Sage ---
     326   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/CompleteBinaryTree.html CompleteBinaryTree][n] returns a complete binary tree on n vertices.
     327
     328 * Complete k-ary tree
     329   * Sage ---
     330   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/CompleteKaryTree.html CompleteKaryTree][n, k] returns a complete k-ary tree on n vertices.
     331
     332 * Contract
     333   * Sage ---
     334   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Contract.html Contract][g, {x, y}] gives the graph resulting from contracting the pair of vertices {x, y} of graph g.
     335
     336 * Delete cycle
     337   * Sage ---
     338   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/DeleteCycle.html DeleteCycle][g, c] deletes a simple cycle c from graph g. c is specified as a sequence of vertices in which the first and last vertices are identical. g can be directed or undirected. If g does not contain c, it is returned unchanged; otherwise g is returned with c deleted."
     339
     340 * Delete edge
     341   * Sage ---
     342   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/DeleteEdge.html DeleteEdge][g, e] gives graph g minus e. If g is undirected, then e is treated as an undirected edge; otherwise it is treated as a directed edge. If there are multiple edges between the specified vertices, only one edge is deleted.
     343
     344 * Delete edges
     345   * Sage ---
     346   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/DeleteEdges.html DeleteEdges][g, edgeList] gives graph g minus the list of edges edgeList. If g is undirected, then the edges in edgeList are treated as undirected edges; otherwise they are treated as directed edges. If there are multiple edges that qualify, then only one edge is deleted.
     347
     348 * Delete vertex
     349   * Sage ---
     350   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/DeleteVertex.html DeleteVertex][g, v] deletes a single vertex v from graph g. Here v is a vertex number.
     351
     352 * Delete vertices
     353   * Sage ---
     354   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/DeleteVertices.html DeleteVertices][g, vList] deletes vertices in vList from graph g. vList has the form {i,j,...}, where i,j,... are vertex numbers.
     355
     356 * Exact random graph
     357   * Sage ---
     358   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ExactRandomGraph.html ExactRandomGraph][n, e] constructs a random labeled graph of exactly e edges and n vertices.
     359
     360 * Functional graph
     361   * Sage ---
     362   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/FunctionalGraph.html FunctionalGraph][f, v] takes a set v and a function f from v to v and constructs a directed graph with vertex set v and edges (x, f(x)) for each x in v. [http://reference.wolfram.com/mathematica/Combinatorica/ref/FunctionalGraph.html FunctionalGraph][f, v], where f is a list of functions, constructs a graph with vertex set v and edge set (x, fi(x)) for every fi in f. An option called Type that takes on the values Directed and Undirected is allowed. Type -> Directed is the default, while Type -> Undirected returns the corresponding underlying undirected graph. [http://reference.wolfram.com/mathematica/Combinatorica/ref/FunctionalGraph.html FunctionalGraph][f, n] takes a nonnegative integer n and a function f from {0,1,..., n-1} onto itself and produces the directed graph with vertex set {0, 1,..., n-1} and edge set {x, f(x)} for each vertex x."
     363
     364 * Graph complement
     365   * Sage ---
     366   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/GraphComplement.html GraphComplement][g] gives the complement of graph g.
     367
     368 * Graph difference
     369   * Sage ---
     370   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/GraphDifference.html GraphDifference][g, h] constructs the graph resulting from subtracting the edges of graph h from the edges of graph g.
     371
     372 * Graph intersection
     373   * Sage ---
     374   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/GraphIntersection.html GraphIntersection][g1, g2, ...] constructs the graph defined by the edges that are in all the graphs g1, g2, ....
     375
     376 * Graph join
     377   * Sage ---
     378   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/GraphJoin.html GraphJoin][g1, g2, ...] constructs the join of graphs g1, g2, and so on. This is the graph obtained by adding all possible edges between different graphs to the graph union of g1, g2, ....
     379
     380 * Graph product
     381   * Sage ---
     382   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/GraphProduct.html GraphProduct][g1, g2, ...] constructs the product of graphs g_1, g_2, and so forth.
     383
     384 * Graph sum
     385   * Sage ---
     386   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/GraphSum.html GraphSum][g1, g2, ...] constructs the graph resulting from joining the edge lists of graphs g1, g2, and so forth.
     387
     388 * Graph union
     389   * Sage ---
     390   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/GraphUnion.html GraphUnion][g1, g2, ...] constructs the union of graphs g_1, g_2, and so forth.
     391
     392 * Greedy vertex cover
     393   * Sage --- Unavailable
     394   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/GreedyVertexCover.html GreedyVertexCover][g] returns a vertex cover of graph g constructed using the greedy algorithm. This is a natural heuristic for constructing a vertex cover, but it can produce poor vertex covers.
     395
     396 * Independent set q
     397   * Sage ---
     398   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/IndependentSetQ.html IndependentSetQ][g, i] yields True if the vertices in list i define an independent set in graph g.
     399
     400 * Induce subgraph
     401   * Sage ---
     402   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/InduceSubgraph.html InduceSubgraph][g, s] constructs the subgraph of graph g induced by the list of vertices s.
     403
     404 * Interval graph
     405   * Sage --- #8284
     406   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/IntervalGraph.html IntervalGraph][l] constructs the interval graph defined by the list of intervals l.
     407
     408 * Labeled tree to code
     409   * Sage ---
     410   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/LabeledTreeToCode.html LabeledTreeToCode][g] reduces the tree g to its Prufer code.
     411
     412 * Line graph
     413   * Sage ---
     414   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/LineGraph.html LineGraph][g] constructs the line graph of graph g.
     415
     416 * Make directed
     417   * Sage ---
     418   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/MakeDirected.html MakeDirected][g] constructs a directed graph from a given undirected graph g by replacing each undirected edge in g by two directed edges pointing in opposite directions.
     419
     420 * Make graph
     421   * Sage ---
     422   * Mathemaica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/MakeGraph.html MakeGraph][v, f] constructs the graph whose vertices correspond to v and edges between pairs of vertices x and y in v for which the binary relation defined by the Boolean function f is True. [http://reference.wolfram.com/mathematica/Combinatorica/ref/MakeGraph.html MakeGraph] takes two options, Type and [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexLabel.html VertexLabel]. Type can be set to Directed or Undirected and this tells [http://reference.wolfram.com/mathematica/Combinatorica/ref/MakeGraph.html MakeGraph] whether to construct a directed or an undirected graph. The default setting is Directed. [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexLabel.html VertexLabel] can be set to True or False, with False being the default setting. Using [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexLabel.html VertexLabel] -> True assigns labels derived from v to the vertices of the graph.
     423
     424 * Make simple
     425   * Sage ---   
     426   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/MakeSimple.html MakeSimple][g] gives the undirected graph, free of multiple edges and self-loops derived from graph g.
     427
     428 * Make undirected
     429   * Sage ---
     430   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/MakeUndirected.html MakeUndirected][g] gives the underlying undirected graph of the given directed graph g.
     431
     432 * Maximum clique
     433   * Sage --- [http://www.sagemath.org/doc/reference/sage/graphs/graph.html#sage.graphs.graph.Graph.clique_maximum clique_maximum]
     434   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/MaximumClique.html MaximumClique][g] finds a largest clique in graph g.
     435
     436 * Maximum independent set
     437   * Sage --- [http://www.sagemath.org/doc/reference/sage/graphs/graph.html#sage.graphs.graph.Graph.independent_set independent_set]
     438   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/MaximumIndependentSet.html MaximumIndependentSet][g] finds a largest independent set of graph g.
     439
     440 * Minimum vertex cover
     441   * Sage ---
     442   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/MinimumVertexCover.html MinimumVertexCover][g] finds a minimum vertex cover of graph g. For bipartite graphs, the function uses the polynomial-time Hungarian algorithm. For everything else, the function uses brute force.
     443
     444 * Non-line graphs
     445   * Sage ---   
     446   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/NonLineGraphs.html NonLineGraphs] returns a graph whose connected components are the 9 graphs whose presence as a vertex-induced subgraph in a graph g makes g a nonline graph.
     447
     448 * Normalize vertices
     449   * Sage ---
     450   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/NormalizeVertices.html NormalizeVertices][v] gives a list of vertices with a similar embedding as v but with all coordinates of all points scaled to be between 0 and 1.
     451
     452 * nth pair
     453   * Sage ---
     454   * Mathemaica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/NthPair.html NthPair][n] returns the `n^(th)` unordered pair of distinct positive integers, when sequenced to minimize the size of the larger integer. Pairs that have the same larger integer are sequenced in increasing order of their smaller integer.
     455
     456 * Path
     457   * Sage ---
     458   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Path.html Path][n] constructs a tree consisting only of a path on n vertices.
     459
     460 * Permute subgraph
     461   * Sage ---
     462   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/PermuteSubgraph.html PermuteSubgraph][g, p] permutes the vertices of a subgraph of g induced by p according to p.
     463
     464 * Random graph
     465   * Sage ---
     466   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/RandomGraph.html RandomGraph][n, p] constructs a random labeled graph on n vertices with an edge probability of p.
     467
     468 * Random tree
     469   * Sage ---
     470   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/RandomTree.html RandomTree][n] constructs a random labeled tree on n vertices.
     471
     472 * Random vertices
     473   * Sage ---
     474   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/RandomVertices.html RandomVertices][g] assigns a random embedding to graph g.
     475
     476 * Regular graph
     477   * Sage ---
     478   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/RegularGraph.html RegularGraph][k, n] constructs a semirandom k-regular graph on n vertices, if such a graph exists.
     479
     480 * Regular q
     481   * Sage ---
     482   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/RegularQ.html RegularQ][g] yields True if g is a regular graph.
     483
     484 * Remove multiple edges
     485   * Sage ---
     486   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/RemoveMultipleEdges.html RemoveMultipleEdges][g] returns the graph obtained by deleting multiple edges from g.
     487
     488 * Remove self-loops
     489   * Sage ---
     490   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/RemoveSelfLoops.html RemoveSelfLoops][g] returns the graph obtained by deleting self-loops in g.
     491
     492 * Reverse edges
     493   * Sage ---
     494   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ReverseEdges.html ReverseEdges][g] flips the directions of all edges in a directed graph.
     495
     496 * Smallest cyclic group graph
     497   * Sage ---
     498   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/SmallestCyclicGroupGraph.html SmallestCyclicGroupGraph] returns a smallest nontrivial graph whose automorphism group is cyclic.
     499
     500 * Tree isomorphism q
     501   * Sage ---
     502   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/TreeIsomorphismQ.html TreeIsomorphismQ][t1, t2] yields True if the trees t1 and t2 are isomorphic. It yields False otherwise.
     503
     504 * Tree to certificate
     505   * Sage ---
     506   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/TreeToCertificate.html TreeToCertificate][t] returns a binary string that is a certificate for the tree t such that trees have the same certificate if and only if they are isomorphic.
     507
     508 * Tree q
     509   * Sage ---
     510   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/TreeQ.html TreeQ][g] yields True if graph g is a tree.
     511
     512 * Vertex cover
     513   * Sage ---
     514   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexCover.html VertexCover][g] returns a vertex cover of the graph g. An option Algorithm that can take on values Greedy, Approximate, or Optimum is allowed. The default setting is Algorithm -> Approximate. Different algorithms are used to compute a vertex cover depending on the setting of the option Algorithm.
     515
     516 * Vertex cover q
     517   * Sage ---   
     518   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexCoverQ.html VertexCoverQ][g, c] yields True if the vertices in list c define a vertex cover of graph g.
     519
     520
     521=== Input and output ===
     522
     523
     524 * Read graph
     525   * Sage ---
     526   * Mathematica ---  [http://reference.wolfram.com/mathematica/Combinatorica/ref/ReadGraph.html ReadGraph][f] reads a graph represented as edge lists from file f and returns a graph object.
     527   
     528 * Write graph
     529   * Sage ---
     530   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/WriteGraph.html WriteGraph][g, f] writes graph g to file f using an edge list representation.
     531
     532
     533=== Built-in graphs ===
     534
     535
     536 * Butterfly graph
     537   * Sage ---
     538   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ButterflyGraph.html ButterflyGraph][n] returns the n-dimensional butterfly graph, a directed graph whose vertices are pairs (w, i), where w is a binary string of length n and i is an integer in the range 0 through n and whose edges go from vertex (w, i) to (w', i+1), if w' is identical to w in all bits with the possible exception of the (i+1)th bit. Here bits are counted left to right. An option [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexLabel.html VertexLabel], with default setting False, is allowed. When this option is set to True, vertices are labeled with strings (w, i).
     539
     540 * Cage graph
     541   * Sage ---
     542   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/CageGraph.html CageGraph][k, r] gives a smallest k-regular graph of girth r for certain small values of k and r. [http://reference.wolfram.com/mathematica/Combinatorica/ref/CageGraph.html CageGraph][r] gives [http://reference.wolfram.com/mathematica/Combinatorica/ref/CageGraph.html CageGraph][3, r]. For k = 3, r can be 3, 4, 5, 6, 7, 8, or 10. For k = 4 or 5, r can be 3, 4, 5, or 6.
     543
     544 * Chvatal graph
     545   * Sage ---
     546   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ChvatalGraph.html ChvatalGraph] returns a smallest triangle-free, 4-regular, 4-chromatic graph.
     547
     548 * Circulant graph
     549   * Sage ---
     550   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/CirculantGraph.html 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 vertices, for each j in list l. [http://reference.wolfram.com/mathematica/Combinatorica/ref/CirculantGraph.html CirculantGraph][n, l], where l is an integer, returns the graph with n vertices in which each i is adjacent to (i+l) and (i-l).
     551
     552 * Complete graph
     553   * Sage ---
     554   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/CompleteGraph.html CompleteGraph]n] creates a complete graph on n vertices. An option Type that takes on the values Directed or Undirected is allowed. The default setting for this option is Type->Undirected.
     555
     556 * Complete k-partite graph
     557   * Sage ---
     558   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/CompleteKPartiteGraph.html CompleteKPartiteGraph][a, b, c, ...] creates a complete k-partite graph of the prescribed shape, provided the k arguments a,b,c,... are positive integers. An option Type that takes on the values Directed or Undirected is allowed. The default setting for this option is Type->Undirected.
     559
     560 * Coxeter graph
     561   * Sage ---
     562   * Matheamtica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/CoxeterGraph.html CoxeterGraph] gives a non-Hamiltonian graph with a high degree of symmetry such that there is a graph automorphism taking any path of length 3 to any other.
     563
     564 * Cube connected cycle
     565   * Sage ---
     566   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/CubeConnectedCycle.html CubeConnectedCycle][d] returns the graph obtained by replacing each vertex in a d-dimensional hypercube by a cycle of length d. Cube-connected cycles share many properties with hypercubes but have the additional desirable property that for d > 1 every vertex has degree 3.
     567
     568 * Cubical graph
     569   * Sage ---
     570   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/CubicalGraph.html CubicalGraph] returns the graph corresponding to the cube, a Platonic solid.
     571
     572 * Cycle
     573   * Sage ---
     574   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Cycle.html Cycle][n] constructs the cycle on n vertices, the 2-regular connected graph. An option Type that takes on values Directed or Undirected is allowed. The default setting is Type->Undirected.
     575
     576 * De Bruijn graph
     577   * Sage ---
     578   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/DeBruijnGraph.html DeBruijnGraph][m, n] constructs the n-dimensional De Bruijn graph with m symbols for integers m > 0 and n > 1. [http://reference.wolfram.com/mathematica/Combinatorica/ref/DeBruijnGraph.html DeBruijnGraph][alph, n] constructs the n-dimensional De Bruijn graph with symbols from alph. Here alph is nonempty and n > 1 is an integer. In the latter form, the function accepts an option [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexLabel.html VertexLabel], with default value False, which can be set to True, if users want to associate strings on alph to the vertices as labels.
     579
     580 * Dodecahedral graph
     581   * Sage ---
     582   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/DodecahedralGraph.html DodecahedralGraph] returns the graph corresponding to the dodecahedron, a Platonic solid.
     583
     584 * Empty graph
     585   * Sage ---
     586   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/EmptyGraph.html EmptyGraph][n] generates an empty graph on n vertices. An option Type that can take on values Directed or Undirected is provided. The default setting is Type->Undirected.
     587
     588 * Folkman graph
     589   * Sage ---
     590   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/FolkmanGraph.html FolkmanGraph] returns a smallest graph that is edge-transitive but not vertex-transitive.
     591
     592 * Franklin graph
     593   * Sage ---
     594   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/FranklinGraph.html FranklinGraph] returns a 12-vertex graph that represents a 6-chromatic map on the Klein bottle. It is the sole counterexample to Heawood's map coloring conjecture.
     595
     596 * Frucht graph
     597   * Sage ---
     598   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/FruchtGraph.html FruchtGraph] returns the smallest 3-regular graph whose automorphism group consists of only the identity.
     599
     600 * Generalized Petersen graph
     601   * Sage ---
     602   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/GeneralizedPetersenGraph.html GeneralizedPetersenGraph][n, k] returns the generalized Petersen graph, for integers n > 1 and k > 0, which is the graph with vertices {u1, u2, ..., un} and {v1, v2, ..., vn} and edges {ui, u(i+1)}, {vi, v(i+k)}, and {ui, vi}. The Petersen graph is identical to the generalized Petersen graph with n = 5 and k = 2.
     603
     604 * Gray graph
     605   * Sage ---
     606   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/GrayGraph.html GrayGraph] returns a 3-regular, 54-vertex graph that is edge-transitive but not vertex-transitive; the smallest known such example."
     607
     608 * Grid graph
     609   * Sage ---
     610   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/GridGraph.html GridGraph][n, m] constructs an n*m grid graph, the product of paths on n and m vertices.
     611
     612 * Groetzsch graph
     613   * Sage ---
     614   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/GroetzschGraph.html GroetzschGraph] returns the smallest triangle-free graph with chromatic number 4. This is identical to [http://reference.wolfram.com/mathematica/Combinatorica/ref/MycielskiGraph.html MycielskiGraph][4].
     615
     616 * Harary graph
     617   * Sage ---
     618   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Harary.html Harary][k, n] constructs the minimal k-connected graph on n vertices.
     619
     620 * Heawood graph
     621   * Sage ---
     622   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/HeawoodGraph.html HeawoodGraph] returns a smallest (6,3)-cage, a 3-regular graph with girth 6.
     623
     624 * Herschel graph
     625   * Sage ---
     626   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/HerschelGraph.html HerschelGraph] returns a graph object that represents a Herschel graph.
     627
     628 * Hypercube
     629   * Sage ---
     630   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Hypercube.html Hypercube][n] constructs an n-dimensional hypercube.
     631
     632 * Icosahedral graph
     633   * Sage ---
     634   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/IcosahedralGraph.html IcosahedralGraph] returns the graph corresponding to the icosahedron, a Platonic solid.
     635
     636 * Knight's tour graph
     637   * Sage ---
     638   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/KnightsTourGraph.html KnightsTourGraph][m, n] returns a graph with m*n vertices in which each vertex represents a square in an m x n chessboard and each edge corresponds to a legal move by a knight from one square to another.
     639
     640 * Levi graph
     641   * Sage ---
     642   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/LeviGraph.html LeviGraph] returns the unique (8, 3)-cage, a 3-regular graph whose girth is 8.
     643
     644 * McGee graph
     645   * Sage ---
     646   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/McGeeGraph.html McGeeGraph] returns the unique (7, 3)-cage, a 3-regular graph with girth 7.
     647
     648 * Meredith graph
     649   * Sage ---
     650   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/MeredithGraph.html MeredithGraph] returns a 4-regular, 4-connected graph that is not Hamiltonian, providing a counterexample to a conjecture by C. St. J. A. Nash-Williams.
     651
     652 * Mycielski graph
     653   * Sage ---
     654   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/MycielskiGraph.html MycielskiGraph][k] returns a triangle-free graph with chromatic number k, for any positive integer k.
     655
     656 * Octahedral graph
     657   * Sage ---
     658   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/OctahedralGraph.html OctahedralGraph] returns the graph corresponding to the octahedron, a Platonic solid.
     659
     660 * Odd graph
     661   * Sage ---   
     662   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/OddGraph.html OddGraph][n] returns the graph whose vertices are the size-(n-1) subsets of a size-(2n-1) set and whose edges connect pairs of vertices that correspond to disjoint subsets. [http://reference.wolfram.com/mathematica/Combinatorica/ref/OddGraph.html OddGraph][3] is the Petersen graph.
     663
     664 * Petersen graph
     665   * Sage ---
     666   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/PetersenGraph.html PetersenGraph] returns the Petersen graph, a graph whose vertices can be viewed as the size-2 subsets of a size-5 set with edges connecting disjoint subsets.
     667
     668 * Robertson graph
     669   * Sage ---
     670   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/RobertsonGraph.html RobertsonGraph] returns a 19-vertex graph that is the unique (4, 5)-cage graph.
     671
     672 * Shuffle exchange graph
     673   * Sage ---
     674   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ShuffleExchangeGraph.html ShuffleExchangeGraph][n] returns the n-dimensional shuffle-exchange graph whose vertices are length n binary strings with an edge from w to w' if (i) w' differs from w in its last bit or (ii) w' is obtained from w by a cyclic shift left or a cyclic shift right. An option [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexLabel.html VertexLabel] is provided, with default setting False, which can be set to True, if the user wants to associate the binary strings to the vertices as labels."
     675
     676 * Star
     677   * Sage ---
     678   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Star.html Star][n] constructs a star on n vertices, which is a tree with one vertex of degree n-1.
     679
     680 * Tetrahedral graph
     681   * Sage ---
     682   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/TetrahedralGraph.html TetrahedralGraph] returns the graph corresponding to the tetrahedron, a Platonic solid.
     683
     684 * Thomassen graph
     685   * Sage ---
     686   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ThomassenGraph.html ThomassenGraph] returns a hypotraceable graph, a graph G that has no Hamiltonian path but whose subgraph G-v for every vertex v has a Hamiltonian path.
     687
     688 * Turan
     689   * Sage ---   
     690   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Turan.html Turan][n, p] constructs the Turan graph, the extremal graph on n vertices that does not contain [http://reference.wolfram.com/mathematica/Combinatorica/ref/CompleteGraph.html CompleteGraph][p].
     691
     692 * Tutte graph
     693   * Sage ---
     694   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/TutteGraph.html TutteGraph] returns the Tutte graph, the first known example of a 3-connected, 3-regular, planar graph that is non-Hamiltonian.
     695
     696 * Uniquely 3-colorable graph
     697   * Sage ---
     698   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Uniquely3ColorableGraph.html Uniquely3ColorableGraph] returns a 12-vertex, triangle-free graph with chromatic number 3 that is uniquely 3-colorable.
     699
     700 * Unitransitive graph
     701   * Sage ---
     702   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/UnitransitiveGraph.html UnitransitiveGraph] returns a 20-vertex, 3-unitransitive graph discovered by Coxeter, that is not isomorphic to a 4-cage or a 5-cage.
     703
     704 * Walther graph
     705   * Sage ---
     706   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/WaltherGraph.html WaltherGraph] returns the Walther graph.
     707
     708 * Wheel
     709   * Sage ---
     710   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Wheel.html Wheel][n] constructs a wheel on n vertices, which is the join of CompleteGraph[1] and Cycle[n-1].
     711
     712
     713== Graph algorithms ==
     714
     715
     716=== Shortest paths ===
     717
     718 * All pairs shortest path
     719   * Sage --- [http://www.sagemath.org/doc/reference/sage/graphs/base/c_graph.html#sage.graphs.base.c_graph.CGraphBackend.shortest_path_all_vertices shortest_path_all_vertices]
     720   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/AllPairsShortestPath.html AllPairsShortestPath][g] gives a matrix, where the `(i,j)^(th)` entry is the length of a shortest path in g  between vertices i  and j.
     721
     722 * Bellman-Ford algorithm
     723    * Sage --- #8714
     724    * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/BellmanFord.html BellmanFord][g, v] gives a shortest-path spanning tree and associated distances from vertex v of graph g. The shortest-path spanning tree is given by a list in which element i is the predecessor of vertex i in the shortest-path spanning tree. [http://reference.wolfram.com/mathematica/Combinatorica/ref/BellmanFord.html BellmanFord] works correctly even when the edge weights are negative, provided there are no negative cycles.
     725
     726 * Diameter
     727   * Sage ---
     728   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Diameter.html Diameter][g] gives the diameter of graph g, the maximum length, among all pairs of vertices in g, of a shortest path between each pair.
     729
     730 * Dijkstra's algorithm
     731  * Sage --- [http://www.sagemath.org/doc/reference/sage/graphs/base/c_graph.html#sage.graphs.base.c_graph.CGraphBackend.bidirectional_dijkstra bidirectional_dijkstra]
     732  * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Dijkstra.html Dijkstra][g, v] gives a shortest-path spanning tree and associated distances from vertex v of graph g. The shortest-path spanning tree is given by a list in which element i is the predecessor of vertex i in the shortest-path spanning tree. Dijkstra does not work correctly when the edge weights are negative; [http://reference.wolfram.com/mathematica/Combinatorica/ref/BellmanFord.html BellmanFord] should be used in this case.
     733
     734 * Eccentricity
     735   * Sage ---
     736   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Eccentricity.html Eccentricity][g] gives the eccentricity of each vertex v  of graph g, the maximum length among all shortest paths from v.
     737
     738 * Girth
     739   * Sage ---
     740   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Girth.html Girth][g] gives the length of a shortest cycle in a simple graph g.
     741
     742 * Graph center
     743   * Sage ---
     744   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/GraphCenter.html GraphCenter][g] gives a list of the vertices of graph g with minimum eccentricity.
     745
     746 * Graph power
     747   * Sage ---
     748   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/GraphPower.html GraphPower][g, k] gives the kth power of graph g. This is the graph whose vertex set is identical to the vertex set of g and that contains an edge between vertices i and j for each path in g between vertices i and j of length at most k.
     749
     750 * Parents to paths
     751   * Sage ---
     752   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ParentsToPaths.html ParentsToPaths][l, i, j] takes a list of parents l and returns the path from i to j encoded in the parent list. [http://reference.wolfram.com/mathematica/Combinatorica/ref/ParentsToPaths.html ParentsToPaths][l, i] returns the paths from i to all vertices.
     753
     754 * Radius
     755   * Sage ---
     756   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Radius.html Radius][g] gives the radius of graph g, the minimum eccentricity of any vertex of g.
     757
     758 * Shortest path
     759   * Sage --- [http://www.sagemath.org/doc/reference/sage/graphs/base/c_graph.html#sage.graphs.base.c_graph.CGraphBackend.shortest_path shortest_path]
     760   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ShortestPath.html ShortestPath][g, start, end] finds a shortest path between vertices start and end in graph g.
     761
     762
     763=== Minimum spanning trees ===
     764
     765
     766 * Cofactor
     767   * Sage ---
     768   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Cofactor.html Cofactor][m, {i, j}] calculates the `(i,j)^(th)` cofactor of matrix m.
     769
     770 * Find set
     771   * Sage ---
     772   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/FindSet.html FindSet][n, s] gives the root of the set containing n in union-find data structure s.
     773
     774 * Initialize union find
     775   * Sage ---
     776   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/InitializeUnionFind.html InitializeUnionFind][n] initializes a union-find data structure for n elements.
     777   
     778 * Maximum spanning tree
     779   * Sage ---
     780   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/MaximumSpanningTree.html MaximumSpanningTree][g] uses Kruskal's algorithm to find a maximum spanning tree of graph g.
     781
     782 * Minimum spanning tree
     783   * Sage --- [http://www.sagemath.org/doc/reference/sage/graphs/graph.html#sage.graphs.graph.Graph.min_spanning_tree min_spanning_tree]
     784   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/MinimumSpanningTree.html MinimumSpanningTree][g] uses Kruskal's algorithm to find a minimum spanning tree of graph g.
     785
     786 * Number of spanning trees
     787   * Sage ---
     788   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/NumberOfSpanningTrees.html NumberOfSpanningTrees][g] gives the number of labeled spanning trees of graph g.
     789
     790 * Shortest path spanning tree
     791   * Sage ---
     792   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ShortestPathSpanningTree.html ShortestPathSpanningTree][g, v] constructs a shortest-path spanning tree rooted at v, so that a shortest path in graph g from v to any other vertex is a path in the tree. An option Algorithm that takes on the values Automatic, Dijkstra, or [http://reference.wolfram.com/mathematica/Combinatorica/ref/BellmanFord.html BellmanFord] is provided. This allows a choice between Dijkstra's algorithm and the Bellman-Ford algorithm. The default is Algorithm -> Automatic. In this case, depending on whether edges have negative weights and depending on the density of the graph, the algorithm chooses between Bellman-Ford and Dijkstra.
     793
     794 * Union set
     795   * Sage ---
     796   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/UnionSet.html UnionSet][a, b, s] merges the sets containing a and b in union-find data structure s.
     797
     798
     799=== Network flow ===
     800
     801
     802 * Networkflow
     803   * Sage --- [http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.flow flow]
     804   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/NetworkFlow.html NetworkFlow][g, source, sink] returns the value of a maximum flow through graph g from source to sink. [http://reference.wolfram.com/mathematica/Combinatorica/ref/NetworkFlow.html NetworkFlow][g, source, sink, Edge] returns the edges in g that have positive flow along with their flows in a maximum flow from source to sink. [http://reference.wolfram.com/mathematica/Combinatorica/ref/NetworkFlow.html NetworkFlow][g, source, sink, Cut] returns a minimum cut between source and sink. [http://reference.wolfram.com/mathematica/Combinatorica/ref/NetworkFlow.html NetworkFlow][g, source, sink, All] returns the adjacency list of g along with flows on each edge in a maximum flow from source to sink. g can be a directed or an undirected graph.
     805
     806 * Residual flow graph
     807   * Sage ---
     808   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ResidualFlowGraph.html ResidualFlowGraph][g, flow] returns the directed residual flow graph for graph g with respect to flow.
     809
     810
     811=== Matching ===
     812
     813
     814 * Alternating paths
     815   * Sage ---
     816   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/AlternatingPaths.html AlternatingPaths][g, start, ME] returns the alternating paths in graph g with respect to the matching ME, starting at the vertices in the list start. The paths are returned in the form of a forest containing trees rooted at vertices in start.
     817
     818 * Bipartite matching
     819   * Sage ---
     820   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/BipartiteMatching.html BipartiteMatching][g] gives the list of edges associated with a maximum matching in bipartite graph g. If the graph is edge weighted, then the function returns a matching with maximum total weight.
     821
     822 * Bipartite matching and cover
     823   * Sage ---
     824   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/BipartiteMatchingAndCover.html BipartiteMatchingAndCover][g] takes a bipartite graph g and returns a matching with maximum weight along with the dual vertex cover. If the graph is not weighted, it is assumed that all edge weights are 1.
     825
     826 * Maximal matching
     827   * Sage --- [http://www.sagemath.org/doc/reference/sage/graphs/generic_graph.html#sage.graphs.generic_graph.GenericGraph.matching matching]
     828   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/MaximalMatching.html MaximalMatching][g] gives the list of edges associated with a maximal matching of graph g.
     829
     830 * No perfect matching graph
     831   * Sage ---   
     832   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/NoPerfectMatchingGraph.html NoPerfectMatchingGraph] returns a connected graph with 16 vertices that contains no perfect matching.
     833
     834 * Stable marriange
     835   * Sage ---
     836   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/StableMarriage.html StableMarriage][mpref, fpref] finds the male optimal stable marriage defined by lists of permutations describing male and female preferences.
     837
     838
     839=== Graph traversals ===
     840
     841
     842 * Breadth-first search
     843   * Sage --- [http://www.sagemath.org/doc/reference/sage/graphs/base/c_graph.html#sage.graphs.base.c_graph.CGraphBackend.breadth_first_search breadth_first_search]
     844   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/BreadthFirstTraversal.html BreadthFirstTraversal][g, v] performs a breadth-first traversal of graph g starting from vertex v, and gives the breadth-first numbers of the vertices.
     845
     846 * Depth-first search
     847   * Sage --- [http://www.sagemath.org/doc/reference/sage/graphs/base/c_graph.html#sage.graphs.base.c_graph.CGraphBackend.depth_first_search depth_first_search]
     848   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/DepthFirstTraversal.html DepthFirstTraversal][g, v] performs a depth-first traversal of graph g starting from vertex v, and gives a list of vertices in the order in which they were encountered.
     849
     850
     851=== Partial orders ===
     852
     853
     854 * Antisymmetric q
     855   * Sage ---
     856   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/AntiSymmetricQ.html AntiSymmetricQ][g] yields True if the adjacency matrix of g represents an anti-symmetric binary relation.
     857
     858 * Boolean algebra
     859   * Sage ---
     860   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/BooleanAlgebra.html BooleanAlgebra][n] gives a Hasse diagram for the Boolean algebra on n elements. The function takes two options: Type and [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexLabel.html VertexLabel], with default values Undirected and False, respectively. When Type is set to Directed, the function produces the underlying directed acyclic graph. When [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexLabel.html VertexLabel] is set to True, labels are produced for the vertices.
     861
     862 * Dominating integer partition q
     863   * Sage ---
     864   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/DominatingIntegerPartitionQ.html DominatingIntegerPartitionQ][a, b] yields True if integer partition a dominates integer partition b, that is, the sum of a size-t prefix of a is no smaller than the sum of a size-t prefix of b for every t.
     865
     866 * Domination lattice
     867   * Sage ---
     868   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/DominationLattice.html DominationLattice][n] returns a Hasse diagram of the partially ordered set on integer partitions of n in which p < q if q dominates p. The function takes two options: Type and [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexLabel.html VertexLabel], with default values Undirected and False, respectively. When Type is set to Directed, the function produces the underlying directed acyclic graph. When [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexLabel.html VertexLabel] is set to True, labels are produced for the vertices.
     869
     870 * Equivalence classes
     871   * Sage ---
     872   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/EquivalenceClasses.html EquivalenceClasses][r] identifies the equivalence classes among the elements of matrix r.
     873
     874 * Equivalence relation q
     875   * Sage ---
     876   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/EquivalenceRelationQ.html EquivalenceRelationQ][r] yields True if the matrix r defines an equivalence relation. [http://reference.wolfram.com/mathematica/Combinatorica/ref/EquivalenceRelationQ.html EquivalenceRelationQ][g] tests whether the adjacency matrix of graph g defines an equivalence relation.
     877
     878 * Hasse diagram
     879   * Sage ---
     880   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/HasseDiagram.html HasseDiagram][g] constructs a Hasse diagram of the relation defined by directed acyclic graph g.
     881
     882 * Inversion poset
     883   * Sage ---
     884   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/InversionPoset.html InversionPoset][n] returns a Hasse diagram of the partially ordered set on size-n permutations in which p < q if q can be obtained from p by an adjacent transposition that places the larger element before the smaller. The function takes two options: Type and [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexLabel.html VertexLabel], with default values Undirected and False, respectively. When Type is set to Directed, the function produces the underlying directed acyclic graph. When [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexLabel.html VertexLabel] is set to True, labels are produced for the vertices.
     885
     886 * Isomorphic q
     887   * Sage ---
     888   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/IsomorphicQ.html IsomorphicQ][g, h] yields True if graphs g and h are isomorphic.
     889
     890 * Maximum antichain
     891   * Sage ---
     892   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/MaximumAntichain.html MaximumAntichain][g] gives a largest set of unrelated vertices in partial order g.
     893
     894 * Minimum chain partition
     895   * Sage ---
     896   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/MinimumChainPartition.html MinimumChainPartition][g] partitions partial order g into a minimum number of chains.
     897
     898 * Partial order q
     899   * Sage ---
     900   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/PartialOrderQ.html PartialOrderQ][g] yields True if the binary relation defined by edges of the graph g is a partial order, meaning it is transitive, reflexive, and antisymmetric.
     901
     902 * Partition lattice
     903   * Sage ---
     904   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/PartitionLattice.html PartitionLattice][n] returns a Hasse diagram of the partially ordered set on set partitions of 1 through n in which p < q if q is finer than p, that is, each block in q is contained in some block in p. The function takes two options: Type and [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexLabel.html VertexLabel], with default values Undirected and False, respectively. When Type is set to Directed, the function produces the underlying directed acyclic graph. When [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexLabel.html VertexLabel] is set to True, labels are produced for the vertices.
     905
     906 * Symmetric q
     907   * Sage ---
     908   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/SymmetricQ.html SymmetricQ][r] tests if a given square matrix r represents a symmetric relation. [http://reference.wolfram.com/mathematica/Combinatorica/ref/SymmetricQ.html SymmetricQ][g] tests if the edges of a given graph represent a symmetric relation.
     909
     910 * Topological sort
     911   * Sage ---
     912   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/TopologicalSort.html TopologicalSort][g] gives a permutation of the vertices of the directed acyclic graph g such that an edge (i,j) implies that vertex i appears before vertex j.
     913
     914 * Transitive closure
     915   * Sage ---
     916   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/TransitiveClosure.html TransitiveClosure][g] finds the transitive closure of graph g, the supergraph of g that contains edge {x, y} if and only if there is a path from x to y.
     917
     918 * Transitive reduction
     919   * Sage ---
     920   * Mathematica [http://reference.wolfram.com/mathematica/Combinatorica/ref/TransitiveReduction.html TransitiveReduction][g] finds a smallest graph that has the same transitive closure as g.
     921
     922
     923=== Graph isomorphism ===
     924
     925
     926 * Degrees of 2-neighborhood
     927   * Sage ---
     928   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/DegreesOf2Neighborhood.html DegreesOf2Neighborhood][g, v] returns the sorted list of degrees of vertices of graph g within a distance of 2 from v.
     929
     930 * Distances
     931   * Sage ---
     932   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Distances.html Distances][g, v] returns the distances in nondecreasing order from vertex v to all vertices in g, treating g as an unweighted graph.
     933
     934 * Equivalences
     935   * Sage ---
     936   * Mathematica --- Equivalences[g, h] lists the vertex equivalence classes between graphs g and h defined by their vertex degrees. Equivalences[g] lists the vertex equivalences for graph g defined by the vertex degrees. Equivalences[g, h, f1, f2, ...] and Equivalences[g, f1, f2, ...] can also be used, where f1, f2, ... are functions that compute other vertex invariants. It is expected that for each function fi, the call fi[g, v] returns the corresponding invariant at vertex v in graph g. The functions f1, f2, ... are evaluated in order, and the evaluation stops either when all functions have been evaluated or when an empty equivalence class is found. Three vertex invariants, [http://reference.wolfram.com/mathematica/Combinatorica/ref/DegreesOf2Neighborhood.html DegreesOf2Neighborhood], [http://reference.wolfram.com/mathematica/Combinatorica/ref/NumberOf2Paths.html NumberOf2Paths], and Distances are Combinatorica functions and can be used to refine the equivalences.
     937
     938 * Identical q
     939   * Sage ---
     940   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/IdenticalQ.html IdenticalQ][g, h] yields True if graphs g and h have identical edge lists, even though the associated graphics information need not be the same.
     941
     942 * Isomorphism
     943   * Sage ---
     944   * Mathematica --- Isomorphism[g, h] gives an isomorphism between graphs g and h if one exists. Isomorphism[g, h, All] gives all isomorphisms between graphs g and h. Isomorphism[g] gives the automorphism group of g. This function takes an option Invariants -> {f1, f2, ...}, where f1, f2, ... are functions that are used to compute vertex invariants. These functions are used in the order in which they are specified. The default value of Invariants is {[http://reference.wolfram.com/mathematica/Combinatorica/ref/DegreesOf2Neighborhood.html DegreesOf2Neighborhood], [http://reference.wolfram.com/mathematica/Combinatorica/ref/NumberOf2Paths.html NumberOf2Paths], Distances}.
     945
     946 * Isomorphism q
     947   * Sage ---
     948   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/IsomorphismQ.html IsomorphismQ][g, h, p] tests if permutation p defines an isomorphism between graphs g and h.
     949
     950 * Neighborhood
     951   * Sage ---
     952   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Neighborhood.html Neighborhood][g, v, k] returns the subset of vertices in g that are at a distance of k or less from vertex v.
     953
     954 * Number of 2-paths
     955   * Sage ---
     956   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/NumberOf2Paths.html NumberOf2Paths][g, v] returns a sorted list that contains the number of paths of length 2 to different vertices of g from v.
     957
     958 * Number of k-paths
     959   * Sage ---
     960   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/NumberOfKPaths.html NumberOfKPaths][g, v, k] returns a sorted list that contains the number of paths of length k to different vertices of g from v. [http://reference.wolfram.com/mathematica/Combinatorica/ref/NumberOfKPaths.html NumberOfKPaths][al, v, k] behaves identically, except that it takes an adjacency list al as input.
     961
     962 * Self-complementary q
     963   * Sage ---
     964   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/SelfComplementaryQ.html SelfComplementaryQ][g] yields True if graph g is self-complementary, meaning it is isomorphic to its complement.
     965
     966
     967== Graph properties ==
     968
     969
     970=== Degrees ===
     971
     972
     973 * Degrees
     974   * Sage ---
     975   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Degrees.html Degrees][g] returns the degrees of vertex 1,2,3,... in that order.
     976
     977 * Degree sequence
     978   * Sage ---
     979   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/DegreeSequence.html DegreeSequence][g] gives the sorted degree sequence of graph g.
     980
     981 * Graphic q
     982   * Sage ---
     983   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/GraphicQ.html GraphicQ][s] yields True if the list of integers s is a graphic sequence, and thus represents a degree sequence of some graph.
     984
     985 * Indegree
     986   * Sage ---
     987   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/InDegree.html InDegree][g, n] returns the in-degree of vertex n in directed graph g.
     988
     989 * Outdegree
     990   * Sage ---
     991   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/OutDegree.html OutDegree][g, n] returns the out-degree of vertex n in directed graph g.
     992
     993 * Realize degree sequence
     994   * Sage ---
     995   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/RealizeDegreeSequence.html RealizeDegreeSequence][s] constructs a semirandom graph with degree sequence s.
     996
     997 * Spectrum
     998   * Sage ---
     999   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Spectrum.html Spectrum][g] gives the eigenvalues of graph g.
     1000
     1001
     1002=== Miscellaneous ===
     1003
     1004
     1005 * Graph polynomial
     1006   * Sage ---
     1007   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/GraphPolynomial.html GraphPolynomial][n, x] returns a polynomial in x in which the coefficient of x^m is the number of nonisomorphic graphs with n vertices and m edges. [http://reference.wolfram.com/mathematica/Combinatorica/ref/GraphPolynomial.html GraphPolynomial][n, x, Directed] returns a polynomial in x in which the coefficient of x^m is the number of nonisomorphic directed graphs with n vertices and m edges.
     1008
     1009 * List graphs
     1010   * Sage ---
     1011   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ListGraphs.html ListGraphs][n, m] returns all nonisomorphic undirected graphs with n vertices and m edges. [http://reference.wolfram.com/mathematica/Combinatorica/ref/ListGraphs.html ListGraphs][n, m, Directed] returns all nonisomorphic directed graphs with n vertices and m edges. [http://reference.wolfram.com/mathematica/Combinatorica/ref/ListGraphs.html ListGraphs][n] returns all nonisomorphic undirected graphs with n vertices. [http://reference.wolfram.com/mathematica/Combinatorica/ref/ListGraphs.html ListGraphs][n, Directed] returns all nonisomorphic directed graphs with n vertices.
     1012
     1013 * List necklaces
     1014   * Sage ---
     1015   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ListNecklaces.html ListNecklaces][n, c, Cyclic] returns all distinct necklaces whose beads are colored by colors from c. Here c is a list of n, not necessarily distinct colors, and two colored necklaces are considered equivalent if one can be obtained by rotating the other.
     1016
     1017 * Necklace polynomial
     1018   * Sage ---
     1019   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/NecklacePolynomial.html NecklacePolynomial][n, c, Cyclic] returns a polynomial in the colors in c whose coefficients represent numbers of ways of coloring an n-bead necklace with colors chosen from c, assuming that two colorings are equivalent if one can be obtained from the other by a rotation.
     1020
     1021 * Number of directed graphs
     1022   * Sage ---
     1023   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/NumberOfDirectedGraphs.html NumberOfDirectedGraphs][n] returns the number of nonisomorphic directed graphs with n vertices. [http://reference.wolfram.com/mathematica/Combinatorica/ref/NumberOfDirectedGraphs.html NumberOfDirectedGraphs][n, m] returns the number of nonisomorphic directed graphs with n vertices and m edges.
     1024
     1025 * Number of graphs
     1026   * Sage ---
     1027   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/NumberOfGraphs.html NumberOfGraphs][n] returns the number of nonisomorphic undirected graphs with n vertices. [http://reference.wolfram.com/mathematica/Combinatorica/ref/NumberOfGraphs.html NumberOfGraphs][n, m] returns the number of nonisomorphic undirected graphs with n vertices and m edges.
     1028
     1029 * Number of necklaces
     1030   * Sage ---
     1031   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/NumberOfNecklaces.html NumberOfNecklaces] [n, nc, Cyclic] returns the number of distinct ways in which an n-bead necklace can be colored with nc colors, assuming that two colorings are equivalent if one can be obtained from the other by a rotation.
     1032
     1033
     1034=== Cycles and connectivity ===
     1035
     1036
     1037 * Acyclic q
     1038   * Sage ---
     1039   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/AcyclicQ.html AcyclicQ][g] yields True if graph g is acyclic.
     1040
     1041 * Articulation vertices
     1042   * Sage ---
     1043   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ArticulationVertices.html ArticulationVertices][g] gives a list of all articulation vertices in graph g. These are vertices whose removal will disconnect the graph.
     1044
     1045 * Biconnected components
     1046   * Sage ---
     1047   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/BiconnectedComponents.html BiconnectedComponents][g] gives a list of the biconnected components of graph g. If g is directed, the underlying undirected graph is used.
     1048
     1049 * Biconnected q
     1050   * Sage ---
     1051   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/BiconnectedQ.html BiconnectedQ][g] yields True if graph g is biconnected. If g is directed, the underlying undirected graph is used.
     1052
     1053 * Bridges
     1054   * Sage ---
     1055   * Mathematica --- Bridges[g] gives a list of the bridges of graph g, where each bridge is an edge whose removal disconnects the graph.
     1056
     1057 * Connected components
     1058   * Sage ---
     1059   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ConnectedComponents.html ConnectedComponents][g] gives the vertices of graph g partitioned into connected components.
     1060
     1061 * Connected q
     1062   * Sage ---
     1063   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ConnectedQ.html ConnectedQ][g] yields True if undirected graph g is connected. If g is directed, the function returns True if the underlying undirected graph is connected.
     1064
     1065 * De Bruijn sequence
     1066   * Sage ---
     1067   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/DeBruijnSequence.html DeBruijnSequence][a, n] returns a De Bruijn sequence on the alphabet a, a shortest sequence in which every string of length n on alphabet a occurs as a contiguous subsequence.
     1068
     1069 * Edge connectivity
     1070   * Sage ---
     1071   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/EdgeConnectivity.html EdgeConnectivity][g] gives the minimum number of edges whose deletion from graph g disconnects it. [http://reference.wolfram.com/mathematica/Combinatorica/ref/EdgeConnectivity.html EdgeConnectivity][g, Cut] gives a set of edges of minimum size whose deletion disconnects the graph.
     1072
     1073 * Eulerian cycle
     1074   * Sage ---
     1075   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/EulerianCycle.html EulerianCycle][g] finds an Eulerian cycle of g if one exists.
     1076
     1077 * Eulerian q
     1078   * Sage ---
     1079   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/EulerianQ.html EulerianQ][g] yields True if graph g is Eulerian, meaning there exists a tour that includes each edge exactly once.
     1080
     1081 * Extract cycles
     1082   * Sage ---
     1083   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ExtractCycles.html ExtractCycles][g] gives a maximal list of edge-disjoint cycles in graph g.
     1084
     1085 * Find cycle
     1086   * Sage ---
     1087   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/FindCycle.html FindCycle][g] finds a list of vertices that define a cycle in graph g.
     1088
     1089 * Hamiltonian cycle
     1090   * Sage ---
     1091   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/HamiltonianCycle.html HamiltonianCycle][g] finds a Hamiltonian cycle in graph g if one exists. [http://reference.wolfram.com/mathematica/Combinatorica/ref/HamiltonianCycle.html HamiltonianCycle][g, All] gives all Hamiltonian cycles of graph g.
     1092
     1093 * Hamiltonian q
     1094   * Sage ---
     1095   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/HamiltonianQ.html HamiltonianQ][g] yields True if there exists a Hamiltonian cycle in graph g, or in other words, if there exists a cycle that visits each vertex exactly once.
     1096
     1097 * Orient graph
     1098   * Sage ---
     1099   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/OrientGraph.html OrientGraph][g] assigns a direction to each edge of a bridgeless, undirected graph g, so that the graph is strongly connected.
     1100
     1101 * Strongly connected components
     1102   * Sage ---
     1103   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/StronglyConnectedComponents.html StronglyConnectedComponents][g] gives the strongly connected components of directed graph g as lists of vertices.
     1104
     1105 * Traveling salesman
     1106   * Sage ---
     1107   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/TravelingSalesman.html TravelingSalesman][g] finds an optimal traveling salesman tour in a Hamiltonian graph g.
     1108
     1109 * Traveling salesman bounds
     1110   * Sage ---
     1111   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/TravelingSalesmanBounds.html TravelingSalesmanBounds][g] gives upper and lower bounds on a minimum cost traveling salesman tour of graph g.
     1112
     1113 * Vertex connectivity
     1114   * Sage ---
     1115   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexConnectivity.html VertexConnectivity][g] gives the minimum number of vertices whose deletion from graph g disconnects it. [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexConnectivity.html VertexConnectivity][g, Cut] gives a set of vertices of minimum size, whose removal disconnects the graph.
     1116
     1117 * Vertex connectivity graph
     1118   * Sage ---
     1119   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexConnectivityGraph.html VertexConnectivityGraph][g] returns a directed graph that contains an edge corresponding to each vertex in g and in which edge disjoint paths correspond to vertex disjoint paths in g.
     1120
     1121 * Weakly connected components
     1122   * Sage ---
     1123   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/WeaklyConnectedComponents.html WeaklyConnectedComponents][g] gives the weakly connected components of directed graph g as lists of vertices.
     1124
     1125
     1126=== Graph coloring ===
     1127
     1128
     1129 * Backtrack
     1130   * Sage ---
     1131   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/Backtrack.html 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.
     1132
     1133 * Bipartite q
     1134   * Sage ---
     1135   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/BipartiteQ.html BipartiteQ][g] yields True if graph g is bipartite.
     1136
     1137 * Brelaz coloring
     1138   * Sage ---
     1139   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/BrelazColoring.html BrelazColoring][g] returns a vertex coloring in which vertices are greedily colored with the smallest available color in decreasing order of vertex degree.
     1140
     1141 * Chromatic number
     1142   * Sage --- [http://www.sagemath.org/doc/reference/sage/graphs/graph_coloring.html#sage.graphs.graph_coloring.chromatic_number chromatic_number]
     1143   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ChromaticNumber.html ChromaticNumber][g] gives the chromatic number of the graph, which is the fewest number of colors necessary to color the graph.
     1144
     1145 * Chromatic polynomial
     1146   * Sage ---
     1147   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/ChromaticPolynomial.html ChromaticPolynomial][g, z] gives the chromatic polynomial P(z) of graph g, which counts the number of ways to color g with, at most, z colors.
     1148
     1149 * Edge chromatic number
     1150   * Sage --- [http://www.sagemath.org/doc/reference/sage/graphs/graph_coloring.html#sage.graphs.graph_coloring.edge_coloring edge_coloring]
     1151   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/EdgeChromaticNumber.html EdgeChromaticNumber][g] gives 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.
     1152
     1153 * Edge coloring
     1154   * Sage --- [http://www.sagemath.org/doc/reference/sage/graphs/graph_coloring.html#sage.graphs.graph_coloring.edge_coloring edge_coloring]
     1155   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/EdgeColoring.html EdgeColoring][g] uses Brelaz's heuristic to find a good, but not necessarily minimal, edge coloring of graph g.
     1156
     1157 * Minimum vertex coloring
     1158   * Sage --- [http://www.sagemath.org/doc/reference/sage/graphs/graph_coloring.html#sage.graphs.graph_coloring.vertex_coloring vertex_coloring]
     1159   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/MinimumVertexColoring.html MinimumVertexColoring][g] returns a minimum vertex coloring of g. [http://reference.wolfram.com/mathematica/Combinatorica/ref/MinimumVertexColoring.html MinimumVertexColoring][g, k] returns a k-coloring of g, if one exists.
     1160
     1161 * Perfect q
     1162   * Sage ---
     1163   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/PerfectQ.html PerfectQ][g] yields True if g is a perfect graph, meaning that for every induced subgraph of g the size of a largest clique equals the chromatic number.
     1164
     1165 * Two coloring
     1166   * Sage ---
     1167   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/TwoColoring.html TwoColoring][g] finds a two-coloring of graph g if g is bipartite. It returns a list of the labels 1 and 2 corresponding to the vertices. This labeling is a valid coloring if and only the graph is bipartite.
     1168
     1169 * Vertex coloring
     1170   * Sage ---
     1171   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/VertexColoring.html VertexColoring][g] uses Brelaz's heuristic to find a good, but not necessarily minimal, vertex coloring of graph g. An option Algorithm that can take on the values Brelaz or Optimum is allowed. The setting Algorithm -> Brelaz is the default, while the setting Algorithm -> Optimum forces the algorithm to do an exhaustive search to find an optimum vertex coloring.
     1172
     1173
     1174=== Graph predicates ===
     1175
     1176
     1177 * Clique q
     1178   * Sage ---
     1179   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/CliqueQ.html CliqueQ][g, c] yields True if the list of vertices c defines a clique in graph g.
     1180
     1181 * Complete q
     1182   * Sage ---
     1183   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/CompleteQ.html CompleteQ][g] yields True if graph g is complete. This means that between any pair of vertices there is an undirected edge or two directed edges going in opposite directions.
     1184
     1185 * Empty q
     1186   * Sage ---
     1187   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/EmptyQ.html EmptyQ][g] yields True if graph g contains no edges.
     1188
     1189 * Multiple edges q
     1190   * Sage ---
     1191   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/MultipleEdgesQ.html MultipleEdgesQ][g] yields True if g has multiple edges between pairs of vertices. It yields False otherwise.
     1192
     1193 * Planar q
     1194   * Sage ---
     1195   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/PlanarQ.html PlanarQ][g] yields True if graph g is planar, meaning it can be drawn in the plane so no two edges cross.
     1196
     1197 * Pseudograph q
     1198   * Sage ---
     1199   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/PseudographQ.html PseudographQ][g] yields True if graph g is a pseudograph, meaning it contains self-loops.
     1200
     1201 * Self-loops q
     1202   * Sage ---
     1203   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/SelfLoopsQ.html SelfLoopsQ][g] yields True if graph g has self-loops.
     1204
     1205 * Simple q
     1206   * Sage ---
     1207   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/SimpleQ.html SimpleQ][g] yields True if g is a simple graph, meaning it has no multiple edges and contains no self-loops.
     1208
     1209 * Triangle inequality q
     1210   * Sage ---
     1211   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/TriangleInequalityQ.html TriangleInequalityQ][g] yields True if the weights assigned to the edges of graph g satisfy the triangle inequality.
     1212
     1213 * Undirected q
     1214   * Sage ---
     1215   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/UndirectedQ.html UndirectedQ][g] yields True if graph g is undirected.
     1216
     1217 * Unweighted q
     1218   * Sage ---
     1219   * Mathematica --- [http://reference.wolfram.com/mathematica/Combinatorica/ref/UnweightedQ.html UnweightedQ][g] yields True if all edge weights are 1 and False otherwise.
     1220
     1221
     1222
     1223== Others ==
     1224
     1225
     1226 * [http://reference.wolfram.com/mathematica/Combinatorica/ref/CostOfPath.html CostOfPath][g, p] sums up the weights of the edges in graph g defined by the path p.
     1227
     1228 * [http://reference.wolfram.com/mathematica/Combinatorica/ref/DilateVertices.html DilateVertices][v, d] multiplies each coordinate of each vertex position in list v by d, thus dilating the embedding. [http://reference.wolfram.com/mathematica/Combinatorica/ref/DilateVertices.html DilateVertices][g, d] dilates the embedding of graph g by the factor d.
     1229
     1230 * [http://reference.wolfram.com/mathematica/Combinatorica/ref/FiniteGraphs.html FiniteGraphs] produces a convenient list of all the interesting, finite, parameterless graphs built into Combinatorica.
     1231
     1232 * [http://reference.wolfram.com/mathematica/Combinatorica/ref/GetEdgeWeights.html GetEdgeWeights][g] returns the list of weights of the edges of g. [http://reference.wolfram.com/mathematica/Combinatorica/ref/GetEdgeWeights.html GetEdgeWeights][g, es] returns the list of weights in graph g of the edges in es.
     1233
     1234 * [http://reference.wolfram.com/mathematica/Combinatorica/ref/GetVertexLabels.html GetVertexLabels][g] returns the list of labels of vertices of g. [http://reference.wolfram.com/mathematica/Combinatorica/ref/GetVertexLabels.html GetVertexLabels][g, vs] returns the list of labels in graph g of the vertices specified in list vs.
     1235
     1236 * [http://reference.wolfram.com/mathematica/Combinatorica/ref/GetVertexWeights.html GetVertexWeights][g] returns the list of weights of vertices of g. [http://reference.wolfram.com/mathematica/Combinatorica/ref/GetVertexWeights.html GetVertexWeights][g, vs] returns the list of weights in graph g of the vertices in vs.
     1237
     1238 * [http://reference.wolfram.com/mathematica/Combinatorica/ref/HamiltonianPath.html HamiltonianPath][g] finds a Hamiltonian path in graph g if one exists. [http://reference.wolfram.com/mathematica/Combinatorica/ref/HamiltonianPath.html HamiltonianPath][g, All] gives all Hamiltonian paths of graph g.
     1239
     1240 * [http://reference.wolfram.com/mathematica/Combinatorica/ref/MinimumChangePermutations.html MinimumChangePermutations][l] constructs all permutations of list l such that adjacent permutations differ by only one transposition.
     1241
     1242 * [http://reference.wolfram.com/mathematica/Combinatorica/ref/NetworkFlowEdges.html NetworkFlowEdges][g, source, sink] returns the edges of the graph with positive flow, showing the distribution of a maximum flow from source to sink in graph g. This is obsolete, and [http://reference.wolfram.com/mathematica/Combinatorica/ref/NetworkFlow.html NetworkFlow][g, source, sink, Edge] should be used instead.
     1243
     1244 * [http://reference.wolfram.com/mathematica/Combinatorica/ref/PartialOrderQ.html PartialOrderQ][g] yields True if the binary relation defined by edges of the graph g is a partial order, meaning it is transitive, reflexive, and antisymmetric. [http://reference.wolfram.com/mathematica/Combinatorica/ref/PartialOrderQ.html PartialOrderQ][r] yields True if the binary relation defined by the square matrix r is a partial order.
     1245
     1246 * [http://reference.wolfram.com/mathematica/Combinatorica/ref/PermutationGraph.html PermutationGraph][p] gives the permutation graph for the permutation p.
     1247
     1248 * [http://reference.wolfram.com/mathematica/Combinatorica/ref/ReflexiveQ.html ReflexiveQ][g] yields True if the adjacency matrix of g represents a reflexive binary relation.
     1249
     1250 * [http://reference.wolfram.com/mathematica/Combinatorica/ref/SetEdgeWeights.html SetEdgeWeights][g] assigns random real weights in the range [0, 1] to edges in g. [http://reference.wolfram.com/mathematica/Combinatorica/ref/SetEdgeWeights.html SetEdgeWeights] accepts options [http://reference.wolfram.com/mathematica/Combinatorica/ref/WeightingFunction.html WeightingFunction] and [http://reference.wolfram.com/mathematica/Combinatorica/ref/WeightRange.html WeightRange]. [http://reference.wolfram.com/mathematica/Combinatorica/ref/WeightingFunction.html WeightingFunction] can take values Random, [http://reference.wolfram.com/mathematica/Combinatorica/ref/RandomInteger.html RandomInteger], Euclidean, or LNorm[n] for nonnegative n, or any pure function that takes two arguments, each argument having the form {Integer, {Number, Number}}. [http://reference.wolfram.com/mathematica/Combinatorica/ref/WeightRange.html WeightRange] can be an integer range or a real range. The default value for [http://reference.wolfram.com/mathematica/Combinatorica/ref/WeightingFunction.html WeightingFunction] is Random and the default value for [http://reference.wolfram.com/mathematica/Combinatorica/ref/WeightRange.html WeightRange] is [0, 1]. [http://reference.wolfram.com/mathematica/Combinatorica/ref/SetEdgeWeights.html SetEdgeWeights][g, e] assigns edge weights to the edges in the edge list e. [http://reference.wolfram.com/mathematica/Combinatorica/ref/SetEdgeWeights.html SetEdgeWeights][g, w] assigns the weights in the weight list w to the edges of g. [http://reference.wolfram.com/mathematica/Combinatorica/ref/SetEdgeWeights.html SetEdgeWeights][g, e, w] assigns the weights in the weight list w to the edges in edge list e.
     1251
     1252 * Vertices[g] gives the embedding of graph g, that is, the coordinates of each vertex in the plane. Vertices[g, All] gives the embedding of the graph along with graphics options associated with each vertex.