Macaulay2 » Documentation
Packages » EdgeIdeals :: Graph
next | previous | forward | backward | up | index | toc

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.

See also

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.


The source of this document is in EdgeIdeals.m2:1485:0.