Chordale graaf

■ cykel

■ koorde

Dit deel van een graaf is chordaal omdat de cykel twee koorden heeft. Beide koorden zijn nodig, als er een zou ontbreken zou er een cykel van lengte vier bestaan zonder koorde.

Een graaf ${\displaystyle G}$ is chordaal als voor iedere cykel ${\displaystyle C}$ van lengte vier of meer in ${\displaystyle G}$ er een koorde bestaat. Een koorde is een zijde die twee knopen in ${\displaystyle C}$ verbindt die in ${\displaystyle C}$ niet naast elkaar liggen, zodat er in ${\displaystyle G}$ geen cykels van vier of meer zijden zonder een koorde meer voorkomen. Men zegt dat dergelijke grafen getrianguleerd zijn. Chordale grafen zijn een deelverzameling van de perfecte grafen. Een intervalgraaf is een voorbeeld van een chordale graaf.

Het is mogelijk om in lineaire tijd te bepalen of een gegeven graaf chordaal is. Men kan een maximumclique van een chordale graaf vinden in polynomiale tijd, voor algemene grafen is dit een NP-volledig probleem.

• Het aantal enkelvoudige chordale grafen met ${\displaystyle n=1,2,3,...}$ knopen is 1, 2, 4, 10, 27, 94, 393...[1]
• Het aantal samenhangende enkelvoudige chordale grafen met ${\displaystyle n=1,2,3,...}$ knopen is 1, 1, 2, 5, 15, 58, 272...[2]

voetnoten

1. rij A048193 in OEIS
2. rij A048192 in OEIS

websites

• MathWorld. Chordal Graph.