Available versions of this document: latest release, release 4.11, release 4.10, release 4.9, release 4.8, release 4.7, release 4.6, release 4.5, release 4.4, release 4.3, release 4.2, release 4.1, release 4.0, release 3.6, release 3.5, nightly master
Reference documentation for older polymake versions: release 3.4, release 3.3, release 3.2
BigObject Graph<Dir>
from application graph
A graph with optional node and edge attributes.
 Type Parameters:
Dir
: tag describing the kind of the graph:Directed
,Undirected
,DirectedMulti
, orUndirectedMulti
. Specializations:
Graph<Directed>
: Unnamed full specialization of GraphGraph<Undirected>
: Unnamed full specialization of Graph Permutations:
 NodePerm:
permutation of nodes
Properties
no category

ADJACENCY
combinatorial description of the Graph in the form of adjacency matrix
 Type:
GraphAdjacency<Dir>
 Example:
This prints the adjacency matrix of the complete graph of three nodes, whereby the ith node is connected to the nodes shown in the ith row:
> print complete(3)>ADJACENCY; {1 2} {0 2} {0 1}

AVERAGE_DEGREE
The average degree of a node
 Type:
 Example:
The following prints the average degree of a node for the complete bipartite graph with 1 and 3 nodes:
> print complete_bipartite(1,3)>AVERAGE_DEGREE; 3/2

BICONNECTED_COMPONENTS
Biconnected components. Every row contains nodes from a single component. Articulation nodes may occur in several rows.
 Type:
 Example:
The following prints the biconnected components of two triangles having a single common node:
> $g = new Graph<Undirected>(ADJACENCY=>[[1,2],[0,2],[0,1,3,4],[2,4],[2,3]]); > print $g>BICONNECTED_COMPONENTS; {2 3 4} {0 1 2}

BIPARTITE
True if the graph is a bipartite.
 Type:
 Example:
The following checks if a square (as a graph) is bipartite:
> $g = new Graph<Undirected>(ADJACENCY=>[[1,3],[0,2],[1,3],[0,2]]); > print $g>BIPARTITE; true

CHARACTERISTIC_POLYNOMIAL
Characteristic polynomial of the adjacency matrix; its roots are the eigenvalues
 Type:
 Example:
The following prints the characteristic polynomial of a complete graph with three nodes:
> print complete(3)>CHARACTERISTIC_POLYNOMIAL x^3 3*x 2

CONNECTED
True if the graph is a connected graph.
 Type:
 Example:
The following checks whether a graph is connected or not. A single edge with its endpoints is obviously connected. We construct the adjacency matrix beforehand:
> $IM = new IncidenceMatrix<Symmetric>([[1],[0]]); > print new Graph(ADJACENCY=>$IM)>CONNECTED; true
The same procedure yields the opposite outcome after adding an isolated node:
> $IM = new IncidenceMatrix<Symmetric>([[1],[0],[]]); > print new Graph(ADJACENCY=>$IM)>CONNECTED; false

CONNECTED_COMPONENTS
The connected components. Every row contains nodes from a single component.
 Type:
 Example:
The following prints the connected components of two separate triangles:
> $g = new Graph<Undirected>(ADJACENCY=>[[1,2],[0,2],[0,1],[4,5],[3,5],[3,4]]); > print $g>CONNECTED_COMPONENTS; {0 1 2} {3 4 5}

CONNECTIVITY
Node connectivity of the graph, that is, the minimal number of nodes to be removed from the graph such that the result is disconnected.
 Type:
 Example:
The following prints the connectivity of the complete bipartite graph of 2 and 4 nodes:
> print complete_bipartite(2,4)>CONNECTIVITY; 2

DEGREE_SEQUENCE
How many times a node of a given degree occurs
 Type:
 Example:
The following prints how often each degree of a node in the complete bipartite graph with 1 and 3 nodes occurs, whereby the first entry of a tuple represents the degree:
> print complete_bipartite(1,3)>DEGREE_SEQUENCE; {(1 3) (3 1)}

DIAMETER
The diameter of the graph.
 Type:
 Example:
This prints the diameter of the complete bipartite graph of 1 and 3 nodes:
> print complete_bipartite(1,3)>NODE_DEGREES; 3 1 1 1

EIGENVALUES_LAPLACIAN
eigenvalues of the discrete laplacian operator of a graph
 Type:
 Example:
The following prints the eigenvalues of the discrete laplacian operator of the complete graph with 3 nodes:
> print complete(3)>EIGENVALUES_LAPLACIAN 3 3 0

MAX_CLIQUES
The maximal cliques of the graph, encoded as node sets.
 Type:
 Example:
The following prints the maximal cliques of two complete graphs with 3 nodes being connected by a single edge:
> $g = new Graph<Undirected>(ADJACENCY=>[[1,2],[0,2],[0,1,3],[2,4,5],[3,5],[3,4]]); > print $g>MAX_CLIQUES; {{0 1 2} {2 3} {3 4 5}}

MAX_INDEPENDENT_SETS
The maximal independent sets of the graph, encoded as node sets.
 Type:

NODE_DEGREES
Degrees of nodes in the graph.
 Type:
 Example:
This prints the node degrees of the complete bipartite graph of 1 and 3 nodes:
> print complete_bipartite(1,3)>NODE_DEGREES; 3 1 1 1

NODE_IN_DEGREES
The number of incoming edges of the graph nodes.
 Type:
 Example:
