The algorithm uses the Strong Perfect Graph Theorem, which says that G is perfect if and only if neither G nor its complement contains an odd hole. hasOddHole is used to determine whether these conditions hold.
i1 : R = QQ[x_1..x_7]; |
i2 : G = complementGraph cycle R; --odd antihole with 7 vertices |
i3 : isPerfect G o3 = false |
i4 : H = cycle(R,4)
o4 = Graph{edges => {{x , x }, {x , x }, {x , x }, {x , x }}}
1 2 2 3 3 4 1 4
ring => R
vertices => {x , x , x , x , x , x , x }
1 2 3 4 5 6 7
o4 : Graph
|
i5 : isPerfect H o5 = true |
The object isPerfect is a method function.