# Undirected graphs#

This module implements functions and operations involving undirected graphs.

Algorithmically hard stuff

 convexity_properties() Return a ConvexityProperties object corresponding to self. has_homomorphism_to() Checks whether there is a homomorphism between two graphs. independent_set() Return a maximum independent set. independent_set_of_representatives() Return an independent set of representatives. is_perfect() Tests whether the graph is perfect. matching_polynomial() Computes the matching polynomial of the graph $$G$$. minor() Return the vertices of a minor isomorphic to $$H$$ in the current graph. pathwidth() Compute the pathwidth of self (and provides a decomposition) rank_decomposition() Compute an optimal rank-decomposition of the given graph. topological_minor() Return a topological $$H$$-minor from self if one exists. treelength() Compute the treelength of $$G$$ (and provide a decomposition). treewidth() Compute the treewidth of $$g$$ (and provide a decomposition). tutte_polynomial() Return the Tutte polynomial of the graph $$G$$. vertex_cover() Return a minimum vertex cover of self represented by a set of vertices.

Basic methods

 bipartite_color() Return a dictionary with vertices as the keys and the color class as the values. bipartite_double() Return the (extended) bipartite double of this graph. bipartite_sets() Return $$(X,Y)$$ where $$X$$ and $$Y$$ are the nodes in each bipartite set of graph $$G$$. graph6_string() Return the graph6 representation of the graph as an ASCII string. is_directed() Since graph is undirected, returns False. join() Return the join of self and other. sparse6_string() Return the sparse6 representation of the graph as an ASCII string. to_directed() Return a directed version of the graph. to_undirected() Since the graph is already undirected, simply returns a copy of itself. write_to_eps() Write a plot of the graph to filename in eps format.

Clique-related methods

 all_cliques() Iterator over the cliques in graph. atoms_and_clique_separators() Return the atoms of the decomposition of $$G$$ by clique minimal separators. clique_complex() Return the clique complex of self. clique_maximum() Return the vertex set of a maximal order complete subgraph. clique_number() Return the order of the largest clique of the graph clique_polynomial() Return the clique polynomial of self. cliques_containing_vertex() Return the cliques containing each vertex, represented as a dictionary of lists of lists, keyed by vertex. cliques_get_clique_bipartite() Return the vertex-clique bipartite graph of self. cliques_get_max_clique_graph() Return the clique graph. cliques_maximal() Return the list of all maximal cliques. cliques_maximum() Return the vertex sets of ALL the maximum complete subgraphs. cliques_number_of() Return a dictionary of the number of maximal cliques containing each vertex, keyed by vertex. cliques_vertex_clique_number() Return a dictionary of sizes of the largest maximal cliques containing each vertex, keyed by vertex. fractional_clique_number() Return the fractional clique number of the graph.

Coloring

 chromatic_index() Return the chromatic index of the graph. chromatic_number() Return the minimal number of colors needed to color the vertices of the graph. chromatic_polynomial() Compute the chromatic polynomial of the graph G. chromatic_quasisymmetric_function() Return the chromatic quasisymmetric function of self. chromatic_symmetric_function() Return the chromatic symmetric function of self. coloring() Return the first (optimal) proper vertex-coloring found. fractional_chromatic_index() Return the fractional chromatic index of the graph. fractional_chromatic_number() Return the fractional chromatic number of the graph.

Connectivity, orientations, trees

 acyclic_orientations() Return an iterator over all acyclic orientations of an undirected graph $$G$$. bounded_outdegree_orientation() Computes an orientation of self such that every vertex $$v$$ has out-degree less than $$b(v)$$ bridges() Return an iterator over the bridges (or cut edges). cleave() Return the connected subgraphs separated by the input vertex cut. degree_constrained_subgraph() Returns a degree-constrained subgraph. ear_decomposition() Return an Ear decomposition of the graph. gomory_hu_tree() Return a Gomory-Hu tree of self. is_triconnected() Check whether the graph is triconnected. minimum_outdegree_orientation() Returns an orientation of self with the smallest possible maximum outdegree. orientations() Return an iterator over orientations of self. random_orientation() Return a random orientation of a graph $$G$$. random_spanning_tree() Return a random spanning tree of the graph. spanning_trees() Return an iterator over all spanning trees of the graph $$g$$. spqr_tree() Return an SPQR-tree representing the triconnected components of the graph. strong_orientation() Returns a strongly connected orientation of the current graph. strong_orientations_iterator() Return an iterator over all strong orientations of a graph $$G$$.

Distances

 center() Return the set of vertices in the center of the graph. centrality_degree() Return the degree centrality of a vertex. diameter() Return the diameter of the graph. distance_graph() Return the graph on the same vertex set as the original graph but vertices are adjacent in the returned graph if and only if they are at specified distances in the original graph. eccentricity() Return the eccentricity of vertex (or vertices) v. hyperbolicity() Return the hyperbolicity of the graph or an approximation of this value. periphery() Return the set of vertices in the periphery of the graph. radius() Return the radius of the graph.

Domination

 is_dominating() Check whether dom is a dominating set of G. is_redundant() Check whether dom has redundant vertices. minimal_dominating_sets() Return an iterator over the minimal dominating sets of a graph. private_neighbors() Return the private neighbors of a vertex with respect to other vertices.

Expansion properties

 cheeger_constant() Return the cheeger constant of the graph. edge_isoperimetric_number() Return the edge-isoperimetric number of the graph. vertex_isoperimetric_number() Return the vertex-isoperimetric number of the graph.

Graph properties

 apex_vertices() Return the list of apex vertices. is_antipodal() Check whether this graph is antipodal. is_apex() Test if the graph is apex. is_arc_transitive() Check if self is an arc-transitive graph is_asteroidal_triple_free() Test if the input graph is asteroidal triple-free is_biconnected() Test if the graph is biconnected. is_block_graph() Return whether this graph is a block graph. is_cactus() Check whether the graph is cactus graph. is_cartesian_product() Test whether the graph is a Cartesian product. is_circumscribable() Test whether the graph is the graph of a circumscribed polyhedron. is_cograph() Check whether the graph is cograph. is_comparability() Tests whether the graph is a comparability graph is_distance_regular() Test if the graph is distance-regular is_edge_transitive() Check if self is an edge transitive graph. is_even_hole_free() Tests whether self contains an induced even hole. is_forest() Tests if the graph is a forest, i.e. a disjoint union of trees. is_half_transitive() Check if self is a half-transitive graph. is_inscribable() Test whether the graph is the graph of an inscribed polyhedron. is_line_graph() Check whether the graph $$g$$ is a line graph. is_long_antihole_free() Tests whether the given graph contains an induced subgraph that is isomorphic to the complement of a cycle of length at least 5. is_long_hole_free() Tests whether g contains an induced cycle of length at least 5. is_odd_hole_free() Tests whether self contains an induced odd hole. is_overfull() Tests whether the current graph is overfull. is_partial_cube() Test whether the given graph is a partial cube. is_path() Check whether self is a path. is_permutation() Tests whether the graph is a permutation graph. is_polyhedral() Check whether the graph is the graph of the polyhedron. is_prime() Test whether the current graph is prime. is_semi_symmetric() Check if self is semi-symmetric. is_split() Returns True if the graph is a Split graph, False otherwise. is_strongly_regular() Check whether the graph is strongly regular. is_tree() Tests if the graph is a tree is_triangle_free() Check whether self is triangle-free is_weakly_chordal() Tests whether the given graph is weakly chordal, i.e., the graph and its complement have no induced cycle of length at least 5.

Leftovers

 antipodal_graph() Return the antipodal graph of self. arboricity() Return the arboricity of the graph and an optional certificate. common_neighbors_matrix() Return a matrix of numbers of common neighbors between each pairs. cores() Return the core number for each vertex in an ordered list. effective_resistance() Return the effective resistance between nodes $$i$$ and $$j$$. effective_resistance_matrix() Return a matrix whose ($$i$$ , $$j$$) entry gives the effective resistance between vertices $$i$$ and $$j$$. folded_graph() Return the antipodal fold of this graph. geodetic_closure() Return the geodetic closure of the set of vertices $$S$$ in $$G$$. has_perfect_matching() Return whether this graph has a perfect matching. INPUT: ihara_zeta_function_inverse() Compute the inverse of the Ihara zeta function of the graph. is_factor_critical() Check whether this graph is factor-critical. kirchhoff_symanzik_polynomial() Return the Kirchhoff-Symanzik polynomial of a graph. least_effective_resistance() Return a list of pairs of nodes with the least effective resistance. lovasz_theta() Return the value of Lovász theta-function of graph. magnitude_function() Return the magnitude function of the graph as a rational function. matching() Return a maximum weighted matching of the graph represented by the list of its edges. maximum_average_degree() Return the Maximum Average Degree (MAD) of the current graph. modular_decomposition() Return the modular decomposition of the current graph. most_common_neighbors() Return vertex pairs with maximal number of common neighbors. perfect_matchings() Return an iterator over all perfect matchings of the graph. seidel_adjacency_matrix() Return the Seidel adjacency matrix of self. seidel_switching() Return the Seidel switching of self w.r.t. subset of vertices s. two_factor_petersen() Return a decomposition of the graph into 2-factors. twograph() Return the two-graph of self

Traversals

 lex_M() Return an ordering of the vertices according the LexM graph traversal. maximum_cardinality_search() Return an ordering of the vertices according a maximum cardinality search. maximum_cardinality_search_M() Return the ordering and the edges of the triangulation produced by MCS-M.

Unsorted

 bandwidth() Compute the bandwidth of an undirected graph. cutwidth() Return the cutwidth of the graph and the corresponding vertex ordering.

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.

• Nathann Cohen (2009-09)Cliquer, Connectivity, Flows 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.

• Birk Eisermann (2012-06): added recognition of weakly chordal graphs and

long-hole-free / long-antihole-free graphs

• Alexandre P. Zuge (2013-07): added join operation.

• Julian Rüth (2018-06-21): upgrade to NetworkX 2

• David Coudert (2018-10-07): cleaning

• Amanda Francis, Caitlin Lienkaemper, Kate Collins, Rajat Mittal (2019-03-10): methods for computing effective resistance

• Amanda Francis, Caitlin Lienkaemper, Kate Collins, Rajat Mittal (2019-03-19): most_common_neighbors and common_neighbors_matrix added.

• Jean-Florent Raymond (2019-04): is_redundant, is_dominating,

private_neighbors

## Graph Format#

### Supported formats#

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()                                           # needs sage.plot

>>> from sage.all import *
>>> d = {Integer(0): [Integer(1),Integer(4),Integer(5)], Integer(1): [Integer(2),Integer(6)], Integer(2): [Integer(3),Integer(7)], Integer(3): [Integer(4),Integer(8)], Integer(4): [Integer(9)], \
5: [7, 8], 6: [8,9], 7: [9]}
>>> G = Graph(d); G
Graph on 10 vertices
>>> G.plot().show()    # or G.show()                                           # needs sage.plot

• A NetworkX graph:

sage: # needs networkx
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]

>>> from sage.all import *
>>> # needs networkx
>>> import networkx
>>> K = networkx.complete_bipartite_graph(Integer(12),Integer(7))
>>> G = Graph(K)
>>> 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 = ':IAKGsaOscI]Gb~'
sage: G = Graph(s, sparse=True); G
Looped multi-graph on 10 vertices
sage: G.plot().show()    # or G.show()                                           # needs sage.plot

>>> from sage.all import *
>>> s = ':IAKGsaOscI]Gb~'
>>> G = Graph(s, sparse=True); G
Looped multi-graph on 10 vertices
>>> G.plot().show()    # or G.show()                                           # needs sage.plot


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

>>> from sage.all import *
>>> 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()                                           # needs sage.plot

>>> from sage.all import *
>>> G = Graph('Ihe\\n@GUA')
>>> G.plot().show()    # or G.show()                                           # needs sage.plot

• adjacency matrix: In an adjacency matrix, each column and each row represent a

vertex. If a 1 shows up in row $$i$$, column $$j$$, there is an edge $$(i,j)$$.

sage: # needs sage.modules
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()                                           # needs sage.plot

>>> from sage.all import *
>>> # needs sage.modules
>>> M = Matrix([(Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0)), (Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0)),
...             (Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0)), (Integer(0),Integer(0),Integer(1),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0)),
...             (Integer(1),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1)), (Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(1),Integer(0)), (Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(1)),
...             (Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(1),Integer(0),Integer(0),Integer(0),Integer(1)), (Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0),Integer(0)), (Integer(0),Integer(0),Integer(0),Integer(0),Integer(1),Integer(0),Integer(1),Integer(1),Integer(0),Integer(0))])
>>> 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]
>>> G = Graph(M); G
Graph on 10 vertices
>>> G.plot().show()    # or G.show()                                           # needs sage.plot

• incidence matrix: In an incidence matrix, each row represents a vertex and

each column represents an edge.

sage: # needs sage.modules
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()                                           # needs sage.plot
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

>>> from sage.all import *
>>> # needs sage.modules
>>> M = Matrix([(-Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)),
...             ( Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0),-Integer(1), Integer(0), Integer(0), Integer(0)),
...             ( Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0),-Integer(1), Integer(0), Integer(0)),
...             ( Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0),-Integer(1), Integer(0)),
...             ( Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0),-Integer(1)),
...             ( Integer(0), Integer(0), Integer(0), Integer(0), Integer(0),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(1), Integer(0), Integer(0), Integer(0), Integer(0)),
...             ( Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0), Integer(0)),
...             ( Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0), Integer(0)),
...             ( Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(1), Integer(0)),
...             ( Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1),-Integer(1), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(0), Integer(1))])
>>> 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]
>>> G = Graph(M); G
Graph on 10 vertices
>>> G.plot().show()    # or G.show()                                           # needs sage.plot
>>> DiGraph(matrix(Integer(2), [Integer(0),Integer(0),-Integer(1),Integer(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)]); g
Graph on 5 vertices

>>> from sage.all import *
>>> g = Graph([(Integer(1), Integer(3)), (Integer(3), Integer(8)), (Integer(5), Integer(2))]); g
Graph on 5 vertices

• an igraph Graph:

sage: import igraph                                 # optional - python_igraph
sage: g = Graph(igraph.Graph([(1,3),(3,2),(0,2)]))  # optional - python_igraph
sage: g                                             # optional - python_igraph
Graph on 4 vertices

>>> from sage.all import *
>>> import igraph                                 # optional - python_igraph
>>> g = Graph(igraph.Graph([(Integer(1),Integer(3)),(Integer(3),Integer(2)),(Integer(0),Integer(2))]))  # optional - python_igraph
>>> g                                             # optional - python_igraph
Graph on 4 vertices


## Generators#

Use graphs(n) to iterate through all non-isomorphic graphs of given size:

sage: for g in graphs(4):
....:     print(g.degree_sequence())
[0, 0, 0, 0]
[1, 1, 0, 0]
[2, 1, 1, 0]
[3, 1, 1, 1]
[1, 1, 1, 1]
[2, 2, 1, 1]
[2, 2, 2, 0]
[3, 2, 2, 1]
[2, 2, 2, 2]
[3, 3, 2, 2]
[3, 3, 3, 3]

>>> from sage.all import *
>>> for g in graphs(Integer(4)):
...     print(g.degree_sequence())
[0, 0, 0, 0]
[1, 1, 0, 0]
[2, 1, 1, 0]
[3, 1, 1, 1]
[1, 1, 1, 1]
[2, 2, 1, 1]
[2, 2, 2, 0]
[3, 2, 2, 1]
[2, 2, 2, 2]
[3, 3, 2, 2]
[3, 3, 3, 3]


Similarly graphs() will iterate through all graphs. The complete graph of 4 vertices is of course the smallest graph with chromatic number bigger than three:

sage: for g in graphs():
....:     if g.chromatic_number() > 3:
....:         break
sage: g.is_isomorphic(graphs.CompleteGraph(4))
True

>>> from sage.all import *
>>> for g in graphs():
...     if g.chromatic_number() > Integer(3):
...         break
>>> g.is_isomorphic(graphs.CompleteGraph(Integer(4)))
True


For some commonly used graphs to play with, type:

sage: graphs.[tab]          # not tested

>>> from sage.all import *
>>> 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()                                              # needs sage.plot
sage: G.degree_histogram()
[0, 0, 0, 10]
[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]

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> G.plot().show()    # or G.show()                                              # needs sage.plot
>>> G.degree_histogram()
[0, 0, 0, 10]
[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()                                              # needs sage.plot
sage: S.density()
1/2

>>> from sage.all import *
>>> S = G.subgraph([Integer(0),Integer(1),Integer(2),Integer(3)])
>>> S.plot().show()    # or S.show()                                              # needs sage.plot
>>> 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)                                                    # needs sage.plot

>>> from sage.all import *
>>> G = GraphQuery(display_cols=['graph6'], num_vertices=Integer(7), diameter=Integer(5))
>>> L = G.get_graphs_list()
>>> graphs_list.show_graphs(L)                                                    # needs sage.plot


## Labels#

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 $$u$$ and $$v$$ 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]])                                                    # needs sage.modules
sage: G = Graph({ 0 : { M : None } })                                               # needs sage.modules
Traceback (most recent call last):
...
TypeError: mutable matrices are unhashable

>>> from sage.all import *
>>> M = Matrix([[Integer(0),Integer(0)], [Integer(0),Integer(0)]])                                                    # needs sage.modules
>>> G = Graph({ Integer(0) : { M : None } })                                               # needs sage.modules
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(sort=True)
[0, 1, 2, 3]
sage: T.set_vertices(d)
sage: T.get_vertex(1)
Flower Snark: Graph on 20 vertices

>>> from sage.all import *
>>> d = {Integer(0) : graphs.DodecahedralGraph(), Integer(1) : graphs.FlowerSnark(), \
2 : graphs.MoebiusKantorGraph(), 3 : graphs.PetersenGraph() }
>>> d[Integer(2)]
Moebius-Kantor Graph: Graph on 16 vertices
>>> T = graphs.TetrahedralGraph()
>>> T.vertices(sort=True)
[0, 1, 2, 3]
>>> T.set_vertices(d)
>>> T.get_vertex(Integer(1))
Flower Snark: Graph on 20 vertices


## Database#

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()
{...}

>>> from sage.all import *
>>> graph_db_info()
{...}


For more details on data types or keyword input, enter

sage: GraphQuery?    # not tested

>>> from sage.all import *
>>> 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?po
F?gqg
F@?]O
F@OKg
F@R@o
FA_pW
FEOhW
FGC{o
FIAHo

>>> from sage.all import *
>>> Q = GraphQuery(display_cols=['graph6'],num_vertices=Integer(7), diameter=Integer(5))
>>> Q.show()
Graph6
--------------------
F?po
F?gqg
F@?]O
F@OKg
F@R@o
FA_pW
FEOhW
FGC{o
FIAHo


Show each graph as you iterate through the results:

sage: for g in Q:                                                                   # needs sage.plot
....:     show(g)

>>> from sage.all import *
>>> for g in Q:                                                                   # needs sage.plot
...     show(g)


## Visualization#

To see a graph $$G$$ 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()                                                                      # needs sage.plot

>>> from sage.all import *
>>> G = graphs.RandomGNP(Integer(15),RealNumber('.3'))
>>> G.show()                                                                      # needs sage.plot


And you can view it in three dimensions via jmol with show3d().

sage: G.show3d()                                                                    # needs sage.plot

>>> from sage.all import *
>>> G.show3d()                                                                    # needs sage.plot


Or it can be rendered with $$\LaTeX$$. This requires the right additions to a standard $$\mbox{\rm\TeX}$$ 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 $$\LaTeX$$ 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}

>>> from sage.all import *
>>> from sage.graphs.graph_latex import check_tkz_graph
>>> check_tkz_graph()  # random - depends on TeX installation
>>> latex(G)
\begin{tikzpicture}
...
\end{tikzpicture}


## Mutability#

Graphs are mutable, and thus unusable as dictionary keys, unless data_structure="static_sparse" is used:

sage: G = graphs.PetersenGraph()
sage: {G:1}[G]
Traceback (most recent call last):
...
TypeError: This graph is mutable, and thus not hashable.
Create an immutable copy by g.copy(immutable=True)
sage: G_immutable = Graph(G, immutable=True)
sage: G_immutable == G
True
sage: {G_immutable:1}[G_immutable]
1

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> {G:Integer(1)}[G]
Traceback (most recent call last):
...
TypeError: This graph is mutable, and thus not hashable.
Create an immutable copy by g.copy(immutable=True)
>>> G_immutable = Graph(G, immutable=True)
>>> G_immutable == G
True
>>> {G_immutable:Integer(1)}[G_immutable]
1


## Methods#

class sage.graphs.graph.Graph(data=None, pos=None, loops=None, format=None, weighted=None, data_structure='sparse', vertex_labels=True, name=None, multiedges=None, convert_empty_dict_labels_to_None=None, sparse=True, immutable=False, hash_labels=None)[source]#

Bases: GenericGraph

Undirected graph.

A graph is a set of vertices connected by edges. See the Wikipedia article Graph_(mathematics) for more information. For a collection of pre-defined graphs, see the graph_generators module.

A Graph object has many methods whose list can be obtained by typing g.<tab> (i.e. hit the Tab key) or by reading the documentation of graph, generic_graph, and digraph.

INPUT:

By default, a Graph object is simple (i.e. no loops nor multiple edges) and unweighted. This can be easily tuned with the appropriate flags (see below).

• data – can be any of the following (see the format argument):

1. Graph() – build a graph on 0 vertices.

2. Graph(5) – return an edgeless graph on the 5 vertices 0,…,4.

3. Graph([list_of_vertices, list_of_edges]) – returns a graph with given vertices/edges.

To bypass auto-detection, prefer the more explicit Graph([V, E], format='vertices_and_edges').

4. Graph(list_of_edges) – return a graph with a given list of edges (see documentation of add_edges()).

To bypass auto-detection, prefer the more explicit Graph(L, format='list_of_edges').

5. Graph({1: [2, 3, 4], 3: [4]}) – return a graph by associating to each vertex the list of its neighbors.

To bypass auto-detection, prefer the more explicit Graph(D, format='dict_of_lists').

6. Graph({1: {2: 'a', 3:'b'} ,3:{2:'c'}}) – return a graph by associating a list of neighbors to each vertex and providing its edge label.

To bypass auto-detection, prefer the more explicit Graph(D, format='dict_of_dicts').

For graphs with multiple edges, you can provide a list of labels instead, e.g.: Graph({1: {2: ['a1', 'a2'], 3:['b']} ,3:{2:['c']}}).

7. Graph(a_symmetric_matrix) – return a graph with given (weighted) adjacency matrix (see documentation of adjacency_matrix()).

To bypass auto-detection, prefer the more explicit Graph(M, format='adjacency_matrix'). To take weights into account, use format='weighted_adjacency_matrix' instead.

8. Graph(a_nonsymmetric_matrix) – return a graph with given incidence matrix (see documentation of incidence_matrix()).

To bypass auto-detection, prefer the more explicit Graph(M, format='incidence_matrix').

9. Graph([V, f]) – return a graph from a vertex set V and a symmetric function f. The graph contains an edge $$u,v$$ whenever f(u,v) is True.. Example: Graph([ [1..10], lambda x,y: abs(x-y).is_square()])

10. Graph(':IES@obGkqegW~') – return a graph from a graph6 or sparse6 string (see documentation of graph6_string() or sparse6_string()).

11. Graph(a_seidel_matrix, format='seidel_adjacency_matrix') – return a graph with a given Seidel adjacency matrix (see documentation of seidel_adjacency_matrix()).