To print the number of incoming edges of a directed version of the complete graph with 3 nodes, type this:
> $g = new Graph<Directed>(ADJACENCY=>[[1,2],[2],[]]); > print $g>NODE_IN_DEGREES; 0 1 2

NODE_LABELS
Labels of the nodes of the graph.
 Type:
 Example:
The following prints the node labels of the generalized_johnson_graph with parameters (4,2,1):
> print generalized_johnson_graph(4,2,1)>NODE_LABELS; {0 1} {0 2} {0 3} {1 2} {1 3} {2 3}

NODE_OUT_DEGREES
The number of outgoing edges of the graph nodes.
 Type:
 Example:
To print the number of incoming edges of a directed version of the complete graph with 3 nodes, type this:
> $g = new Graph<Directed>(ADJACENCY=>[[1,2],[2],[]]); > print $g>NODE_OUT_DEGREES; 2 1 0

N_CONNECTED_COMPONENTS
Number of
CONNECTED_COMPONENTS
of the graph. Type:
 Example:
The following prints the number of connected components of two separate triangles:
> $g = new Graph<Undirected>(ADJACENCY=>[[1,2],[0,2],[0,1],[4,5],[3,5],[3,4]]); > print $g>N_CONNECTED_COMPONENTS; 2

N_EDGES
Number of
EDGES
of the graph. Type:
 Example:
This prints the number of edges of the complete graph of 4 nodes (which is 4 choose 2):
> print complete(4)>N_EDGES; 6

N_NODES
Number of nodes of the graph.
 Type:
 Example:
This prints the number of nodes of the complete bipartite graph of 1 and 3 nodes (which is the sum of the nodes in each partition):
> print complete_bipartite(1,3)>N_NODES; 4

SIGNATURE
Difference of the black and white nodes if the graph is
BIPARTITE
. Otherwise 1. Type:
 Example:
The following prints the signature of the complete bipartite graph with 2 and 7 nodes:
> print complete_bipartite(2,7)>SIGNATURE; 5

SIGNED_INCIDENCE_MATRIX
Signed vertexedge incidence matrix; for undirected graphs, the orientation comes from the lexicographic order of the nodes.
 Type:
 Example:
The following prints the signed incidence matrix of the cylcic graph with 4 nodes:
> print cycle_graph(4)>SIGNED_INCIDENCE_MATRIX; 1 0 1 0 1 1 0 0 0 1 0 1 0 0 1 1

STRONGLY_CONNECTED
True if the graph is strongly connected
 Type:
 Example:
The following checks a graph for strong connectivity. First we construct a graph with 4 nodes consisting of two directed circles, which are connected by a single directed edge. We then and check the property:
> $g = new Graph<Directed>(ADJACENCY=>[[1],[0,2],[3],[2]]); > print $g>STRONGLY_CONNECTED; false
The same procedure yields the opposite result for the graph with the reversed edge added in the middle:
> $g = new Graph<Directed>(ADJACENCY=>[[1],[0,2],[1,3],[2]]); > print $g>STRONGLY_CONNECTED; true

STRONG_COMPONENTS
Strong components. Every row contains nodes from a single component
 Type:
 Example:
To print the strong connected components of a graph with 4 nodes consisting of two directed circles and which are connected by a single directed edge, type this:
> $g = new Graph<Directed>(ADJACENCY=>[[1],[0,2],[3],[2]]); > print $g>STRONG_COMPONENTS; {2 3} {0 1}

TRIANGLE_FREE
Determine whether the graph has triangles or not.
 Type:
 Example:
The following checks if the petersen graph contains triangles:
> print petersen()>TRIANGLE_FREE; true

WEAKLY_CONNECTED
True if the graph is weakly connected
 Type:
 Example:
The following checks a graph for weak connectivity. First we construct a graph with 4 nodes consisting of two directed circles, which are connected by a single directed edge. We then check the property:
> $g = new Graph<Directed>(ADJACENCY=>[[1],[0,2],[3],[2]]); > print $g>WEAKLY_CONNECTED; true

WEAKLY_CONNECTED_COMPONENTS
Weakly connected components. Every row contains nodes from a single component
 Type:
 Example:
To print the weakly connected components of a graph with 4 nodes consisting of two directed circles, which are connected by a single directed edge, type this:
> $g = new Graph<Directed>(ADJACENCY=>[[1],[0,2],[3],[2]]); > print $g>WEAKLY_CONNECTED_COMPONENTS; {0 1 2 3}
The same procedure yields the opposite outcome using the same graph without the linking edge between the two circles:
> $g = new Graph<Directed>(ADJACENCY=>[[1],[0],[3],[2]]); > print $g>WEAKLY_CONNECTED_COMPONENTS; {0 1} {2 3}
Methods
Combinatorics
These methods capture combinatorial information of the object. Combinatorial properties only depend on combinatorial data of the object like, e.g., the face lattice.

EDGES()
Explore the graph as a sequence of its edges.
 Returns:
Visualization
These methods are for visualization.

VISUAL()
Visualizes the graph. Decorations may include
Coord
, disabling the default spring embedder. Options:
Int
seed
: random seed value for the spring embedder option list
Visual::Graph::decorations
 Returns:
 Example:
The following visualizes the petersen graph with default settings:
> petersen()>VISUAL;
The following shows some modified visualization style of the same graph:
> petersen()>VISUAL(NodeColor=>"green",NodeThickness=>6,EdgeColor=>"purple",EdgeThickness=>4);