Chordale graaf

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Dit deel van een graaf is chordaal omdat de zwarte cykel twee koorden (groen) heeft. Beide koorden zijn nodig; als er een zou ontbreken zou er een cykel van lengte vier bestaan zonder koorde.

Een graaf G is chordaal als voor elke cykel van lengte vier of meer er een koorde bestaat, dit is een kant die twee niet-naburige knopen in de cykel verbindt. Dit wil zeggen dat een chordale graaf geen "circuits" of cykels van vier of meer kanten bevat zonder een koorde. Men zegt dat dergelijke grafen getrianguleerd zijn.

Chordale grafen zijn een deelverzameling van de perfecte grafen.

Het aantal enkelvoudige chordale grafen met n=1,2, 3,... knopen is 1, 2, 4, 10, 27, 94, 393...[1]

Het aantal samenhangende enkelvoudige chordale grafen met n=1,2, 3,... knopen is 1, 1, 2, 5, 15, 58, 272...[2]

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).

Een intervalgraaf is een voorbeeld van een chordale graaf.

Externe link[bewerken]

Bronnen, noten en/of referenties
  1. rij A048193 in OEIS
  2. rij A048192 in OEIS