12. Graph(another_graph) – return a graph from a Sage (di)graph, pygraphviz graph, NetworkX graph, or igraph graph.

• pos – a positioning dictionary (cf. documentation of layout()). For example, to draw 4 vertices on a square:

{0: [-1,-1],
1: [ 1,-1],
2: [ 1, 1],
3: [-1, 1]}

• name – (must be an explicitly named parameter, i.e.,

name="complete") gives the graph a name

• loops – boolean (default: None); whether to allow loops (ignored

if data is an instance of the Graph class)

• multiedges – boolean (default: None); whether to allow multiple

edges (ignored if data is an instance of the Graph class).

• weighted – boolean (default: None); whether graph thinks of itself as weighted or not. See weighted().

• format – if set to None (default), Graph tries to guess input’s format. To avoid this possibly time-consuming step, one of the following values can be specified (see description above): "int", "graph6", "sparse6", "rule", "list_of_edges", "dict_of_lists", "dict_of_dicts", "adjacency_matrix", "weighted_adjacency_matrix", "seidel_adjacency_matrix", "incidence_matrix", "NX", "igraph".

• sparse – boolean (default: True); sparse=True is an alias for data_structure="sparse", and sparse=False is an alias for data_structure="dense".

• data_structure – one of the following (for more information, see overview)

• immutable – boolean (default: False); whether to create a immutable graph. Note that immutable=True is actually a shortcut for data_structure='static_sparse'. Set to False by default.

• hash_labels – boolean (default: None); whether to include edge labels during hashing. This parameter defaults to True if the graph is weighted. This parameter is ignored if the graph is mutable. Beware that trying to hash unhashable labels will raise an error.

• vertex_labels – boolean (default: True); 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):

1. An integer giving the number of vertices:

sage: g = Graph(5); g
Graph on 5 vertices
sage: g.vertices(sort=True)
[0, 1, 2, 3, 4]
sage: g.edges(sort=False)
[]

>>> from sage.all import *
>>> g = Graph(Integer(5)); g
Graph on 5 vertices
>>> g.vertices(sort=True)
[0, 1, 2, 3, 4]
>>> g.edges(sort=False)
[]

2. A dictionary of dictionaries:

sage: g = Graph({0:{1:'x',2:'z',3:'a'}, 2:{5:'out'}}); g
Graph on 5 vertices

>>> from sage.all import *
>>> g = Graph({Integer(0):{Integer(1):'x',Integer(2):'z',Integer(3):'a'}, Integer(2):{Integer(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))                              # needs sage.groups
sage: Graph({b: {d: 'c', e: 'p'}, c: {d: 'p', e: 'c'}})                         # needs sage.groups
Graph on 4 vertices

>>> from sage.all import *
>>> a, b, c, d, e, f = sorted(SymmetricGroup(Integer(3)))                              # needs sage.groups
>>> Graph({b: {d: 'c', e: 'p'}, c: {d: 'p', e: 'c'}})                         # needs sage.groups
Graph on 4 vertices

3. A dictionary of lists:

sage: g = Graph({0:[1,2,3], 2:[4]}); g
Graph on 5 vertices

>>> from sage.all import *
>>> g = Graph({Integer(0):[Integer(1),Integer(2),Integer(3)], Integer(2):[Integer(4)]}); g
Graph on 5 vertices

4. 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()])             # needs sage.rings.finite_rings
sage: g.vertices(sort=True)                                                   # needs sage.rings.finite_rings
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
sage: g.adjacency_matrix()                                                    # needs sage.modules sage.rings.finite_rings
[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]

>>> from sage.all import *
>>> g = Graph([GF(Integer(13)), lambda i,j: i!=j and (i-j).is_square()])             # needs sage.rings.finite_rings
>>> g.vertices(sort=True)                                                   # needs sage.rings.finite_rings
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
>>> g.adjacency_matrix()                                                    # needs sage.modules sage.rings.finite_rings
[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(sort=True, labels=false),
....:                     lambda i,j: len(set(i).intersection(set(j)))>0],
....:                    loops=False)
sage: line_graph.vertices(sort=True)
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
[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]

>>> from sage.all import *
>>> g = graphs.CompleteGraph(Integer(4))
>>> line_graph = Graph([g.edges(sort=True, labels=false),
...                     lambda i,j: len(set(i).intersection(set(j)))>Integer(0)],
...                    loops=False)
>>> line_graph.vertices(sort=True)
[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]
[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]

5. A graph6 or sparse6 string: Sage automatically recognizes whether a string is in graph6 or sparse6 format:

sage: s = ':IAKGsaOscI]Gb~'
sage: Graph(s, sparse=True)
Looped multi-graph on 10 vertices

>>> from sage.all import *
>>> s = ':IAKGsaOscI]Gb~'
>>> 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

>>> from sage.all import *
>>> G = Graph('G?????')
>>> G = Graph("G'?G?C")
Traceback (most recent call last):
...
RuntimeError: the string seems corrupt: valid characters are
?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_abcdefghijklmnopqrstuvwxyz{|}~
>>> 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'AKGsaOscI]Gb~")
Traceback (most recent call last):
...
RuntimeError: the string seems corrupt: valid characters are
?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\]^_abcdefghijklmnopqrstuvwxyz{|}~

