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

- graph -- constructor for Graph
- HyperGraph -- a class for hypergraphs
- Constructor Overview -- a summary of the many ways of making graphs and hypergraphs

## 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 /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/EdgeIdeals.m2:1485:0.