Perfecte graaf

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Voorbeeld van een perfecte graaf. In vet is een geïnduceerde subgraaf aangeduid met 3 knopen. Het is een clique met chromatisch getal 3. Voor elke subgraaf van deze graaf is het cliquegetal gelijk aan het chromatisch getal.

Een perfecte graaf is een graaf waarvan voor elke geïnduceerde subgraaf geldt dat het cliquegetal gelijk is aan het chromatisch getal van die subgraaf.

Een geïnduceerde subgraaf bestaat uit een deelverzameling van de knopen van de graaf en enkel de zijden van de graaf tussen die knopen.

Het cliquegetal is het aantal knopen in de grootste volledige subgraaf van een graaf.

De term "perfecte graaf" wordt toegeschreven aan de Franse wiskundige Claude Berge die hem in 1963 in een artikel gebruikte.

Men kan in polynomiale tijd bepalen of een gegeven graaf een perfecte graaf is.

Van een perfecte graaf kan men in polynomiale tijd het chromatisch getal, cliquegetal of stabiliteitsgetal berekenen, terwijl dit in het algemene geval een NP-compleet probleem is.

Voorbeelden van perfecte grafen[bewerken]

Sterke stelling over perfecte grafen[bewerken]

Claude Berge formuleerde in 1961 het vermoeden, dat een graaf G een perfecte graaf is als en slechts als G geen geïnduceerde subgraaf bevat die een oneven cykel van lengte 5 of meer is, of het complement van zo een cykel is (een cykel is een reeks door zijden verbonden knopen met hetzelfde begin- en eindpunt). Het bewijs van dit vermoeden werd in 2002 aangekondigd en in 2006 gepubliceerd door Maria Chudnovsky, Neil Robertson, Paul Seymour en Robin Thomas in een artikel dat 179 bladzijden beslaat.[1] Het vermoeden staat nu bekend als de "sterke stelling over perfecte grafen".

De "(zwakke) stelling over perfecte grafen" zegt dat de complementgraaf van een perfecte graaf ook een perfecte graaf is. Dit was ook een vermoeden van Claude Berge, dat in 1972 bewezen is door László Lovász.[2]

Bronnen, noten en/of referenties
  1. Maria Chudnovsky, Neil Robertson, Paul Seymour, Robin Thomas. "The strong perfect graph theorem", Annals of Mathematics, Vol. 164, 2006, pp. 51–229. DOI:10.4007/annals.2006.164.51
  2. L. Lovász. "A Characterization of Perfect Graphs." Journal of Combinatorial Theory (B), 1972, Vol. 13, pp. 95-98. DOI:10.1016/0095-8956(72)90045-7