>>> from sage.all import *
>>> G = Graph(":I'AKGsaOscI]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:IAKGsaOscI]Gb~\n:IEDOAEQ?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]

>>> from sage.all import *
>>> s = ':IgMoqoCUOqeb\n:IAKGsaOscI]Gb~\n:IEDOAEQ?PccSsge\\N\n'
>>> graphs_list.from_sparse6(s)
[Looped multi-graph on 10 vertices,
Looped multi-graph on 10 vertices,
Looped multi-graph on 10 vertices]

6. A Sage matrix: Note: If format is not specified, then Sage assumes a symmetric square matrix is an adjacency matrix, otherwise an incidence matrix.

sage: M = graphs.PetersenGraph().am(); M                                    # needs sage.modules
[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)                                                              # needs sage.modules
Graph on 10 vertices

>>> from sage.all import *
>>> M = graphs.PetersenGraph().am(); M                                    # needs sage.modules
[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]
>>> Graph(M)                                                              # needs sage.modules
Graph on 10 vertices

sage: Graph(matrix([[1,2], [2,4]]), loops=True, sparse=True)                # needs sage.modules
Looped multi-graph on 2 vertices

sage: M = Matrix([[0,1,-1], [1,0,-1/2], [-1,-1/2,0]]); M                    # needs sage.modules
[   0    1   -1]
[   1    0 -1/2]
[  -1 -1/2    0]
sage: G = Graph(M, sparse=True); G                                          # needs sage.modules
Graph on 3 vertices
sage: G.weighted()                                                          # needs sage.modules
True

>>> from sage.all import *
>>> Graph(matrix([[Integer(1),Integer(2)], [Integer(2),Integer(4)]]), loops=True, sparse=True)                # needs sage.modules
Looped multi-graph on 2 vertices

>>> M = Matrix([[Integer(0),Integer(1),-Integer(1)], [Integer(1),Integer(0),-Integer(1)/Integer(2)], [-Integer(1),-Integer(1)/Integer(2),Integer(0)]]); M                    # needs sage.modules
[   0    1   -1]
[   1    0 -1/2]
[  -1 -1/2    0]
>>> G = Graph(M, sparse=True); G                                          # needs sage.modules
Graph on 3 vertices
>>> G.weighted()                                                          # needs sage.modules
True

• an incidence matrix:

sage: M = Matrix(6, [-1,0,0,0,1, 1,-1,0,0,0, 0,1,-1,0,0,                    # needs sage.modules
....:                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)                                                              # needs sage.modules
Graph on 6 vertices

sage: Graph(Matrix([[1],[1],[1]]))                                          # needs sage.modules
Traceback (most recent call last):
...
ValueError: there must be one or two nonzero entries per column
in an incidence matrix, got entries [1, 1, 1] in column 0
sage: Graph(Matrix([[1],[1],[0]]))                                          # needs sage.modules
Graph on 3 vertices

sage: M = Matrix([[0,1,-1], [1,0,-1], [-1,-1,0]]); M                        # needs sage.modules
[ 0  1 -1]
[ 1  0 -1]
[-1 -1  0]
sage: Graph(M, sparse=True)                                                 # needs sage.modules
Graph on 3 vertices

sage: M = Matrix([[0,1,1], [1,0,1], [-1,-1,0]]); M                          # needs sage.modules
[ 0  1  1]
[ 1  0  1]
[-1 -1  0]
sage: Graph(M)                                                              # needs sage.modules
Traceback (most recent call last):
...
ValueError: there must be one or two nonzero entries per column
in an incidence matrix, got entries [1, 1] in column 2

>>> from sage.all import *
>>> M = Matrix(Integer(6), [-Integer(1),Integer(0),Integer(0),Integer(0),Integer(1), Integer(1),-Integer(1),Integer(0),Integer(0),Integer(0), Integer(0),Integer(1),-Integer(1),Integer(0),Integer(0),                    # needs sage.modules
...                Integer(0),Integer(0),Integer(1),-Integer(1),Integer(0), Integer(0),Integer(0),Integer(0),Integer(1),-Integer(1), Integer(0),Integer(0),Integer(0),Integer(0),Integer(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]
>>> Graph(M)                                                              # needs sage.modules
Graph on 6 vertices

>>> Graph(Matrix([[Integer(1)],[Integer(1)],[Integer(1)]]))                                          # needs sage.modules
Traceback (most recent call last):
...
ValueError: there must be one or two nonzero entries per column
in an incidence matrix, got entries [1, 1, 1] in column 0
>>> Graph(Matrix([[Integer(1)],[Integer(1)],[Integer(0)]]))                                          # needs sage.modules
Graph on 3 vertices

>>> M = Matrix([[Integer(0),Integer(1),-Integer(1)], [Integer(1),Integer(0),-Integer(1)], [-Integer(1),-Integer(1),Integer(0)]]); M                        # needs sage.modules
[ 0  1 -1]
[ 1  0 -1]
[-1 -1  0]
>>> Graph(M, sparse=True)                                                 # needs sage.modules
Graph on 3 vertices

>>> M = Matrix([[Integer(0),Integer(1),Integer(1)], [Integer(1),Integer(0),Integer(1)], [-Integer(1),-Integer(1),Integer(0)]]); M                          # needs sage.modules
[ 0  1  1]
[ 1  0  1]
[-1 -1  0]
>>> Graph(M)                                                              # needs sage.modules
Traceback (most recent call last):
...
ValueError: there must be one or two nonzero entries per column
in an incidence matrix, got entries [1, 1] in column 2


Check that Issue #9714 is fixed:

sage: # needs sage.modules
sage: MA = Matrix([[1,2,0], [0,2,0], [0,0,1]])
sage: MI = GA.incidence_matrix(oriented=False); MI
[2 1 1 0 0 0]
[0 1 1 2 2 0]
[0 0 0 0 0 2]
sage: Graph(MI).edges(sort=True, labels=None)
[(0, 0), (0, 1), (0, 1), (1, 1), (1, 1), (2, 2)]

sage: M = Matrix([[1], [-1]]); M                                            # needs sage.modules
[ 1]
[-1]
sage: Graph(M).edges(sort=True)                                             # needs sage.modules
[(0, 1, None)]

>>> from sage.all import *
>>> # needs sage.modules
>>> MA = Matrix([[Integer(1),Integer(2),Integer(0)], [Integer(0),Integer(2),Integer(0)], [Integer(0),Integer(0),Integer(1)]])
>>> MI = GA.incidence_matrix(oriented=False); MI
[2 1 1 0 0 0]
[0 1 1 2 2 0]
[0 0 0 0 0 2]
>>> Graph(MI).edges(sort=True, labels=None)
[(0, 0), (0, 1), (0, 1), (1, 1), (1, 1), (2, 2)]

>>> M = Matrix([[Integer(1)], [-Integer(1)]]); M                                            # needs sage.modules
[ 1]
[-1]
>>> Graph(M).edges(sort=True)                                             # needs sage.modules
[(0, 1, None)]


sage: from sage.combinat.matrices.hadamard_matrix import (                    # needs sage.combinat sage.modules
sage: m = rshcd(16,1) - matrix.identity(16)                                   # needs sage.combinat sage.modules
sage: Graph(m,                                                                # needs sage.combinat sage.modules
(16, 6, 2, 2)

>>> from sage.all import *
>>> from sage.combinat.matrices.hadamard_matrix import (                    # needs sage.combinat sage.modules
>>> m = rshcd(Integer(16),Integer(1)) - matrix.identity(Integer(16))                                   # needs sage.combinat sage.modules
>>> Graph(m,                                                                # needs sage.combinat sage.modules
(16, 6, 2, 2)

8. List of edges, or labelled edges:

sage: g = Graph([(1, 3), (3, 8), (5, 2)]); g
Graph on 5 vertices

sage: g = Graph([(1, 2, "Peace"), (7, -9, "and"), (77, 2, "Love")]); g
Graph on 5 vertices
sage: g = Graph([(0, 2, '0'), (0, 2, '1'), (3, 3, '2')],
....:           loops=True, multiedges=True)
sage: g.loops()
[(3, 3, '2')]

>>> from sage.all import *
>>> g = Graph([(Integer(1), Integer(3)), (Integer(3), Integer(8)), (Integer(5), Integer(2))]); g
Graph on 5 vertices

>>> g = Graph([(Integer(1), Integer(2), "Peace"), (Integer(7), -Integer(9), "and"), (Integer(77), Integer(2), "Love")]); g
Graph on 5 vertices
>>> g = Graph([(Integer(0), Integer(2), '0'), (Integer(0), Integer(2), '1'), (Integer(3), Integer(3), '2')],
...           loops=True, multiedges=True)
>>> g.loops()
[(3, 3, '2')]

9. A NetworkX MultiGraph:

sage: import networkx                                                         # needs networkx
sage: g = networkx.MultiGraph({0:[1,2,3], 2:[4]})                             # needs networkx
sage: Graph(g)                                                                # needs networkx
Multi-graph on 5 vertices

>>> from sage.all import *
>>> import networkx                                                         # needs networkx
>>> g = networkx.MultiGraph({Integer(0):[Integer(1),Integer(2),Integer(3)], Integer(2):[Integer(4)]})                             # needs networkx
>>> Graph(g)                                                                # needs networkx
Multi-graph on 5 vertices

10. A NetworkX graph:

sage: import networkx                                                        # needs networkx
sage: g = networkx.Graph({0:[1,2,3], 2:[4]})                                 # needs networkx
sage: DiGraph(g)                                                             # needs networkx
Digraph on 5 vertices

>>> from sage.all import *
>>> import networkx                                                        # needs networkx
>>> g = networkx.Graph({Integer(0):[Integer(1),Integer(2),Integer(3)], Integer(2):[Integer(4)]})                                 # needs networkx
>>> DiGraph(g)                                                             # needs networkx
Digraph on 5 vertices

11. An igraph Graph (see also igraph_graph()):

sage: import igraph                       # optional - python_igraph
sage: g = igraph.Graph([(0, 1), (0, 2)])  # optional - python_igraph
sage: Graph(g)                            # optional - python_igraph
Graph on 3 vertices

>>> from sage.all import *
>>> import igraph                       # optional - python_igraph
>>> g = igraph.Graph([(Integer(0), Integer(1)), (Integer(0), Integer(2))])  # optional - python_igraph
>>> Graph(g)                            # optional - python_igraph
Graph on 3 vertices


If vertex_labels is True, the names of the vertices are given by the vertex attribute 'name', if available:

sage: # optional - python_igraph
sage: g = igraph.Graph([(0,1),(0,2)], vertex_attrs={'name':['a','b','c']})
sage: Graph(g).vertices(sort=True)
['a', 'b', 'c']
sage: g = igraph.Graph([(0,1),(0,2)], vertex_attrs={'label':['a','b','c']})
sage: Graph(g).vertices(sort=True)
[0, 1, 2]

>>> from sage.all import *
>>> # optional - python_igraph
>>> g = igraph.Graph([(Integer(0),Integer(1)),(Integer(0),Integer(2))], vertex_attrs={'name':['a','b','c']})
>>> Graph(g).vertices(sort=True)
['a', 'b', 'c']
>>> g = igraph.Graph([(Integer(0),Integer(1)),(Integer(0),Integer(2))], vertex_attrs={'label':['a','b','c']})
>>> Graph(g).vertices(sort=True)
[0, 1, 2]


If the igraph Graph has edge attributes, they are used as edge labels:

sage: g = igraph.Graph([(0, 1), (0, 2)],                             # optional - python_igraph
....:                  edge_attrs={'name': ['a', 'b'], 'weight': [1, 3]})
sage: Graph(g).edges(sort=True)                                      # optional - python_igraph
[(0, 1, {'name': 'a', 'weight': 1}), (0, 2, {'name': 'b', 'weight': 3})]

>>> from sage.all import *
>>> g = igraph.Graph([(Integer(0), Integer(1)), (Integer(0), Integer(2))],                             # optional - python_igraph
...                  edge_attrs={'name': ['a', 'b'], 'weight': [Integer(1), Integer(3)]})
>>> Graph(g).edges(sort=True)                                      # optional - python_igraph
[(0, 1, {'name': 'a', 'weight': 1}), (0, 2, {'name': 'b', 'weight': 3})]


When defining an undirected graph from a function f, it is very important that f be symmetric. If it is not, anything can happen:

sage: f_sym = lambda x,y: abs(x-y) == 1
sage: f_nonsym = lambda x,y: (x-y) == 1
sage: G_sym = Graph([[4,6,1,5,3,7,2,0], f_sym])
sage: G_sym.is_isomorphic(graphs.PathGraph(8))
True
sage: G_nonsym = Graph([[4,6,1,5,3,7,2,0], f_nonsym])
sage: G_nonsym.size()
4
sage: G_nonsym.is_isomorphic(G_sym)
False

>>> from sage.all import *
>>> f_sym = lambda x,y: abs(x-y) == Integer(1)
>>> f_nonsym = lambda x,y: (x-y) == Integer(1)
>>> G_sym = Graph([[Integer(4),Integer(6),Integer(1),Integer(5),Integer(3),Integer(7),Integer(2),Integer(0)], f_sym])
>>> G_sym.is_isomorphic(graphs.PathGraph(Integer(8)))
True
>>> G_nonsym = Graph([[Integer(4),Integer(6),Integer(1),Integer(5),Integer(3),Integer(7),Integer(2),Integer(0)], f_nonsym])
>>> G_nonsym.size()
4
>>> G_nonsym.is_isomorphic(G_sym)
False


By default, graphs are mutable and can thus not be used as a dictionary key:

sage: G = graphs.PetersenGraph()
sage: {G:1}[G]
Traceback (most recent call last):
...
TypeError: This graph is mutable, and thus not hashable.
Create an immutable copy by g.copy(immutable=True)

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> {G:Integer(1)}[G]
Traceback (most recent call last):
...
TypeError: This graph is mutable, and thus not hashable.
Create an immutable copy by g.copy(immutable=True)


When providing the optional arguments data_structure="static_sparse" or immutable=True (both mean the same), then an immutable graph results:

sage: G_imm = Graph(G, immutable=True)
sage: H_imm = Graph(G, data_structure='static_sparse')
sage: G_imm == H_imm == G
True
sage: {G_imm:1}[H_imm]
1

>>> from sage.all import *
>>> G_imm = Graph(G, immutable=True)
>>> H_imm = Graph(G, data_structure='static_sparse')
>>> G_imm == H_imm == G
True
>>> {G_imm:Integer(1)}[H_imm]
1

acyclic_orientations(G)[source]#

Return an iterator over all acyclic orientations of an undirected graph $$G$$.

ALGORITHM:

The algorithm is based on [Sq1998]. It presents an efficient algorithm for listing the acyclic orientations of a graph. The algorithm is shown to require O(n) time per acyclic orientation generated, making it the most efficient known algorithm for generating acyclic orientations.

The function uses a recursive approach to generate acyclic orientations of the graph. It reorders the vertices and edges of the graph, creating a new graph with updated labels. Then, it iteratively generates acyclic orientations by considering subsets of edges and checking whether they form upsets in a corresponding poset.

INPUT:

• G – an undirected graph.

OUTPUT:

• An iterator over all acyclic orientations of the input graph.

Note

The function assumes that the input graph is undirected and the edges are unlabelled.

EXAMPLES:

To count number acyclic orientations for a graph:

sage: g = Graph([(0, 3), (0, 4), (3, 4), (1, 3), (1, 2), (2, 3), (2, 4)])
sage: it = g.acyclic_orientations()
sage: len(list(it))
54

>>> from sage.all import *
>>> g = Graph([(Integer(0), Integer(3)), (Integer(0), Integer(4)), (Integer(3), Integer(4)), (Integer(1), Integer(3)), (Integer(1), Integer(2)), (Integer(2), Integer(3)), (Integer(2), Integer(4))])
>>> it = g.acyclic_orientations()
>>> len(list(it))
54


Test for arbitary vertex labels:

sage: g_str = Graph([('abc', 'def'), ('ghi', 'def'), ('xyz', 'abc'), ('xyz', 'uvw'), ('uvw', 'abc'), ('uvw', 'ghi')])
sage: it = g_str.acyclic_orientations()
sage: len(list(it))
42

>>> from sage.all import *
>>> g_str = Graph([('abc', 'def'), ('ghi', 'def'), ('xyz', 'abc'), ('xyz', 'uvw'), ('uvw', 'abc'), ('uvw', 'ghi')])
>>> it = g_str.acyclic_orientations()
>>> len(list(it))
42

all_cliques(graph, min_size=0, max_size=0)[source]#

Iterator over the cliques in graph.

A clique is an induced complete subgraph. This method is an iterator over all the cliques with size in between min_size and max_size. By default, this method returns only maximum cliques. Each yielded clique is represented by a list of vertices.

Note

Currently only implemented for undirected graphs. Use to_undirected() to convert a digraph to an undirected graph.

INPUT:

• min_size – integer (default: 0); minimum size of reported cliques. When set to 0 (default), this method searches for maximum cliques. In such case, parameter max_size must also be set to 0.

• max_size – integer (default: 0); maximum size of reported cliques. When set to 0 (default), the maximum size of the cliques is unbounded. When min_size is set to 0, this parameter must be set to 0.

ALGORITHM:

This function is based on Cliquer [NO2003].

EXAMPLES:

sage: G = graphs.CompleteGraph(5)
sage: list(sage.graphs.cliquer.all_cliques(G))
[[0, 1, 2, 3, 4]]
sage: list(sage.graphs.cliquer.all_cliques(G, 2, 3))
[[3, 4],
[2, 3],
[2, 3, 4],
[2, 4],
[1, 2],
[1, 2, 3],
[1, 2, 4],
[1, 3],
[1, 3, 4],
[1, 4],
[0, 1],
[0, 1, 2],
[0, 1, 3],
[0, 1, 4],
[0, 2],
[0, 2, 3],
[0, 2, 4],
[0, 3],
[0, 3, 4],
[0, 4]]
sage: G.delete_edge([1,3])
sage: list(sage.graphs.cliquer.all_cliques(G))
[[0, 2, 3, 4], [0, 1, 2, 4]]

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(5))
>>> list(sage.graphs.cliquer.all_cliques(G))
[[0, 1, 2, 3, 4]]
>>> list(sage.graphs.cliquer.all_cliques(G, Integer(2), Integer(3)))
[[3, 4],
[2, 3],
[2, 3, 4],
[2, 4],
[1, 2],
[1, 2, 3],
[1, 2, 4],
[1, 3],
[1, 3, 4],
[1, 4],
[0, 1],
[0, 1, 2],
[0, 1, 3],
[0, 1, 4],
[0, 2],
[0, 2, 3],
[0, 2, 4],
[0, 3],
[0, 3, 4],
[0, 4]]
>>> G.delete_edge([Integer(1),Integer(3)])
>>> list(sage.graphs.cliquer.all_cliques(G))
[[0, 2, 3, 4], [0, 1, 2, 4]]


Todo

Use the re-entrant functionality of Cliquer [NO2003] to avoid storing all cliques.

antipodal_graph()[source]#

Return the antipodal graph of self.

The antipodal graph of a graph $$G$$ has the same vertex set of $$G$$ and two vertices are adjacent if their distance in $$G$$ is equal to the diameter of $$G$$.

OUTPUT:

A new graph. self is not touched.

EXAMPLES:

sage: G = graphs.JohnsonGraph(10, 5)
sage: G.antipodal_graph()
Antipodal graph of Johnson graph with parameters 10,5: Graph on 252 vertices
sage: G = graphs.HammingGraph(8, 2)
sage: G.antipodal_graph()
Antipodal graph of Hamming Graph with parameters 8,2: Graph on 256 vertices

>>> from sage.all import *
>>> G = graphs.JohnsonGraph(Integer(10), Integer(5))
>>> G.antipodal_graph()
Antipodal graph of Johnson graph with parameters 10,5: Graph on 252 vertices
>>> G = graphs.HammingGraph(Integer(8), Integer(2))
>>> G.antipodal_graph()
Antipodal graph of Hamming Graph with parameters 8,2: Graph on 256 vertices


The antipodal graph of a disconnected graph is its complement:

sage: G = Graph(5)
sage: H = G.antipodal_graph()
sage: H.is_isomorphic(G.complement())
True

>>> from sage.all import *
>>> G = Graph(Integer(5))
>>> H = G.antipodal_graph()
>>> H.is_isomorphic(G.complement())
True

apex_vertices(k=None)[source]#

Return the list of apex vertices.

A graph is apex if it can be made planar by the removal of a single vertex. The deleted vertex is called an apex of the graph, and a graph may have more than one apex. For instance, in the minimal nonplanar graphs $$K_5$$ or $$K_{3,3}$$, every vertex is an apex. The apex graphs include graphs that are themselves planar, in which case again every vertex is an apex. The null graph is also counted as an apex graph even though it has no vertex to remove. If the graph is not connected, we say that it is apex if it has at most one non planar connected component and that this component is apex. See the Wikipedia article Apex_graph for more information.

INPUT:

• k – integer (default: None); when set to None, the method returns the list of all apex of the graph, possibly empty if the graph is not apex. When set to a positive integer, the method ends as soon as $$k$$ apex vertices are found.

OUTPUT:

By default, the method returns the list of all apex of the graph. When parameter k is set to a positive integer, the returned list is bounded to $$k$$ apex vertices.

EXAMPLES:

$$K_5$$ and $$K_{3,3}$$ are apex graphs, and each of their vertices is an apex:

sage: G = graphs.CompleteGraph(5)
sage: G.apex_vertices()
[0, 1, 2, 3, 4]
sage: G = graphs.CompleteBipartiteGraph(3,3)
sage: G.is_apex()
True
sage: G.apex_vertices()
[0, 1, 2, 3, 4, 5]
sage: G.apex_vertices(k=3)
[0, 1, 2]

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(5))
>>> G.apex_vertices()
[0, 1, 2, 3, 4]
>>> G = graphs.CompleteBipartiteGraph(Integer(3),Integer(3))
>>> G.is_apex()
True
>>> G.apex_vertices()
[0, 1, 2, 3, 4, 5]
>>> G.apex_vertices(k=Integer(3))
[0, 1, 2]


A $$4\\times 4$$-grid is apex and each of its vertices is an apex. When adding a universal vertex, the resulting graph is apex and the universal vertex is the unique apex vertex

sage: G = graphs.Grid2dGraph(4,4)
sage: set(G.apex_vertices()) == set(G.vertices(sort=False))
True
sage: G.add_edges([('universal',v) for v in G])
sage: G.apex_vertices()
['universal']

>>> from sage.all import *
>>> G = graphs.Grid2dGraph(Integer(4),Integer(4))
>>> set(G.apex_vertices()) == set(G.vertices(sort=False))
True
>>> G.add_edges([('universal',v) for v in G])
>>> G.apex_vertices()
['universal']


The Petersen graph is not apex:

sage: G = graphs.PetersenGraph()
sage: G.apex_vertices()
[]

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> G.apex_vertices()
[]


A graph is apex if all its connected components are apex, but at most one is not planar:

sage: M = graphs.Grid2dGraph(3,3)
sage: K5 = graphs.CompleteGraph(5)
sage: (M+K5).apex_vertices()
[9, 10, 11, 12, 13]
sage: (M+K5+K5).apex_vertices()
[]

>>> from sage.all import *
>>> M = graphs.Grid2dGraph(Integer(3),Integer(3))
>>> K5 = graphs.CompleteGraph(Integer(5))
>>> (M+K5).apex_vertices()
[9, 10, 11, 12, 13]
>>> (M+K5+K5).apex_vertices()
[]


Neighbors of an apex of degree 2 are apex:

sage: G = graphs.Grid2dGraph(5,5)
sage: v = (666, 666)
sage: G.add_path([(1, 1), v, (3, 3)])
sage: G.is_planar()
False
sage: G.degree(v)
2
sage: sorted(G.apex_vertices())
[(1, 1), (2, 2), (3, 3), (666, 666)]

>>> from sage.all import *
>>> G = graphs.Grid2dGraph(Integer(5),Integer(5))
>>> v = (Integer(666), Integer(666))
>>> G.add_path([(Integer(1), Integer(1)), v, (Integer(3), Integer(3))])
>>> G.is_planar()
False
>>> G.degree(v)
2
>>> sorted(G.apex_vertices())
[(1, 1), (2, 2), (3, 3), (666, 666)]

arboricity(certificate=False)[source]#

Return the arboricity of the graph and an optional certificate.

The arboricity is the minimum number of forests that covers the graph.

INPUT:

• certificate – boolean (default: False); whether to return a certificate.

OUTPUT:

When certificate = True, then the function returns $$(a, F)$$ where $$a$$ is the arboricity and $$F$$ is a list of $$a$$ disjoint forests that partitions the edge set of $$g$$. The forests are represented as subgraphs of the original graph.

If certificate = False, the function returns just a integer indicating the arboricity.

ALGORITHM:

Represent the graph as a graphical matroid, then apply matroid sage.matroid.partition() algorithm from the matroids module.

EXAMPLES:

sage: G = graphs.PetersenGraph()
sage: a, F = G.arboricity(True)                                             # needs sage.modules
sage: a                                                                     # needs sage.modules
2
sage: all([f.is_forest() for f in F])                                       # needs sage.modules
True
sage: len(set.union(*[set(f.edges(sort=False)) for f in F])) == G.size()    # needs sage.modules
True

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> a, F = G.arboricity(True)                                             # needs sage.modules
>>> a                                                                     # needs sage.modules
2
>>> all([f.is_forest() for f in F])                                       # needs sage.modules
True
>>> len(set.union(*[set(f.edges(sort=False)) for f in F])) == G.size()    # needs sage.modules
True

atoms_and_clique_separators(G, tree=False, rooted_tree=False, separators=False)[source]#

Return the atoms of the decomposition of $$G$$ by clique minimal separators.

Let $$G = (V, E)$$ be a graph. A set $$S \subset V$$ is a clique separator if $$G[S]$$ is a clique and the graph $$G \setminus S$$ has at least 2 connected components. Let $$C \subset V$$ be the vertices of a connected component of $$G \setminus S$$. The graph $$G[C + S]$$ is an atom if it has no clique separator.

This method implements the algorithm proposed in [BPS2010], that improves upon the algorithm proposed in [TY1984], for computing the atoms and the clique minimal separators of a graph. This algorithm is based on the maximum_cardinality_search_M() graph traversal and has time complexity in $$O(|V|\cdot|E|)$$.

Note

As the graph is converted to a short_digraph (with sort_neighbors=True), the complexity has an extra $$O(|V|+|E|\log{|E|})$$ for SparseGraph and $$O(|V|^2\log{|E|})$$ for DenseGraph.

If the graph is not connected, we insert empty separators between the lists of separators of each connected components. See the examples below for more details.

INPUT:

• G – a Sage graph

• tree – boolean (default: False); whether to return the result as a directed tree in which internal nodes are clique separators and leaves are the atoms of the decomposition. Since a clique separator is repeated when its removal partition the graph into 3 or more connected components, vertices are labels by tuples $$(i, S)$$, where $$S$$ is the set of vertices of the atom or the clique separator, and $$0 \leq i \leq |T|$$.

• rooted_tree – boolean (default: False); whether to return the result as a LabelledRootedTree. When tree is True, this parameter is ignored.

• separators – boolean (default: False); whether to also return the complete list of separators considered during the execution of the algorithm. When tree or rooted_tree is True, this parameter is ignored.

OUTPUT:

• By default, return a tuple $$(A, S_c)$$, where $$A$$ is the list of atoms of the graph in the order of discovery, and $$S_c$$ is the list of clique separators, with possible repetitions, in the order the separator has been considered. If furthermore separators is True, return a tuple $$(A, S_h, S_c)$$, where $$S_c$$ is the list of considered separators of the graph in the order they have been considered.

• When tree is True, format the result as a directed tree

• When rooted_tree is True and tree is False, format the output as a LabelledRootedTree

EXAMPLES:

Example of [BPS2010]:

sage: G = Graph({'a': ['b', 'k'], 'b': ['c'], 'c': ['d', 'j', 'k'],
....:            'd': ['e', 'f', 'j', 'k'], 'e': ['g'],
....:            'f': ['g', 'j', 'k'], 'g': ['j', 'k'], 'h': ['i', 'j'],
....:            'i': ['k'], 'j': ['k']})
sage: atoms, cliques = G.atoms_and_clique_separators()
sage: sorted(sorted(a) for a in atoms)
[['a', 'b', 'c', 'k'],
['c', 'd', 'j', 'k'],
['d', 'e', 'f', 'g', 'j', 'k'],
['h', 'i', 'j', 'k']]
sage: sorted(sorted(c) for c in cliques)
[['c', 'k'], ['d', 'j', 'k'], ['j', 'k']]
sage: T = G.atoms_and_clique_separators(tree=True)
sage: T.is_tree()
True
sage: T.diameter() == len(atoms)
True
sage: all(u[1] in atoms for u in T if T.degree(u) == 1)
True
sage: all(u[1] in cliques for u in T if T.degree(u) != 1)
True

>>> from sage.all import *
>>> G = Graph({'a': ['b', 'k'], 'b': ['c'], 'c': ['d', 'j', 'k'],
...            'd': ['e', 'f', 'j', 'k'], 'e': ['g'],
...            'f': ['g', 'j', 'k'], 'g': ['j', 'k'], 'h': ['i', 'j'],
...            'i': ['k'], 'j': ['k']})
>>> atoms, cliques = G.atoms_and_clique_separators()
>>> sorted(sorted(a) for a in atoms)
[['a', 'b', 'c', 'k'],
['c', 'd', 'j', 'k'],
['d', 'e', 'f', 'g', 'j', 'k'],
['h', 'i', 'j', 'k']]
>>> sorted(sorted(c) for c in cliques)
[['c', 'k'], ['d', 'j', 'k'], ['j', 'k']]
>>> T = G.atoms_and_clique_separators(tree=True)
>>> T.is_tree()
True
>>> T.diameter() == len(atoms)
True
>>> all(u[Integer(1)] in atoms for u in T if T.degree(u) == Integer(1))
True
>>> all(u[Integer(1)] in cliques for u in T if T.degree(u) != Integer(1))
True


A graph without clique separator:

sage: G = graphs.CompleteGraph(5)
sage: G.atoms_and_clique_separators()
([{0, 1, 2, 3, 4}], [])
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
{0, 1, 2, 3, 4}

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(5))
>>> G.atoms_and_clique_separators()
([{0, 1, 2, 3, 4}], [])
>>> ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
{0, 1, 2, 3, 4}


Graphs with several biconnected components:

sage: G = graphs.PathGraph(4)
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
____{2}____
/          /
{2, 3}   __{1}__
/      /
{1, 2} {0, 1}

sage: G = graphs.WindmillGraph(3, 4)
sage: G.atoms_and_clique_separators()
([{0, 1, 2}, {0, 3, 4}, {0, 5, 6}, {0, 8, 7}], [{0}, {0}, {0}])
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
________{0}________
/                  /
{0, 1, 2}   _______{0}______
/               /
{0, 3, 4}   ____{0}___
/         /
{0, 8, 7} {0, 5, 6}

>>> from sage.all import *
>>> G = graphs.PathGraph(Integer(4))
>>> ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
____{2}____
/          /
{2, 3}   __{1}__
/      /
{1, 2} {0, 1}

>>> G = graphs.WindmillGraph(Integer(3), Integer(4))
>>> G.atoms_and_clique_separators()
([{0, 1, 2}, {0, 3, 4}, {0, 5, 6}, {0, 8, 7}], [{0}, {0}, {0}])
>>> ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
________{0}________
/                  /
{0, 1, 2}   _______{0}______
/               /
{0, 3, 4}   ____{0}___
/         /
{0, 8, 7} {0, 5, 6}


When the removal of a clique separator results in $$k > 2$$ connected components, this separator is repeated $$k - 1$$ times, but the repetitions are not necessarily contiguous:

sage: G = Graph(2)
sage: for i in range(5):
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
_________{0, 1}_____
/                   /
{0, 1, 4}   ________{0, 1}_____
/                  /
{0, 1, 2}   _______{0, 1}___
/               /
{0, 1, 3}   ____{0, 1}
/         /
{0, 1, 5} {0, 1, 6}

sage: G = graphs.StarGraph(3)
sage: G.subdivide_edges(G.edges(sort=False), 2)
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
______{5}______
/              /
{1, 5}   ______{7}______
/              /
{2, 7}   ______{9}______
/              /
{9, 3}   ______{6}______
/              /
{6, 7}   ______{4}_____
/             /
{4, 5}   _____{0}_____
/            /
{0, 6}   ____{8}____
/          /
{8, 9}   __{0}__
/      /
{0, 8} {0, 4}

>>> from sage.all import *
>>> G = Graph(Integer(2))
>>> for i in range(Integer(5)):
>>> ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
_________{0, 1}_____
/                   /
{0, 1, 4}   ________{0, 1}_____
/                  /
{0, 1, 2}   _______{0, 1}___
/               /
{0, 1, 3}   ____{0, 1}
/         /
{0, 1, 5} {0, 1, 6}

>>> G = graphs.StarGraph(Integer(3))
>>> G.subdivide_edges(G.edges(sort=False), Integer(2))
>>> ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
______{5}______
/              /
{1, 5}   ______{7}______
/              /
{2, 7}   ______{9}______
/              /
{9, 3}   ______{6}______
/              /
{6, 7}   ______{4}_____
/             /
{4, 5}   _____{0}_____
/            /
{0, 6}   ____{8}____
/          /
{8, 9}   __{0}__
/      /
{0, 8} {0, 4}


If the graph is not connected, we insert empty separators between the lists of separators of each connected components. For instance, let $$G$$ be a graph with 3 connected components. The method returns the list $$S_c = [S_0,\cdots,S_{i},\ldots, S_{j},\ldots,S_{k-1}]$$ of $$k$$ clique separators, where $$i$$ and $$j$$ are the indexes of the inserted empty separators and $$0 \leq i < j < k - 1$$. The method also returns the list $$A = [A_0,\ldots,S_{k}]$$ of the $$k + 1$$ atoms, with $$k + 1 \geq 3$$. The lists of atoms and clique separators of each of the connected components are respectively $$[A_0,\ldots,A_{i}]$$ and $$[S_0,\ldots,S_{i-1}]$$, $$[A_{i+1},\ldots,A_{j}]$$ and $$[S_{i+1},\ldots,S_{j-1}]$$, and $$[A_{j+1},\ldots,A_{k}]$$ and $$[S_{j+1},\ldots,S_{k-1}]$$. One can check that for each connected component, we get one atom more than clique separators:

sage: G = graphs.PathGraph(3) * 3
sage: A, Sc = G.atoms_and_clique_separators()
sage: A
[{1, 2}, {0, 1}, {4, 5}, {3, 4}, {8, 7}, {6, 7}]
sage: Sc
[{1}, {}, {4}, {}, {7}]
sage: i , j = [i for i, s in enumerate(Sc) if not s]
sage: i, j
(1, 3)
sage: A[:i+1], Sc[:i]
([{1, 2}, {0, 1}], [{1}])
sage: A[i+1:j+1], Sc[i+1:j]
([{4, 5}, {3, 4}], [{4}])
sage: A[j+1:], Sc[j+1:]
([{8, 7}, {6, 7}], [{7}])
sage: I = [-1, i, j, len(Sc)]
sage: for i, j in zip(I[:-1], I[1:]):
....:     print(A[i+1:j+1], Sc[i+1:j])
[{1, 2}, {0, 1}] [{1}]
[{4, 5}, {3, 4}] [{4}]
[{8, 7}, {6, 7}] [{7}]
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
______{1}______
/              /
{1, 2}   ______{}______
/             /
{0, 1}   _____{4}_____
/            /
{4, 5}   ____{}_____
/          /
{3, 4}   __{7}__
/      /
{6, 7} {8, 7}

>>> from sage.all import *
>>> G = graphs.PathGraph(Integer(3)) * Integer(3)
>>> A, Sc = G.atoms_and_clique_separators()
>>> A
[{1, 2}, {0, 1}, {4, 5}, {3, 4}, {8, 7}, {6, 7}]
>>> Sc
[{1}, {}, {4}, {}, {7}]
>>> i , j = [i for i, s in enumerate(Sc) if not s]
>>> i, j
(1, 3)
>>> A[:i+Integer(1)], Sc[:i]
([{1, 2}, {0, 1}], [{1}])
>>> A[i+Integer(1):j+Integer(1)], Sc[i+Integer(1):j]
([{4, 5}, {3, 4}], [{4}])
>>> A[j+Integer(1):], Sc[j+Integer(1):]
([{8, 7}, {6, 7}], [{7}])
>>> I = [-Integer(1), i, j, len(Sc)]
>>> for i, j in zip(I[:-Integer(1)], I[Integer(1):]):
...     print(A[i+Integer(1):j+Integer(1)], Sc[i+Integer(1):j])
[{1, 2}, {0, 1}] [{1}]
[{4, 5}, {3, 4}] [{4}]
[{8, 7}, {6, 7}] [{7}]
>>> ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
______{1}______
/              /
{1, 2}   ______{}______
/             /
{0, 1}   _____{4}_____
/            /
{4, 5}   ____{}_____
/          /
{3, 4}   __{7}__
/      /
{6, 7} {8, 7}


Loops and multiple edges are ignored:

sage: G.allow_loops(True)
sage: G.add_edges([(u, u) for u in G])
sage: G.allow_multiple_edges(True)
sage: ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
______{1}______
/              /
{1, 2}   ______{}______
/             /
{0, 1}   _____{4}_____
/            /
{4, 5}   ____{}_____
/          /
{3, 4}   __{7}__
/      /
{6, 7} {8, 7}

>>> from sage.all import *
>>> G.allow_loops(True)
>>> G.add_edges([(u, u) for u in G])
>>> G.allow_multiple_edges(True)
>>> ascii_art(G.atoms_and_clique_separators(rooted_tree=True))
______{1}______
/              /
{1, 2}   ______{}______
/             /
{0, 1}   _____{4}_____
/            /
{4, 5}   ____{}_____
/          /
{3, 4}   __{7}__
/      /
{6, 7} {8, 7}


We can check that the returned list of separators is valid:

sage: G = graphs.RandomGNP(50, .1)
sage: while not G.is_connected():
....:     G = graphs.RandomGNP(50, .1)
sage: _, separators, _ = G.atoms_and_clique_separators(separators=True)
sage: for S in separators:
....:     H = G.copy()
....:     H.delete_vertices(S)
....:     if H.is_connected():
....:         raise ValueError("something goes wrong")

>>> from sage.all import *
>>> G = graphs.RandomGNP(Integer(50), RealNumber('.1'))
>>> while not G.is_connected():
...     G = graphs.RandomGNP(Integer(50), RealNumber('.1'))
>>> _, separators, _ = G.atoms_and_clique_separators(separators=True)
>>> for S in separators:
...     H = G.copy()
...     H.delete_vertices(S)
...     if H.is_connected():
...         raise ValueError("something goes wrong")

bandwidth(G, k=None)[source]#

Compute the bandwidth of an undirected graph.

For a definition of the bandwidth of a graph, see the documentation of the bandwidth module.

INPUT:

• G – a graph

• k – integer (default: None); set to an integer value to test whether $$bw(G)\leq k$$, or to None (default) to compute $$bw(G)$$

OUTPUT:

When $$k$$ is an integer value, the function returns either False or an ordering of cost $$\leq k$$.

When $$k$$ is equal to None, the function returns a pair (bw, ordering).

sage.graphs.generic_graph.GenericGraph.adjacency_matrix() – return the adjacency matrix from an ordering of the vertices.

EXAMPLES:

sage: from sage.graphs.graph_decompositions.bandwidth import bandwidth
sage: G = graphs.PetersenGraph()
sage: bandwidth(G,3)
False
sage: bandwidth(G)
(5, [0, 4, 5, 8, 1, 9, 3, 7, 6, 2])
sage: G.adjacency_matrix(vertices=[0, 4, 5, 8, 1, 9, 3, 7, 6, 2])               # needs sage.modules
[0 1 1 0 1 0 0 0 0 0]
[1 0 0 0 0 1 1 0 0 0]
[1 0 0 1 0 0 0 1 0 0]
[0 0 1 0 0 0 1 0 1 0]
[1 0 0 0 0 0 0 0 1 1]
[0 1 0 0 0 0 0 1 1 0]
[0 1 0 1 0 0 0 0 0 1]
[0 0 1 0 0 1 0 0 0 1]
[0 0 0 1 1 1 0 0 0 0]
[0 0 0 0 1 0 1 1 0 0]
sage: G = graphs.ChvatalGraph()
sage: bandwidth(G)
(6, [0, 5, 9, 4, 10, 1, 6, 11, 3, 8, 7, 2])
sage: G.adjacency_matrix(vertices=[0, 5, 9, 4, 10, 1, 6, 11, 3, 8, 7, 2])       # needs sage.modules
[0 0 1 1 0 1 1 0 0 0 0 0]
[0 0 0 1 1 1 0 1 0 0 0 0]
[1 0 0 0 1 0 0 1 1 0 0 0]
[1 1 0 0 0 0 0 0 1 1 0 0]
[0 1 1 0 0 0 1 0 0 1 0 0]
[1 1 0 0 0 0 0 0 0 0 1 1]
[1 0 0 0 1 0 0 1 0 0 0 1]
[0 1 1 0 0 0 1 0 0 0 1 0]
[0 0 1 1 0 0 0 0 0 0 1 1]
[0 0 0 1 1 0 0 0 0 0 1 1]
[0 0 0 0 0 1 0 1 1 1 0 0]
[0 0 0 0 0 1 1 0 1 1 0 0]

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.bandwidth import bandwidth
>>> G = graphs.PetersenGraph()
>>> bandwidth(G,Integer(3))
False
>>> bandwidth(G)
(5, [0, 4, 5, 8, 1, 9, 3, 7, 6, 2])
>>> G.adjacency_matrix(vertices=[Integer(0), Integer(4), Integer(5), Integer(8), Integer(1), Integer(9), Integer(3), Integer(7), Integer(6), Integer(2)])               # needs sage.modules
[0 1 1 0 1 0 0 0 0 0]
[1 0 0 0 0 1 1 0 0 0]
[1 0 0 1 0 0 0 1 0 0]
[0 0 1 0 0 0 1 0 1 0]
[1 0 0 0 0 0 0 0 1 1]
[0 1 0 0 0 0 0 1 1 0]
[0 1 0 1 0 0 0 0 0 1]
[0 0 1 0 0 1 0 0 0 1]
[0 0 0 1 1 1 0 0 0 0]
[0 0 0 0 1 0 1 1 0 0]
>>> G = graphs.ChvatalGraph()
>>> bandwidth(G)
(6, [0, 5, 9, 4, 10, 1, 6, 11, 3, 8, 7, 2])
>>> G.adjacency_matrix(vertices=[Integer(0), Integer(5), Integer(9), Integer(4), Integer(10), Integer(1), Integer(6), Integer(11), Integer(3), Integer(8), Integer(7), Integer(2)])       # needs sage.modules
[0 0 1 1 0 1 1 0 0 0 0 0]
[0 0 0 1 1 1 0 1 0 0 0 0]
[1 0 0 0 1 0 0 1 1 0 0 0]
[1 1 0 0 0 0 0 0 1 1 0 0]
[0 1 1 0 0 0 1 0 0 1 0 0]
[1 1 0 0 0 0 0 0 0 0 1 1]
[1 0 0 0 1 0 0 1 0 0 0 1]
[0 1 1 0 0 0 1 0 0 0 1 0]
[0 0 1 1 0 0 0 0 0 0 1 1]
[0 0 0 1 1 0 0 0 0 0 1 1]
[0 0 0 0 0 1 0 1 1 1 0 0]
[0 0 0 0 0 1 1 0 1 1 0 0]

bipartite_color()[source]#

Return 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.

>>> from sage.all import *
>>> graphs.CycleGraph(Integer(4)).bipartite_color()
{0: 1, 1: 0, 2: 1, 3: 0}
>>> graphs.CycleGraph(Integer(5)).bipartite_color()
Traceback (most recent call last):
...
RuntimeError: Graph is not bipartite.

bipartite_double(extended=False)[source]#

Return the (extended) bipartite double of this graph.

The bipartite double of a graph $$G$$ has vertex set $$\{ (v,0), (v,1) : v \in G\}$$ and for any edge $$(u, v)$$ in $$G$$ it has edges $$((u,0),(v,1))$$ and $$((u,1),(v,0))$$. Note that this is the tensor product of $$G$$ with $$K_2$$.

The extended bipartite double of $$G$$ is the bipartite double of $$G$$ after added all edges $$((v,0),(v,1))$$ for all vertices $$v$$.

INPUT:

• extended – boolean (default: False); Whether to return the extended bipartite double, or only the bipartite double (default)

OUTPUT:

A graph; self is left untouched.

EXAMPLES:

sage: G = graphs.PetersenGraph()
sage: H = G.bipartite_double()
sage: G == graphs.PetersenGraph()  # G is left invariant
True
sage: H.order() == 2 * G.order()
True
sage: H.size() == 2 * G.size()
True
sage: H.is_bipartite()
True
sage: H.bipartite_sets() == (set([(v, 0) for v in G]),
....: set([(v, 1) for v in G]))
True
sage: H.is_isomorphic(G.tensor_product(graphs.CompleteGraph(2)))
True

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> H = G.bipartite_double()
>>> G == graphs.PetersenGraph()  # G is left invariant
True
>>> H.order() == Integer(2) * G.order()
True
>>> H.size() == Integer(2) * G.size()
True
>>> H.is_bipartite()
True
>>> H.bipartite_sets() == (set([(v, Integer(0)) for v in G]),
... set([(v, Integer(1)) for v in G]))
True
>>> H.is_isomorphic(G.tensor_product(graphs.CompleteGraph(Integer(2))))
True


Behaviour with disconnected graphs:

sage: G1 = graphs.PetersenGraph()
sage: G2 = graphs.HoffmanGraph()
sage: G = G1.disjoint_union(G2)
sage: H = G.bipartite_double()
sage: H1 = G1.bipartite_double()
sage: H2 = G2.bipartite_double()
sage: H.is_isomorphic(H1.disjoint_union(H2))
True

>>> from sage.all import *
>>> G1 = graphs.PetersenGraph()
>>> G2 = graphs.HoffmanGraph()
>>> G = G1.disjoint_union(G2)
>>> H = G.bipartite_double()
>>> H1 = G1.bipartite_double()
>>> H2 = G2.bipartite_double()
>>> H.is_isomorphic(H1.disjoint_union(H2))
True


Wikipedia article Bipartite_double_cover, WolframAlpha Bipartite Double, [VDKT2016] p. 20 for the extended bipartite double.

bipartite_sets()[source]#

Return $$(X,Y)$$ where $$X$$ and $$Y$$ are the nodes in each bipartite set of graph $$G$$.

Fails with an error if graph is not bipartite.

EXAMPLES:

sage: graphs.CycleGraph(4).bipartite_sets()
({0, 2}, {1, 3})
sage: graphs.CycleGraph(5).bipartite_sets()
Traceback (most recent call last):
...
RuntimeError: Graph is not bipartite.

>>> from sage.all import *
>>> graphs.CycleGraph(Integer(4)).bipartite_sets()
({0, 2}, {1, 3})
>>> graphs.CycleGraph(Integer(5)).bipartite_sets()
Traceback (most recent call last):
...
RuntimeError: Graph is not bipartite.

bounded_outdegree_orientation(bound, solver, verbose=None, integrality_tolerance=False)[source]#

Computes an orientation of self such that every vertex $$v$$ has out-degree less than $$b(v)$$

INPUT:

• bound – Maximum bound on the out-degree. Can be of three different types :

• An integer $$k$$. In this case, computes an orientation whose maximum out-degree is less than $$k$$.

• A dictionary associating to each vertex its associated maximum out-degree.

• A function associating to each vertex its associated maximum out-degree.

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP 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.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

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 $$G$$, we create a DiGraph $$D$$ defined on $$E(G)\cup V(G)\cup \{s,t\}$$. We then link $$s$$ to all of $$V(G)$$ (these edges having a capacity equal to the bound associated to each element of $$V(G)$$), and all the elements of $$E(G)$$ to $$t$$ . We then link each $$v \in V(G)$$ to each of its incident edges in $$G$$. A maximum integer flow of value $$|E(G)|$$ corresponds to an admissible orientation of $$G$$. Otherwise, none exists.

EXAMPLES:

There is always an orientation of a graph $$G$$ such that a vertex $$v$$ has out-degree at most $$\lceil \frac {d(v)} 2 \rceil$$:

sage: g = graphs.RandomGNP(40, .4)
sage: b = lambda v: integer_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

>>> from sage.all import *
>>> g = graphs.RandomGNP(Integer(40), RealNumber('.4'))
>>> b = lambda v: integer_ceil(g.degree(v)/Integer(2))
>>> D = g.bounded_outdegree_orientation(b)
>>> 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

>>> from sage.all import *
>>> g = graphs.ChvatalGraph()
>>> D = g.bounded_outdegree_orientation(Integer(2))
>>> max(D.out_degree())
2


For any graph $$G$$, it is possible to compute an orientation such that the maximum out-degree is at most the maximum average degree of $$G$$ divided by 2. Anything less, though, is impossible.

sage: g = graphs.RandomGNP(40, .4) sage: mad = g.maximum_average_degree() # needs sage.numerical.mip

Hence this is possible

sage: d = g.bounded_outdegree_orientation(integer_ceil(mad/2))              # needs sage.numerical.mip

>>> from sage.all import *
>>> d = g.bounded_outdegree_orientation(integer_ceil(mad/Integer(2)))              # needs sage.numerical.mip


While this is not:

sage: try:                                                                  # needs sage.numerical.mip
....:     print("Error")
....: except ValueError:
....:     pass

>>> from sage.all import *
>>> try:                                                                  # needs sage.numerical.mip
...     print("Error")
... except ValueError:
...     pass

bridges(G, labels=True)[source]#

Return an iterator over the bridges (or cut edges).

A bridge is an edge whose deletion disconnects the undirected graph. A disconnected graph has no bridge.

INPUT:

• labels – boolean (default: True); if False, each bridge is a tuple $$(u, v)$$ of vertices

EXAMPLES:

sage: from sage.graphs.connectivity import bridges
sage: from sage.graphs.connectivity import is_connected
sage: g = 2 * graphs.PetersenGraph()
sage: is_connected(g)
True
sage: list(bridges(g))
[(1, 10, None)]
sage: list(g.bridges())
[(1, 10, None)]

>>> from sage.all import *
>>> from sage.graphs.connectivity import bridges
>>> from sage.graphs.connectivity import is_connected
>>> g = Integer(2) * graphs.PetersenGraph()
>>> is_connected(g)
True
>>> list(bridges(g))
[(1, 10, None)]
>>> list(g.bridges())
[(1, 10, None)]


Every edge of a tree is a bridge:

sage: g = graphs.RandomTree(100)
sage: sum(1 for _ in g.bridges()) == 99
True

>>> from sage.all import *
>>> g = graphs.RandomTree(Integer(100))
>>> sum(Integer(1) for _ in g.bridges()) == Integer(99)
True

center(by_weight=False, algorithm=None, weight_function=None, check_weight=True)[source]#

Return the set of vertices in the center of the graph.

The center is the set of vertices whose eccentricity is equal to the radius of the graph, i.e., achieving the minimum eccentricity.

For more information and examples on how to use input variables, see shortest_paths() and eccentricity()

INPUT:

• by_weight – boolean (default: False); if True, edge weights are taken into account; if False, all edges have weight 1

• algorithm – string (default: None); see method eccentricity() for the list of available algorithms

• weight_function – function (default: None); a function that takes as input an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l as a weight, if l is not None, else 1 as a weight.

• check_weight – boolean (default: True); if True, we check that the weight_function outputs a number for each edge

EXAMPLES:

Is Central African Republic in the center of Africa in graph theoretic sense? Yes:

sage: A = graphs.AfricaMap(continental=True)
sage: sorted(A.center())
['Cameroon', 'Central Africa']

>>> from sage.all import *
>>> A = graphs.AfricaMap(continental=True)
>>> sorted(A.center())
['Cameroon', 'Central Africa']


Some other graphs. Center can be the whole graph:

sage: G = graphs.DiamondGraph()
sage: G.center()
[1, 2]
sage: P = graphs.PetersenGraph()
sage: P.subgraph(P.center()) == P
True
sage: S = graphs.StarGraph(19)
sage: S.center()
[0]

>>> from sage.all import *
>>> G = graphs.DiamondGraph()
>>> G.center()
[1, 2]
>>> P = graphs.PetersenGraph()
>>> P.subgraph(P.center()) == P
True
>>> S = graphs.StarGraph(Integer(19))
>>> S.center()
[0]

centrality_degree(v=None)[source]#

Return the degree centrality of a vertex.

The degree centrality of a vertex $$v$$ is its degree, divided by $$|V(G)|-1$$. For more information, see the Wikipedia article Centrality.

INPUT:

• v – a vertex (default: None); set to None (default) to get a dictionary associating each vertex with its centrality degree.

EXAMPLES:

sage: (graphs.ChvatalGraph()).centrality_degree()
{0: 4/11, 1: 4/11, 2: 4/11, 3: 4/11,  4: 4/11,  5: 4/11,
6: 4/11, 7: 4/11, 8: 4/11, 9: 4/11, 10: 4/11, 11: 4/11}
sage: D = graphs.DiamondGraph()
sage: D.centrality_degree()
{0: 2/3, 1: 1, 2: 1, 3: 2/3}
sage: D.centrality_degree(v=1)
1

>>> from sage.all import *
>>> (graphs.ChvatalGraph()).centrality_degree()
{0: 4/11, 1: 4/11, 2: 4/11, 3: 4/11,  4: 4/11,  5: 4/11,
6: 4/11, 7: 4/11, 8: 4/11, 9: 4/11, 10: 4/11, 11: 4/11}
>>> D = graphs.DiamondGraph()
>>> D.centrality_degree()
{0: 2/3, 1: 1, 2: 1, 3: 2/3}
>>> D.centrality_degree(v=Integer(1))
1

cheeger_constant(g)[source]#

Return the cheeger constant of the graph.

The Cheeger constant of a graph $$G = (V,E)$$ is the minimum of $$|\partial S| / |Vol(S)|$$ where $$Vol(S)$$ is the sum of degrees of element in $$S$$, $$\partial S$$ is the edge boundary of $$S$$ (number of edges with one end in $$S$$ and one end in $$V \setminus S$$) and the minimum is taken over all non-empty subsets $$S$$ of vertices so that $$|Vol(S)| \leq |E|$$.

Alternative but similar quantities can be obtained via the methods edge_isoperimetric_number() and vertex_isoperimetric_number().

EXAMPLES:

sage: graphs.PetersenGraph().cheeger_constant()
1/3

>>> from sage.all import *
>>> graphs.PetersenGraph().cheeger_constant()
1/3


The Cheeger constant of a cycle on $$n$$ vertices is $$1/\lfloor n/2 \rfloor$$:

sage: [graphs.CycleGraph(k).cheeger_constant() for k in range(2,10)]
[1, 1, 1/2, 1/2, 1/3, 1/3, 1/4, 1/4]

>>> from sage.all import *
>>> [graphs.CycleGraph(k).cheeger_constant() for k in range(Integer(2),Integer(10))]
[1, 1, 1/2, 1/2, 1/3, 1/3, 1/4, 1/4]


The Cheeger constant of a complete graph on $$n$$ vertices is $$\lceil n/2 \rceil / (n-1)$$:

sage: [graphs.CompleteGraph(k).cheeger_constant() for k in range(2,10)]
[1, 1, 2/3, 3/4, 3/5, 2/3, 4/7, 5/8]

>>> from sage.all import *
>>> [graphs.CompleteGraph(k).cheeger_constant() for k in range(Integer(2),Integer(10))]
[1, 1, 2/3, 3/4, 3/5, 2/3, 4/7, 5/8]


For complete bipartite:

sage: [graphs.CompleteBipartiteGraph(i,j).cheeger_constant() for i in range(2,7) for j in range(2, i)]
[3/5, 1/2, 3/5, 5/9, 4/7, 5/9, 1/2, 5/9, 1/2, 5/9]

>>> from sage.all import *
>>> [graphs.CompleteBipartiteGraph(i,j).cheeger_constant() for i in range(Integer(2),Integer(7)) for j in range(Integer(2), i)]
[3/5, 1/2, 3/5, 5/9, 4/7, 5/9, 1/2, 5/9, 1/2, 5/9]


More examples:

sage: G = Graph([(0, 1), (0, 3), (0, 8), (1, 4), (1, 6), (2, 4), (2, 7), (2, 9),
....:            (3, 6), (3, 8), (4, 9), (5, 6), (5, 7), (5, 8), (7, 9)])
sage: G.cheeger_constant()
1/6

sage: G = Graph([(0, 1), (0, 2), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (3, 4), (3, 5)])
sage: G.cheeger_constant()
1/2

sage: Graph([[1,2,3,4],[(1,2),(3,4)]]).cheeger_constant()
0

>>> from sage.all import *
>>> G = Graph([(Integer(0), Integer(1)), (Integer(0), Integer(3)), (Integer(0), Integer(8)), (Integer(1), Integer(4)), (Integer(1), Integer(6)), (Integer(2), Integer(4)), (Integer(2), Integer(7)), (Integer(2), Integer(9)),
...            (Integer(3), Integer(6)), (Integer(3), Integer(8)), (Integer(4), Integer(9)), (Integer(5), Integer(6)), (Integer(5), Integer(7)), (Integer(5), Integer(8)), (Integer(7), Integer(9))])
>>> G.cheeger_constant()
1/6

>>> G = Graph([(Integer(0), Integer(1)), (Integer(0), Integer(2)), (Integer(1), Integer(2)), (Integer(1), Integer(3)), (Integer(1), Integer(4)), (Integer(1), Integer(5)), (Integer(2), Integer(3)), (Integer(3), Integer(4)), (Integer(3), Integer(5))])
>>> G.cheeger_constant()
1/2

>>> Graph([[Integer(1),Integer(2),Integer(3),Integer(4)],[(Integer(1),Integer(2)),(Integer(3),Integer(4))]]).cheeger_constant()
0

chromatic_index(solver, verbose=None, integrality_tolerance=0)[source]#

Return the chromatic index of the graph.

The chromatic index is the minimal number of colors needed to properly color the edges of the graph.

INPUT:

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP 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.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

This method is a frontend for method sage.graphs.graph_coloring.edge_coloring() that uses a mixed integer-linear programming formulation to compute the chromatic index.

EXAMPLES:

The clique $$K_n$$ has chromatic index $$n$$ when $$n$$ is odd and $$n-1$$ when $$n$$ is even:

sage: graphs.CompleteGraph(4).chromatic_index()
3
sage: graphs.CompleteGraph(5).chromatic_index()
5
sage: graphs.CompleteGraph(6).chromatic_index()
5

>>> from sage.all import *
>>> graphs.CompleteGraph(Integer(4)).chromatic_index()
3
>>> graphs.CompleteGraph(Integer(5)).chromatic_index()
5
>>> graphs.CompleteGraph(Integer(6)).chromatic_index()
5


The path $$P_n$$ with $$n \geq 2$$ has chromatic index 2:

sage: graphs.PathGraph(5).chromatic_index()                                 # needs sage.numerical.mip
2

>>> from sage.all import *
>>> graphs.PathGraph(Integer(5)).chromatic_index()                                 # needs sage.numerical.mip
2


The windmill graph with parameters $$k,n$$ has chromatic index $$(k-1)n$$:

sage: k,n = 3,4
sage: G = graphs.WindmillGraph(k,n)
sage: G.chromatic_index() == (k-1)*n                                        # needs sage.numerical.mip
True

>>> from sage.all import *
>>> k,n = Integer(3),Integer(4)
>>> G = graphs.WindmillGraph(k,n)
>>> G.chromatic_index() == (k-Integer(1))*n                                        # needs sage.numerical.mip
True

chromatic_number(algorithm, solver='DLX', verbose=None, integrality_tolerance=0)[source]#

Return the minimal number of colors needed to color the vertices of the graph.

INPUT:

• algorithm – string (default: "DLX"); one of the following algorithms:

• "DLX" (default): the chromatic number is computed using the dancing link algorithm. It is inefficient speedwise to compute the chromatic number through the dancing link algorithm because this algorithm computes all the possible colorings to check that one exists.

• "CP": the chromatic number is computed using the coefficients of the chromatic polynomial. Again, this method is inefficient in terms of speed and it only useful for small graphs.

• "MILP": the chromatic number is computed using a mixed integer linear program. The performance of this implementation is affected by whether optional MILP solvers have been installed (see the MILP module, or Sage’s tutorial on Linear Programming).

• "parallel": all the above algorithms are executed in parallel and the result is returned as soon as one algorithm ends. Observe that the speed of the above algorithms depends on the size and structure of the graph.

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP 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.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

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")                                    # needs sage.libs.flint
3
sage: G.chromatic_number(algorithm="parallel")
3

>>> from sage.all import *
>>> G = Graph({Integer(0): [Integer(1), Integer(2), Integer(3)], Integer(1): [Integer(2)]})
>>> G.chromatic_number(algorithm="DLX")
3
>>> G.chromatic_number(algorithm="MILP")
3
>>> G.chromatic_number(algorithm="CP")                                    # needs sage.libs.flint
3
>>> G.chromatic_number(algorithm="parallel")
3


A bipartite graph has (by definition) chromatic number 2:

sage: graphs.RandomBipartite(50,50,0.7).chromatic_number()                  # needs numpy
2

>>> from sage.all import *
>>> graphs.RandomBipartite(Integer(50),Integer(50),RealNumber('0.7')).chromatic_number()                  # needs numpy
2


A complete multipartite graph with $$k$$ parts has chromatic number $$k$$:

sage: all(graphs.CompleteMultipartiteGraph([5]*i).chromatic_number() == i
....:     for i in range(2, 5))
True

>>> from sage.all import *
>>> all(graphs.CompleteMultipartiteGraph([Integer(5)]*i).chromatic_number() == i
...     for i in range(Integer(2), Integer(5)))
True


The complete graph has the largest chromatic number from all the graphs of order $$n$$. Namely its chromatic number is $$n$$:

sage: all(graphs.CompleteGraph(i).chromatic_number() == i for i in range(10))
True

>>> from sage.all import *
>>> all(graphs.CompleteGraph(i).chromatic_number() == i for i in range(Integer(10)))
True


The Kneser graph with parameters $$(n, 2)$$ for $$n > 3$$ has chromatic number $$n-2$$:

sage: all(graphs.KneserGraph(i,2).chromatic_number() == i-2 for i in range(4,6))
True

>>> from sage.all import *
>>> all(graphs.KneserGraph(i,Integer(2)).chromatic_number() == i-Integer(2) for i in range(Integer(4),Integer(6)))
True


The Flower Snark graph has chromatic index 4 hence its line graph has chromatic number 4:

sage: graphs.FlowerSnark().line_graph().chromatic_number()
4

>>> from sage.all import *
>>> graphs.FlowerSnark().line_graph().chromatic_number()
4

chromatic_polynomial(G, return_tree_basis=False, algorithm='C', cache=None)[source]#

Compute 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’’.

INPUT:

• G – a Sage graph

• return_tree_basis – boolean (default: False); not used yet

• algorithm – string (default: "C"); the algorithm to use among

• "C", an implementation in C by Robert Miller and Gordon Royle.

• "Python", an implementation in Python using caching to avoid recomputing the chromatic polynomial of a graph that has already been seen. This seems faster on some dense graphs.

• cache – dictionary (default: None); this parameter is used only for algorithm "Python". It is a dictionary keyed by canonical labelings of graphs and used to cache the chromatic polynomials of the graphs generated by the algorithm. In other words, it avoids computing twice the chromatic polynomial of isometric graphs. One will be created automatically if not provided.

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

>>> from sage.all import *
>>> graphs.CycleGraph(Integer(4)).chromatic_polynomial()
x^4 - 4*x^3 + 6*x^2 - 3*x
>>> graphs.CycleGraph(Integer(3)).chromatic_polynomial()
x^3 - 3*x^2 + 2*x
>>> graphs.CubeGraph(Integer(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
>>> 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
>>> graphs.CompleteBipartiteGraph(Integer(3),Integer(3)).chromatic_polynomial()
x^6 - 9*x^5 + 36*x^4 - 75*x^3 + 78*x^2 - 31*x
>>> for i in range(Integer(2),Integer(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
>>> graphs.CycleGraph(Integer(5)).chromatic_polynomial().factor()
(x - 2) * (x - 1) * x * (x^2 - 2*x + 2)
>>> graphs.OctahedralGraph().chromatic_polynomial().factor()
(x - 2) * (x - 1) * x * (x^3 - 9*x^2 + 29*x - 32)
>>> graphs.WheelGraph(Integer(5)).chromatic_polynomial().factor()
(x - 2) * (x - 1) * x * (x^2 - 5*x + 7)
>>> graphs.WheelGraph(Integer(6)).chromatic_polynomial().factor()
(x - 3) * (x - 2) * (x - 1) * x * (x^2 - 4*x + 5)
>>> __tmp__=var("x"); C = symbolic_expression(graphs.LCFGraph(Integer(24), [Integer(12),Integer(7),-Integer(7)], Integer(8)).chromatic_polynomial()  ).function(x)# long time (6s on sage.math, 2011)
>>> C(Integer(2))  # long time
0


By definition, the chromatic number of a graph G is the least integer k such that the chromatic polynomial of G is strictly positive at k:

sage: G = graphs.PetersenGraph()
sage: P = G.chromatic_polynomial()
sage: min(i for i in range(11) if P(i) > 0) == G.chromatic_number()
True

sage: G = graphs.RandomGNP(10,0.7)
sage: P = G.chromatic_polynomial()
sage: min(i for i in range(11) if P(i) > 0) == G.chromatic_number()
True

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> P = G.chromatic_polynomial()
>>> min(i for i in range(Integer(11)) if P(i) > Integer(0)) == G.chromatic_number()
True

>>> G = graphs.RandomGNP(Integer(10),RealNumber('0.7'))
>>> P = G.chromatic_polynomial()
>>> min(i for i in range(Integer(11)) if P(i) > Integer(0)) == G.chromatic_number()
True


Check that algorithms "C" and "Python" return the same results:

sage: G = graphs.RandomGNP(8, randint(1, 9)*0.1)
sage: c = G.chromatic_polynomial(algorithm='C')
sage: p = G.chromatic_polynomial(algorithm='Python')
sage: c == p
True

>>> from sage.all import *
>>> G = graphs.RandomGNP(Integer(8), randint(Integer(1), Integer(9))*RealNumber('0.1'))
>>> c = G.chromatic_polynomial(algorithm='C')
>>> p = G.chromatic_polynomial(algorithm='Python')
>>> c == p
True

chromatic_quasisymmetric_function(t=None, R=None)[source]#

Return the chromatic quasisymmetric function of self.

Let $$G$$ be a graph whose vertex set is totally ordered. The chromatic quasisymmetric function $$X_G(t)$$ was first described in [SW2012]. We use the equivalent definition given in [BC2018]:

$X_G(t) = \sum_{\sigma=(\sigma_1,\ldots,\sigma_n)} t^{\operatorname{asc}(\sigma)} M_{|\sigma_1|,\ldots,|\sigma_n|},$

where we sum over all ordered set partitions of the vertex set of $$G$$ such that each block $$\sigma_i$$ is an independent (i.e., stable) set of $$G$$, and where $$\operatorname{asc}(\sigma)$$ denotes the number of edges $$\{u, v\}$$ of $$G$$ such that $$u < v$$ and $$v$$ appears in a later part of $$\sigma$$ than $$u$$.

INPUT:

• t – (optional) the parameter $$t$$; uses the variable $$t$$ in $$\ZZ[t]$$ by default

• R – (optional) the base ring for the quasisymmetric functions; uses the parent of $$t$$ by default

EXAMPLES:

sage: # needs sage.combinat sage.modules
sage: G = Graph([[1,2,3], [[1,3], [2,3]]])
sage: G.chromatic_quasisymmetric_function()
(2*t^2+2*t+2)*M[1, 1, 1] + M[1, 2] + t^2*M[2, 1]
sage: G = graphs.PathGraph(4)
sage: XG = G.chromatic_quasisymmetric_function(); XG
(t^3+11*t^2+11*t+1)*M[1, 1, 1, 1] + (3*t^2+3*t)*M[1, 1, 2]
+ (3*t^2+3*t)*M[1, 2, 1] + (3*t^2+3*t)*M[2, 1, 1]
+ (t^2+t)*M[2, 2]
sage: XG.to_symmetric_function()
(t^3+11*t^2+11*t+1)*m[1, 1, 1, 1] + (3*t^2+3*t)*m[2, 1, 1]
+ (t^2+t)*m[2, 2]
sage: G = graphs.CompleteGraph(4)
sage: G.chromatic_quasisymmetric_function()
(t^6+3*t^5+5*t^4+6*t^3+5*t^2+3*t+1)*M[1, 1, 1, 1]

>>> from sage.all import *
>>> # needs sage.combinat sage.modules
>>> G = Graph([[Integer(1),Integer(2),Integer(3)], [[Integer(1),Integer(3)], [Integer(2),Integer(3)]]])
>>> G.chromatic_quasisymmetric_function()
(2*t^2+2*t+2)*M[1, 1, 1] + M[1, 2] + t^2*M[2, 1]
>>> G = graphs.PathGraph(Integer(4))
>>> XG = G.chromatic_quasisymmetric_function(); XG
(t^3+11*t^2+11*t+1)*M[1, 1, 1, 1] + (3*t^2+3*t)*M[1, 1, 2]
+ (3*t^2+3*t)*M[1, 2, 1] + (3*t^2+3*t)*M[2, 1, 1]
+ (t^2+t)*M[2, 2]
>>> XG.to_symmetric_function()
(t^3+11*t^2+11*t+1)*m[1, 1, 1, 1] + (3*t^2+3*t)*m[2, 1, 1]
+ (t^2+t)*m[2, 2]
>>> G = graphs.CompleteGraph(Integer(4))
>>> G.chromatic_quasisymmetric_function()
(t^6+3*t^5+5*t^4+6*t^3+5*t^2+3*t+1)*M[1, 1, 1, 1]


Not all chromatic quasisymmetric functions are symmetric:

sage: G = Graph([[1,2], [1,5], [3,4], [3,5]])
sage: G.chromatic_quasisymmetric_function().is_symmetric()                  # needs sage.combinat sage.modules
False

>>> from sage.all import *
>>> G = Graph([[Integer(1),Integer(2)], [Integer(1),Integer(5)], [Integer(3),Integer(4)], [Integer(3),Integer(5)]])
>>> G.chromatic_quasisymmetric_function().is_symmetric()                  # needs sage.combinat sage.modules
False


We check that at $$t = 1$$, we recover the usual chromatic symmetric function:

sage: p = SymmetricFunctions(QQ).p()                                        # needs sage.combinat sage.modules
sage: G = graphs.CycleGraph(5)
sage: XG = G.chromatic_quasisymmetric_function(t=1); XG                     # needs sage.combinat sage.modules
120*M[1, 1, 1, 1, 1] + 30*M[1, 1, 1, 2] + 30*M[1, 1, 2, 1]
+ 30*M[1, 2, 1, 1] + 10*M[1, 2, 2] + 30*M[2, 1, 1, 1]
+ 10*M[2, 1, 2] + 10*M[2, 2, 1]
sage: p(XG.to_symmetric_function())                                         # needs sage.combinat sage.modules
p[1, 1, 1, 1, 1] - 5*p[2, 1, 1, 1] + 5*p[2, 2, 1]
+ 5*p[3, 1, 1] - 5*p[3, 2] - 5*p[4, 1] + 4*p[5]

sage: G = graphs.ClawGraph()
sage: XG = G.chromatic_quasisymmetric_function(t=1); XG                     # needs sage.combinat sage.modules
24*M[1, 1, 1, 1] + 6*M[1, 1, 2] + 6*M[1, 2, 1] + M[1, 3]
+ 6*M[2, 1, 1] + M[3, 1]
sage: p(XG.to_symmetric_function())                                         # needs sage.combinat sage.modules
p[1, 1, 1, 1] - 3*p[2, 1, 1] + 3*p[3, 1] - p[4]

>>> from sage.all import *
>>> p = SymmetricFunctions(QQ).p()                                        # needs sage.combinat sage.modules
>>> G = graphs.CycleGraph(Integer(5))
>>> XG = G.chromatic_quasisymmetric_function(t=Integer(1)); XG                     # needs sage.combinat sage.modules
120*M[1, 1, 1, 1, 1] + 30*M[1, 1, 1, 2] + 30*M[1, 1, 2, 1]
+ 30*M[1, 2, 1, 1] + 10*M[1, 2, 2] + 30*M[2, 1, 1, 1]
+ 10*M[2, 1, 2] + 10*M[2, 2, 1]
>>> p(XG.to_symmetric_function())                                         # needs sage.combinat sage.modules
p[1, 1, 1, 1, 1] - 5*p[2, 1, 1, 1] + 5*p[2, 2, 1]
+ 5*p[3, 1, 1] - 5*p[3, 2] - 5*p[4, 1] + 4*p[5]

>>> G = graphs.ClawGraph()
>>> XG = G.chromatic_quasisymmetric_function(t=Integer(1)); XG                     # needs sage.combinat sage.modules
24*M[1, 1, 1, 1] + 6*M[1, 1, 2] + 6*M[1, 2, 1] + M[1, 3]
+ 6*M[2, 1, 1] + M[3, 1]
>>> p(XG.to_symmetric_function())                                         # needs sage.combinat sage.modules
p[1, 1, 1, 1] - 3*p[2, 1, 1] + 3*p[3, 1] - p[4]

chromatic_symmetric_function(R=None)[source]#

Return the chromatic symmetric function of self.

Let $$G$$ be a graph. The chromatic symmetric function $$X_G$$ was described in [Sta1995], specifically Theorem 2.5 states that

$X_G = \sum_{F \subseteq E(G)} (-1)^{|F|} p_{\lambda(F)},$

where $$\lambda(F)$$ is the partition of the sizes of the connected components of the subgraph induced by the edges $$F$$ and $$p_{\mu}$$ is the powersum symmetric function.

INPUT:

• R – (optional) the base ring for the symmetric functions; this uses $$\ZZ$$ by default

ALGORITHM:

We traverse a binary tree whose leaves correspond to subsets of edges, and whose internal vertices at depth $$d$$ correspond to a choice of whether to include the $$d$$-th edge in a given subset. The components of the induced subgraph are incrementally updated using a disjoint-set forest. If the next edge would introduce a cycle to the subset, we prune the branch as the terms produced by the two subtrees cancel in this case.

EXAMPLES:

sage: s = SymmetricFunctions(ZZ).s()                                        # needs sage.combinat sage.modules
sage: G = graphs.CycleGraph(5)
sage: XG = G.chromatic_symmetric_function(); XG                             # needs sage.combinat sage.modules
p[1, 1, 1, 1, 1] - 5*p[2, 1, 1, 1] + 5*p[2, 2, 1]
+ 5*p[3, 1, 1] - 5*p[3, 2] - 5*p[4, 1] + 4*p[5]
sage: s(XG)                                                                 # needs sage.combinat sage.modules
30*s[1, 1, 1, 1, 1] + 10*s[2, 1, 1, 1] + 10*s[2, 2, 1]

>>> from sage.all import *
>>> s = SymmetricFunctions(ZZ).s()                                        # needs sage.combinat sage.modules
>>> G = graphs.CycleGraph(Integer(5))
>>> XG = G.chromatic_symmetric_function(); XG                             # needs sage.combinat sage.modules
p[1, 1, 1, 1, 1] - 5*p[2, 1, 1, 1] + 5*p[2, 2, 1]
+ 5*p[3, 1, 1] - 5*p[3, 2] - 5*p[4, 1] + 4*p[5]
>>> s(XG)                                                                 # needs sage.combinat sage.modules
30*s[1, 1, 1, 1, 1] + 10*s[2, 1, 1, 1] + 10*s[2, 2, 1]


Not all graphs have a positive Schur expansion:

sage: G = graphs.ClawGraph()
sage: XG = G.chromatic_symmetric_function(); XG                             # needs sage.combinat sage.modules
p[1, 1, 1, 1] - 3*p[2, 1, 1] + 3*p[3, 1] - p[4]
sage: s(XG)                                                                 # needs sage.combinat sage.modules
8*s[1, 1, 1, 1] + 5*s[2, 1, 1] - s[2, 2] + s[3, 1]

>>> from sage.all import *
>>> G = graphs.ClawGraph()
>>> XG = G.chromatic_symmetric_function(); XG                             # needs sage.combinat sage.modules
p[1, 1, 1, 1] - 3*p[2, 1, 1] + 3*p[3, 1] - p[4]
>>> s(XG)                                                                 # needs sage.combinat sage.modules
8*s[1, 1, 1, 1] + 5*s[2, 1, 1] - s[2, 2] + s[3, 1]


We show that given a triangle $$\{e_1, e_2, e_3\}$$, we have $$X_G = X_{G - e_1} + X_{G - e_2} - X_{G - e_1 - e_2}$$:

sage: # needs sage.combinat sage.modules
sage: G = Graph([[1,2],[1,3],[2,3]])
sage: XG = G.chromatic_symmetric_function()
sage: G1 = copy(G)
sage: G1.delete_edge([1,2])
sage: XG1 = G1.chromatic_symmetric_function()
sage: G2 = copy(G)
sage: G2.delete_edge([1,3])
sage: XG2 = G2.chromatic_symmetric_function()
sage: G3 = copy(G1)
sage: G3.delete_edge([1,3])
sage: XG3 = G3.chromatic_symmetric_function()
sage: XG == XG1 + XG2 - XG3
True

>>> from sage.all import *
>>> # needs sage.combinat sage.modules
>>> G = Graph([[Integer(1),Integer(2)],[Integer(1),Integer(3)],[Integer(2),Integer(3)]])
>>> XG = G.chromatic_symmetric_function()
>>> G1 = copy(G)
>>> G1.delete_edge([Integer(1),Integer(2)])
>>> XG1 = G1.chromatic_symmetric_function()
>>> G2 = copy(G)
>>> G2.delete_edge([Integer(1),Integer(3)])
>>> XG2 = G2.chromatic_symmetric_function()
>>> G3 = copy(G1)
>>> G3.delete_edge([Integer(1),Integer(3)])
>>> XG3 = G3.chromatic_symmetric_function()
>>> XG == XG1 + XG2 - XG3
True

cleave(G, cut_vertices=None, virtual_edges=True, solver=None, verbose=0, integrality_tolerance=0.001)[source]#

Return the connected subgraphs separated by the input vertex cut.

Given a connected (multi)graph $$G$$ and a vertex cut $$X$$, this method computes the list of subgraphs of $$G$$ induced by each connected component $$c$$ of $$G\setminus X$$ plus $$X$$, i.e., $$G[c\cup X]$$.

INPUT:

• G – a Graph.

• cut_vertices – iterable container of vertices (default: None); a set of vertices representing a vertex cut of G. If no vertex cut is given, the method will compute one via a call to vertex_connectivity().

• virtual_edges – boolean (default: True); whether to add virtual edges to the sides of the cut or not. A virtual edge is an edge between a pair of vertices of the cut that are not connected by an edge in G.

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP 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.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

OUTPUT: A triple $$(S, C, f)$$, where

• $$S$$ is a list of the graphs that are sides of the vertex cut.

• $$C$$ is the graph of the cocycles. For each pair of vertices of the cut, if there exists an edge between them, $$C$$ has one copy of each edge connecting them in G per sides of the cut plus one extra copy. Furthermore, when virtual_edges == True, if a pair of vertices of the cut is not connected by an edge in G, then it has one virtual edge between them per sides of the cut.

• $$f$$ is the complement of the subgraph of G induced by the vertex cut. Hence, its vertex set is the vertex cut, and its edge set is the set of virtual edges (i.e., edges between pairs of vertices of the cut that are not connected by an edge in G). When virtual_edges == False, the edge set is empty.

EXAMPLES:

If there is an edge between cut vertices:

sage: from sage.graphs.connectivity import cleave
sage: G = Graph(2)
sage: for _ in range(3):
sage: S1,C1,f1 = cleave(G, cut_vertices=[0, 1])
sage: [g.order() for g in S1]
[4, 4, 4]
sage: C1.order(), C1.size()
(2, 4)
sage: f1.vertices(sort=True), f1.edges(sort=True)
([0, 1], [])

>>> from sage.all import *
>>> from sage.graphs.connectivity import cleave
>>> G = Graph(Integer(2))
>>> for _ in range(Integer(3)):
>>> S1,C1,f1 = cleave(G, cut_vertices=[Integer(0), Integer(1)])
>>> [g.order() for g in S1]
[4, 4, 4]
>>> C1.order(), C1.size()
(2, 4)
>>> f1.vertices(sort=True), f1.edges(sort=True)
([0, 1], [])


If virtual_edges == False and there is an edge between cut vertices:

sage: G.subgraph([0, 1]).complement() == Graph([[0, 1], []])
True
sage: S2,C2,f2 = cleave(G, cut_vertices=[0, 1], virtual_edges=False)
sage: (S1 == S2, C1 == C2, f1 == f2)
(True, True, True)

>>> from sage.all import *
>>> G.subgraph([Integer(0), Integer(1)]).complement() == Graph([[Integer(0), Integer(1)], []])
True
>>> S2,C2,f2 = cleave(G, cut_vertices=[Integer(0), Integer(1)], virtual_edges=False)
>>> (S1 == S2, C1 == C2, f1 == f2)
(True, True, True)


If cut vertices doesn’t have edge between them:

sage: G.delete_edge(0, 1)
sage: S1,C1,f1 = cleave(G, cut_vertices=[0, 1])
sage: [g.order() for g in S1]
[4, 4, 4]
sage: C1.order(), C1.size()
(2, 3)
sage: f1.vertices(sort=True), f1.edges(sort=True)
([0, 1], [(0, 1, None)])

>>> from sage.all import *
>>> G.delete_edge(Integer(0), Integer(1))
>>> S1,C1,f1 = cleave(G, cut_vertices=[Integer(0), Integer(1)])
>>> [g.order() for g in S1]
[4, 4, 4]
>>> C1.order(), C1.size()
(2, 3)
>>> f1.vertices(sort=True), f1.edges(sort=True)
([0, 1], [(0, 1, None)])


If virtual_edges == False and the cut vertices are not connected by an edge:

sage: G.subgraph([0, 1]).complement() == Graph([[0, 1], []])
False
sage: S2,C2,f2 = cleave(G, cut_vertices=[0, 1], virtual_edges=False)
sage: [g.order() for g in S2]
[4, 4, 4]
sage: C2.order(), C2.size()
(2, 0)
sage: f2.vertices(sort=True), f2.edges(sort=True)
([0, 1], [])
sage: (S1 == S2, C1 == C2, f1 == f2)
(False, False, False)

>>> from sage.all import *
>>> G.subgraph([Integer(0), Integer(1)]).complement() == Graph([[Integer(0), Integer(1)], []])
False
>>> S2,C2,f2 = cleave(G, cut_vertices=[Integer(0), Integer(1)], virtual_edges=False)
>>> [g.order() for g in S2]
[4, 4, 4]
>>> C2.order(), C2.size()
(2, 0)
>>> f2.vertices(sort=True), f2.edges(sort=True)
([0, 1], [])
>>> (S1 == S2, C1 == C2, f1 == f2)
(False, False, False)


If $$G$$ is a biconnected multigraph:

sage: G = graphs.CompleteBipartiteGraph(2, 3)
sage: G.allow_multiple_edges(True)
sage: G.add_edges([(0, 1), (0, 1), (0, 1)])
sage: S,C,f = cleave(G, cut_vertices=[0, 1])
sage: for g in S:
....:     print(g.edges(sort=True, labels=0))
[(0, 1), (0, 1), (0, 1), (0, 2), (0, 2), (0, 3), (0, 3), (1, 2), (1, 2), (1, 3), (1, 3), (2, 3), (2, 3)]
[(0, 1), (0, 1), (0, 1), (0, 4), (0, 4), (1, 4), (1, 4)]

>>> from sage.all import *
>>> G = graphs.CompleteBipartiteGraph(Integer(2), Integer(3))
>>> G.allow_multiple_edges(True)
>>> G.add_edges([(Integer(0), Integer(1)), (Integer(0), Integer(1)), (Integer(0), Integer(1))])
>>> S,C,f = cleave(G, cut_vertices=[Integer(0), Integer(1)])
>>> for g in S:
...     print(g.edges(sort=True, labels=Integer(0)))
[(0, 1), (0, 1), (0, 1), (0, 2), (0, 2), (0, 3), (0, 3), (1, 2), (1, 2), (1, 3), (1, 3), (2, 3), (2, 3)]
[(0, 1), (0, 1), (0, 1), (0, 4), (0, 4), (1, 4), (1, 4)]

clique_complex()[source]#

Return 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

>>> from sage.all import *
>>> g = Graph({Integer(0):[Integer(1),Integer(2)],Integer(1):[Integer(2)],Integer(4):[]})
>>> g.clique_complex()
Simplicial complex with vertex set (0, 1, 2, 4) and facets {(4,), (0, 1, 2)}

>>> h = Graph({Integer(0):[Integer(1),Integer(2),Integer(3),Integer(4)],Integer(1):[Integer(2),Integer(3),Integer(4)],Integer(2):[Integer(3)]})
>>> x = h.clique_complex()
>>> x
Simplicial complex with vertex set (0, 1, 2, 3, 4) and facets {(0, 1, 4), (0, 1, 2, 3)}
>>> i = x.graph()
>>> i==h
True
>>> x==i.clique_complex()
True

clique_maximum(algorithm, solver='Cliquer', verbose=None, integrality_tolerance=0)[source]#

Return the vertex set of a maximal order complete subgraph.

INPUT:

• algorithm – the algorithm to be used :

• If algorithm = "Cliquer" (default), wraps the C program Cliquer [NO2003].

• If algorithm = "MILP", the problem is solved through a Mixed Integer Linear Program.

• If algorithm = "mcqd", uses the MCQD solver (http://www.sicmm.org/~konc/maxclique/). Note that the MCQD package must be installed.

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP 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.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

Parameters solver and verbose are used only when algorithm="MILP".

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 [NO2003].

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]

>>> from sage.all import *
>>> C = graphs.PetersenGraph()
>>> C.clique_maximum()
[7, 9]
>>> C = Graph('DJ{')
>>> C.clique_maximum()
[1, 2, 3, 4]


Through a Linear Program:

sage: len(C.clique_maximum(algorithm="MILP"))
4

>>> from sage.all import *
>>> len(C.clique_maximum(algorithm="MILP"))
4

clique_number(algorithm, cliques='Cliquer', solver=None, verbose=None, integrality_tolerance=0)[source]#

Return the order of the largest clique of the graph

This is also called as 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", wraps the C program Cliquer [NO2003].

• If algorithm = "networkx", uses the NetworkX’s implementation of the Bron and Kerbosch Algorithm [BK1973].

• If algorithm = "MILP", the problem is solved through a Mixed Integer Linear Program.

• If algorithm = "mcqd", uses the MCQD solver (http://insilab.org/maxclique/). Note that the MCQD package must be installed.

• cliques – an optional list of cliques that can be input if already computed. Ignored unless algorithm=="networkx".

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP 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.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

ALGORITHM:

This function is based on Cliquer [NO2003] and [BK1973].

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])                                                 # needs sage.plot
sage: G.clique_number()
3

>>> from sage.all import *
>>> C = Graph('DJ{')
>>> C.clique_number()
4
>>> G = Graph({Integer(0):[Integer(1),Integer(2),Integer(3)], Integer(1):[Integer(2)], Integer(3):[Integer(0),Integer(1)]})
>>> G.show(figsize=[Integer(2),Integer(2)])                                                 # needs sage.plot
>>> G.clique_number()
3


By definition the clique number of a complete graph is its order:

sage: all(graphs.CompleteGraph(i).clique_number() == i for i in range(1,15))
True

>>> from sage.all import *
>>> all(graphs.CompleteGraph(i).clique_number() == i for i in range(Integer(1),Integer(15)))
True


A non-empty graph without edges has a clique number of 1:

sage: all((i*graphs.CompleteGraph(1)).clique_number() == 1
....:     for i in range(1,15))
True

>>> from sage.all import *
>>> all((i*graphs.CompleteGraph(Integer(1))).clique_number() == Integer(1)
...     for i in range(Integer(1),Integer(15)))
True


A complete multipartite graph with k parts has clique number k:

sage: all((i*graphs.CompleteMultipartiteGraph(i*[5])).clique_number() == i
....:     for i in range(1,6))
True

>>> from sage.all import *
>>> all((i*graphs.CompleteMultipartiteGraph(i*[Integer(5)])).clique_number() == i
...     for i in range(Integer(1),Integer(6)))
True

clique_polynomial(t=None)[source]#

Return the clique polynomial of self.

This is the polynomial where the coefficient of $$t^n$$ is the number of cliques in the graph with $$n$$ vertices. The constant term of the clique polynomial is always taken to be one.

EXAMPLES:

sage: g = Graph()
sage: g.clique_polynomial()
1
sage: g = Graph({0:[1]})
sage: g.clique_polynomial()
t^2 + 2*t + 1
sage: g = graphs.CycleGraph(4)
sage: g.clique_polynomial()
4*t^2 + 4*t + 1

>>> from sage.all import *
>>> g = Graph()
>>> g.clique_polynomial()
1
>>> g = Graph({Integer(0):[Integer(1)]})
>>> g.clique_polynomial()
t^2 + 2*t + 1
>>> g = graphs.CycleGraph(Integer(4))
>>> g.clique_polynomial()
4*t^2 + 4*t + 1

cliques_containing_vertex(vertices=None, cliques=None)[source]#

Return 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:

• vertices – the vertices to inspect (default is entire graph)

• cliques – list of cliques (if already computed)

EXAMPLES:

sage: # needs networkx
sage: C = Graph('DJ{')
sage: C.cliques_containing_vertex()
{0: [[0, 4]],
1: [[1, 2, 3, 4]],
2: [[1, 2, 3, 4]],
3: [[1, 2, 3, 4]],
4: [[0, 4], [1, 2, 3, 4]]}
sage: C.cliques_containing_vertex(4)
[[0, 4], [1, 2, 3, 4]]
sage: C.cliques_containing_vertex([0, 1])
{0: [[0, 4]], 1: [[1, 2, 3, 4]]}
sage: E = C.cliques_maximal(); E
[[0, 4], [1, 2, 3, 4]]
sage: C.cliques_containing_vertex(cliques=E)
{0: [[0, 4]],
1: [[1, 2, 3, 4]],
2: [[1, 2, 3, 4]],
3: [[1, 2, 3, 4]],
4: [[0, 4], [1, 2, 3, 4]]}

sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])                                                 # needs sage.plot
sage: G.cliques_containing_vertex()                                         # needs networkx
{0: [[0, 1, 2], [0, 1, 3]],
1: [[0, 1, 2], [0, 1, 3]],
2: [[0, 1, 2]],
3: [[0, 1, 3]]}

>>> from sage.all import *
>>> # needs networkx
>>> C = Graph('DJ{')
>>> C.cliques_containing_vertex()
{0: [[0, 4]],
1: [[1, 2, 3, 4]],
2: [[1, 2, 3, 4]],
3: [[1, 2, 3, 4]],
4: [[0, 4], [1, 2, 3, 4]]}
>>> C.cliques_containing_vertex(Integer(4))
[[0, 4], [1, 2, 3, 4]]
>>> C.cliques_containing_vertex([Integer(0), Integer(1)])
{0: [[0, 4]], 1: [[1, 2, 3, 4]]}
>>> E = C.cliques_maximal(); E
[[0, 4], [1, 2, 3, 4]]
>>> C.cliques_containing_vertex(cliques=E)
{0: [[0, 4]],
1: [[1, 2, 3, 4]],
2: [[1, 2, 3, 4]],
3: [[1, 2, 3, 4]],
4: [[0, 4], [1, 2, 3, 4]]}

>>> G = Graph({Integer(0):[Integer(1),Integer(2),Integer(3)], Integer(1):[Integer(2)], Integer(3):[Integer(0),Integer(1)]})
>>> G.show(figsize=[Integer(2),Integer(2)])                                                 # needs sage.plot
>>> G.cliques_containing_vertex()                                         # needs networkx
{0: [[0, 1, 2], [0, 1, 3]],
1: [[0, 1, 2], [0, 1, 3]],
2: [[0, 1, 2]],
3: [[0, 1, 3]]}


Since each clique of a 2 dimensional grid corresponds to an edge, the number of cliques in which a vertex is involved equals its degree:

sage: # needs networkx
sage: F = graphs.Grid2dGraph(2,3)
sage: d = F.cliques_containing_vertex()
sage: all(F.degree(u) == len(cliques) for u,cliques in d.items())
True
sage: d = F.cliques_containing_vertex(vertices=[(0, 1)])
sage: list(d)
[(0, 1)]
sage: sorted(sorted(x for x in L) for L in d[(0, 1)])
[[(0, 0), (0, 1)], [(0, 1), (0, 2)], [(0, 1), (1, 1)]]

>>> from sage.all import *
>>> # needs networkx
>>> F = graphs.Grid2dGraph(Integer(2),Integer(3))
>>> d = F.cliques_containing_vertex()
>>> all(F.degree(u) == len(cliques) for u,cliques in d.items())
True
>>> d = F.cliques_containing_vertex(vertices=[(Integer(0), Integer(1))])
>>> list(d)
[(0, 1)]
>>> sorted(sorted(x for x in L) for L in d[(Integer(0), Integer(1))])
[[(0, 0), (0, 1)], [(0, 1), (0, 2)], [(0, 1), (1, 1)]]

cliques_get_clique_bipartite(**kwds)[source]#

Return the vertex-clique bipartite graph of self.

In the returned bipartite graph, the left vertices are the vertices of self and the right vertices represent the maximal cliques of self. There is an edge from vertex $$v$$ to clique $$C$$ in the bipartite graph if and only if $$v$$ belongs to $$C$$.

Note

Currently only implemented for undirected graphs. Use to_undirected to convert a digraph to an undirected graph.

EXAMPLES:

sage: CBG = graphs.ChvatalGraph().cliques_get_clique_bipartite(); CBG
Bipartite graph on 36 vertices
sage: CBG.show(figsize=[2,2], vertex_size=20, vertex_labels=False)          # needs sage.plot
sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])                                                 # needs sage.plot
sage: G.cliques_get_clique_bipartite()
Bipartite graph on 6 vertices
sage: G.cliques_get_clique_bipartite().show(figsize=[2,2])                  # needs sage.plot

>>> from sage.all import *
>>> CBG = graphs.ChvatalGraph().cliques_get_clique_bipartite(); CBG
Bipartite graph on 36 vertices
>>> CBG.show(figsize=[Integer(2),Integer(2)], vertex_size=Integer(20), vertex_labels=False)          # needs sage.plot
>>> G = Graph({Integer(0):[Integer(1),Integer(2),Integer(3)], Integer(1):[Integer(2)], Integer(3):[Integer(0),Integer(1)]})
>>> G.show(figsize=[Integer(2),Integer(2)])                                                 # needs sage.plot
>>> G.cliques_get_clique_bipartite()
Bipartite graph on 6 vertices
>>> G.cliques_get_clique_bipartite().show(figsize=[Integer(2),Integer(2)])                  # needs sage.plot

cliques_get_max_clique_graph()[source]#

Return the clique graph.

Vertices of the result are the maximal cliques of the graph, and edges of the result are 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.

EXAMPLES:

sage: MCG = graphs.ChvatalGraph().cliques_get_max_clique_graph(); MCG
Graph on 24 vertices
sage: MCG.show(figsize=[2,2], vertex_size=20, vertex_labels=False)          # needs sage.plot
sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])                                                 # needs sage.plot
sage: G.cliques_get_max_clique_graph()
Graph on 2 vertices
sage: G.cliques_get_max_clique_graph().show(figsize=[2,2])                  # needs sage.plot

>>> from sage.all import *
>>> MCG = graphs.ChvatalGraph().cliques_get_max_clique_graph(); MCG
Graph on 24 vertices
>>> MCG.show(figsize=[Integer(2),Integer(2)], vertex_size=Integer(20), vertex_labels=False)          # needs sage.plot
>>> G = Graph({Integer(0):[Integer(1),Integer(2),Integer(3)], Integer(1):[Integer(2)], Integer(3):[Integer(0),Integer(1)]})
>>> G.show(figsize=[Integer(2),Integer(2)])                                                 # needs sage.plot
>>> G.cliques_get_max_clique_graph()
Graph on 2 vertices
>>> G.cliques_get_max_clique_graph().show(figsize=[Integer(2),Integer(2)])                  # needs sage.plot

cliques_maximal(algorithm='native')[source]#

Return the list of all maximal cliques.

Each clique is 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.

INPUT:

• algorithm – can be set to "native" (default) to use Sage’s own implementation, or to "NetworkX" to use NetworkX’ implementation of the Bron and Kerbosch Algorithm [BK1973].

Note

This method sorts its output before returning it. If you prefer to save the extra time, you can call sage.graphs.independent_sets.IndependentSets directly.

Note

Sage’s implementation of the enumeration of maximal independent sets is not much faster than NetworkX’ (expect a 2x speedup), which is surprising as it is written in Cython. This being said, the algorithm from NetworkX appears to be slightly different from this one, and that would be a good thing to explore if one wants to improve the implementation.

ALGORITHM:

This function is based on NetworkX’s implementation of the Bron and Kerbosch Algorithm [BK1973].

EXAMPLES:

sage: graphs.ChvatalGraph().cliques_maximal()
[[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])                                                # needs sage.plot
sage: G.cliques_maximal()
[[0, 1, 2], [0, 1, 3]]
sage: C = graphs.PetersenGraph()
sage: C.cliques_maximal()
[[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_maximal()
[[0, 4], [1, 2, 3, 4]]

>>> from sage.all import *
>>> graphs.ChvatalGraph().cliques_maximal()
[[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]]
>>> G = Graph({Integer(0):[Integer(1),Integer(2),Integer(3)], Integer(1):[Integer(2)], Integer(3):[Integer(0),Integer(1)]})
>>> G.show(figsize=[Integer(2), Integer(2)])                                                # needs sage.plot
>>> G.cliques_maximal()
[[0, 1, 2], [0, 1, 3]]
>>> C = graphs.PetersenGraph()
>>> C.cliques_maximal()
[[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]]
>>> C = Graph('DJ{')
>>> C.cliques_maximal()
[[0, 4], [1, 2, 3, 4]]


Comparing the two implementations:

sage: g = graphs.RandomGNP(20,.7)
sage: s1 = Set(map(Set, g.cliques_maximal(algorithm="NetworkX")))           # needs networkx
sage: s2 = Set(map(Set, g.cliques_maximal(algorithm="native")))
sage: s1 == s2                                                              # needs networkx
True

>>> from sage.all import *
>>> g = graphs.RandomGNP(Integer(20),RealNumber('.7'))
>>> s1 = Set(map(Set, g.cliques_maximal(algorithm="NetworkX")))           # needs networkx
>>> s2 = Set(map(Set, g.cliques_maximal(algorithm="native")))
>>> s1 == s2                                                              # needs networkx
True

cliques_maximum(graph)[source]#

Return 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 [NO2003].

EXAMPLES:

sage: graphs.ChvatalGraph().cliques_maximum() # indirect doctest
[[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])                                                     # needs sage.plot
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]]

>>> from sage.all import *
>>> graphs.ChvatalGraph().cliques_maximum() # indirect doctest
[[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]]
>>> G = Graph({Integer(0):[Integer(1),Integer(2),Integer(3)], Integer(1):[Integer(2)], Integer(3):[Integer(0),Integer(1)]})
>>> G.show(figsize=[Integer(2),Integer(2)])                                                     # needs sage.plot
>>> G.cliques_maximum()
[[0, 1, 2], [0, 1, 3]]
>>> C = graphs.PetersenGraph()
>>> 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]]
>>> C = Graph('DJ{')
>>> C.cliques_maximum()
[[1, 2, 3, 4]]

