Available versions of this document: latest release, 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

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 seperate 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}}

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 seperate 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);