Graph -- a class for graphs

Description

This class represents simple graphs. This class extends HyperGraph and hence inherits all HyperGraph methods.

i1 : R = QQ[w,x,y,z];

i2 : G = graph(R, {{w,x},{w,y},{w,z},{y,z}});

i3 : vertices G

o3 = {w, x, y, z}

o3 : List

i4 : edges G

o4 = {{w, x}, {w, y}, {w, z}, {y, z}}

o4 : List

i5 : ring G

o5 = R

o5 : PolynomialRing

Like hypergraphs, graphs are associated with a polynomial ring whose variables are the vertices of the graph. Isolated vertices should not appear in the edge list. As a consequence, the edgeIdeal of a graph is always generated by quadratics. The fact that isolated vertices are not edges in a graph affects the output of the methods connectedComponents, numConnectedComponents, and isConnected. One can use connectedGraphComponents, numConnectedGraphComponents, and isConnectedGraph to ensure that each isolated vertex is counted as a separate connected component.

Functions and methods returning a graph :

antiCycle -- returns a graph of an anticycle
antiCycle(List), see antiCycle -- returns a graph of an anticycle
antiCycle(Ring), see antiCycle -- returns a graph of an anticycle
antiCycle(Ring,ZZ), see antiCycle -- returns a graph of an anticycle
completeGraph(List), see completeGraph -- returns a complete graph
completeGraph(Ring), see completeGraph -- returns a complete graph
completeGraph(Ring,ZZ), see completeGraph -- returns a complete graph
completeMultiPartite(Ring,List), see completeMultiPartite -- returns a complete multipartite graph
completeMultiPartite(Ring,ZZ,ZZ), see completeMultiPartite -- returns a complete multipartite graph
cycle -- returns a graph cycle
cycle(List), see cycle -- returns a graph cycle
cycle(Ring), see cycle -- returns a graph cycle
cycle(Ring,ZZ), see cycle -- returns a graph cycle
graph -- constructor for Graph
graph(HyperGraph), see graph -- constructor for Graph
graph(Ideal), see graph -- constructor for Graph
graph(List), see graph -- constructor for Graph
graph(MonomialIdeal), see graph -- constructor for Graph
graph(PolynomialRing,List), see graph -- constructor for Graph

Methods that use a graph :

adjacencyMatrix(Graph), see adjacencyMatrix -- returns the adjacency Matrix of a graph
allEvenHoles(Graph), see allEvenHoles -- returns all even holes in a graph
allOddHoles(Graph), see allOddHoles -- returns all odd holes in a graph
cliqueComplex(Graph), see cliqueComplex -- returns the clique complex of a graph
cliqueNumber(Graph), see cliqueNumber -- computes the clique number of a graph
complementGraph(Graph), see complementGraph -- returns the complement of a graph or hypergraph
getCliques(Graph), see getCliques -- returns cliques in a graph
getCliques(Graph,ZZ), see getCliques -- returns cliques in a graph
getMaxCliques(Graph), see getMaxCliques -- returns maximal cliques in a graph
hasOddHole(Graph), see hasOddHole -- tells whether a graph contains an odd hole
hyperGraph(Graph), see hyperGraph -- constructor for HyperGraph
independenceNumber(Graph), see independenceNumber -- determines the independence number of a graph
inducedGraph(Graph,List), see inducedGraph -- returns the induced subgraph of a graph
isBipartite(Graph), see isBipartite -- determines if a graph is bipartite
isChordal(Graph), see isChordal -- determines if a graph is chordal
isForest(Graph), see isForest -- determines whether a (hyper)graph is a forest
isLeaf(Graph,ZZ), see isLeaf -- determines if an edge (or vertex) is a leaf of a (hyper)graph
isPerfect(Graph), see isPerfect -- determines whether a graph is perfect
numTriangles(Graph), see numTriangles -- returns the number of triangles in a graph
smallestCycleSize(Graph), see smallestCycleSize -- returns the size of the smallest induced cycle of a graph
spanningTree(Graph), see spanningTree -- returns a spanning tree of a graph

For the programmer

The object Graph is a type, with ancestor classes HyperGraph < HashTable < Thing.

Graph -- a class for graphs

Description

See also

Functions and methods returning a graph :

Methods that use a graph :

For the programmer