cliques_number_of(vertices=None, cliques=None)[source]#

Return a dictionary of the number of maximal cliques containing each vertex, keyed by vertex.

This 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:

• vertices – the vertices to inspect (default is entire graph)

• cliques – list of cliques (if already computed)

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(); E
[[0, 4], [1, 2, 3, 4]]
sage: C.cliques_number_of(cliques=E)
{0: 1, 1: 1, 2: 1, 3: 1, 4: 2}
sage: F = graphs.Grid2dGraph(2,3)
sage: F.cliques_number_of()
{(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: F.cliques_number_of(vertices=(0, 1))
3
sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])                                                 # needs sage.plot
sage: G.cliques_number_of()
{0: 2, 1: 2, 2: 1, 3: 1}

>>> from sage.all import *
>>> C = Graph('DJ{')
>>> C.cliques_number_of()
{0: 1, 1: 1, 2: 1, 3: 1, 4: 2}
>>> E = C.cliques_maximal(); E
[[0, 4], [1, 2, 3, 4]]
>>> C.cliques_number_of(cliques=E)
{0: 1, 1: 1, 2: 1, 3: 1, 4: 2}
>>> F = graphs.Grid2dGraph(Integer(2),Integer(3))
>>> F.cliques_number_of()
{(0, 0): 2, (0, 1): 3, (0, 2): 2, (1, 0): 2, (1, 1): 3, (1, 2): 2}
>>> F.cliques_number_of(vertices=[(Integer(0), Integer(1)), (Integer(1), Integer(2))])
{(0, 1): 3, (1, 2): 2}
>>> F.cliques_number_of(vertices=(Integer(0), Integer(1)))
3
>>> G = Graph({Integer(0):[Integer(1),Integer(2),Integer(3)], Integer(1):[Integer(2)], Integer(3):[Integer(0),Integer(1)]})
>>> G.show(figsize=[Integer(2),Integer(2)])                                                 # needs sage.plot
>>> G.cliques_number_of()
{0: 2, 1: 2, 2: 1, 3: 1}

