Macaulay2 » Documentation
Packages » Chordal :: chordalGraph
next | previous | forward | backward | up | index | toc

# chordalGraph -- chordal completion of a graph

- Usage:
    `chordalGraph(G)`
    `chordalGraph(G,ordering)`
- Inputs:
  - G, a graph,
  - ordering, a list, (optional)
- Outputs:
  - an instance of the type ChordalGraph, chordal graph that contains G as a subgraph

## Description

This method finds a simple chordal completion of a given graph G. A chordal completion is a supergraph of G that is chordal. If a vertex ordering is given, it completes the graph using this ordering; otherwise it finds one using a minimum degree ordering heuristic.

    i1 : G = wheelGraph(6)

    o1 = Graph{0 => {1, 2, 3, 4, 5}}
               1 => {0, 2, 5}
               2 => {0, 1, 3}
               3 => {0, 2, 4}
               4 => {0, 3, 5}
               5 => {0, 1, 4}

    o1 : Graph

    i2 : chordalGraph G

    o2 = ChordalGraph{1 => {2, 0, 5} }
                      2 => {0, 3, 5}
                      0 => {3, 4, 5}
                      3 => {4, 5}
                      4 => {5}
                      5 => {}

    o2 : ChordalGraph

    i3 : G = graph(toList(0..9),{
             {0,{6,7}},{1,{4,9}},{2,{3,5}},{3,{7,8}},
             {4,{5,8}},{5,{8}},{6,{8,9}},{7,{8}},{8,{9}} });

    i4 : chordalGraph G

    o4 = ChordalGraph{0 => {6, 7}    }
                      1 => {4, 9}
                      2 => {3, 5}
                      3 => {5, 7, 8}
                      4 => {5, 8, 9}
                      5 => {7, 8, 9}
                      6 => {7, 8, 9}
                      7 => {8, 9}
                      8 => {9}
                      9 => {}

    o4 : ChordalGraph

## Caveat

If the input is a digraph, it must be topologically ordered; no check is made.

## See also

- ChordalGraph -- a chordal graph

## Ways to use chordalGraph:

- `chordalGraph(Digraph)`
- `chordalGraph(Graph)`
- `chordalGraph(Graph,List)`
- `chordalGraph(ElimTree)` -- see ElimTree -- the elimination tree of a chordal graph

## For the programmer

The object chordalGraph is a method function.

The source of this document is in /build/macaulay2-88fgJW/macaulay2-1.25.11+ds/M2/Macaulay2/packages/Chordal/ChordalDoc.m2:402:0.