This module implements functions and operations involving undirected graphs.
Graph basic operations:
write_to_eps() | Writes a plot of the graph to filename in eps format. |
to_undirected() | Since the graph is already undirected, simply returns a copy of itself. |
to_directed() | Returns a directed version of the graph. |
sparse6_string() | Returns the sparse6 representation of the graph as an ASCII string. |
graph6_string() | Returns the graph6 representation of the graph as an ASCII string. |
bipartite_sets() | Returns ![]() |
bipartite_color() | Returns a dictionary with vertices as the keys and the color class as the values. |
is_directed() | Since graph is undirected, returns False. |
Distances:
centrality_closeness() | Returns the closeness centrality (1/average distance to all vertices) |
centrality_degree() | Returns the degree centrality |
centrality_betweenness() | Returns the betweenness centrality |
Graph properties:
is_prime() | Tests whether the current graph is prime. |
is_split() | Returns True if the graph is a Split graph, False otherwise. |
is_triangle_free() | Returns whether self is triangle-free. |
is_bipartite() | Returns True if graph G is bipartite, False if not. |
is_line_graph() | Tests wether the graph is a line graph. |
is_odd_hole_free() | Tests whether self contains an induced odd hole. |
is_even_hole_free() | Tests whether self contains an induced even hole. |
is_cartesian_product() | Tests whether self is a cartesian product of graphs. |
is_long_hole_free() | Tests whether self contains an induced cycle of length at least 5. |
is_long_antihole_free() | Tests whether self contains an induced anticycle of length at least 5. |
is_weakly_chordal() | Tests whether self is weakly chordal. |
is_strongly_regular() | Tests whether self is strongly regular. |
odd_girth() | Returns the odd girth of self. |
is_edge_transitive() | Returns true if self is edge-transitive. |
is_arc_transitive() | Returns true if self is arc-transitive. |
is_half_transitive() | Returns true if self is a half-transitive graph. |
is_semi_symmetric() | Returns true if self is a semi-symmetric graph. |
Connectivity and orientations:
gomory_hu_tree() | Returns a Gomory-Hu tree of self. |
minimum_outdegree_orientation() | Returns an orientation of self with the smallest possible maximum outdegree |
bounded_outdegree_orientation() | Computes an orientation of self such that every vertex ![]() ![]() |
strong_orientation() | Returns a strongly connected orientation of the current graph. |
degree_constrained_subgraph() | Returns a degree-constrained subgraph. |
Clique-related methods:
clique_complex() | Returns the clique complex of self |
cliques_containing_vertex() | Returns the cliques containing each vertex |
cliques_vertex_clique_number() | Returns a dictionary of sizes of the largest maximal cliques containing each vertex |
cliques_get_clique_bipartite() | Returns a bipartite graph constructed such that maximal cliques are the right vertices and the left vertices are retained from the given graph |
cliques_get_max_clique_graph() | Returns a graph constructed with maximal cliques as vertices, and edges between maximal cliques sharing vertices. |
cliques_number_of() | Returns a dictionary of the number of maximal cliques containing each vertex, keyed by vertex. |
clique_number() | Returns the order of the largest clique of the graph. |
clique_maximum() | Returns the vertex set of a maximal order complete subgraph. |
cliques_maximum() | Returns the list of all maximum cliques |
cliques_maximal() | Returns the list of all maximal cliques |
Algorithmically hard stuff:
vertex_cover() | Returns a minimum vertex cover of self |
independent_set() | Returns a maximum independent set. |
topological_minor() | Returns a topological ![]() |
convexity_properties() | Returns a ConvexityProperties objet corresponding to self. |
matching_polynomial() | Computes the matching polynomial of the graph ![]() |
rank_decomposition() | Returns an rank-decomposition of self achieving optiml rank-width. |
minor() | Returns the vertices of a minor isomorphic to ![]() |
independent_set_of_representatives() | Returns an independent set of representatives. |
coloring() | Returns the first (optimal) proper vertex-coloring found. |
has_homomorphism_to() | Checks whether there is a morphism between two graphs. |
chromatic_number() | Returns the minimal number of colors needed to color the vertices of the graph. |
chromatic_polynomial() | Returns the chromatic polynomial of the graph. |
is_perfect() | Tests whether the graph is perfect. |
Leftovers:
cores() | Returns the core number for each vertex in an ordered list. |
matching() | Returns a maximum weighted matching of the graph |
fractional_chromatic_index() | Computes the fractional chromatic index of self |
modular_decomposition() | Returns the modular decomposition of the current graph. |
maximum_average_degree() | Returns the Maximum Average Degree (MAD) of the current graph. |
two_factor_petersen() | Returns a decomposition of the graph into 2-factors. |
AUTHORS:
Robert L. Miller (2006-10-22): initial version
William Stein (2006-12-05): Editing
Robert L. Miller (2007-01-13): refactoring, adjusting for NetworkX-0.33, fixed plotting bugs (2007-01-23): basic tutorial, edge labels, loops, multiple edges and arcs (2007-02-07): graph6 and sparse6 formats, matrix input
Emily Kirkmann (2007-02-11): added graph_border option to plot and show
Robert L. Miller (2007-02-12): vertex color-maps, graph boundaries, graph6 helper functions in Cython
Robert L. Miller Sage Days 3 (2007-02-17-21): 3d plotting in Tachyon
Robert L. Miller (2007-02-25): display a partition
Robert L. Miller (2007-02-28): associate arbitrary objects to vertices, edge and arc label display (in 2d), edge coloring
Robert L. Miller (2007-03-21): Automorphism group, isomorphism check, canonical label
Robert L. Miller (2007-06-07-09): NetworkX function wrapping
Michael W. Hansen (2007-06-09): Topological sort generation
Emily Kirkman, Robert L. Miller Sage Days 4: Finished wrapping NetworkX
Emily Kirkman (2007-07-21): Genus (including circular planar, all embeddings and all planar embeddings), all paths, interior paths
Bobby Moretti (2007-08-12): fixed up plotting of graphs with edge colors differentiated by label
Jason Grout (2007-09-25): Added functions, bug fixes, and general enhancements
Robert L. Miller (Sage Days 7): Edge labeled graph isomorphism
Tom Boothby (Sage Days 7): Miscellaneous awesomeness
Tom Boothby (2008-01-09): Added graphviz output
David Joyner (2009-2): Fixed docstring bug related to GAP.
Stephen Hartke (2009-07-26): Fixed bug in blocks_and_cut_vertices() that caused an incorrect result when the vertex 0 was a cut vertex.
Stephen Hartke (2009-08-22): Fixed bug in blocks_and_cut_vertices() where the list of cut_vertices is not treated as a set.
Anders Jonsson (2009-10-10): Counting of spanning trees and out-trees added.
and everything that uses Linear Programming and class numerical.MIP
Nicolas M. Thiery (2010-02): graph layout code refactoring, dot2tex/graphviz interface
David Coudert (2012-04) : Reduction rules in vertex_cover.
long-hole-free / long-antihole-free graphs
Sage Graphs can be created from a wide range of inputs. A few examples are covered here.
NetworkX dictionary format:
sage: d = {0: [1,4,5], 1: [2,6], 2: [3,7], 3: [4,8], 4: [9], \
5: [7, 8], 6: [8,9], 7: [9]}
sage: G = Graph(d); G
Graph on 10 vertices
sage: G.plot().show() # or G.show()
A NetworkX graph:
sage: import networkx
sage: K = networkx.complete_bipartite_graph(12,7)
sage: G = Graph(K)
sage: G.degree()
[7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 12, 12, 12, 12, 12, 12, 12]
graph6 or sparse6 format:
sage: s = ':I`AKGsaOs`cI]Gb~'
sage: G = Graph(s, sparse=True); G
Looped multi-graph on 10 vertices
sage: G.plot().show() # or G.show()
Note that the \ character is an escape character in Python, and also a character used by graph6 strings:
sage: G = Graph('Ihe\n@GUA')
Traceback (most recent call last):
...
RuntimeError: The string (Ihe) seems corrupt: for n = 10, the string is too short.
In Python, the escaped character \ is represented by \\:
sage: G = Graph('Ihe\\n@GUA')
sage: G.plot().show() # or G.show()
adjacency matrix: In an adjacency matrix, each column and each
row represent a vertex. If a 1 shows up in row , column
, there is an edge
.
sage: M = Matrix([(0,1,0,0,1,1,0,0,0,0),(1,0,1,0,0,0,1,0,0,0), \
(0,1,0,1,0,0,0,1,0,0), (0,0,1,0,1,0,0,0,1,0),(1,0,0,1,0,0,0,0,0,1), \
(1,0,0,0,0,0,0,1,1,0), (0,1,0,0,0,0,0,0,1,1),(0,0,1,0,0,1,0,0,0,1), \
(0,0,0,1,0,1,1,0,0,0), (0,0,0,0,1,0,1,1,0,0)])
sage: M
[0 1 0 0 1 1 0 0 0 0]
[1 0 1 0 0 0 1 0 0 0]
[0 1 0 1 0 0 0 1 0 0]
[0 0 1 0 1 0 0 0 1 0]
[1 0 0 1 0 0 0 0 0 1]
[1 0 0 0 0 0 0 1 1 0]
[0 1 0 0 0 0 0 0 1 1]
[0 0 1 0 0 1 0 0 0 1]
[0 0 0 1 0 1 1 0 0 0]
[0 0 0 0 1 0 1 1 0 0]
sage: G = Graph(M); G
Graph on 10 vertices
sage: G.plot().show() # or G.show()
incidence matrix: In an incidence matrix, each row represents a vertex and each column represents an edge.
sage: M = Matrix([(-1,0,0,0,1,0,0,0,0,0,-1,0,0,0,0), \
(1,-1,0,0,0,0,0,0,0,0,0,-1,0,0,0),(0,1,-1,0,0,0,0,0,0,0,0,0,-1,0,0), \
(0,0,1,-1,0,0,0,0,0,0,0,0,0,-1,0),(0,0,0,1,-1,0,0,0,0,0,0,0,0,0,-1), \
(0,0,0,0,0,-1,0,0,0,1,1,0,0,0,0),(0,0,0,0,0,0,0,1,-1,0,0,1,0,0,0), \
(0,0,0,0,0,1,-1,0,0,0,0,0,1,0,0),(0,0,0,0,0,0,0,0,1,-1,0,0,0,1,0), \
(0,0,0,0,0,0,1,-1,0,0,0,0,0,0,1)])
sage: M
[-1 0 0 0 1 0 0 0 0 0 -1 0 0 0 0]
[ 1 -1 0 0 0 0 0 0 0 0 0 -1 0 0 0]
[ 0 1 -1 0 0 0 0 0 0 0 0 0 -1 0 0]
[ 0 0 1 -1 0 0 0 0 0 0 0 0 0 -1 0]
[ 0 0 0 1 -1 0 0 0 0 0 0 0 0 0 -1]
[ 0 0 0 0 0 -1 0 0 0 1 1 0 0 0 0]
[ 0 0 0 0 0 0 0 1 -1 0 0 1 0 0 0]
[ 0 0 0 0 0 1 -1 0 0 0 0 0 1 0 0]
[ 0 0 0 0 0 0 0 0 1 -1 0 0 0 1 0]
[ 0 0 0 0 0 0 1 -1 0 0 0 0 0 0 1]
sage: G = Graph(M); G
Graph on 10 vertices
sage: G.plot().show() # or G.show()
sage: DiGraph(matrix(2,[0,0,-1,1]), format="incidence_matrix")
Traceback (most recent call last):
...
ValueError: There must be two nonzero entries (-1 & 1) per column.
a list of edges:
sage: g = Graph([(1,3),(3,8),(5,2)])
sage: g
Graph on 5 vertices
If you wish to iterate through all the isomorphism types of graphs, type, for example:
sage: for g in graphs(4):
... print g.spectrum()
[0, 0, 0, 0]
[1, 0, 0, -1]
[1.4142135623..., 0, 0, -1.4142135623...]
[2, 0, -1, -1]
[1.7320508075..., 0, 0, -1.7320508075...]
[1, 1, -1, -1]
[1.6180339887..., 0.6180339887..., -0.6180339887..., -1.6180339887...]
[2.1700864866..., 0.3111078174..., -1, -1.4811943040...]
[2, 0, 0, -2]
[2.5615528128..., 0, -1, -1.5615528128...]
[3, -1, -1, -1]
For some commonly used graphs to play with, type
sage: graphs.[tab] # not tested
and hit {tab}. Most of these graphs come with their own custom plot, so you can see how people usually visualize these graphs.
sage: G = graphs.PetersenGraph()
sage: G.plot().show() # or G.show()
sage: G.degree_histogram()
[0, 0, 0, 10]
sage: G.adjacency_matrix()
[0 1 0 0 1 1 0 0 0 0]
[1 0 1 0 0 0 1 0 0 0]
[0 1 0 1 0 0 0 1 0 0]
[0 0 1 0 1 0 0 0 1 0]
[1 0 0 1 0 0 0 0 0 1]
[1 0 0 0 0 0 0 1 1 0]
[0 1 0 0 0 0 0 0 1 1]
[0 0 1 0 0 1 0 0 0 1]
[0 0 0 1 0 1 1 0 0 0]
[0 0 0 0 1 0 1 1 0 0]
sage: S = G.subgraph([0,1,2,3])
sage: S.plot().show() # or S.show()
sage: S.density()
1/2
sage: G = GraphQuery(display_cols=['graph6'], num_vertices=7, diameter=5)
sage: L = G.get_graphs_list()
sage: graphs_list.show_graphs(L)
Each vertex can have any hashable object as a label. These are
things like strings, numbers, and tuples. Each edge is given a
default label of None, but if specified, edges can
have any label at all. Edges between vertices and
are represented typically as (u, v, l), where
l is the label for the edge.
Note that vertex labels themselves cannot be mutable items:
sage: M = Matrix( [[0,0],[0,0]] )
sage: G = Graph({ 0 : { M : None } })
Traceback (most recent call last):
...
TypeError: mutable matrices are unhashable
However, if one wants to define a dictionary, with the same keys and arbitrary objects for entries, one can make that association:
sage: d = {0 : graphs.DodecahedralGraph(), 1 : graphs.FlowerSnark(), \
2 : graphs.MoebiusKantorGraph(), 3 : graphs.PetersenGraph() }
sage: d[2]
Moebius-Kantor Graph: Graph on 16 vertices
sage: T = graphs.TetrahedralGraph()
sage: T.vertices()
[0, 1, 2, 3]
sage: T.set_vertices(d)
sage: T.get_vertex(1)
Flower Snark: Graph on 20 vertices
There is a database available for searching for graphs that satisfy a certain set of parameters, including number of vertices and edges, density, maximum and minimum degree, diameter, radius, and connectivity. To see a list of all search parameter keywords broken down by their designated table names, type
sage: graph_db_info()
{...}
For more details on data types or keyword input, enter
sage: GraphQuery? # not tested
The results of a query can be viewed with the show method, or can be viewed individually by iterating through the results:
sage: Q = GraphQuery(display_cols=['graph6'],num_vertices=7, diameter=5)
sage: Q.show()
Graph6
--------------------
F@?]O
F@OKg
F?`po
F?gqg
FIAHo
F@R@o
FA_pW
FGC{o
FEOhW
Show each graph as you iterate through the results:
sage: for g in Q:
... show(g)
To see a graph you are working with, there
are three main options. You can view the graph in two dimensions via
matplotlib with show().
sage: G = graphs.RandomGNP(15,.3)
sage: G.show()
And you can view it in three dimensions via jmol with show3d().
sage: G.show3d()
Or it can be rendered with . This requires the right
additions to a standard
installation. Then standard
Sage commands, such as view(G) will display the graph, or
latex(G) will produce a string suitable for inclusion in a
document. More details on this are at
the sage.graphs.graph_latex module.
sage: from sage.graphs.graph_latex import check_tkz_graph
sage: check_tkz_graph() # random - depends on TeX installation
sage: latex(G)
\begin{tikzpicture}
...
\end{tikzpicture}
Bases: sage.graphs.generic_graph.GenericGraph
Undirected graph.
A graph is a set of vertices connected by edges. See also the Wikipedia article on graphs.
One can very easily create a graph in Sage by typing:
sage: g = Graph()
By typing the name of the graph, one can get some basic information about it:
sage: g
Graph on 0 vertices
This graph is not very interesting as it is by default the empty graph. But Sage contains a large collection of pre-defined graph classes that can be listed this way:
You will see a list of methods which will construct named graphs. For example:
sage: g = graphs.PetersenGraph()
sage: g.plot()
or:
sage: g = graphs.ChvatalGraph()
sage: g.plot()
In order to obtain more information about these graph constructors, access the documentation using the command graphs.RandomGNP?.
Once you have defined the graph you want, you can begin to work on it by using the almost 200 functions on graphs in the Sage library! If your graph is named g, you can list these functions as previously this way
As usual, you can get some information about what these functions do by typing (e.g. if you want to know about the diameter() method) g.diameter?.
If you have defined a graph g having several connected components (i.e. g.is_connected() returns False), you can print each one of its connected components with only two lines:
sage: for component in g.connected_components():
... g.subgraph(component).plot()
INPUT:
- An integer specifying the number of vertices
- A dictionary of dictionaries
- A dictionary of lists
- A NumPy matrix or ndarray
- A Sage adjacency matrix or incidence matrix
- A pygraphviz graph
- A SciPy sparse matrix
- A NetworkX graph
pos - a positioning dictionary: for example, the spring layout from NetworkX for the 5-cycle is:
{0: [-0.91679746, 0.88169588],
1: [ 0.47294849, 1.125 ],
2: [ 1.125 ,-0.12867615],
3: [ 0.12743933,-1.125 ],
4: [-1.125 ,-0.50118505]}
name - (must be an explicitly named parameter, i.e., name="complete") gives the graph a name
loops - boolean, whether to allow loops (ignored if data is an instance of the Graph class)
multiedges - boolean, whether to allow multiple edges (ignored if data is an instance of the Graph class)
weighted - whether graph thinks of itself as weighted or not. See self.weighted()
format - if None, Graph tries to guess- can be several values, including:
'int' - an integer specifying the number of vertices in an edge-free graph with vertices labelled from 0 to n-1
'graph6' - Brendan McKay’s graph6 format, in a string (if the string has multiple graphs, the first graph is taken)
'sparse6' - Brendan McKay’s sparse6 format, in a string (if the string has multiple graphs, the first graph is taken)
'adjacency_matrix' - a square Sage matrix M, with M[i,j] equal to the number of edges {i,j}
'weighted_adjacency_matrix' - a square Sage matrix M, with M[i,j] equal to the weight of the single edge {i,j}. Given this format, weighted is ignored (assumed True).
'incidence_matrix' - a Sage matrix, with one column C for each edge, where if C represents {i, j}, C[i] is -1 and C[j] is 1
'elliptic_curve_congruence' - data must be an iterable container of elliptic curves, and the graph produced has each curve as a vertex (it’s Cremona label) and an edge E-F labelled p if and only if E is congruent to F mod p
NX - data must be a NetworkX Graph.
Note
As Sage’s default edge labels is None while NetworkX uses {}, the {} labels of a NetworkX graph are automatically set to None when it is converted to a Sage graph. This behaviour can be overruled by setting the keyword convert_empty_dict_labels_to_None to False (it is True by default).
boundary - a list of boundary vertices, if empty, graph is considered as a ‘graph without boundary’
implementation - what to use as a backend for the graph. Currently, the options are either ‘networkx’ or ‘c_graph’
sparse - only for implementation == ‘c_graph’. Whether to use sparse or dense graphs as backend. Note that currently dense graphs do not have edge labels, nor can they be multigraphs
vertex_labels - only for implementation == ‘c_graph’. Whether to allow any object as a vertex (slower), or only the integers 0, ..., n-1, where n is the number of vertices.
convert_empty_dict_labels_to_None - this arguments sets the default edge labels used by NetworkX (empty dictionaries) to be replaced by None, the default Sage edge label. It is set to True iff a NetworkX graph is on the input.
EXAMPLES:
We illustrate the first seven input formats (the other two involve packages that are currently not standard in Sage):
An integer giving the number of vertices:
sage: g = Graph(5); g
Graph on 5 vertices
sage: g.vertices()
[0, 1, 2, 3, 4]
sage: g.edges()
[]
A dictionary of dictionaries:
sage: g = Graph({0:{1:'x',2:'z',3:'a'}, 2:{5:'out'}}); g
Graph on 5 vertices
The labels (‘x’, ‘z’, ‘a’, ‘out’) are labels for edges. For example, ‘out’ is the label for the edge on 2 and 5. Labels can be used as weights, if all the labels share some common parent.
sage: a,b,c,d,e,f = sorted(SymmetricGroup(3))
sage: Graph({b:{d:'c',e:'p'}, c:{d:'p',e:'c'}})
Graph on 4 vertices
A dictionary of lists:
sage: g = Graph({0:[1,2,3], 2:[4]}); g
Graph on 5 vertices
A list of vertices and a function describing adjacencies. Note that the list of vertices and the function must be enclosed in a list (i.e., [list of vertices, function]).
Construct the Paley graph over GF(13).
sage: g=Graph([GF(13), lambda i,j: i!=j and (i-j).is_square()])
sage: g.vertices()
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
sage: g.adjacency_matrix()
[0 1 0 1 1 0 0 0 0 1 1 0 1]
[1 0 1 0 1 1 0 0 0 0 1 1 0]
[0 1 0 1 0 1 1 0 0 0 0 1 1]
[1 0 1 0 1 0 1 1 0 0 0 0 1]
[1 1 0 1 0 1 0 1 1 0 0 0 0]
[0 1 1 0 1 0 1 0 1 1 0 0 0]
[0 0 1 1 0 1 0 1 0 1 1 0 0]
[0 0 0 1 1 0 1 0 1 0 1 1 0]
[0 0 0 0 1 1 0 1 0 1 0 1 1]
[1 0 0 0 0 1 1 0 1 0 1 0 1]
[1 1 0 0 0 0 1 1 0 1 0 1 0]
[0 1 1 0 0 0 0 1 1 0 1 0 1]
[1 0 1 1 0 0 0 0 1 1 0 1 0]
Construct the line graph of a complete graph.
sage: g=graphs.CompleteGraph(4)
sage: line_graph=Graph([g.edges(labels=false), \
lambda i,j: len(set(i).intersection(set(j)))>0], \
loops=False)
sage: line_graph.vertices()
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
sage: line_graph.adjacency_matrix()
[0 1 1 1 1 0]
[1 0 1 1 0 1]
[1 1 0 0 1 1]
[1 1 0 0 1 1]
[1 0 1 1 0 1]
[0 1 1 1 1 0]
A NumPy matrix or ndarray:
sage: import numpy
sage: A = numpy.array([[0,1,1],[1,0,1],[1,1,0]])
sage: Graph(A)
Graph on 3 vertices
A graph6 or sparse6 string: Sage automatically recognizes whether a string is in graph6 or sparse6 format:
sage: s = ':I`AKGsaOs`cI]Gb~'
sage: Graph(s,sparse=True)
Looped multi-graph on 10 vertices
sage: G = Graph('G?????')
sage: G = Graph("G'?G?C")
Traceback (most recent call last):
...
RuntimeError: The string seems corrupt: valid characters are
?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
sage: G = Graph('G??????')
Traceback (most recent call last):
...
RuntimeError: The string (G??????) seems corrupt: for n = 8, the string is too long.
sage: G = Graph(":I'AKGsaOs`cI]Gb~")
Traceback (most recent call last):
...
RuntimeError: The string seems corrupt: valid characters are
?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_`abcdefghijklmnopqrstuvwxyz{|}~
There are also list functions to take care of lists of graphs:
sage: s = ':IgMoqoCUOqeb\n:I`AKGsaOs`cI]Gb~\n:I`EDOAEQ?PccSsge\N\n'
sage: graphs_list.from_sparse6(s)
[Looped multi-graph on 10 vertices, Looped multi-graph on 10 vertices, Looped multi-graph on 10 vertices]
A Sage matrix: Note: If format is not specified, then Sage assumes a symmetric square matrix is an adjacency matrix, otherwise an incidence matrix.
an adjacency matrix:
sage: M = graphs.PetersenGraph().am(); M
[0 1 0 0 1 1 0 0 0 0]
[1 0 1 0 0 0 1 0 0 0]
[0 1 0 1 0 0 0 1 0 0]
[0 0 1 0 1 0 0 0 1 0]
[1 0 0 1 0 0 0 0 0 1]
[1 0 0 0 0 0 0 1 1 0]
[0 1 0 0 0 0 0 0 1 1]
[0 0 1 0 0 1 0 0 0 1]
[0 0 0 1 0 1 1 0 0 0]
[0 0 0 0 1 0 1 1 0 0]
sage: Graph(M)
Graph on 10 vertices
sage: Graph(matrix([[1,2],[2,4]]),loops=True,sparse=True)
Looped multi-graph on 2 vertices
sage: M = Matrix([[0,1,-1],[1,0,-1/2],[-1,-1/2,0]]); M
[ 0 1 -1]
[ 1 0 -1/2]
[ -1 -1/2 0]
sage: G = Graph(M,sparse=True); G
Graph on 3 vertices
sage: G.weighted()
True
an incidence matrix:
sage: M = Matrix(6, [-1,0,0,0,1, 1,-1,0,0,0, 0,1,-1,0,0, 0,0,1,-1,0, 0,0,0,1,-1, 0,0,0,0,0]); M
[-1 0 0 0 1]
[ 1 -1 0 0 0]
[ 0 1 -1 0 0]
[ 0 0 1 -1 0]
[ 0 0 0 1 -1]
[ 0 0 0 0 0]
sage: Graph(M)
Graph on 6 vertices
sage: Graph(Matrix([[1],[1],[1]]))
Traceback (most recent call last):
...
ValueError: Non-symmetric or non-square matrix assumed to be an incidence matrix: There must be two nonzero entries (-1 & 1) per column.
sage: Graph(Matrix([[1],[1],[0]]))
Traceback (most recent call last):
...
ValueError: Non-symmetric or non-square matrix assumed to be an incidence matrix: Each column represents an edge: -1 goes to 1.
sage: M = Matrix([[0,1,-1],[1,0,-1],[-1,-1,0]]); M
[ 0 1 -1]
[ 1 0 -1]
[-1 -1 0]
sage: Graph(M,sparse=True)
Graph on 3 vertices
sage: M = Matrix([[0,1,1],[1,0,1],[-1,-1,0]]); M
[ 0 1 1]
[ 1 0 1]
[-1 -1 0]
sage: Graph(M)
Traceback (most recent call last):
...
ValueError: Non-symmetric or non-square matrix assumed to be an incidence matrix: Each column represents an edge: -1 goes to 1.
sage: MA = Matrix([[1,2,0], [0,2,0], [0,0,1]]) # trac 9714 sage: MI = Graph(MA, format='adjacency_matrix').incidence_matrix(); MI [-1 -1 0 0 0 1] [ 1 1 0 1 1 0] [ 0 0 1 0 0 0] sage: Graph(MI).edges(labels=None) [(0, 0), (0, 1), (0, 1), (1, 1), (1, 1), (2, 2)] sage: M = Matrix([[1], [-1]]); M [ 1] [-1] sage: Graph(M).edges() [(0, 1, None)]
a list of edges, or labelled edges:
sage: g = Graph([(1,3),(3,8),(5,2)])
sage: g
Graph on 5 vertices
::
sage: g = Graph([(1,2,"Peace"),(7,-9,"and"),(77,2, "Love")])
sage: g
Graph on 5 vertices
sage: g = Graph([(0, 2, '0'), (0, 2, '1'), (3, 3, '2')])
sage: g.loops()
[(3, 3, '2')]
A NetworkX MultiGraph:
sage: import networkx
sage: g = networkx.MultiGraph({0:[1,2,3], 2:[4]})
sage: Graph(g)
Graph on 5 vertices
A NetworkX graph:
sage: import networkx
sage: g = networkx.Graph({0:[1,2,3], 2:[4]})
sage: DiGraph(g)
Digraph on 5 vertices
Note that in all cases, we copy the NetworkX structure.
sage: import networkx sage: g = networkx.Graph({0:[1,2,3], 2:[4]}) sage: G = Graph(g, implementation='networkx') sage: H = Graph(g, implementation='networkx') sage: G._backend._nxg is H._backend._nxg False
Returns a dictionary with vertices as the keys and the color class as the values. Fails with an error if the graph is not bipartite.
EXAMPLES:
sage: graphs.CycleGraph(4).bipartite_color()
{0: 1, 1: 0, 2: 1, 3: 0}
sage: graphs.CycleGraph(5).bipartite_color()
Traceback (most recent call last):
...
RuntimeError: Graph is not bipartite.
Returns where
and
are the nodes in each bipartite set of
graph
. Fails with an error if graph is not bipartite.
EXAMPLES:
sage: graphs.CycleGraph(4).bipartite_sets()
(set([0, 2]), set([1, 3]))
sage: graphs.CycleGraph(5).bipartite_sets()
Traceback (most recent call last):
...
RuntimeError: Graph is not bipartite.
Computes an orientation of self such that every vertex
has out-degree less than
INPUT:
bound – Maximum bound on the out-degree. Can be of three different types :
- An integer
. In this case, computes an orientation whose maximum out-degree is less than
.
- A dictionary associating to each vertex its associated maximum out-degree.
- A function associating to each vertex its associated maximum out-degree.
OUTPUT:
A DiGraph representing the orientation if it exists. A ValueError exception is raised otherwise.
ALGORITHM:
The problem is solved through a maximum flow :
Given a graph , we create a DiGraph
defined on
. We then link
to all of
(these edges having a capacity equal to the bound associated
to each element of
), and all the elements of
to
. We then link each
to each of its incident
edges in
. A maximum integer flow of value
corresponds to an admissible orientation of
. Otherwise,
none exists.
EXAMPLES:
There is always an orientation of a graph such that a
vertex
has out-degree at most
:
sage: g = graphs.RandomGNP(40, .4)
sage: b = lambda v : ceil(g.degree(v)/2)
sage: D = g.bounded_outdegree_orientation(b)
sage: all( D.out_degree(v) <= b(v) for v in g )
True
Chvatal’s graph, being 4-regular, can be oriented in such a way that its maximum out-degree is 2:
sage: g = graphs.ChvatalGraph()
sage: D = g.bounded_outdegree_orientation(2)
sage: max(D.out_degree())
2
For any graph , it is possible to compute an orientation
such that the maximum out-degree is at most the maximum
average degree of
divided by 2. Anything less, though, is
impossible.
sage: g = graphs.RandomGNP(40, .4) sage: mad = g.maximum_average_degree()
Hence this is possible
sage: d = g.bounded_outdegree_orientation(ceil(mad/2))
While this is not:
sage: try:
... g.bounded_outdegree_orientation(ceil(mad/2-1))
... print "Error"
... except ValueError:
... pass
TESTS:
As previously for random graphs, but more intensively:
sage: for i in xrange(30): # long time (up to 6s on sage.math, 2012)
... g = graphs.RandomGNP(40, .4)
... b = lambda v : ceil(g.degree(v)/2)
... D = g.bounded_outdegree_orientation(b)
... if not (
... all( D.out_degree(v) <= b(v) for v in g ) or
... D.size() != g.size()):
... print "Something wrong happened"
Returns the betweenness centrality (fraction of number of shortest paths that go through each vertex) as a dictionary keyed by vertices. The betweenness is normalized by default to be in range (0,1). This wraps NetworkX’s implementation of the algorithm described in [Brandes2003].
Measures of the centrality of a vertex within a graph determine the relative importance of that vertex to its graph. Vertices that occur on more shortest paths between other vertices have higher betweenness than vertices that occur on less.
INPUT:
REFERENCE:
[Brandes2003] | Ulrik Brandes. (2003). Faster Evaluation of Shortest-Path Based Centrality Indices. [Online] Available: http://citeseer.nj.nec.com/brandes00faster.html |
EXAMPLES:
sage: (graphs.ChvatalGraph()).centrality_betweenness()
{0: 0.06969696969696969, 1: 0.06969696969696969,
2: 0.0606060606060606, 3: 0.0606060606060606,
4: 0.06969696969696969, 5: 0.06969696969696969,
6: 0.0606060606060606, 7: 0.0606060606060606,
8: 0.0606060606060606, 9: 0.0606060606060606,
10: 0.0606060606060606, 11: 0.0606060606060606}
sage: (graphs.ChvatalGraph()).centrality_betweenness(
... normalized=False)
{0: 3.833333333333333, 1: 3.833333333333333, 2: 3.333333333333333,
3: 3.333333333333333, 4: 3.833333333333333, 5: 3.833333333333333,
6: 3.333333333333333, 7: 3.333333333333333, 8: 3.333333333333333,
9: 3.333333333333333, 10: 3.333333333333333,
11: 3.333333333333333}
sage: D = DiGraph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: D.show(figsize=[2,2])
sage: D = D.to_undirected()
sage: D.show(figsize=[2,2])
sage: D.centrality_betweenness()
{0: 0.16666666666666666, 1: 0.16666666666666666, 2: 0.0, 3: 0.0}
Returns the closeness centrality (1/average distance to all vertices) as a dictionary of values keyed by vertex. The degree centrality is normalized to be in range (0,1).
Measures of the centrality of a vertex within a graph determine the relative importance of that vertex to its graph. ‘Closeness centrality may be defined as the total graph-theoretic distance of a given vertex from all other vertices... Closeness is an inverse measure of centrality in that a larger value indicates a less central actor while a smaller value indicates a more central actor,’ [Borgatti95].
INPUT:
REFERENCE:
[Borgatti95] | Stephen P Borgatti. (1995). Centrality and AIDS. [Online] Available: http://www.analytictech.com/networks/centaids.htm |
EXAMPLES:
sage: (graphs.ChvatalGraph()).centrality_closeness()
{0: 0.61111111111111..., 1: 0.61111111111111..., 2: 0.61111111111111..., 3: 0.61111111111111..., 4: 0.61111111111111..., 5: 0.61111111111111..., 6: 0.61111111111111..., 7: 0.61111111111111..., 8: 0.61111111111111..., 9: 0.61111111111111..., 10: 0.61111111111111..., 11: 0.61111111111111...}
sage: D = DiGraph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: D.show(figsize=[2,2])
sage: D = D.to_undirected()
sage: D.show(figsize=[2,2])
sage: D.centrality_closeness()
{0: 1.0, 1: 1.0, 2: 0.75, 3: 0.75}
sage: D.centrality_closeness(v=1)
1.0
Returns the degree centrality (fraction of vertices connected to) as a dictionary of values keyed by vertex. The degree centrality is normalized to be in range (0,1).
Measures of the centrality of a vertex within a graph determine the relative importance of that vertex to its graph. Degree centrality measures the number of links incident upon a vertex.
INPUT:
EXAMPLES:
sage: (graphs.ChvatalGraph()).centrality_degree()
{0: 0.36363636363636365, 1: 0.36363636363636365, 2: 0.36363636363636365, 3: 0.36363636363636365, 4: 0.36363636363636365, 5: 0.36363636363636365, 6: 0.36363636363636365, 7: 0.36363636363636365, 8: 0.36363636363636365, 9: 0.36363636363636365, 10: 0.36363636363636365, 11: 0.36363636363636365}
sage: D = DiGraph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: D.show(figsize=[2,2])
sage: D = D.to_undirected()
sage: D.show(figsize=[2,2])
sage: D.centrality_degree()
{0: 1.0, 1: 1.0, 2: 0.6666666666666666, 3: 0.6666666666666666}
sage: D.centrality_degree(v=1)
1.0
Returns the minimal number of colors needed to color the vertices
of the graph .
INPUT:
See also
For more functions related to graph coloring, see the module sage.graphs.graph_coloring.
EXAMPLES:
sage: G = Graph({0: [1, 2, 3], 1: [2]})
sage: G.chromatic_number(algorithm="DLX")
3
sage: G.chromatic_number(algorithm="MILP")
3
sage: G.chromatic_number(algorithm="CP")
3
TESTS:
sage: G = Graph({0: [1, 2, 3], 1: [2]})
sage: G.chromatic_number(algorithm="foo")
Traceback (most recent call last):
...
ValueError: The 'algorithm' keyword must be set to either 'DLX', 'MILP' or 'CP'.
Computes the chromatic polynomial of the graph G.
The algorithm used is a recursive one, based on the following observations of Read:
- The chromatic polynomial of a tree on n vertices is x(x-1)^(n-1).
- If e is an edge of G, G’ is the result of deleting the edge e, and G’’ is the result of contracting e, then the chromatic polynomial of G is equal to that of G’ minus that of G’‘.
EXAMPLES:
sage: graphs.CycleGraph(4).chromatic_polynomial()
x^4 - 4*x^3 + 6*x^2 - 3*x
sage: graphs.CycleGraph(3).chromatic_polynomial()
x^3 - 3*x^2 + 2*x
sage: graphs.CubeGraph(3).chromatic_polynomial()
x^8 - 12*x^7 + 66*x^6 - 214*x^5 + 441*x^4 - 572*x^3 + 423*x^2 - 133*x
sage: graphs.PetersenGraph().chromatic_polynomial()
x^10 - 15*x^9 + 105*x^8 - 455*x^7 + 1353*x^6 - 2861*x^5 + 4275*x^4 - 4305*x^3 + 2606*x^2 - 704*x
sage: graphs.CompleteBipartiteGraph(3,3).chromatic_polynomial()
x^6 - 9*x^5 + 36*x^4 - 75*x^3 + 78*x^2 - 31*x
sage: for i in range(2,7):
... graphs.CompleteGraph(i).chromatic_polynomial().factor()
(x - 1) * x
(x - 2) * (x - 1) * x
(x - 3) * (x - 2) * (x - 1) * x
(x - 4) * (x - 3) * (x - 2) * (x - 1) * x
(x - 5) * (x - 4) * (x - 3) * (x - 2) * (x - 1) * x
sage: graphs.CycleGraph(5).chromatic_polynomial().factor()
(x - 2) * (x - 1) * x * (x^2 - 2*x + 2)
sage: graphs.OctahedralGraph().chromatic_polynomial().factor()
(x - 2) * (x - 1) * x * (x^3 - 9*x^2 + 29*x - 32)
sage: graphs.WheelGraph(5).chromatic_polynomial().factor()
(x - 2) * (x - 1) * x * (x^2 - 5*x + 7)
sage: graphs.WheelGraph(6).chromatic_polynomial().factor()
(x - 3) * (x - 2) * (x - 1) * x * (x^2 - 4*x + 5)
sage: C(x)=graphs.LCFGraph(24, [12,7,-7], 8).chromatic_polynomial() # long time (6s on sage.math, 2011)
sage: C(2) # long time
0
Returns the clique complex of self. This is the largest simplicial complex on the vertices of self whose 1-skeleton is self.
This is only makes sense for undirected simple graphs.
EXAMPLES:
sage: g = Graph({0:[1,2],1:[2],4:[]})
sage: g.clique_complex()
Simplicial complex with vertex set (0, 1, 2, 4) and facets {(4,), (0, 1, 2)}
sage: h = Graph({0:[1,2,3,4],1:[2,3,4],2:[3]})
sage: x = h.clique_complex()
sage: x
Simplicial complex with vertex set (0, 1, 2, 3, 4) and facets {(0, 1, 4), (0, 1, 2, 3)}
sage: i = x.graph()
sage: i==h
True
sage: x==i.clique_complex()
True
Returns the vertex set of a maximal order complete subgraph.
INPUT:
algorithm – the algorithm to be used :
If algorithm = "Cliquer" (default) - This wraps the C program Cliquer [NisOst2003].
If algorithm = "MILP", the problem is solved through a Mixed Integer Linear Program.
(see MixedIntegerLinearProgram)
Note
Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.
ALGORITHM:
This function is based on Cliquer [NisOst2003].
EXAMPLES:
Using Cliquer (default):
sage: C=graphs.PetersenGraph()
sage: C.clique_maximum()
[7, 9]
sage: C = Graph('DJ{')
sage: C.clique_maximum()
[1, 2, 3, 4]
Through a Linear Program:
sage: len(C.clique_maximum(algorithm = "MILP"))
4
TESTS:
Wrong algorithm:
sage: C.clique_maximum(algorithm = "BFS")
Traceback (most recent call last):
...
NotImplementedError: Only 'MILP' and 'Cliquer' are supported.
Returns the order of the largest clique of the graph (the clique number).
Note
Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.
INPUT:
algorithm – the algorithm to be used :
If algorithm = "Cliquer" - This wraps the C program Cliquer [NisOst2003].
If algorithm = "networkx" - This function is based on NetworkX’s implementation of the Bron and Kerbosch Algorithm [BroKer1973].
If algorithm = "MILP", the problem is solved through a Mixed Integer Linear Program.
(see MixedIntegerLinearProgram)
cliques - an optional list of cliques that can be input if already computed. Ignored unless algorithm=="networkx".
ALGORITHM:
This function is based on Cliquer [NisOst2003] and [BroKer1973].
EXAMPLES:
sage: C = Graph('DJ{')
sage: C.clique_number()
4
sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])
sage: G.clique_number()
3
TESTS:
sage: g = graphs.PetersenGraph()
sage: g.clique_number(algorithm="MILP")
2
Deprecated: Use cliques_maximal() instead. See trac ticket #5739 for details.
Returns the cliques containing each vertex, represented as a dictionary of lists of lists, keyed by vertex. (Returns a single list if only one input vertex).
Note
Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.
INPUT:
EXAMPLES:
sage: C = Graph('DJ{')
sage: C.cliques_containing_vertex()
{0: [[4, 0]], 1: [[4, 1, 2, 3]], 2: [[4, 1, 2, 3]], 3: [[4, 1, 2, 3]], 4: [[4, 0], [4, 1, 2, 3]]}
sage: E = C.cliques_maximal()
sage: E
[[4, 0], [4, 1, 2, 3]]
sage: C.cliques_containing_vertex(cliques=E)
{0: [[4, 0]], 1: [[4, 1, 2, 3]], 2: [[4, 1, 2, 3]], 3: [[4, 1, 2, 3]], 4: [[4, 0], [4, 1, 2, 3]]}
sage: F = graphs.Grid2dGraph(2,3)
sage: X = F.cliques_containing_vertex()
sage: for v in sorted(X.iterkeys()):
... print v, X[v]
(0, 0) [[(0, 1), (0, 0)], [(1, 0), (0, 0)]]
(0, 1) [[(0, 1), (0, 0)], [(0, 1), (0, 2)], [(0, 1), (1, 1)]]
(0, 2) [[(0, 1), (0, 2)], [(1, 2), (0, 2)]]
(1, 0) [[(1, 0), (0, 0)], [(1, 0), (1, 1)]]
(1, 1) [[(0, 1), (1, 1)], [(1, 2), (1, 1)], [(1, 0), (1, 1)]]
(1, 2) [[(1, 2), (0, 2)], [(1, 2), (1, 1)]]
sage: F.cliques_containing_vertex(vertices=[(0, 1), (1, 2)])
{(0, 1): [[(0, 1), (0, 0)], [(0, 1), (0, 2)], [(0, 1), (1, 1)]], (1, 2): [[(1, 2), (0, 2)], [(1, 2), (1, 1)]]}
sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])
sage: G.cliques_containing_vertex()
{0: [[0, 1, 2], [0, 1, 3]], 1: [[0, 1, 2], [0, 1, 3]], 2: [[0, 1, 2]], 3: [[0, 1, 3]]}
Returns a bipartite graph constructed such that maximal cliques are the right vertices and the left vertices are retained from the given graph. Right and left vertices are connected if the bottom vertex belongs to the clique represented by a top vertex.
Note
Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.
EXAMPLES:
sage: (graphs.ChvatalGraph()).cliques_get_clique_bipartite()
Bipartite graph on 36 vertices
sage: ((graphs.ChvatalGraph()).cliques_get_clique_bipartite()).show(figsize=[2,2], vertex_size=20, vertex_labels=False)
sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])
sage: G.cliques_get_clique_bipartite()
Bipartite graph on 6 vertices
sage: (G.cliques_get_clique_bipartite()).show(figsize=[2,2])
Returns a graph constructed with maximal cliques as vertices, and edges between maximal cliques with common members in the original graph.
Note
Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.
INPUT:
EXAMPLES:
sage: (graphs.ChvatalGraph()).cliques_get_max_clique_graph()
Graph on 24 vertices
sage: ((graphs.ChvatalGraph()).cliques_get_max_clique_graph()).show(figsize=[2,2], vertex_size=20, vertex_labels=False)
sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])
sage: G.cliques_get_max_clique_graph()
Graph on 2 vertices
sage: (G.cliques_get_max_clique_graph()).show(figsize=[2,2])
Returns the list of all maximal cliques, with each clique represented by a list of vertices. A clique is an induced complete subgraph, and a maximal clique is one not contained in a larger one.
Note
Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.
ALGORITHM:
This function is based on NetworkX’s implementation of the Bron and Kerbosch Algorithm [BroKer1973].
REFERENCE:
[BroKer1973] | (1, 2, 3, 4) Coen Bron and Joep Kerbosch. (1973). Algorithm 457: Finding All Cliques of an Undirected Graph. Commun. ACM. v 16. n 9. pages 575-577. ACM Press. [Online] Available: http://www.ram.org/computing/rambin/rambin.html |
EXAMPLES:
sage: graphs.ChvatalGraph().cliques_maximal()
[[0, 1], [0, 4], [0, 6], [0, 9], [2, 1], [2, 3], [2, 6], [2, 8], [3, 4], [3, 7], [3, 9], [5, 1], [5, 4], [5, 10], [5, 11], [7, 1], [7, 8], [7, 11], [8, 4], [8, 10], [10, 6], [10, 9], [11, 6], [11, 9]]
sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])
sage: G.cliques_maximal()
[[0, 1, 2], [0, 1, 3]]
sage: C=graphs.PetersenGraph()
sage: C.cliques_maximal()
[[0, 1], [0, 4], [0, 5], [2, 1], [2, 3], [2, 7], [3, 4], [3, 8], [6, 1], [6, 8], [6, 9], [7, 5], [7, 9], [8, 5], [9, 4]]
sage: C = Graph('DJ{')
sage: C.cliques_maximal()
[[4, 0], [4, 1, 2, 3]]
Returns the vertex sets of ALL the maximum complete subgraphs.
Returns the list of all maximum cliques, with each clique represented by a list of vertices. A clique is an induced complete subgraph, and a maximum clique is one of maximal order.
Note
Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.
ALGORITHM:
This function is based on Cliquer [NisOst2003].
EXAMPLES:
sage: graphs.ChvatalGraph().cliques_maximum()
[[0, 1], [0, 4], [0, 6], [0, 9], [1, 2], [1, 5], [1, 7], [2, 3],
[2, 6], [2, 8], [3, 4], [3, 7], [3, 9], [4, 5], [4, 8], [5, 10],
[5, 11], [6, 10], [6, 11], [7, 8], [7, 11], [8, 10], [9, 10], [9, 11]]
sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])
sage: G.cliques_maximum()
[[0, 1, 2], [0, 1, 3]]
sage: C=graphs.PetersenGraph()
sage: C.cliques_maximum()
[[0, 1], [0, 4], [0, 5], [1, 2], [1, 6], [2, 3], [2, 7], [3, 4],
[3, 8], [4, 9], [5, 7], [5, 8], [6, 8], [6, 9], [7, 9]]
sage: C = Graph('DJ{')
sage: C.cliques_maximum()
[[1, 2, 3, 4]]
Returns a dictionary of the number of maximal cliques containing each vertex, keyed by vertex. (Returns a single value if only one input vertex).
Note
Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.
INPUT:
EXAMPLES:
sage: C = Graph('DJ{')
sage: C.cliques_number_of()
{0: 1, 1: 1, 2: 1, 3: 1, 4: 2}
sage: E = C.cliques_maximal()
sage: E
[[4, 0], [4, 1, 2, 3]]
sage: C.cliques_number_of(cliques=E)
{0: 1, 1: 1, 2: 1, 3: 1, 4: 2}
sage: F = graphs.Grid2dGraph(2,3)
sage: X = F.cliques_number_of()
sage: for v in sorted(X.iterkeys()):
... print v, X[v]
(0, 0) 2
(0, 1) 3
(0, 2) 2
(1, 0) 2
(1, 1) 3
(1, 2) 2
sage: F.cliques_number_of(vertices=[(0, 1), (1, 2)])
{(0, 1): 3, (1, 2): 2}
sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])
sage: G.cliques_number_of()
{0: 2, 1: 2, 2: 1, 3: 1}
Returns a dictionary of sizes of the largest maximal cliques containing each vertex, keyed by vertex. (Returns a single value if only one input vertex).
Note
Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.
INPUT:
algorithm - either cliquer or networkx
cliquer - This wraps the C program Cliquer [NisOst2003].
- networkx - This function is based on NetworkX’s implementation
of the Bron and Kerbosch Algorithm [BroKer1973].
EXAMPLES:
sage: C = Graph('DJ{')
sage: C.cliques_vertex_clique_number()
{0: 2, 1: 4, 2: 4, 3: 4, 4: 4}
sage: E = C.cliques_maximal()
sage: E
[[4, 0], [4, 1, 2, 3]]
sage: C.cliques_vertex_clique_number(cliques=E,algorithm="networkx")
{0: 2, 1: 4, 2: 4, 3: 4, 4: 4}
sage: F = graphs.Grid2dGraph(2,3)
sage: X = F.cliques_vertex_clique_number(algorithm="networkx")
sage: for v in sorted(X.iterkeys()):
... print v, X[v]
(0, 0) 2
(0, 1) 2
(0, 2) 2
(1, 0) 2
(1, 1) 2
(1, 2) 2
sage: F.cliques_vertex_clique_number(vertices=[(0, 1), (1, 2)])
{(0, 1): 2, (1, 2): 2}
sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])
sage: G.cliques_vertex_clique_number()
{0: 3, 1: 3, 2: 3, 3: 3}
Returns the first (optimal) proper vertex-coloring found.
INPUT:
See also
For more functions related to graph coloring, see the module sage.graphs.graph_coloring.
EXAMPLES:
sage: G = Graph("Fooba")
sage: P = G.coloring(algorithm="MILP"); P
[[2, 1, 3], [0, 6, 5], [4]]
sage: P = G.coloring(algorithm="DLX"); P
[[1, 2, 3], [0, 5, 6], [4]]
sage: G.plot(partition=P)
sage: H = G.coloring(hex_colors=True, algorithm="MILP")
sage: for c in sorted(H.keys()):
... print c, H[c]
#0000ff [4]
#00ff00 [0, 6, 5]
#ff0000 [2, 1, 3]
sage: H = G.coloring(hex_colors=True, algorithm="DLX")
sage: for c in sorted(H.keys()):
... print c, H[c]
#0000ff [4]
#00ff00 [1, 2, 3]
#ff0000 [0, 5, 6]
sage: G.plot(vertex_colors=H)
TESTS:
sage: G.coloring(algorithm="foo")
Traceback (most recent call last):
...
ValueError: The 'algorithm' keyword must be set to either 'DLX' or 'MILP'.
Returns a ConvexityProperties objet corresponding to self.
This object contains the methods related to convexity in graphs (convex hull, hull number) and caches useful information so that it becomes comparatively cheaper to compute the convex hull of many different sets of the same graph.
See also
In order to know what can be done through this object, please refer to module sage.graphs.convexity_properties.
Note
If you want to compute many convex hulls, keep this object in memory ! When it is created, it builds a table of useful information to compute convex hulls. As a result
sage: g = graphs.PetersenGraph()
sage: g.convexity_properties().hull([1, 3])
[1, 2, 3]
sage: g.convexity_properties().hull([3, 7])
[2, 3, 7]
Is a terrible waste of computations, while
sage: g = graphs.PetersenGraph()
sage: CP = g.convexity_properties()
sage: CP.hull([1, 3])
[1, 2, 3]
sage: CP.hull([3, 7])
[2, 3, 7]
Makes perfect sense.
Returns the core number for each vertex in an ordered list.
(for homomorphisms cores, see the Graph.has_homomorphism_to() method)
DEFINITIONS
K-cores in graph theory were introduced by Seidman in 1983 and by Bollobas in 1984 as a method of (destructively) simplifying graph topology to aid in analysis and visualization. They have been more recently defined as the following by Batagelj et al:
Given a graph `G` with vertices set `V` and edges set `E`, the `k`-core of `G` is the graph obtained from `G` by recursively removing the vertices with degree less than `k`, for as long as there are any.
This operation can be useful to filter or to study some properties of the graphs. For instance, when you compute the 2-core of graph G, you are cutting all the vertices which are in a tree part of graph. (A tree is a graph with no loops). [WPkcore]
[PSW1996] defines a -core of
as the largest subgraph (it is
unique) of
with minimum degree at least
.
Core number of a vertex
The core number of a vertex is the largest integer
such that
belongs to the
-core of
.
Degeneracy
The degeneracy of a graph , usually denoted
, is the
smallest integer
such that the graph
can be reduced to the
empty graph by iteratively removing vertices of degree
. Equivalently,
if
is the smallest integer such
that the
-core of
is empty.
IMPLEMENTATION
This implementation is based on the NetworkX implementation of the algorithm described in [BZ].
INPUT
k (integer)
- If k = None (default), returns the core number for each vertex.
- If k is an integer, returns a pair (ordering, core), where core is the list of vertices in the
-core of self, and ordering is an elimination order for the other vertices such that each vertex is of degree strictly less than
when it is to be eliminated from the graph.
with_labels (boolean)
When set to False, and k = None, the method returns a list whose
th element is the core number of the
th vertex. When set to True, the method returns a dictionary whose keys are vertices, and whose values are the corresponding core numbers.
By default, with_labels = False.
See also
REFERENCE:
[WPkcore] | K-core. Wikipedia. (2007). [Online] Available: http://en.wikipedia.org/wiki/K-core |
[PSW1996] | Boris Pittel, Joel Spencer and Nicholas Wormald. Sudden Emergence of a Giant k-Core in a Random Graph. (1996). J. Combinatorial Theory. Ser B 67. pages 111-151. [Online] Available: http://cs.nyu.edu/cs/faculty/spencer/papers/k-core.pdf |
[BZ] | Vladimir Batagelj and Matjaz Zaversnik. An ![]() |
EXAMPLES:
sage: (graphs.FruchtGraph()).cores()
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
sage: (graphs.FruchtGraph()).cores(with_labels=True)
{0: 3, 1: 3, 2: 3, 3: 3, 4: 3, 5: 3, 6: 3, 7: 3, 8: 3, 9: 3, 10: 3, 11: 3}
sage: a=random_matrix(ZZ,20,x=2,sparse=True, density=.1)
sage: b=Graph(20)
sage: b.add_edges(a.nonzero_positions())
sage: cores=b.cores(with_labels=True); cores
{0: 3, 1: 3, 2: 3, 3: 3, 4: 2, 5: 2, 6: 3, 7: 1, 8: 3, 9: 3, 10: 3, 11: 3, 12: 3, 13: 3, 14: 2, 15: 3, 16: 3, 17: 3, 18: 3, 19: 3}
sage: [v for v,c in cores.items() if c>=2] # the vertices in the 2-core
[0, 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
Checking the 2-core of a random lobster is indeed the empty set:
sage: g = graphs.RandomLobster(20,.5,.5)
sage: ordering, core = g.cores(2)
sage: len(core) == 0
True
Returns a degree-constrained subgraph.
Given a graph and two functions
such that
, a degree-constrained subgraph in
is
a subgraph
such that for any vertex
,
.
INPUT:
OUTPUT:
Note
EXAMPLES:
Is there a perfect matching in an even cycle?
sage: g = graphs.CycleGraph(6)
sage: bounds = lambda x: [1,1]
sage: m = g.degree_constrained_subgraph(bounds=bounds)
sage: m.size()
3
Computes the fractional chromatic index of self
The fractional chromatic index is a relaxed version of edge-coloring. An
edge coloring of a graph being actually a covering of its edges into the
smallest possible number of matchings, the fractional chromatic index of
a graph is the smallest real value
such that there
exists a list of matchings
of
and coefficients
with the property that each edge is covered by
the matchings in the following relaxed way
For more information, see the Wikipedia article on fractional coloring.
ALGORITHM:
The fractional chromatic index is computed through Linear Programming through its dual. The LP solved by sage is actually:
INPUT:
Note
This implementation can be improved by computing matchings through a LP formulation, and not using the Python implementation of Edmonds’ algorithm (which requires to copy the graph, etc). It may be more efficient to write the matching problem as a LP, as we would then just have to update the weights on the edges between each call to solve (and so avoiding the generation of all the constraints).
EXAMPLE:
The fractional chromatic index of a is
:
sage: g = graphs.CycleGraph(5)
sage: g.fractional_chromatic_index()
2.5
Returns a Gomory-Hu tree of self.
Given a tree with labeled edges representing capacities, it is very
easy to determine the maximal flow between any pair of vertices :
it is the minimal label on the edges of the unique path between them.
Given a graph , a Gomory-Hu tree
of
is a tree
with the same set of vertices, and such that the maximal flow
between any two vertices is the same in
as in
. See the
Wikipedia article on Gomory-Hu tree.
Note that, in general, a graph admits more than one Gomory-Hu tree.
INPUT:
method – There are currently two different implementations of this method :
- If method = "FF" (default), a Python implementation of the Ford-Fulkerson algorithm is used.
- If method = "LP", the flow problems are solved using Linear Programming.
OUTPUT:
A graph with labeled edges
EXAMPLE:
Taking the Petersen graph:
sage: g = graphs.PetersenGraph()
sage: t = g.gomory_hu_tree()
Obviously, this graph is a tree:
sage: t.is_tree()
True
Note that if the original graph is not connected, then the Gomory-Hu tree is in fact a forest:
sage: (2*g).gomory_hu_tree().is_forest()
True
sage: (2*g).gomory_hu_tree().is_connected()
False
On the other hand, such a tree has lost nothing of the initial graph connectedness:
sage: all([ t.flow(u,v) == g.flow(u,v) for u,v in Subsets( g.vertices(), 2 ) ])
True
Just to make sure, we can check that the same is true for two vertices in a random graph:
sage: g = graphs.RandomGNP(20,.3)
sage: t = g.gomory_hu_tree()
sage: g.flow(0,1) == t.flow(0,1)
True
And also the min cut:
sage: g.edge_connectivity() == min(t.edge_labels())
True
Returns the graph6 representation of the graph as an ASCII string. Only valid for simple (no loops, multiple edges) graphs on 0 to 262143 vertices.
EXAMPLES:
sage: G = graphs.KrackhardtKiteGraph()
sage: G.graph6_string()
'IvUqwK@?G'
Checks whether there is a homomorphism between two graphs.
A homomorphism from a graph to a graph
is a function
such that for any edge
the pair
is an edge of
.
Saying that a graph can be -colored is equivalent to saying that it
has a homomorphism to
, the complete graph on
elements.
For more information, see the Wikipedia article on graph homomorphisms.
INPUT:
Note
One can compute the core of a graph (with respect to homomorphism) with this method
sage: g = graphs.CycleGraph(10)
sage: mapping = g.has_homomorphism_to(g, core = True)
sage: print "The size of the core is",len(set(mapping.values()))
The size of the core is 2
OUTPUT:
This method returns False when the homomorphism does not exist, and
returns the homomorphism otherwise as a dictionnary associating a vertex
of to a vertex of
.
EXAMPLE:
Is Petersen’s graph 3-colorable:
sage: P = graphs.PetersenGraph()
sage: P.has_homomorphism_to(graphs.CompleteGraph(3)) is not False
True
An odd cycle admits a homomorphism to a smaller odd cycle, but not to an even cycle:
sage: g = graphs.CycleGraph(9)
sage: g.has_homomorphism_to(graphs.CycleGraph(5)) is not False
True
sage: g.has_homomorphism_to(graphs.CycleGraph(7)) is not False
True
sage: g.has_homomorphism_to(graphs.CycleGraph(4)) is not False
False
Returns a maximum independent set.
An independent set of a graph is a set of pairwise non-adjacent vertices. A maximum independent set is an independent set of maximum cardinality. It induces an empty subgraph.
Equivalently, an independent set is defined as the complement of a vertex cover.
INPUT:
algorithm – the algorithm to be used
If algorithm = "Cliquer" (default), the problem is solved using Cliquer [NisOst2003].
(see the Cliquer modules)
If algorithm = "MILP", the problem is solved through a Mixed Integer Linear Program.
(see MixedIntegerLinearProgram)
value_only – boolean (default: False). If set to True, only the size of a maximum independent set is returned. Otherwise, a maximum independent set is returned as a list of vertices.
reduction_rules – (default: True) Specify if the reductions rules from kernelization must be applied as pre-processing or not. See [ACFLSS04] for more details. Note that depending on the instance, it might be faster to disable reduction rules.
solver – (default: None) Specify a Linear Program (LP) solver to be used. If set to None, the default one is used. For more information on LP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbosity – non-negative integer (default: 0). Set the level
of verbosity you want from the linear program solver. Since the
problem of computing an independent set is -complete, its solving
may take some time depending on the graph. A value of 0 means that
there will be no message printed by the solver. This option is only
useful if algorithm="MILP".
Note
While Cliquer is usually (and by far) the most efficient of the two implementations, the Mixed Integer Linear Program formulation sometimes proves faster on very “symmetrical” graphs.
EXAMPLES:
Using Cliquer:
sage: C = graphs.PetersenGraph()
sage: C.independent_set()
[0, 3, 6, 7]
As a linear program:
sage: C = graphs.PetersenGraph()
sage: len(C.independent_set(algorithm = "MILP"))
4
Returns an independent set of representatives.
Given a graph and and a family
of
subsets of g.vertices(), an Independent Set of Reprersentatives
(ISR) is an assignation of a vertex
to each set
such that
if
(they are represdentatives) and the
set
is an independent set in
.
It generalizes, for example, graph coloring and graph list coloring.
(See [AhaBerZiv07] for more information.)
INPUT:
OUTPUT:
EXAMPLES:
For a bipartite graph missing one edge, the solution is as expected:
sage: g = graphs.CompleteBipartiteGraph(3,3)
sage: g.delete_edge(1,4)
sage: g.independent_set_of_representatives([[0,1,2],[3,4,5]])
[1, 4]
The Petersen Graph is 3-colorable, which can be expressed as an independent set of representatives problem : take 3 disjoint copies of the Petersen Graph, each one representing one color. Then take as a partition of the set of vertices the family defined by the three copies of each vertex. The ISR of such a family defines a 3-coloring:
sage: g = 3 * graphs.PetersenGraph()
sage: n = g.order()/3
sage: f = [[i,i+n,i+2*n] for i in xrange(n)]
sage: isr = g.independent_set_of_representatives(f)
sage: c = [floor(i/n) for i in isr]
sage: color_classes = [[],[],[]]
sage: for v,i in enumerate(c):
... color_classes[i].append(v)
sage: for classs in color_classes:
... g.subgraph(classs).size() == 0
True
True
True
REFERENCE:
[AhaBerZiv07] | R. Aharoni and E. Berger and R. Ziv Independent systems of representatives in weighted graphs Combinatorica vol 27, num 3, p253–267 2007 |
Returns true if self is an arc-transitive graph
A graph is arc-transitive if its automorphism group acts transitively on its pairs of adjacent vertices.
Equivalently, if there exists for any pair of edges an
automorphism
of
such that
and
, as well as another automorphism
of
such
that
and
See the wikipedia article on arc-transitive graphs for more information.
EXAMPLES:
sage: P = graphs.PetersenGraph()
sage: P.is_arc_transitive()
True
sage: G = graphs.GrayGraph()
sage: G.is_arc_transitive()
False
Returns True if graph is bipartite, False if not.
Traverse the graph G with breadth-first-search and color nodes.
INPUT:
EXAMPLES:
sage: graphs.CycleGraph(4).is_bipartite()
True
sage: graphs.CycleGraph(5).is_bipartite()
False
A random graph is very rarely bipartite:
sage: g = graphs.PetersenGraph()
sage: g.is_bipartite()
False
sage: false, oddcycle = g.is_bipartite(certificate = True)
sage: len(oddcycle) % 2
1
Tests whether the graph is a cartesian product.
INPUT:
certificate (boolean) – if certificate = False (default) the method only returns True or False answers. If certificate = True, the True answers are replaced by the list of the factors of the graph.
relabeling (boolean) – if relabeling = True (implies
certificate = True), the method also returns a dictionary associating
to each vertex its natural coordinates as a vertex of a product graph. If
is not a cartesian product, None is returned instead.
This is set to False by default.
See also
Note
This algorithm may run faster whenever the graph’s vertices are integers (see relabel()). Give it a try if it is too slow !
EXAMPLE:
The Petersen graph is prime:
sage: from sage.graphs.graph_decompositions.graph_products import is_cartesian_product
sage: g = graphs.PetersenGraph()
sage: is_cartesian_product(g)
False
A 2d grid is the product of paths:
sage: g = graphs.Grid2dGraph(5,5)
sage: p1, p2 = is_cartesian_product(g, certificate = True)
sage: p1.is_isomorphic(graphs.PathGraph(5))
True
sage: p2.is_isomorphic(graphs.PathGraph(5))
True
Forgetting the graph’s labels, then finding them back:
sage: g.relabel()
sage: g.is_cartesian_product(g, relabeling = True)
(True, {0: (0, 0), 1: (0, 1), 2: (0, 2), 3: (0, 3),
4: (0, 4), 5: (5, 0), 6: (5, 1), 7: (5, 2),
8: (5, 3), 9: (5, 4), 10: (10, 0), 11: (10, 1),
12: (10, 2), 13: (10, 3), 14: (10, 4), 15: (15, 0),
16: (15, 1), 17: (15, 2), 18: (15, 3), 19: (15, 4),
20: (20, 0), 21: (20, 1), 22: (20, 2), 23: (20, 3),
24: (20, 4)})
And of course, we find the factors back when we build a graph from a product:
sage: g = graphs.PetersenGraph().cartesian_product(graphs.CycleGraph(3))
sage: g1, g2 = is_cartesian_product(g, certificate = True)
sage: any( x.is_isomorphic(graphs.PetersenGraph()) for x in [g1,g2])
True
sage: any( x.is_isomorphic(graphs.CycleGraph(3)) for x in [g1,g2])
True
TESTS:
Wagner’s Graph (trac ticket #13599):
sage: g = graphs.WagnerGraph()
sage: g.is_cartesian_product()
False
Since graph is undirected, returns False.
EXAMPLES:
sage: Graph().is_directed()
False
Returns true if self is an edge transitive graph.
A graph is edge-transitive if its automorphism group acts transitively on its edge set.
Equivalently, if there exists for any pair of edges an
automorphism
of
such that
(note this does not
necessarily mean that
and
).
See the wikipedia article on edge-transitive graphs for more information.
EXAMPLES:
sage: P = graphs.PetersenGraph()
sage: P.is_edge_transitive()
True
sage: C = graphs.CubeGraph(3)
sage: C.is_edge_transitive()
True
sage: G = graphs.GrayGraph()
sage: G.is_edge_transitive()
True
sage: P = graphs.PathGraph(4)
sage: P.is_edge_transitive()
False
Tests whether self contains an induced even hole.
A Hole is a cycle of length at least 4 (included). It is said to be even (resp. odd) if its length is even (resp. odd).
Even-hole-free graphs always contain a bisimplicial vertex, which ensures that their chromatic number is at most twice their clique number [ABCHRS08].
INPUT:
EXAMPLE:
Is the Petersen Graph even-hole-free
sage: g = graphs.PetersenGraph()
sage: g.is_even_hole_free()
False
As any chordal graph is hole-free, interval graphs behave the same way:
sage: g = graphs.RandomInterval(20)
sage: g.is_even_hole_free()
True
It is clear, though, that a random Bipartite Graph which is not a forest has an even hole:
sage: g = graphs.RandomBipartite(10, 10, .5)
sage: g.is_even_hole_free() and not g.is_forest()
False
We can check the certificate returned is indeed an even cycle:
sage: if not g.is_forest():
... cycle = g.is_even_hole_free(certificate = True)
... if cycle.order() % 2 == 1:
... print "Error !"
... if not cycle.is_isomorphic(
... graphs.CycleGraph(cycle.order())):
... print "Error !"
...
sage: print "Everything is Fine !"
Everything is Fine !
TESTS:
Bug reported in #9925, and fixed by #9420:
sage: g = Graph(':SiBFGaCEF_@CE`DEGH`CEFGaCDGaCDEHaDEF`CEH`ABCDEF')
sage: g.is_even_hole_free()
False
sage: g.is_even_hole_free(certificate = True)
Subgraph of (): Looped multi-graph on 4 vertices
Making sure there are no other counter-examples around
sage: t = lambda x : (Graph(x).is_forest() or
... isinstance(Graph(x).is_even_hole_free(certificate = True),Graph))
sage: all( t(graphs.RandomBipartite(10,10,.5)) for i in range(100) )
True
REFERENCE:
[ABCHRS08] | L. Addario-Berry, M. Chudnovsky, F. Havet, B. Reed, P. Seymour Bisimplicial vertices in even-hole-free graphs Journal of Combinatorial Theory, Series B vol 98, n.6 pp 1119-1164, 2008 |
Returns true if self is a half-transitive graph.
A graph is is half-transitive if it is both vertex and edge transitive but not arc-transitive.
See the wikipedia article on half-transitive graphs for more information.
EXAMPLES:
The Petersen Graph is not half-transitive:
sage: P = graphs.PetersenGraph()
sage: P.is_half_transitive()
False
The smallest half-transitive graph is the Holt Graph:
sage: H = graphs.HoltGraph()
sage: H.is_half_transitive()
True
Tests wether the graph is a line graph.
INPUT:
TODO:
This methods sequentially tests each of the forbidden subgraphs, which is a very slow method. There exist much better algorithms, including those which are actually able to return a graph whose line graph is isomorphic to the given graph.
EXAMPLES:
A complete graph is always the line graph of a star:
sage: graphs.CompleteGraph(5).is_line_graph()
True
The Petersen Graph not being claw-free, it is not a line graph:
sage: graphs.PetersenGraph().is_line_graph() False
This is indeed the subgraph returned:
sage: C = graphs.PetersenGraph().is_line_graph(certificate = True)
sage: C.is_isomorphic(graphs.ClawGraph())
True
Tests whether the given graph contains an induced subgraph that is isomorphic to the complement of a cycle of length at least 5.
INPUT:
certificate – boolean (default: False)
Whether to return a certificate. When certificate = True, then the function returns
When certificate = False, the function returns just True or False accordingly.
ALGORITHM:
This algorithm tries to find a cycle in the graph of all induced
of
, where two copies
and
of
are adjacent if there exists a (not necessarily induced)
copy of
such that
and
.
This is done through a depth-first-search. For efficiency, the auxiliary graph is constructed on-the-fly and never stored in memory.
The run time of this algorithm is [NikolopoulosPalios07] ( where
is the number of edges of the graph ) .
EXAMPLES:
The Petersen Graph contains an antihole:
sage: g = graphs.PetersenGraph()
sage: g.is_long_antihole_free()
False
The complement of a cycle is an antihole:
sage: g = graphs.CycleGraph(6).complement()
sage: r,a = g.is_long_antihole_free(certificate=True)
sage: r
False
sage: a.complement().is_isomorphic( graphs.CycleGraph(6) )
True
TESTS:
Further tests:
sage: g = Graph({0:[6,7],1:[7,8],2:[8,9],3:[9,10],4:[10,11],5:[11,6],6:[0,5,7],7:[0,1,6],8:[1,2,9],9:[2,3,8],10:[3,4,11],11:[4,5,10]}).complement()
sage: r,a = g.is_long_antihole_free(certificate=True)
sage: r
False
sage: a.complement().is_isomorphic( graphs.CycleGraph(9) )
True
Tests whether g contains an induced cycle of length at least 5.
INPUT:
certificate – boolean (default: False)
Whether to return a certificate. When certificate = True, then the function returns
If certificate = False, the function returns just True or False accordingly.
ALGORITHM:
This algorithm tries to find a cycle in the graph of all induced of
, where two copies
and
of
are adjacent if there exists a
(not necessarily induced) copy of
such that
and
.
This is done through a depth-first-search. For efficiency, the auxiliary graph is constructed on-the-fly and never stored in memory.
The run time of this algorithm is [NikolopoulosPalios07] ( where
is the number of edges of the graph ) .
EXAMPLES:
The Petersen Graph contains a hole:
sage: g = graphs.PetersenGraph()
sage: g.is_long_hole_free()
False
The following graph contains a hole, which we want to display:
sage: g = graphs.FlowerSnark()
sage: r,h = g.is_long_hole_free(certificate=True)
sage: r
False
sage: Graph(h).is_isomorphic(graphs.CycleGraph(h.order()))
True
TESTS:
Another graph with vertices 2, ..., 8, 10:
sage: g = Graph({2:[3,8],3:[2,4],4:[3,8,10],5:[6,10],6:[5,7],7:[6,8],8:[2,4,7,10],10:[4,5,8]})
sage: r,hole = g.is_long_hole_free(certificate=True)
sage: r
False
sage: hole
Subgraph of (): Graph on 5 vertices
sage: hole.is_isomorphic(graphs.CycleGraph(hole.order()))
True
Tests whether self contains an induced odd hole.
A Hole is a cycle of length at least 4 (included). It is said to be even (resp. odd) if its length is even (resp. odd).
It is interesting to notice that while it is polynomial to check whether a graph has an odd hole or an odd antihole [CRST06], it is not known whether testing for one of these two cases independently is polynomial too.
INPUT:
EXAMPLE:
Is the Petersen Graph odd-hole-free
sage: g = graphs.PetersenGraph()
sage: g.is_odd_hole_free()
False
Which was to be expected, as its girth is 5
sage: g.girth()
5
We can check the certificate returned is indeed a 5-cycle:
sage: cycle = g.is_odd_hole_free(certificate = True)
sage: cycle.is_isomorphic(graphs.CycleGraph(5))
True
As any chordal graph is hole-free, no interval graph has an odd hole:
sage: g = graphs.RandomInterval(20)
sage: g.is_odd_hole_free()
True
REFERENCES:
[CRST06] | M. Chudnovsky, G. Cornuejols, X. Liu, P. Seymour, K. Vuskovic Recognizing berge graphs Combinatorica vol 25, n 2, pages 143–186 2005 |
Tests whether the graph is perfect.
A graph is said to be perfect if
hold
for any induced subgraph
(and so for
itself, too), where
represents the chromatic number
of
, and
its clique number. The Strong Perfect
Graph Theorem [SPGT] gives another characterization of
perfect graphs:
A graph is perfect if and only if it contains no odd hole
(cycle on an odd number of vertices,
) nor any odd
antihole (complement of a hole) as an induced subgraph.
INPUT:
OUTPUT:
When certificate = False, this function returns a boolean value. When certificate = True, it returns a subgraph of self isomorphic to an odd hole or an odd antihole if any, and None otherwise.
EXAMPLE:
A Bipartite Graph is always perfect
sage: g = graphs.RandomBipartite(8,4,.5)
sage: g.is_perfect()
True
Interval Graphs, which are chordal graphs, too
sage: g = graphs.RandomInterval(7)
sage: g.is_perfect()
True
The PetersenGraph, which is triangle-free and has chromatic number 3 is obviously not perfect:
sage: g = graphs.PetersenGraph()
sage: g.is_perfect()
False
We can obtain an induced 5-cycle as a certificate:
sage: g.is_perfect(certificate = True)
Subgraph of (Petersen graph): Graph on 5 vertices
TEST:
Check that trac ticket #13546 has been fixed:
sage: Graph(':FgGE@I@GxGs').is_perfect()
False
sage: g = Graph({0: [2, 3, 4, 5],
... 1: [3, 4, 5, 6],
... 2: [0, 4, 5, 6],
... 3: [0, 1, 5, 6],
... 4: [0, 1, 2, 6],
... 5: [0, 1, 2, 3],
... 6: [1, 2, 3, 4]})
sage: g.is_perfect()
False
REFERENCES:
[SPGT] | M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas. The strong perfect graph theorem Annals of Mathematics vol 164, number 1, pages 51–230 2006 |
TESTS:
sage: Graph(':Ab').is_perfect()
Traceback (most recent call last):
...
ValueError: This method is only defined for simple graphs, and yours is not one of them !
sage: g = Graph()
sage: g.allow_loops(True)
sage: g.add_edge(0,0)
sage: g.edges()
[(0, 0, None)]
sage: g.is_perfect()
Traceback (most recent call last):
...
ValueError: This method is only defined for simple graphs, and yours is not one of them !
Tests whether the current graph is prime. A graph is prime if
all its modules are trivial (i.e. empty, all of the graph or
singletons)– see .
EXAMPLE:
The Petersen Graph and the Bull Graph are both prime
sage: graphs.PetersenGraph().is_prime()
True
sage: graphs.BullGraph().is_prime()
True
Though quite obviously, the disjoint union of them is not:
sage: (graphs.PetersenGraph() + graphs.BullGraph()).is_prime()
False
Returns true if self is semi-symmetric.
A graph is semi-symmetric if it is regular, edge-transitve but not vertex-transitive.
See the wikipedia article on semi-symmetric graphs for more information.
See also
EXAMPLES:
The Petersen graph is not semi-symmetric:
sage: P = graphs.PetersenGraph()
sage: P.is_semi_symmetric()
False
The Gray graph is the smallest possible semi-symmetric graph:
sage: G = graphs.GrayGraph()
sage: G.is_semi_symmetric()
True
Another well known semi-symmetric graph is the Ljubljana graph:
sage: L = graphs.LjubljanaGraph()
sage: L.is_semi_symmetric()
True
Returns True if the graph is a Split graph, False otherwise.
A Graph is said to be a split graph if its vertices
can be partitioned into two sets
and
such that the
vertices of
induce a complete graphe, and those of
are
an independent set.
There is a simple test to check whether a graph is a split graph (see, for instance, the book “Graph Classes, a survey” [GraphClasses] page 203) :
Given the degree sequence of
, a graph
is a split graph if and only if :
where .
EXAMPLES:
Split graphs are, in particular, chordal graphs. Hence, The Petersen graph can not be split:
sage: graphs.PetersenGraph().is_split()
False
We can easily build some “random” split graph by creating a complete graph, and adding vertices only connected to some random vertices of the clique:
sage: g = graphs.CompleteGraph(10)
sage: sets = Subsets(Set(range(10)))
sage: for i in range(10, 25):
... g.add_edges([(i,k) for k in sets.random_element()])
sage: g.is_split()
True
REFERENCES:
[GraphClasses] | A. Brandstadt, VB Le and JP Spinrad Graph classes: a survey SIAM Monographs on Discrete Mathematics and Applications}, 1999 |
Tests whether self is strongly regular.
A graph is said to be strongly regular with parameters (n, k,
lambda, mu)` if and only if:
has
vertices.
is
-regular.
- Any two adjacent vertices of
have
common neighbors.
- Any two non-adjacent vertices of
have
common neighbors.
INPUT:
EXAMPLES:
Petersen’s graph is strongly regular:
sage: g = graphs.PetersenGraph()
sage: g.is_strongly_regular()
True
sage: g.is_strongly_regular(parameters = True)
(10, 3, 0, 1)
And Clebsch’s graph is too:
sage: g = graphs.ClebschGraph()
sage: g.is_strongly_regular()
True
sage: g.is_strongly_regular(parameters = True)
(16, 5, 0, 2)
But Chvatal’s graph is not:
sage: g = graphs.ChvatalGraph()
sage: g.is_strongly_regular()
False
Returns whether self is triangle-free
INPUT:
algorithm – (default: 'bitset') specifies the algorithm to use among:
- 'matrix' – tests if the trace of the adjacency matrix is positive.
- 'bitset' – encodes adjacencies into bitsets and uses fast bitset operations to test if the input graph contains a triangle. This method is generaly faster than stantard matrix multiplication.
EXAMPLE:
The Petersen Graph is triangle-free:
sage: g = graphs.PetersenGraph()
sage: g.is_triangle_free()
True
or a complete Bipartite Graph:
sage: G = graphs.CompleteBipartiteGraph(5,6)
sage: G.is_triangle_free(algorithm='matrix')
True
sage: G.is_triangle_free(algorithm='bitset')
True
a tripartite graph, though, contains many triangles:
sage: G = (3 * graphs.CompleteGraph(5)).complement()
sage: G.is_triangle_free(algorithm='matrix')
False
sage: G.is_triangle_free(algorithm='bitset')
False
TESTS:
Comparison of algorithms:
sage: for i in xrange(10): # long test
... G = graphs.RandomBarabasiAlbert(50,2)
... bm = G.is_triangle_free(algorithm='matrix')
... bb = G.is_triangle_free(algorithm='bitset')
... if bm != bb:
... print "That's not good!"
Tests whether the given graph is weakly chordal, i.e., the graph and its complement have no induced cycle of length at least 5.
INPUT:
certificate – Boolean value (default: False) whether to return a certificate. If certificate = False, return True or False according to the graph. If certificate = True, return
(False, forbidden_subgraph) when the graph contains a forbidden subgraph H, this graph is returned.
For this case, it is not known how to provide a certificate.
ALGORITHM:
This algorithm checks whether the graph g or its complement contain an induced cycle of length at least 5.
Using is_long_hole_free() and is_long_antihole_free() yields a run time
of (where
is the number of edges of the graph).
EXAMPLES:
The Petersen Graph is not weakly chordal and contains a hole:
sage: g = graphs.PetersenGraph()
sage: r,s = g.is_weakly_chordal(certificate = True)
sage: r
False
sage: l = len(s.vertices())
sage: s.is_isomorphic( graphs.CycleGraph(l) )
True
Returns a maximum weighted matching of the graph represented by the list of its edges. For more information, see the Wikipedia article on matchings.
Given a graph such that each edge
has a weight
,
a maximum matching is a subset
of the edges of
of
maximum weight such that no two edges of
are incident
with each other.
As an optimization problem, it can be expressed as:
INPUT:
ALGORITHM:
The problem is solved using Edmond’s algorithm implemented in NetworkX, or using Linear Programming depending on the value of algorithm.
EXAMPLES:
Maximum matching in a Pappus Graph:
sage: g = graphs.PappusGraph()
sage: g.matching(value_only=True)
9.0
Same test with the Linear Program formulation:
sage: g = graphs.PappusGraph()
sage: g.matching(algorithm="LP", value_only=True)
9.0
TESTS:
If algorithm is set to anything different from "Edmonds" or "LP", an exception is raised:
sage: g = graphs.PappusGraph()
sage: g.matching(algorithm="somethingdifferent")
Traceback (most recent call last):
...
ValueError: algorithm must be set to either "Edmonds" or "LP"
Computes the matching polynomial of the graph .
If denotes the number of
-matchings (matchings with
edges)
in
, then the matching polynomial is defined as [Godsil93]:
INPUT:
Note
The complement option uses matching polynomials of complete graphs, which are cached. So if you are crazy enough to try computing the matching polynomial on a graph with millions of vertices, you might not want to use this option, since it will end up caching millions of polynomials of degree in the millions.
ALGORITHM:
The algorithm used is a recursive one, based on the following observation [Godsil93]:
If is an edge of
,
is the result of deleting the edge
, and
is the result of deleting each vertex in
, then the matching
polynomial of
is equal to that of
minus that of
.
(the algorithm actually computes the signless matching polynomial, for which the recursion is the same when one replaces the substraction by an addition. It is then converted into the matching polynomial and returned)
Depending on the value of complement, Godsil’s duality theorem
[Godsil93] can also be used to compute :
Where is the complement of
, and
the complete graph
on
vertices.
EXAMPLES:
sage: g = graphs.PetersenGraph()
sage: g.matching_polynomial()
x^10 - 15*x^8 + 75*x^6 - 145*x^4 + 90*x^2 - 6
sage: g.matching_polynomial(complement=False)
x^10 - 15*x^8 + 75*x^6 - 145*x^4 + 90*x^2 - 6
sage: g.matching_polynomial(name='tom')
tom^10 - 15*tom^8 + 75*tom^6 - 145*tom^4 + 90*tom^2 - 6
sage: g = Graph()
sage: L = [graphs.RandomGNP(8, .3) for i in [1..5]]
sage: prod([h.matching_polynomial() for h in L]) == sum(L, g).matching_polynomial() # long time (up to 10s on sage.math, 2011)
True
sage: from sage.graphs.matchpoly import matching_polynomial
sage: for i in [1..12]: # long time (10s on sage.math, 2011)
... for t in graphs.trees(i):
... c = t.complement()
... assert matching_polynomial(t) == t.characteristic_polynomial()
... assert matching_polynomial(c, complement=False) == matching_polynomial(c)
sage: matching_polynomial(graphs.CompleteGraph(0))
1
sage: matching_polynomial(graphs.CompleteGraph(1))
x
sage: matching_polynomial(graphs.CompleteGraph(2))
x^2 - 1
sage: matching_polynomial(graphs.CompleteGraph(3))
x^3 - 3*x
sage: matching_polynomial(graphs.CompleteGraph(4))
x^4 - 6*x^2 + 3
sage: matching_polynomial(graphs.CompleteGraph(5))
x^5 - 10*x^3 + 15*x
sage: matching_polynomial(graphs.CompleteGraph(6))
x^6 - 15*x^4 + 45*x^2 - 15
sage: matching_polynomial(graphs.CompleteGraph(7))
x^7 - 21*x^5 + 105*x^3 - 105*x
sage: matching_polynomial(graphs.CompleteGraph(8))
x^8 - 28*x^6 + 210*x^4 - 420*x^2 + 105
sage: matching_polynomial(graphs.CompleteGraph(9))
x^9 - 36*x^7 + 378*x^5 - 1260*x^3 + 945*x
sage: matching_polynomial(graphs.CompleteGraph(10))
x^10 - 45*x^8 + 630*x^6 - 3150*x^4 + 4725*x^2 - 945
sage: matching_polynomial(graphs.CompleteGraph(11))
x^11 - 55*x^9 + 990*x^7 - 6930*x^5 + 17325*x^3 - 10395*x
sage: matching_polynomial(graphs.CompleteGraph(12))
x^12 - 66*x^10 + 1485*x^8 - 13860*x^6 + 51975*x^4 - 62370*x^2 + 10395
sage: matching_polynomial(graphs.CompleteGraph(13))
x^13 - 78*x^11 + 2145*x^9 - 25740*x^7 + 135135*x^5 - 270270*x^3 + 135135*x
sage: 13*11*9*7*5*3
135135
sage: binomial(13,5)*7*5*3
135135
sage: 11*9*7*5*3
10395
sage: binomial(9,3)*5*3
1260
sage: 9*7*5*3
945
sage: G = Graph({0:[1,2], 1:[2]})
sage: matching_polynomial(G)
x^3 - 3*x
sage: G = Graph({0:[1,2]})
sage: matching_polynomial(G)
x^3 - 2*x
sage: G = Graph({0:[1], 2:[]})
sage: matching_polynomial(G)
x^3 - x
sage: G = Graph({0:[], 1:[], 2:[]})
sage: matching_polynomial(G)
x^3
sage: matching_polynomial(graphs.CompleteGraph(0), complement=False)
1
sage: matching_polynomial(graphs.CompleteGraph(1), complement=False)
x
sage: matching_polynomial(graphs.CompleteGraph(2), complement=False)
x^2 - 1
sage: matching_polynomial(graphs.CompleteGraph(3), complement=False)
x^3 - 3*x
sage: matching_polynomial(graphs.CompleteGraph(4), complement=False)
x^4 - 6*x^2 + 3
sage: matching_polynomial(graphs.CompleteGraph(5), complement=False)
x^5 - 10*x^3 + 15*x
sage: matching_polynomial(graphs.CompleteGraph(6), complement=False)
x^6 - 15*x^4 + 45*x^2 - 15
sage: matching_polynomial(graphs.CompleteGraph(7), complement=False)
x^7 - 21*x^5 + 105*x^3 - 105*x
sage: matching_polynomial(graphs.CompleteGraph(8), complement=False)
x^8 - 28*x^6 + 210*x^4 - 420*x^2 + 105
sage: matching_polynomial(graphs.CompleteGraph(9), complement=False)
x^9 - 36*x^7 + 378*x^5 - 1260*x^3 + 945*x
sage: matching_polynomial(graphs.CompleteGraph(10), complement=False)
x^10 - 45*x^8 + 630*x^6 - 3150*x^4 + 4725*x^2 - 945
sage: matching_polynomial(graphs.CompleteGraph(11), complement=False)
x^11 - 55*x^9 + 990*x^7 - 6930*x^5 + 17325*x^3 - 10395*x
sage: matching_polynomial(graphs.CompleteGraph(12), complement=False)
x^12 - 66*x^10 + 1485*x^8 - 13860*x^6 + 51975*x^4 - 62370*x^2 + 10395
sage: matching_polynomial(graphs.CompleteGraph(13), complement=False)
x^13 - 78*x^11 + 2145*x^9 - 25740*x^7 + 135135*x^5 - 270270*x^3 + 135135*x
Returns the Maximum Average Degree (MAD) of the current graph.
The Maximum Average Degree (MAD) of a graph is defined as
the average degree of its densest subgraph. More formally,
Mad(G) = \max_{H\subseteq G} Ad(H), where denotes
the average degree of
.
This can be computed in polynomial time.
INPUT:
value_only (boolean) – True by default
- If value_only=True, only the numerical value of the
is returned.
- Else, the subgraph of
realizing the
is returned.
solver – (default: None) Specify a Linear Program (LP) solver to be used. If set to None, the default one is used. For more information on LP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.
verbose – integer (default: 0). Sets the level of verbosity. Set to 0 by default, which means quiet.
EXAMPLES:
In any graph, the is always larger than the average
degree:
sage: g = graphs.RandomGNP(20,.3)
sage: mad_g = g.maximum_average_degree()
sage: g.average_degree() <= mad_g
True
Unlike the average degree, the of the disjoint
union of two graphs is the maximum of the
of each
graphs:
sage: h = graphs.RandomGNP(20,.3)
sage: mad_h = h.maximum_average_degree()
sage: (g+h).maximum_average_degree() == max(mad_g, mad_h)
True
The subgraph of a regular graph realizing the maximum average degree is always the whole graph
sage: g = graphs.CompleteGraph(5)
sage: mad_g = g.maximum_average_degree(value_only=False)
sage: g.is_isomorphic(mad_g)
True
This also works for complete bipartite graphs
sage: g = graphs.CompleteBipartiteGraph(3,4)
sage: mad_g = g.maximum_average_degree(value_only=False)
sage: g.is_isomorphic(mad_g)
True
Returns an orientation of self with the smallest possible maximum outdegree.
Given a Graph , is is polynomial to compute an orientation
of the edges of
such that the maximum out-degree in
is minimized. This problem, though, is NP-complete in the
weighted case [AMOZ06].
INPUT:
EXAMPLE:
Given a complete bipartite graph , the maximum out-degree
of an optimal orientation is
:
sage: g = graphs.CompleteBipartiteGraph(3,4)
sage: o = g.minimum_outdegree_orientation()
sage: max(o.out_degree()) == ceil((4*3)/(3+4))
True
REFERENCES:
[AMOZ06] | Asahiro, Y. and Miyano, E. and Ono, H. and Zenmyo, K. Graph orientation algorithms to minimize the maximum outdegree Proceedings of the 12th Computing: The Australasian Theory Symposium Volume 51, page 20 Australian Computer Society, Inc. 2006 |
Returns the vertices of a minor isomorphic to in the current graph.
We say that a graph has a
-minor (or that it has
a graph isomorphic to
as a minor), if for all
,
there exist disjoint sets
such that
once the vertices of each
have been merged to create
a new graph
, this new graph contains
as a subgraph.
For more information, see the Wikipedia article on graph minor.
INPUT:
OUTPUT:
A dictionary associating to each vertex of the set of vertices
in the current graph representing it.
ALGORITHM:
Mixed Integer Linear Programming
COMPLEXITY:
Theoretically, when is fixed, testing for the existence of
a
-minor is polynomial. The known algorithms are highly
exponential in
, though.
Note
This function can be expected to be very slow, especially where the minor does not exist.
EXAMPLES:
Trying to find a minor isomorphic to in
the
grid:
sage: g = graphs.GridGraph([4,4])
sage: h = graphs.CompleteGraph(4)
sage: L = g.minor(h)
sage: gg = g.subgraph(flatten(L.values(), max_level = 1))
sage: _ = [gg.merge_vertices(l) for l in L.values() if len(l)>1]
sage: gg.is_isomorphic(h)
True
We can also try to prove this way that the Petersen graph
is not planar, as it has a minor:
sage: g = graphs.PetersenGraph()
sage: K5_minor = g.minor(graphs.CompleteGraph(5)) # long time
And even a minor:
sage: K33_minor = g.minor(graphs.CompleteBipartiteGraph(3,3)) # long time
(It is much faster to use the linear-time test of planarity in this situation, though.)
As there is no cycle in a tree, looking for a minor is useless.
This function will raise an exception in this case:
sage: g = graphs.RandomGNP(20,.5)
sage: g = g.subgraph(edges = g.min_spanning_tree())
sage: g.is_tree()
True
sage: L = g.minor(graphs.CompleteGraph(3))
Traceback (most recent call last):
...
ValueError: This graph has no minor isomorphic to H !
Returns the modular decomposition of the current graph.
Crash course on modular decomposition:
A module of a graph
is a proper subset of its vertices
such that for all
the relation
holds, where
denotes
the adjacency relation in
. Equivalently,
is a module if all its vertices have the same adjacency
relations with each vertex outside of the module (vertex by
vertex).
Hence, for a set like a module, it is very easy to encode the
information of the adjacencies between the vertices inside and
outside the module – we can actually add a new vertex
to our graph representing our module
, and let
be
adjacent to
if and only if some
(and
hence all the vertices contained in the module) is adjacent to
. We can now independently (and recursively) study the
structure of our module
and the new graph
,
without any loss of information.
Here are two very simple modules :
- A connected component
(or the union of some –but not all– of them) of a disconnected graph
, for instance, is a module, as no vertex of
has a neighbor outside of it.
- An anticomponent
(or the union of some –but not all– of them) of an non-anticonnected graph
, for the same reason (it is just the complement of the previous graph !).
These modules being of special interest, the disjoint union of graphs is called a Parallel composition, and the complement of a disjoint union is called a Parallel composition. A graph whose only modules are singletons is called Prime.
For more information on modular decomposition, in particular for an explanation of the terms “Parallel,” “Prime” and “Serie,” see the Wikipedia article on modular decomposition.
You may also be interested in the survey from Michel Habib and Christophe Paul entitled “A survey on Algorithmic aspects of modular decomposition” [HabPau10].
OUTPUT:
A pair of two values (recursively encoding the decomposition) :
The type of the current module :
- "Parallel"
- "Prime"
- "Serie"
The list of submodules (as list of pairs (type, list), recursively...) or the vertex’s name if the module is a singleton.
EXAMPLES:
The Bull Graph is prime:
sage: graphs.BullGraph().modular_decomposition()
('Prime', [3, 4, 0, 1, 2])
The Petersen Graph too:
sage: graphs.PetersenGraph().modular_decomposition()
('Prime', [2, 6, 3, 9, 7, 8, 0, 1, 5, 4])
This a clique on 5 vertices with 2 pendant edges, though, has a more interesting decomposition
sage: g = graphs.CompleteGraph(5)
sage: g.add_edge(0,5)
sage: g.add_edge(0,6)
sage: g.modular_decomposition()
('Serie', [0, ('Parallel', [5, ('Serie', [1, 4, 3, 2]), 6])])
ALGORITHM:
This function uses a C implementation of a 2-step algorithm implemented by Fabien de Montgolfier [FMDec] :
- Computation of a factorizing permutation [HabibViennot1999].
- Computation of the tree itself [CapHabMont02].
See also
REFERENCE:
[FMDec] | Fabien de Montgolfier http://www.liafa.jussieu.fr/~fm/algos/index.html |
[HabibViennot1999] | Michel Habib, Christiphe Paul, Laurent Viennot Partition refinement techniques: An interesting algorithmic tool kit International Journal of Foundations of Computer Science vol. 10 n2 pp.147–170, 1999 |
[CapHabMont02] | C. Capelle, M. Habib et F. de Montgolfier Graph decomposition and Factorising Permutations Discrete Mathematics and Theoretical Computer Sciences, vol 5 no. 1 , 2002. |
[HabPau10] | Michel Habib and Christophe Paul A survey of the algorithmic aspects of modular decomposition Computer Science Review vol 4, number 1, pages 41–59, 2010 http://www.lirmm.fr/~paul/md-survey.pdf |
Returns the odd girth of self.
The odd girth of a graph is defined as the smallest cycle of odd length.
OUTPUT:
The odd girth of self.
EXAMPLES:
The McGee graph has girth 7 and therefore its odd girth is 7 as well.
sage: G = graphs.McGeeGraph()
sage: G.odd_girth()
7
Any complete graph on more than 2 vertices contains a triangle and has thus odd girth 3.
sage: G = graphs.CompleteGraph(10)
sage: G.odd_girth()
3
Every bipartite graph has no odd cycles and consequently odd girth of infinity.
sage: G = graphs.CompleteBipartiteGraph(100,100)
sage: G.odd_girth()
+Infinity
See also
REFERENCES:
The property relating the odd girth to the coefficients of the characteristic polynomial is an old result from algebraic graph theory see
[Har62] | Harary, F (1962). The determinant of the adjacency matrix of a graph, SIAM Review 4, 202-210 |
[Biggs93] | Biggs, N. L. Algebraic Graph Theory, 2nd ed. Cambridge, England: Cambridge University Press, pp. 45, 1993. |
TESTS:
sage: graphs.CycleGraph(5).odd_girth()
5
sage: graphs.CycleGraph(11).odd_girth()
11
Computes an optimal rank-decomposition of the given graph.
This function is available as a method of the Graph class. See rank_decomposition.
INPUT:
OUTPUT:
A pair (rankwidth, decomposition_tree), where rankwidth is a numerical value and decomposition_tree is a ternary tree describing the decomposition (cf. the module’s documentation).
EXAMPLE:
sage: from sage.graphs.graph_decompositions.rankwidth import rank_decomposition
sage: g = graphs.PetersenGraph()
sage: rank_decomposition(g)
(3, Graph on 19 vertices)
On more than 32 vertices:
sage: g = graphs.RandomGNP(40, .5)
sage: rank_decomposition(g)
Traceback (most recent call last):
...
RuntimeError: the rank decomposition cannot be computed on graphs of >= 32 vertices
The empty graph:
sage: g = Graph()
sage: rank_decomposition(g)
(0, Graph on 0 vertices)
Returns the sparse6 representation of the graph as an ASCII string. Only valid for undirected graphs on 0 to 262143 vertices, but loops and multiple edges are permitted.
EXAMPLES:
sage: G = graphs.BullGraph()
sage: G.sparse6_string()
':Da@en'
sage: G = Graph()
sage: G.sparse6_string()
':?'
sage: G = Graph(loops=True, multiedges=True,sparse=True)
sage: Graph(':?',sparse=True) == G
True
Returns a strongly connected orientation of the current graph. See also the Wikipedia article Strongly_connected_component.
An orientation of an undirected graph is a digraph obtained by giving an unique direction to each of its edges. An orientation is said to be strong if there is a directed path between each pair of vertices.
If the graph is 2-edge-connected, a strongly connected orientation can be found in linear time. If the given graph is not 2-connected, the orientation returned will ensure that each 2-connected component has a strongly connected orientation.
OUTPUT:
A digraph representing an orientation of the current graph.
Note
EXAMPLE:
For a 2-regular graph, a strong orientation gives to each vertex an out-degree equal to 1:
sage: g = graphs.CycleGraph(5)
sage: g.strong_orientation().out_degree()
[1, 1, 1, 1, 1]
The Petersen Graph is 2-edge connected. It then has a strongly connected orientation:
sage: g = graphs.PetersenGraph()
sage: o = g.strong_orientation()
sage: len(o.strongly_connected_components())
1
The same goes for the CubeGraph in any dimension
sage: for i in range(2,5):
... g = graphs.CubeGraph(i)
... o = g.strong_orientation()
... len(o.strongly_connected_components())
1
1
1
Returns a directed version of the graph. A single edge becomes two edges, one in each direction.
EXAMPLES:
sage: graphs.PetersenGraph().to_directed()
Petersen graph: Digraph on 10 vertices
Since the graph is already undirected, simply returns a copy of itself.
EXAMPLES:
sage: graphs.PetersenGraph().to_undirected()
Petersen graph: Graph on 10 vertices
Returns a topological -minor from self if one exists.
We say that a graph has a topological
-minor (or that
it has a graph isomorphic to
as a topological minor), if
contains a subdivision of a graph isomorphic to
(=
obtained from
through arbitrary subdivision of its edges)
as a subgraph.
For more information, see the .
INPUT:
OUTPUT:
The topological -minor found is returned as a subgraph
of self, such that the vertex
of
that represents a
vertex
has h as a label (see
get_vertex
and
set_vertex),
and such that every edge of
has as a label the edge of
it (partially) represents.
If no topological minor is found, this method returns False.
ALGORITHM:
Mixed Integer Linear Programming.
COMPLEXITY:
Theoretically, when is fixed, testing for the existence of
a topological
-minor is polynomial. The known algorithms
are highly exponential in
, though.
Note
This function can be expected to be very slow, especially where the topological minor does not exist.
(CPLEX seems to be much more efficient than GLPK on this kind of problem)
EXAMPLES:
Petersen’s graph has a topological -minor:
sage: g = graphs.PetersenGraph()
sage: g.topological_minor(graphs.CompleteGraph(4))
Subgraph of (Petersen graph): Graph on ...
And a topological -minor:
sage: g.topological_minor(graphs.CompleteBipartiteGraph(3,3))
Subgraph of (Petersen graph): Graph on ...
And of course, a tree has no topological -minor:
sage: g = graphs.RandomGNP(15,.3)
sage: g = g.subgraph(edges = g.min_spanning_tree())
sage: g.topological_minor(graphs.CycleGraph(3))
False
Returns a decomposition of the graph into 2-factors.
Petersen’s 2-factor decomposition theorem asserts that any
-regular graph
can be decomposed into 2-factors.
Equivalently, it means that the edges of any
-regular
graphs can be partitionned in
sets
such
that for all
, the set
is a disjoint union of cycles
( a 2-regular graph ).
As any graph of maximal degree can be completed into
a regular graph of degree
, this
result also means that the edges of any graph of degree
can be partitionned in
sets
such that for all
, the set
is a
graph of maximal degree
( a disjoint union of paths
and cycles ).
EXAMPLE:
The Complete Graph on vertices is a
-regular graph, so it can
be edge-partitionned into
-regular graphs:
sage: g = graphs.CompleteGraph(7)
sage: classes = g.two_factor_petersen()
sage: for c in classes:
... gg = Graph()
... gg.add_edges(c)
... print max(gg.degree())<=2
True
True
True
sage: Set(set(classes[0]) | set(classes[1]) | set(classes[2])).cardinality() == g.size()
True
sage: g = graphs.CirculantGraph(24, [7, 11])
sage: cl = g.two_factor_petersen()
sage: g.plot(edge_colors={'black':cl[0], 'red':cl[1]})
Returns a minimum vertex cover of self represented by a set of vertices.
A minimum vertex cover of a graph is a set of vertices such that
each edge is incident to at least one element of
, and such that
is of minimum cardinality. For more information, see the
Wikipedia article on vertex cover.
Equivalently, a vertex cover is defined as the complement of an independent set.
As an optimization problem, it can be expressed as follows:
INPUT:
EXAMPLES:
On the Pappus graph:
sage: g = graphs.PappusGraph()
sage: g.vertex_cover(value_only=True)
9
TESTS:
The two algorithms should return the same result:
sage: g = graphs.RandomGNP(10,.5)
sage: vc1 = g.vertex_cover(algorithm="MILP")
sage: vc2 = g.vertex_cover(algorithm="Cliquer")
sage: len(vc1) == len(vc2)
True
The cardinality of the vertex cover is unchanged when reduction rules are used. First for trees:
sage: for i in range(20):
... g = graphs.RandomTree(20)
... vc1_set = g.vertex_cover()
... vc1 = len(vc1_set)
... vc2 = g.vertex_cover(value_only = True, reduction_rules = False)
... if vc1 != vc2:
... print "Error :", vc1, vc2
... print "With reduction rules :", vc1
... print "Without reduction rules :", vc2
... break
... g.delete_vertices(vc1_set)
... if g.size() != 0:
... print "This thing is not a vertex cover !"
Then for random GNP graphs:
sage: for i in range(20):
... g = graphs.RandomGNP(50,4/50)
... vc1_set = g.vertex_cover()
... vc1 = len(vc1_set)
... vc2 = g.vertex_cover(value_only = True, reduction_rules = False)
... if vc1 != vc2:
... print "Error :", vc1, vc2
... print "With reduction rules :", vc1
... print "Without reduction rules :", vc2
... break
... g.delete_vertices(vc1_set)
... if g.size() != 0:
... print "This thing is not a vertex cover !"
Given a wrong algorithm:
sage: graphs.PetersenGraph().vertex_cover(algorithm = "guess")
Traceback (most recent call last):
...
ValueError: The algorithm must be either "Cliquer" or "MILP".
REFERENCE:
[ACFLSS04] | (1, 2) F. N. Abu-Khzam, R. L. Collins, M. R. Fellows, M. A. Langston, W. H. Suters, and C. T. Symons: Kernelization Algorithm for the Vertex Cover Problem: Theory and Experiments. SIAM ALENEX/ANALCO 2004: 62-69. |
Writes a plot of the graph to filename in eps format.
INPUT:
- filename – a string
- **options – same layout options as layout()
EXAMPLES:
sage: P = graphs.PetersenGraph()
sage: P.write_to_eps(tmp_filename(ext='.eps'))
It is relatively simple to include this file in a LaTeX document. \usepackagegraphics must appear in the preamble, and \includegraphics{filename.eps} will include the file. To compile the document to pdf with pdflatex the file needs first to be converted to pdf, for example with ps2pdf filename.eps filename.pdf.
This function has been deprecated.
Compare edge x to edge y, return -1 if x y, 1 if x y, else 0.
TEST:
sage: G = graphs.PetersenGraph()
sage: E = G.edges()
sage: from sage.graphs.graph import compare_edges
sage: compare_edges(E[0], E[2])
doctest:...: DeprecationWarning: compare_edges(x,y) is deprecated. Use statement 'cmp(x[1],y[1]) or cmp(x[0],y[0])' instead.
See http://trac.sagemath.org/13192 for details.
-1