cliques_vertex_clique_number(algorithm='cliquer', vertices=None, cliques=None)[source]#

Return 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 [NO2003].

• networkx – This function is based on NetworkX’s implementation of the Bron and Kerbosch Algorithm [BK1973].

• vertices – the vertices to inspect (default is entire graph). Ignored unless algorithm=='networkx'.

• cliques – list of cliques (if already computed). Ignored unless algorithm=='networkx'.

EXAMPLES:

sage: C = Graph('DJ{')
sage: C.cliques_vertex_clique_number()                                      # needs sage.plot
{0: 2, 1: 4, 2: 4, 3: 4, 4: 4}
sage: E = C.cliques_maximal(); E
[[0, 4], [1, 2, 3, 4]]
sage: C.cliques_vertex_clique_number(cliques=E, algorithm="networkx")       # needs networkx
{0: 2, 1: 4, 2: 4, 3: 4, 4: 4}

sage: F = graphs.Grid2dGraph(2,3)
sage: F.cliques_vertex_clique_number(algorithm="networkx")                  # needs networkx
{(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)])             # needs sage.plot
{(0, 1): 2, (1, 2): 2}

sage: G = Graph({0:[1,2,3], 1:[2], 3:[0,1]})
sage: G.show(figsize=[2,2])                                                 # needs sage.plot
sage: G.cliques_vertex_clique_number()                                      # needs sage.plot
{0: 3, 1: 3, 2: 3, 3: 3}

>>> from sage.all import *
>>> C = Graph('DJ{')
>>> C.cliques_vertex_clique_number()                                      # needs sage.plot
{0: 2, 1: 4, 2: 4, 3: 4, 4: 4}
>>> E = C.cliques_maximal(); E
[[0, 4], [1, 2, 3, 4]]
>>> C.cliques_vertex_clique_number(cliques=E, algorithm="networkx")       # needs networkx
{0: 2, 1: 4, 2: 4, 3: 4, 4: 4}

>>> F = graphs.Grid2dGraph(Integer(2),Integer(3))
>>> F.cliques_vertex_clique_number(algorithm="networkx")                  # needs networkx
{(0, 0): 2, (0, 1): 2, (0, 2): 2, (1, 0): 2, (1, 1): 2, (1, 2): 2}
>>> F.cliques_vertex_clique_number(vertices=[(Integer(0), Integer(1)), (Integer(1), Integer(2))])             # needs sage.plot
{(0, 1): 2, (1, 2): 2}

>>> G = Graph({Integer(0):[Integer(1),Integer(2),Integer(3)], Integer(1):[Integer(2)], Integer(3):[Integer(0),Integer(1)]})
>>> G.show(figsize=[Integer(2),Integer(2)])                                                 # needs sage.plot
>>> G.cliques_vertex_clique_number()                                      # needs sage.plot
{0: 3, 1: 3, 2: 3, 3: 3}

coloring(algorithm, hex_colors='DLX', solver=False, verbose=None, integrality_tolerance=0)[source]#

Return the first (optimal) proper vertex-coloring found.

INPUT:

• algorithm – Select an algorithm from the following supported algorithms:

• If algorithm="DLX" (default), the coloring is computed using the dancing link algorithm.

• If algorithm="MILP", the coloring is computed using a mixed integer linear program. The performance of this implementation is affected by whether optional MILP solvers have been installed (see the MILP module).

• hex_colors – boolean (default: False); if True, return a dictionary which can easily be used for plotting.

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP 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.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

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")
sage: Q = G.coloring(algorithm="DLX")
sage: def are_equal_colorings(A, B):
....:     return Set(map(Set, A)) == Set(map(Set, B))
sage: are_equal_colorings(P, [[1, 2, 3], [0, 5, 6], [4]])
True
sage: are_equal_colorings(P, Q)
True

sage: # needs sage.plot
sage: G.plot(partition=P)
Graphics object consisting of 16 graphics primitives
sage: G.coloring(hex_colors=True, algorithm="MILP")
{'#0000ff': [4], '#00ff00': [0, 6, 5], '#ff0000': [2, 1, 3]}
sage: H = G.coloring(hex_colors=True, algorithm="DLX"); H
{'#0000ff': [4], '#00ff00': [1, 2, 3], '#ff0000': [0, 5, 6]}
sage: G.plot(vertex_colors=H)
Graphics object consisting of 16 graphics primitives

>>> from sage.all import *
>>> G = Graph("Fooba")
>>> P = G.coloring(algorithm="MILP")
>>> Q = G.coloring(algorithm="DLX")
>>> def are_equal_colorings(A, B):
...     return Set(map(Set, A)) == Set(map(Set, B))
>>> are_equal_colorings(P, [[Integer(1), Integer(2), Integer(3)], [Integer(0), Integer(5), Integer(6)], [Integer(4)]])
True
>>> are_equal_colorings(P, Q)
True

>>> # needs sage.plot
>>> G.plot(partition=P)
Graphics object consisting of 16 graphics primitives
>>> G.coloring(hex_colors=True, algorithm="MILP")
{'#0000ff': [4], '#00ff00': [0, 6, 5], '#ff0000': [2, 1, 3]}
>>> H = G.coloring(hex_colors=True, algorithm="DLX"); H
{'#0000ff': [4], '#00ff00': [1, 2, 3], '#ff0000': [0, 5, 6]}
>>> G.plot(vertex_colors=H)
Graphics object consisting of 16 graphics primitives

common_neighbors_matrix(vertices, nonedgesonly=None, base_ring=True, **kwds)[source]#

Return a matrix of numbers of common neighbors between each pairs.

The $$(i , j)$$ entry of the matrix gives the number of common neighbors between vertices $$i$$ and $$j$$.

This method is only valid for simple (no loops, no multiple edges) graphs.

INPUT:

• nonedgesonly – boolean (default: True); if True, assigns $$0$$ value to adjacent vertices.

• vertices – list (default: None); the ordering of the vertices defining how they should appear in the matrix. By default, the ordering given by GenericGraph.vertices() is used.

• base_ring – a ring (default: None); the base ring of the matrix space to use

• **kwds – other keywords to pass to matrix()

OUTPUT: matrix

EXAMPLES:

The common neighbors matrix for a straight linear 2-tree counting only non-adjacent vertex pairs

sage: G1 = Graph()
sage: G1.common_neighbors_matrix(nonedgesonly=True)                         # needs sage.modules
[0 0 0 2 1 0]
[0 0 0 0 2 1]
[0 0 0 0 0 2]
[2 0 0 0 0 0]
[1 2 0 0 0 0]
[0 1 2 0 0 0]

>>> from sage.all import *
>>> G1 = Graph()
>>> G1.common_neighbors_matrix(nonedgesonly=True)                         # needs sage.modules
[0 0 0 2 1 0]
[0 0 0 0 2 1]
[0 0 0 0 0 2]
[2 0 0 0 0 0]
[1 2 0 0 0 0]
[0 1 2 0 0 0]


We now show the common neighbors matrix which includes adjacent vertices

sage: G1.common_neighbors_matrix(nonedgesonly=False)                        # needs sage.modules
[0 1 1 2 1 0]
[1 0 2 1 2 1]
[1 2 0 2 1 2]
[2 1 2 0 2 1]
[1 2 1 2 0 1]
[0 1 2 1 1 0]

>>> from sage.all import *
>>> G1.common_neighbors_matrix(nonedgesonly=False)                        # needs sage.modules
[0 1 1 2 1 0]
[1 0 2 1 2 1]
[1 2 0 2 1 2]
[2 1 2 0 2 1]
[1 2 1 2 0 1]
[0 1 2 1 1 0]


The common neighbors matrix for a fan on 6 vertices counting only non-adjacent vertex pairs

sage: H = Graph([(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(1,2),(2,3),(3,4),(4,5)])
sage: H.common_neighbors_matrix()                                           # needs sage.modules
[0 0 0 0 0 0 0]
[0 0 0 2 1 1 1]
[0 0 0 0 2 1 1]
[0 2 0 0 0 2 1]
[0 1 2 0 0 0 1]
[0 1 1 2 0 0 1]
[0 1 1 1 1 1 0]

>>> from sage.all import *
>>> H = Graph([(Integer(0),Integer(1)),(Integer(0),Integer(2)),(Integer(0),Integer(3)),(Integer(0),Integer(4)),(Integer(0),Integer(5)),(Integer(0),Integer(6)),(Integer(1),Integer(2)),(Integer(2),Integer(3)),(Integer(3),Integer(4)),(Integer(4),Integer(5))])
>>> H.common_neighbors_matrix()                                           # needs sage.modules
[0 0 0 0 0 0 0]
[0 0 0 2 1 1 1]
[0 0 0 0 2 1 1]
[0 2 0 0 0 2 1]
[0 1 2 0 0 0 1]
[0 1 1 2 0 0 1]
[0 1 1 1 1 1 0]


A different base ring:

sage: H.common_neighbors_matrix(base_ring=RDF)                              # needs sage.modules
[0.0 0.0 0.0 0.0 0.0 0.0 0.0]
[0.0 0.0 0.0 2.0 1.0 1.0 1.0]
[0.0 0.0 0.0 0.0 2.0 1.0 1.0]
[0.0 2.0 0.0 0.0 0.0 2.0 1.0]
[0.0 1.0 2.0 0.0 0.0 0.0 1.0]
[0.0 1.0 1.0 2.0 0.0 0.0 1.0]
[0.0 1.0 1.0 1.0 1.0 1.0 0.0]

>>> from sage.all import *
>>> H.common_neighbors_matrix(base_ring=RDF)                              # needs sage.modules
[0.0 0.0 0.0 0.0 0.0 0.0 0.0]
[0.0 0.0 0.0 2.0 1.0 1.0 1.0]
[0.0 0.0 0.0 0.0 2.0 1.0 1.0]
[0.0 2.0 0.0 0.0 0.0 2.0 1.0]
[0.0 1.0 2.0 0.0 0.0 0.0 1.0]
[0.0 1.0 1.0 2.0 0.0 0.0 1.0]
[0.0 1.0 1.0 1.0 1.0 1.0 0.0]


It is an error to input anything other than a simple graph:

sage: G = Graph([(0,0)], loops=True)
sage: G.common_neighbors_matrix()                                           # needs sage.modules
Traceback (most recent call last):
...
ValueError: This method is not known to work on graphs with loops.
Perhaps this method can be updated to handle them, but in the
meantime if you want to use it please disallow loops using
allow_loops().

>>> from sage.all import *
>>> G = Graph([(Integer(0),Integer(0))], loops=True)
>>> G.common_neighbors_matrix()                                           # needs sage.modules
Traceback (most recent call last):
...
ValueError: This method is not known to work on graphs with loops.
Perhaps this method can be updated to handle them, but in the
meantime if you want to use it please disallow loops using
allow_loops().


convexity_properties()[source]#

Return a ConvexityProperties object 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.

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: # needs sage.numerical.mip
sage: g = graphs.PetersenGraph()
sage: g.convexity_properties().hull([1, 3])
[1, 2, 3]
sage: g.convexity_properties().hull([3, 7])
[2, 3, 7]

>>> from sage.all import *
>>> # needs sage.numerical.mip
>>> g = graphs.PetersenGraph()
>>> g.convexity_properties().hull([Integer(1), Integer(3)])
[1, 2, 3]
>>> g.convexity_properties().hull([Integer(3), Integer(7)])
[2, 3, 7]


is a terrible waste of computations, while

sage: # needs sage.numerical.mip
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]

>>> from sage.all import *
>>> # needs sage.numerical.mip
>>> g = graphs.PetersenGraph()
>>> CP = g.convexity_properties()
>>> CP.hull([Integer(1), Integer(3)])
[1, 2, 3]
>>> CP.hull([Integer(3), Integer(7)])
[2, 3, 7]


makes perfect sense.

cores(k=None, with_labels=False)[source]#

Return 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). See the Wikipedia article K-core.

[PSW1996] defines a $$k$$-core of $$G$$ as the largest subgraph (it is unique) of $$G$$ with minimum degree at least $$k$$.

• Core number of a vertex

The core number of a vertex $$v$$ is the largest integer $$k$$ such that $$v$$ belongs to the $$k$$-core of $$G$$.

• Degeneracy

The degeneracy of a graph $$G$$, usually denoted $$\delta^*(G)$$, is the smallest integer $$k$$ such that the graph $$G$$ can be reduced to the empty graph by iteratively removing vertices of degree $$\leq k$$. Equivalently, $$\delta^*(G) = k - 1$$ if $$k$$ is the smallest integer such that the $$k$$-core of $$G$$ is empty.

IMPLEMENTATION:

This implementation is based on the NetworkX implementation of the algorithm described in [BZ2003].

INPUT:

• k – integer (default: None);

• 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 $$k$$-core of self, and ordering is an elimination order for the other vertices such that each vertex is of degree strictly less than $$k$$ when it is to be eliminated from the graph.

• with_labels – boolean (default: False); when set to False, and k = None, the method returns a list whose $$i$$ th element is the core number of the $$i$$ th vertex. When set to True, the method returns a dictionary whose keys are vertices, and whose values are the corresponding core numbers.

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: # needs sage.modules
sage: set_random_seed(0)
sage: a = random_matrix(ZZ, 20, x=2, sparse=True, density=.1)
sage: b = Graph(20)
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]

>>> from sage.all import *
>>> (graphs.FruchtGraph()).cores()
[3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3]
>>> (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}

>>> # needs sage.modules
>>> set_random_seed(Integer(0))
>>> a = random_matrix(ZZ, Integer(20), x=Integer(2), sparse=True, density=RealNumber('.1'))
>>> b = Graph(Integer(20))
>>> 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}
>>> [v for v,c in cores.items() if c >= Integer(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)                                  # needs networkx
sage: ordering, core = g.cores(2)                                           # needs networkx
sage: len(core) == 0                                                        # needs networkx
True

>>> from sage.all import *
>>> g = graphs.RandomLobster(Integer(20), RealNumber('.5'), RealNumber('.5'))                                  # needs networkx
>>> ordering, core = g.cores(Integer(2))                                           # needs networkx
>>> len(core) == Integer(0)                                                        # needs networkx
True


Checking the cores of a bull graph:

sage: G = graphs.BullGraph()
sage: G.cores(with_labels=True)
{0: 2, 1: 2, 2: 2, 3: 1, 4: 1}
sage: G.cores(k=2)
([3, 4], [0, 1, 2])

>>> from sage.all import *
>>> G = graphs.BullGraph()
>>> G.cores(with_labels=True)
{0: 2, 1: 2, 2: 2, 3: 1, 4: 1}
>>> G.cores(k=Integer(2))
([3, 4], [0, 1, 2])


Graphs with multiple edges:

sage: G.allow_multiple_edges(True)
sage: G.cores(with_labels=True)
{0: 4, 1: 4, 2: 4, 3: 2, 4: 2}
sage: G.cores(k=4)
([3, 4], [0, 1, 2])

>>> from sage.all import *
>>> G.allow_multiple_edges(True)
>>> G.cores(with_labels=True)
{0: 4, 1: 4, 2: 4, 3: 2, 4: 2}
>>> G.cores(k=Integer(4))
([3, 4], [0, 1, 2])

cutwidth(G, algorithm='exponential', cut_off=0, solver=None, verbose=False, integrality_tolerance=0.001)[source]#

Return the cutwidth of the graph and the corresponding vertex ordering.

INPUT:

• G – a Graph or a DiGraph

• algorithm – string (default: "exponential"); algorithm to use among:

• exponential – Use an exponential time and space algorithm based on dynamic programming. This algorithm only works on graphs with strictly less than 32 vertices.

• MILP – Use a mixed integer linear programming formulation. This algorithm has no size restriction but could take a very long time.

• cut_off – integer (default: 0); used to stop the search as soon as a solution with width at most cut_off is found, if any. If this bound cannot be reached, the best solution found is returned.

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP solvers and which default solver is used, see the method solve of the class MixedIntegerLinearProgram.

• verbose – boolean (default: False); whether to display information on the computations.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

OUTPUT:

A pair (cost, ordering) representing the optimal ordering of the vertices and its cost.

EXAMPLES:

Cutwidth of a Complete Graph:

sage: from sage.graphs.graph_decompositions.cutwidth import cutwidth
sage: G = graphs.CompleteGraph(5)
sage: cw,L = cutwidth(G); cw
6
sage: K = graphs.CompleteGraph(6)
sage: cw,L = cutwidth(K); cw
9
sage: cw,L = cutwidth(K+K); cw
9

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.cutwidth import cutwidth
>>> G = graphs.CompleteGraph(Integer(5))
>>> cw,L = cutwidth(G); cw
6
>>> K = graphs.CompleteGraph(Integer(6))
>>> cw,L = cutwidth(K); cw
9
>>> cw,L = cutwidth(K+K); cw
9


The cutwidth of a $$p\times q$$ Grid Graph with $$p\leq q$$ is $$p+1$$:

sage: from sage.graphs.graph_decompositions.cutwidth import cutwidth
sage: G = graphs.Grid2dGraph(3,3)
sage: cw,L = cutwidth(G); cw
4
sage: G = graphs.Grid2dGraph(3,5)
sage: cw,L = cutwidth(G); cw
4

>>> from sage.all import *
>>> from sage.graphs.graph_decompositions.cutwidth import cutwidth
>>> G = graphs.Grid2dGraph(Integer(3),Integer(3))
>>> cw,L = cutwidth(G); cw
4
>>> G = graphs.Grid2dGraph(Integer(3),Integer(5))
>>> cw,L = cutwidth(G); cw
4

degree_constrained_subgraph(bounds, solver, verbose=None, integrality_tolerance=0)[source]#

Returns a degree-constrained subgraph.

Given a graph $$G$$ and two functions $$f, g:V(G)\rightarrow \mathbb Z$$ such that $$f \leq g$$, a degree-constrained subgraph in $$G$$ is a subgraph $$G' \subseteq G$$ such that for any vertex $$v \in G$$, $$f(v) \leq d_{G'}(v) \leq g(v)$$.

INPUT:

• bounds – (default: None); Two possibilities:

• A dictionary whose keys are the vertices, and values a pair of real values (min,max) corresponding to the values $$(f(v),g(v))$$.

• A function associating to each vertex a pair of real values (min,max) corresponding to the values $$(f(v),g(v))$$.

• solver – string (default: None); specify a Mixed Integer Linear Programming (MILP) solver to be used. If set to None, the default one is used. For more information on MILP 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.

• integrality_tolerance – float; parameter for use with MILP solvers over an inexact base ring; see MixedIntegerLinearProgram.get_values().

OUTPUT:

• When a solution exists, this method outputs the degree-constrained subgraph as a Graph object.

• When no solution exists, returns False.

Note

• This algorithm computes the degree-constrained subgraph of minimum weight.

• If the graph’s edges are weighted, these are taken into account.

• This problem can be solved in polynomial time.

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)                      # needs sage.numerical.mip
sage: m.size()                                                              # needs sage.numerical.mip
3

>>> from sage.all import *
>>> g = graphs.CycleGraph(Integer(6))
>>> bounds = lambda x: [Integer(1),Integer(1)]
>>> m = g.degree_constrained_subgraph(bounds=bounds)                      # needs sage.numerical.mip
>>> m.size()                                                              # needs sage.numerical.mip
3

diameter(by_weight=False, algorithm=None, weight_function=None, check_weight=True)[source]#

Return the diameter of the graph.

The diameter is defined to be the maximum distance between two vertices. It is infinite if the graph is not connected.

For more information and examples on how to use input variables, see shortest_paths() and eccentricity()

INPUT:

• by_weight – boolean (default: False); if True, edge weights are taken into account; if False, all edges have weight 1

• algorithm – string (default: None); one of the following algorithms:

• 'BFS': the computation is done through a BFS centered on each vertex successively. Works only if by_weight==False.

• 'Floyd-Warshall-Cython': a Cython implementation of the Floyd-Warshall algorithm. Works only if by_weight==False and v is None.

• 'Floyd-Warshall-Python': a Python implementation of the Floyd-Warshall algorithm. Works also with weighted graphs, even with negative weights (but no negative cycle is allowed). However, v must be None.

• 'Dijkstra_NetworkX': the Dijkstra algorithm, implemented in NetworkX. It works with weighted graphs, but no negative weight is allowed.

• 'DHV' – diameter computation is done using the algorithm proposed in [Dragan2018]. Works only for non-negative edge weights. For more information see method sage.graphs.distances_all_pairs.diameter_DHV() and sage.graphs.base.boost_graph.diameter_DHV().

• 'standard', '2sweep', 'multi-sweep', 'iFUB': these algorithms are implemented in sage.graphs.distances_all_pairs.diameter() They work only if by_weight==False. See the function documentation for more information.

• 'Dijkstra_Boost': the Dijkstra algorithm, implemented in Boost (works only with positive weights).

• 'Johnson_Boost': the Johnson algorithm, implemented in Boost (works also with negative weights, if there is no negative cycle).

• None (default): Sage chooses the best algorithm: 'iFUB' for unweighted graphs, 'Dijkstra_Boost' if all weights are positive, 'Johnson_Boost' otherwise.

• weight_function – function (default: None); a function that takes as input an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l as a weight, if l is not None, else 1 as a weight.

• check_weight – boolean (default: True); if True, we check that the weight_function outputs a number for each edge

EXAMPLES:

The more symmetric a graph is, the smaller (diameter - radius) is:

sage: G = graphs.BarbellGraph(9, 3)
3
sage: G.diameter()
6

>>> from sage.all import *
>>> G = graphs.BarbellGraph(Integer(9), Integer(3))
3
>>> G.diameter()
6

sage: G = graphs.OctahedralGraph()
2
sage: G.diameter()
2

>>> from sage.all import *
>>> G = graphs.OctahedralGraph()
2
>>> G.diameter()
2

distance_graph(dist)[source]#

Return the graph on the same vertex set as the original graph but vertices are adjacent in the returned graph if and only if they are at specified distances in the original graph.

INPUT:

• dist – a nonnegative integer or a list of nonnegative integers; specified distance(s) for the connecting vertices. Infinity may be used here to describe vertex pairs in separate components.

OUTPUT:

The returned value is an undirected graph. The vertex set is identical to the calling graph, but edges of the returned graph join vertices whose distance in the calling graph are present in the input dist. Loops will only be present if distance 0 is included. If the original graph has a position dictionary specifying locations of vertices for plotting, then this information is copied over to the distance graph. In some instances this layout may not be the best, and might even be confusing when edges run on top of each other due to symmetries chosen for the layout.

EXAMPLES:

sage: G = graphs.CompleteGraph(3)
sage: H = G.cartesian_product(graphs.CompleteGraph(2))
sage: K = H.distance_graph(2)
sage: K.am()                                                                # needs sage.modules
[0 0 0 1 0 1]
[0 0 1 0 1 0]
[0 1 0 0 0 1]
[1 0 0 0 1 0]
[0 1 0 1 0 0]
[1 0 1 0 0 0]

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(3))
>>> H = G.cartesian_product(graphs.CompleteGraph(Integer(2)))
>>> K = H.distance_graph(Integer(2))
>>> K.am()                                                                # needs sage.modules
[0 0 0 1 0 1]
[0 0 1 0 1 0]
[0 1 0 0 0 1]
[1 0 0 0 1 0]
[0 1 0 1 0 0]
[1 0 1 0 0 0]


To obtain the graph where vertices are adjacent if their distance apart is d or less use a range() command to create the input, using d + 1 as the input to range. Notice that this will include distance 0 and hence place a loop at each vertex. To avoid this, use range(1, d + 1):

sage: G = graphs.OddGraph(4)
sage: d = G.diameter()
sage: n = G.num_verts()
sage: H = G.distance_graph(list(range(d+1)))
sage: H.is_isomorphic(graphs.CompleteGraph(n))
False
sage: H = G.distance_graph(list(range(1,d+1)))
sage: H.is_isomorphic(graphs.CompleteGraph(n))
True

>>> from sage.all import *
>>> G = graphs.OddGraph(Integer(4))
>>> d = G.diameter()
>>> n = G.num_verts()
>>> H = G.distance_graph(list(range(d+Integer(1))))
>>> H.is_isomorphic(graphs.CompleteGraph(n))
False
>>> H = G.distance_graph(list(range(Integer(1),d+Integer(1))))
>>> H.is_isomorphic(graphs.CompleteGraph(n))
True


A complete collection of distance graphs will have adjacency matrices that sum to the matrix of all ones:

sage: P = graphs.PathGraph(20)
sage: all_ones = sum([P.distance_graph(i).am() for i in range(20)])         # needs sage.modules
sage: all_ones == matrix(ZZ, 20, 20, [1]*400)                               # needs sage.modules
True

>>> from sage.all import *
>>> P = graphs.PathGraph(Integer(20))
>>> all_ones = sum([P.distance_graph(i).am() for i in range(Integer(20))])         # needs sage.modules
>>> all_ones == matrix(ZZ, Integer(20), Integer(20), [Integer(1)]*Integer(400))                               # needs sage.modules
True


Four-bit strings differing in one bit is the same as four-bit strings differing in three bits:

sage: G = graphs.CubeGraph(4)
sage: H = G.distance_graph(3)
sage: G.is_isomorphic(H)
True

>>> from sage.all import *
>>> G = graphs.CubeGraph(Integer(4))
>>> H = G.distance_graph(Integer(3))
>>> G.is_isomorphic(H)
True


The graph of eight-bit strings, adjacent if different in an odd number of bits:

sage: # long time, needs sage.symbolic
sage: G = graphs.CubeGraph(8)
sage: H = G.distance_graph([1,3,5,7])
sage: degrees = [0]*sum([binomial(8,j) for j in [1,3,5,7]])
sage: degrees.append(2^8)
sage: degrees == H.degree_histogram()
True

>>> from sage.all import *
>>> # long time, needs sage.symbolic
>>> G = graphs.CubeGraph(Integer(8))
>>> H = G.distance_graph([Integer(1),Integer(3),Integer(5),Integer(7)])
>>> degrees = [Integer(0)]*sum([binomial(Integer(8),j) for j in [Integer(1),Integer(3),Integer(5),Integer(7)]])
>>> degrees.append(Integer(2)**Integer(8))
>>> degrees == H.degree_histogram()
True


An example of using Infinity as the distance in a graph that is not connected:

sage: G = graphs.CompleteGraph(3)
sage: H = G.disjoint_union(graphs.CompleteGraph(2))
sage: L = H.distance_graph(Infinity)
sage: L.am()                                                                # needs sage.modules
[0 0 0 1 1]
[0 0 0 1 1]
[0 0 0 1 1]
[1 1 1 0 0]
[1 1 1 0 0]
sage: L.is_isomorphic(graphs.CompleteBipartiteGraph(3, 2))
True

>>> from sage.all import *
>>> G = graphs.CompleteGraph(Integer(3))
>>> H = G.disjoint_union(graphs.CompleteGraph(Integer(2)))
>>> L = H.distance_graph(Infinity)
>>> L.am()                                                                # needs sage.modules
[0 0 0 1 1]
[0 0 0 1 1]
[0 0 0 1 1]
[1 1 1 0 0]
[1 1 1 0 0]
>>> L.is_isomorphic(graphs.CompleteBipartiteGraph(Integer(3), Integer(2)))
True


AUTHOR:

Rob Beezer, 2009-11-25, Issue #7533

ear_decomposition()[source]#

Return an Ear decomposition of the graph.

An ear of an undirected graph $$G$$ is a path $$P$$ where the two endpoints of the path may coincide (i.e., form a cycle), but where otherwise no repetition of edges or vertices is allowed, so every internal vertex of $$P$$ has degree two in $$P$$.

An ear decomposition of an undirected graph $$G$$ is a partition of its set of edges into a sequence of ears, such that the one or two endpoints of each ear belong to earlier ears in the sequence and such that the internal vertices of each ear do not belong to any earlier ear.

This method implements the linear time algorithm presented in [Sch2013].

OUTPUT:

• A nested list representing the cycles and chains of the ear decomposition of the graph.

EXAMPLES:

Ear decomposition of an outer planar graph of order 13:

sage: g = Graph('LlCG{O@?GBOMW?')
sage: g.ear_decomposition()
[[0, 3, 2, 1, 0],
[0, 7, 4, 3],
[0, 11, 9, 8, 7],
[1, 12, 2],
[3, 6, 5, 4],
[4, 6],
[7, 10, 8],
[7, 11],
[8, 11]]

>>> from sage.all import *
>>> g = Graph('LlCG{O@?GBOMW?')
>>> g.ear_decomposition()
[[0, 3, 2, 1, 0],
[0, 7, 4, 3],
[0, 11, 9, 8, 7],
[1, 12, 2],
[3, 6, 5, 4],
[4, 6],
[7, 10, 8],
[7, 11],
[8, 11]]


Ear decomposition of a biconnected graph:

sage: g = graphs.CycleGraph(4)
sage: g.ear_decomposition()
[[0, 3, 2, 1, 0]]

>>> from sage.all import *
>>> g = graphs.CycleGraph(Integer(4))
>>> g.ear_decomposition()
[[0, 3, 2, 1, 0]]


Ear decomposition of a connected but not biconnected graph:

sage: G = Graph()
sage: G.ear_decomposition()
[[0, 2, 1, 0], [3, 6, 5, 4, 3]]

>>> from sage.all import *
>>> G = Graph()
>>> G.ear_decomposition()
[[0, 2, 1, 0], [3, 6, 5, 4, 3]]


The ear decomposition of a multigraph with loops is the same as the ear decomposition of the underlying simple graph:

sage: g = graphs.BullGraph()
sage: g.allow_multiple_edges(True)
sage: g.allow_loops(True)
sage: u = g.random_vertex()
sage: g
Bull graph: Looped multi-graph on 5 vertices
sage: h = g.to_simple()
sage: g.ear_decomposition() == h.ear_decomposition()
True

>>> from sage.all import *
>>> g = graphs.BullGraph()
>>> g.allow_multiple_edges(True)
>>> g.allow_loops(True)
>>> u = g.random_vertex()
>>> g
Bull graph: Looped multi-graph on 5 vertices
>>> h = g.to_simple()
>>> g.ear_decomposition() == h.ear_decomposition()
True

eccentricity(v=None, by_weight=False, algorithm=None, weight_function=None, check_weight=True, dist_dict=None, with_labels=False)[source]#

Return the eccentricity of vertex (or vertices) v.

The eccentricity of a vertex is the maximum distance to any other vertex.

For more information and examples on how to use input variables, see shortest_path_all_pairs(), shortest_path_lengths() and shortest_paths()

INPUT:

• v – either a single vertex or a list of vertices. If it is not specified, then it is taken to be all vertices.

• by_weight – boolean (default: False); if True, edge weights are taken into account; if False, all edges have weight 1

• algorithm – string (default: None); one of the following algorithms:

• 'BFS' – the computation is done through a BFS centered on each vertex successively. Works only if by_weight==False.

• 'DHV' – the computation is done using the algorithm proposed in [Dragan2018]. Works only if self has non-negative edge weights and v is None or v should contain all vertices of self. For more information see method sage.graphs.distances_all_pairs.eccentricity() and sage.graphs.base.boost_graph.eccentricity_DHV().

• 'Floyd-Warshall-Cython' – a Cython implementation of the Floyd-Warshall algorithm. Works only if by_weight==False and v is None or v should contain all vertices of self.

• 'Floyd-Warshall-Python' – a Python implementation of the Floyd-Warshall algorithm. Works also with weighted graphs, even with negative weights (but no negative cycle is allowed). However, v must be None or v should contain all vertices of self.

• 'Dijkstra_NetworkX' – the Dijkstra algorithm, implemented in NetworkX. It works with weighted graphs, but no negative weight is allowed.

• 'Dijkstra_Boost' – the Dijkstra algorithm, implemented in Boost (works only with positive weights).

• 'Johnson_Boost' – the Johnson algorithm, implemented in Boost (works also with negative weights, if there is no negative cycle). Works only if v is None or v should contain all vertices of self.

• 'From_Dictionary' – uses the (already computed) distances, that are provided by input variable dist_dict.

• None (default): Sage chooses the best algorithm: 'From_Dictionary' if dist_dict is not None, 'BFS' for unweighted graphs, 'Dijkstra_Boost' if all weights are positive, 'Johnson_Boost' otherwise.

• weight_function – function (default: None); a function that takes as input an edge (u, v, l) and outputs its weight. If not None, by_weight is automatically set to True. If None and by_weight is True, we use the edge label l as a weight, if l is not None, else 1 as a weight.

• check_weight – boolean (default: True); if True, we check that the weight_function outputs a number for each edge

• dist_dict – a dictionary (default: None); a dict of dicts of distances (used only if algorithm=='From_Dictionary')

• with_labels – boolean (default: False); whether to return a list or a dictionary keyed by vertices.

EXAMPLES:

sage: G = graphs.KrackhardtKiteGraph()
sage: G.eccentricity()
[4, 4, 4, 4, 4, 3, 3, 2, 3, 4]
sage: G.vertices(sort=True)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sage: G.eccentricity(7)
2
sage: G.eccentricity([7,8,9])
[2, 3, 4]
sage: G.eccentricity([7, 8, 9], with_labels=True) == {8: 3, 9: 4, 7: 2}
True
sage: G = Graph({0: [], 1: [], 2: [1]})
sage: G.eccentricity()
[+Infinity, +Infinity, +Infinity]
sage: G = Graph({0:[]})
sage: G.eccentricity(with_labels=True)
{0: 0}
sage: G = Graph({0:[], 1:[]})
sage: G.eccentricity(with_labels=True)
{0: +Infinity, 1: +Infinity}
sage: G = Graph([(0, 1, 1), (1, 2, 1), (0, 2, 3)])
sage: G.eccentricity(algorithm='BFS')
[1, 1, 1]
sage: G.eccentricity(algorithm='Floyd-Warshall-Cython')
[1, 1, 1]
sage: G.eccentricity(by_weight=True, algorithm='Dijkstra_NetworkX')         # needs networkx
[2, 1, 2]
sage: G.eccentricity(by_weight=True, algorithm='Dijkstra_Boost')
[2, 1, 2]
sage: G.eccentricity(by_weight=True, algorithm='Johnson_Boost')
[2, 1, 2]
sage: G.eccentricity(by_weight=True, algorithm='Floyd-Warshall-Python')
[2, 1, 2]
sage: G.eccentricity(dist_dict=G.shortest_path_all_pairs(by_weight=True)[0])
[2, 1, 2]
sage: G.eccentricity(by_weight=False, algorithm='DHV')
[1, 1, 1]
sage: G.eccentricity(by_weight=True, algorithm='DHV')
[2.0, 1.0, 2.0]

>>> from sage.all import *
>>> G = graphs.KrackhardtKiteGraph()
>>> G.eccentricity()
[4, 4, 4, 4, 4, 3, 3, 2, 3, 4]
>>> G.vertices(sort=True)
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
>>> G.eccentricity(Integer(7))
2
>>> G.eccentricity([Integer(7),Integer(8),Integer(9)])
[2, 3, 4]
>>> G.eccentricity([Integer(7), Integer(8), Integer(9)], with_labels=True) == {Integer(8): Integer(3), Integer(9): Integer(4), Integer(7): Integer(2)}
True
>>> G = Graph({Integer(0): [], Integer(1): [], Integer(2): [Integer(1)]})
>>> G.eccentricity()
[+Infinity, +Infinity, +Infinity]
>>> G = Graph({Integer(0):[]})
>>> G.eccentricity(with_labels=True)
{0: 0}
>>> G = Graph({Integer(0):[], Integer(1):[]})
>>> G.eccentricity(with_labels=True)
{0: +Infinity, 1: +Infinity}
>>> G = Graph([(Integer(0), Integer(1), Integer(1)), (Integer(1), Integer(2), Integer(1)), (Integer(0), Integer(2), Integer(3))])
>>> G.eccentricity(algorithm='BFS')
[1, 1, 1]
>>> G.eccentricity(algorithm='Floyd-Warshall-Cython')
[1, 1, 1]
>>> G.eccentricity(by_weight=True, algorithm='Dijkstra_NetworkX')         # needs networkx
[2, 1, 2]
>>> G.eccentricity(by_weight=True, algorithm='Dijkstra_Boost')
[2, 1, 2]
>>> G.eccentricity(by_weight=True, algorithm='Johnson_Boost')
[2, 1, 2]
>>> G.eccentricity(by_weight=True, algorithm='Floyd-Warshall-Python')
[2, 1, 2]
>>> G.eccentricity(dist_dict=G.shortest_path_all_pairs(by_weight=True)[Integer(0)])
[2, 1, 2]
>>> G.eccentricity(by_weight=False, algorithm='DHV')
[1, 1, 1]
>>> G.eccentricity(by_weight=True, algorithm='DHV')
[2.0, 1.0, 2.0]

edge_isoperimetric_number(g)[source]#

Return the edge-isoperimetric number of the graph.

The edge-isoperimetric number of a graph $$G = (V,E)$$ is also sometimes called the isoperimetric number. It is defined as the minimum of $$|\partial S| / |S|$$ where $$\partial S$$ is the edge boundary of $$S$$ (number of edges with one end in $$S$$ and one end in $$V \setminus S$$) and the minimum is taken over all subsets of vertices whose cardinality does not exceed half the size $$|V|$$ of the graph.

Alternative but similar quantities can be obtained via the methods cheeger_constant() and vertex_isoperimetric_number().

EXAMPLES:

The edge-isoperimetric number of a complete graph on $$n$$ vertices is $$\lceil n/2 \rceil$$:

sage: [graphs.CompleteGraph(n).edge_isoperimetric_number() for n in range(2,10)]
[1, 2, 2, 3, 3, 4, 4, 5]

>>> from sage.all import *
>>> [graphs.CompleteGraph(n).edge_isoperimetric_number() for n in range(Integer(2),Integer(10))]
[1, 2, 2, 3, 3, 4, 4, 5]


The edge-isoperimetric constant of a cycle on $$n$$ vertices is $$2/\lfloor n/2 \rfloor$$:

sage: [graphs.CycleGraph(n).edge_isoperimetric_number() for n in range(2,15)]
[1, 2, 1, 1, 2/3, 2/3, 1/2, 1/2, 2/5, 2/5, 1/3, 1/3, 2/7]

>>> from sage.all import *
>>> [graphs.CycleGraph(n).edge_isoperimetric_number() for n in range(Integer(2),Integer(15))]
[1, 2, 1, 1, 2/3, 2/3, 1/2, 1/2, 2/5, 2/5, 1/3, 1/3, 2/7]


In general, for $$d$$-regular graphs the edge-isoperimetric number is $$d$$ times larger than the Cheeger constant of the graph:

sage: g = graphs.RandomRegular(3, 10)                                           # needs networkx
sage: g.edge_isoperimetric_number() == g.cheeger_constant() * 3                 # needs networkx
True

>>> from sage.all import *
>>> g = graphs.RandomRegular(Integer(3), Integer(10))                                           # needs networkx
>>> g.edge_isoperimetric_number() == g.cheeger_constant() * Integer(3)                 # needs networkx
True


And the edge-isoperimetric constant of a disconnected graph is $$0$$:

sage: Graph([[1,2,3,4],[(1,2),(3,4)]]).edge_isoperimetric_number()
0

>>> from sage.all import *
>>> Graph([[Integer(1),Integer(2),Integer(3),Integer(4)],[(Integer(1),Integer(2)),(Integer(3),Integer(4))]]).edge_isoperimetric_number()
0

effective_resistance(i, j, base_ring)[source]#

Return the effective resistance between nodes $$i$$ and $$j$$.

The resistance distance between vertices $$i$$ and $$j$$ of a simple connected graph $$G$$ is defined as the effective resistance between the two vertices on an electrical network constructed from $$G$$ replacing each edge of the graph by a unit (1 ohm) resistor.

INPUT:

• i, j – vertices of the graph

• base_ring – a ring (default: None); the base ring of the matrix space to use

OUTPUT: rational number denoting resistance between nodes $$i$$ and $$j$$

EXAMPLES:

Effective resistances in a straight linear 2-tree on 6 vertices

sage: # needs sage.modules
sage: G = Graph([(0,1),(0,2),(1,2),(1,3),(3,5),(2,4),(2,3),(3,4),(4,5)])
sage: G.effective_resistance(0,1)
34/55
sage: G.effective_resistance(0,3)
49/55
sage: G.effective_resistance(1,4)
9/11
sage: G.effective_resistance(0,5)
15/11

>>> from sage.all import *
>>> # needs sage.modules
>>> G = Graph([(Integer(0),Integer(1)),(Integer(0),Integer(2)),(Integer(1),Integer(2)),(Integer(1),Integer(3)),(Integer(3),Integer(5)),(Integer(2),Integer(4)),(Integer(2),Integer(3)),(Integer(3),Integer(4)),(Integer(4),Integer(5))])
>>> G.effective_resistance(Integer(0),Integer(1))
34/55
>>> G.effective_resistance(Integer(0),Integer(3))
49/55
>>> G.effective_resistance(Integer(1),Integer(4))
9/11
>>> G.effective_resistance(Integer(0),Integer(5))
15/11


Effective resistances in a fan on 6 vertices

sage: # needs sage.modules
sage: H = Graph([(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(1,2),(2,3),(3,4),(4,5)])
sage: H.effective_resistance(1,5)
6/5
sage: H.effective_resistance(1,3)
49/55
sage: H.effective_resistance(1,1)
0

>>> from sage.all import *
>>> # needs sage.modules
>>> H = Graph([(Integer(0),Integer(1)),(Integer(0),Integer(2)),(Integer(0),Integer(3)),(Integer(0),Integer(4)),(Integer(0),Integer(5)),(Integer(0),Integer(6)),(Integer(1),Integer(2)),(Integer(2),Integer(3)),(Integer(3),Integer(4)),(Integer(4),Integer(5))])
>>> H.effective_resistance(Integer(1),Integer(5))
6/5
>>> H.effective_resistance(Integer(1),Integer(3))
49/55
>>> H.effective_resistance(Integer(1),Integer(1))
0


Using a different base ring:

sage: H.effective_resistance(1, 5, base_ring=RDF)   # abs tol 1e-14         # needs numpy sage.modules
1.2000000000000000
sage: H.effective_resistance(1, 1, base_ring=RDF)                           # needs sage.modules
0.0

>>> from sage.all import *
>>> H.effective_resistance(Integer(1), Integer(5), base_ring=RDF)   # abs tol 1e-14         # needs numpy sage.modules
1.2000000000000000
>>> H.effective_resistance(Integer(1), Integer(1), base_ring=RDF)                           # needs sage.modules
0.0


effective_resistance_matrix(vertices, nonedgesonly=None, base_ring=True, **kwds)[source]#

Return a matrix whose ($$i$$ , $$j$$) entry gives the effective resistance between vertices $$i$$ and $$j$$.

The resistance distance between vertices $$i$$ and $$j$$ of a simple connected graph $$G$$ is defined as the effective resistance between the two vertices on an electrical network constructed from $$G$$ replacing each edge of the graph by a unit (1 ohm) resistor.

By default, the matrix returned is over the rationals.

INPUT:

• nonedgesonly – boolean (default: True); if True assign zero resistance to pairs of adjacent vertices.

• vertices – list (default: None); the ordering of the vertices defining how they should appear in the matrix. By default, the ordering given by GenericGraph.vertices() is used.

• base_ring – a ring (default: None); the base ring of the matrix space to use

• **kwds – other keywords to pass to matrix()

OUTPUT: matrix

EXAMPLES:

The effective resistance matrix for a straight linear 2-tree counting only non-adjacent vertex pairs

sage: G = Graph([(0,1),(0,2),(1,2),(1,3),(3,5),(2,4),(2,3),(3,4),(4,5)])
sage: G.effective_resistance_matrix()                                       # needs sage.modules
[    0     0     0 49/55 59/55 15/11]
[    0     0     0     0  9/11 59/55]
[    0     0     0     0     0 49/55]
[49/55     0     0     0     0     0]
[59/55  9/11     0     0     0     0]
[15/11 59/55 49/55     0     0     0]

>>> from sage.all import *
>>> G = Graph([(Integer(0),Integer(1)),(Integer(0),Integer(2)),(Integer(1),Integer(2)),(Integer(1),Integer(3)),(Integer(3),Integer(5)),(Integer(2),Integer(4)),(Integer(2),Integer(3)),(Integer(3),Integer(4)),(Integer(4),Integer(5))])
>>> G.effective_resistance_matrix()                                       # needs sage.modules
[    0     0     0 49/55 59/55 15/11]
[    0     0     0     0  9/11 59/55]
[    0     0     0     0     0 49/55]
[49/55     0     0     0     0     0]
[59/55  9/11     0     0     0     0]
[15/11 59/55 49/55     0     0     0]


The same effective resistance matrix, this time including adjacent vertices

sage: G.effective_resistance_matrix(nonedgesonly=False)                     # needs sage.modules
[    0 34/55 34/55 49/55 59/55 15/11]
[34/55     0 26/55 31/55  9/11 59/55]
[34/55 26/55     0  5/11 31/55 49/55]
[49/55 31/55  5/11     0 26/55 34/55]
[59/55  9/11 31/55 26/55     0 34/55]
[15/11 59/55 49/55 34/55 34/55     0]

>>> from sage.all import *
>>> G.effective_resistance_matrix(nonedgesonly=False)                     # needs sage.modules
[    0 34/55 34/55 49/55 59/55 15/11]
[34/55     0 26/55 31/55  9/11 59/55]
[34/55 26/55     0  5/11 31/55 49/55]
[49/55 31/55  5/11     0 26/55 34/55]
[59/55  9/11 31/55 26/55     0 34/55]
[15/11 59/55 49/55 34/55 34/55     0]


This example illustrates the common neighbors matrix for a fan on 6 vertices counting only non-adjacent vertex pairs

sage: H = Graph([(0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(1,2),(2,3),(3,4),(4,5)])
sage: H.effective_resistance_matrix()                                       # needs sage.modules
[    0     0     0     0     0     0     0]
[    0     0     0 49/55 56/55   6/5 89/55]
[    0     0     0     0   4/5 56/55 81/55]
[    0 49/55     0     0     0 49/55 16/11]
[    0 56/55   4/5     0     0     0 81/55]
[    0   6/5 56/55 49/55     0     0 89/55]
[    0 89/55 81/55 16/11 81/55 89/55     0]

>>> from sage.all import *
>>> H = Graph([(Integer(0),Integer(1)),(Integer(0),Integer(2)),(Integer(0),Integer(3)),(Integer(0),Integer(4)),(Integer(0),Integer(5)),(Integer(0),Integer(6)),(Integer(1),Integer(2)),(Integer(2),Integer(3)),(Integer(3),Integer(4)),(Integer(4),Integer(5))])
>>> H.effective_resistance_matrix()                                       # needs sage.modules
[    0     0     0     0     0     0     0]
[    0     0     0 49/55 56/55   6/5 89/55]
[    0     0     0     0   4/5 56/55 81/55]
[    0 49/55     0     0     0 49/55 16/11]
[    0 56/55   4/5     0     0     0 81/55]
[    0   6/5 56/55 49/55     0     0 89/55]
[    0 89/55 81/55 16/11 81/55 89/55     0]


A different base ring:

sage: H.effective_resistance_matrix(base_ring=RDF)[0, 0].parent()           # needs numpy sage.modules
Real Double Field

>>> from sage.all import *
>>> H.effective_resistance_matrix(base_ring=RDF)[Integer(0), Integer(0)].parent()           # needs numpy sage.modules
Real Double Field


folded_graph(check=False)[source]#

Return the antipodal fold of this graph.

Given an antipodal graph $$G$$ let $$G_d$$ be its distance-$$d$$ graph. Then the folded graph of $$G$$ has a vertex for each maximal clique of $$G_d$$ and two cliques are adjacent if there is an edge in $$G$$ connecting the two.

sage.graphs.graph.is_antipodal()

INPUT:

• check – boolean (default: False); whether to check if the graph is antipodal. If check is True and the graph is not antipodal, then return False.

OUTPUT:

This function returns a new graph and self is not touched.

Note

The input is expected to be an antipodal graph. You can check that a graph is antipodal using sage.graphs.graph.is_antipodal().

EXAMPLES:

sage: G = graphs.JohnsonGraph(10, 5)
sage: H = G.folded_graph(); H
Folded Johnson graph with parameters 10,5: Graph on 126 vertices
sage: Gd = G.distance_graph(G.diameter())
sage: all(i == 1 for i in Gd.degree())
True
sage: H.is_distance_regular(True)
([25, 16, None], [None, 1, 4])

>>> from sage.all import *
>>> G = graphs.JohnsonGraph(Integer(10), Integer(5))
>>> H = G.folded_graph(); H
Folded Johnson graph with parameters 10,5: Graph on 126 vertices
>>> Gd = G.distance_graph(G.diameter())
>>> all(i == Integer(1) for i in Gd.degree())
True
>>> H.is_distance_regular(True)
([25, 16, None], [None, 1, 4])


This method doesn’t check if the graph is antipodal:

sage: G = graphs.PetersenGraph()
sage: G.is_antipodal()
False
sage: G.folded_graph()  # some garbage
Folded Petersen graph: Graph on 2 vertices
sage: G.folded_graph(check=True)
False

>>> from sage.all import *
>>> G = graphs.PetersenGraph()
>>> G.is_antipodal()
False
>>> G.folded_graph()  # some garbage
Folded Petersen graph: Graph on 2 vertices
>>> G.folded_graph(check=True)
False


REFERENCES:

See [BCN1989] p. 438 or [Sam2012] for this definition of folded graph.

fractional_chromatic_index(G, solver='PPL', verbose_constraints=False, verbose=0)[source]#

Return the fractional chromatic index of the graph.

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 $$G$$ is the smallest real value $$\chi_f(G)$$ such that there exists a list of matchings $$M_1, \ldots, M_k$$ of $$G$$ and coefficients $$\alpha_1, \ldots, \alpha_k$$ with the property that each edge is covered by the matchings in the following relaxed way

$\forall e \in E(G), \sum_{e \in M_i} \alpha_i \geq 1.$

ALGORITHM:

The fractional chromatic index is computed through Linear Programming through its dual. The LP solved by sage is actually:

$\begin{split}\mbox{Maximize : }&\sum_{e\in E(G)} r_{e}\\ \mbox{Such that : }&\\ &\forall M\text{ matching }\subseteq G, \sum_{e\in M}r_{v}\leq 1\\\end{split}$

INPUT:

• G – a graph

• solver – (default: "PPL"); 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.

Note

The default solver used here is "PPL" which provides exact results, i.e. a rational number, although this may be slower that using other solvers. Be aware that this method may loop endlessly when using some non exact solvers as reported in Issue #23658 and Issue #23798.

• verbose_constraints – boolean (default: False); whether to display which constraints are being generated

• verbose – integer (default: $$0$$); sets the level of verbosity of the LP solver

EXAMPLES:

The fractional chromatic index of a $$C_5$$ is $$5/2$$:

sage: g = graphs.CycleGraph(5)
sage: g.fractional_chromatic_index()                                            # needs sage.numerical.mip
5/2

>>> from sage.all import *
>>> g = graphs.CycleGraph(Integer(5))
>>> g.fractional_chromatic_index()                                            # needs sage.numerical.mip
5/2

fractional_chromatic_number(G, solver='PPL', verbose=0, check_components=True, check_bipartite=True)[source]#

Return the fractional chromatic number of the graph.

Fractional coloring is a relaxed version of vertex coloring with several equivalent definitions, such as the optimum value in a linear relaxation of the integer program that gives the usual chromatic number. It is also equal to the fractional clique number by LP-duality.

ALGORITHM:

The fractional chromatic number is computed via the usual Linear Program. The LP solved by sage is essentially,

$\begin{split}\mbox{Minimize : }&\sum_{I\in \mathcal{I}(G)} x_{I}\\ \mbox{Such that : }&\\ &\forall v\in V(G), \sum_{I\in \mathcal{I}(G),\, v\in I}x_{v}\geq 1\\ &\forall I\in \mathcal{I}(G), x_{I} \geq 0\end{split}$

where $$\mathcal{I}(G)$$ is the set of maximal independent sets of $$G$$ (see Section 2.1 of [CFKPR2010] to know why it is sufficient to consider maximal independent sets). As optional optimisations, we construct the LP on each biconnected component of $$G$$ (and output the maximum value), and avoid using the LP if G is bipartite (as then the output must be 1 or 2).

Note

Computing the fractional chromatic number can be very slow. Since the variables of the LP are independent sets, in general the LP has size exponential in the order of the graph. In the current implementation a list of all maximal independent sets is created and stored, which can be both slow and memory-hungry.

INPUT:

• G – a graph

• solver – (default: "PPL"); 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.

Note

The default solver used here is "PPL" which provides exact results, i.e. a rational number, although this may be slower that using other solvers.

• verbose – integer (default: $$0$$); sets the level of verbosity of the LP solver

• check_components – boolean (default: True); whether the method is called on each biconnected component of $$G$$

• check_bipartite – boolean (default: True); whether the graph is checked for bipartiteness. If the graph is bipartite then we can avoid creating and solving the LP.

EXAMPLES:

The fractional chromatic number of a $$C_5$$ is $$5/2$$:

sage: g = graphs.CycleGraph(5)
sage: g.fractional_chromatic_number()                                           # needs sage.numerical.mip
5/2

>>> from sage.all import *
>>> g = graphs.CycleGraph(Integer(5))
>>> g.fractional_chromatic_number()                                           # needs sage.numerical.mip
5/2

fractional_clique_number(solver='PPL', verbose=0, check_components=True, check_bipartite=True)[source]#

Return the fractional clique number of the graph.

A fractional clique is a nonnegative weight function on the vertices of a graph such that the sum of the weights over any independent set is at most 1. The fractional clique number is the largest total weight of a fractional clique, which is equal to the fractional chromatic number by LP-duality.

ALGORITHM:

The fractional clique number is computed via the Linear Program for fractional chromatic number, see fractional_chromatic_number

INPUT:

• solver – (default: "PPL"); 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.

Note

The default solver used here is "PPL" which provides exact results, i.e. a rational number, although this may be slower that using other solvers.

• verbose – integer (default: $$0$$); sets the level of verbosity of the LP solver

• check_components – boolean (default: True); whether the method is called on each biconnected component of $$G$$

• check_bipartite – boolean (default: True); whether the graph is checked for bipartiteness. If the graph is bipartite then we can avoid creating and solving the LP.

EXAMPLES:

The fractional clique number of a $$C_7$$ is $$7/3$$:

sage: g = graphs.CycleGraph(7)
sage: g.fractional_clique_number()                                          # needs sage.numerical.mip
7/3

>>> from sage.all import *
>>> g = graphs.CycleGraph(Integer(7))
>>> g.fractional_clique_number()                                          # needs sage.numerical.mip
7/3

geodetic_closure(G, S)[source]#

Return the geodetic closure of the set of vertices $$S$$ in $$G$$.

The geodetic closure $$g(S)$$ of a subset of vertices $$S$$ of a graph $$G$$ is in [HLT1993] as the set of all vertices that lie on a shortest $$u-v$$ path for any pair of vertices $$u,v \in S$$. We assume that $$g(\emptyset) = \emptyset$$ and that $$g(\{u\}) = \{u\}$$ for any $$u$$ in $$G$$.

Warning

This operation is not a closure function. Indeed, a closure function must satisfy the property that $$f(f(X))$$ should be equal to $$f(X)$$, which is not always the case here. The term closure is used here to follow the terminology of the domain. See for instance [HLT1993].

Here, we implement a simple algorithm to determine this set. Roughly, for each vertex $$u \in S$$, the algorithm first performs a breadth first search from $$u$$ to get distances, and then identifies the vertices of $$G$$ lying on a shortest path from $$u$$ to any $$v\in S$$ using a reversal traversal from vertices in $$S$$. This algorithm has time complexity in $$O(|S|(n + m) + (n + m\log{m}))$$ for SparseGraph, $$O(|S|(n + m) + n^2\log{m})$$ for DenseGraph and space complexity in $$O(n + m)$$ (the extra $$\log$$ factor is due to init_short_digraph being called with sort_neighbors=True).

INPUT:

• G – a Sage graph

• S – a subset of vertices of $$G$$

EXAMPLES:

The vertices of the Petersen graph can be obtained by a geodetic closure of four of its vertices:

sage: from sage.graphs.convexity_properties import geodetic_closure
sage: G = graphs.PetersenGraph()
sage: geodetic_closure(G, [0, 2, 8, 9])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
`
<