În matematică , în special în teoria graficelor , teorema grafurilor perfecte (uneori cunoscută teorema graficelor puternice perfecte ) este o caracterizare a graficelor perfecte prin unele subgrafe excluse (în) , conjecturată de Claude Berge în 1961. Maria Chudnovsky , Neil Robertson , Paul Seymour , iar Robin Thomas a anunțat demonstrația în 2002 și a publicat-o în 2006. A câștigat autorilor Premiul Fulkerson 2009 .
Numim un subgraf indus de un anumit set de vârfuri ale unui grafic G graficul format din aceste vârfuri și marginile lui G care le leagă; o clică este un subgraf indus izomorf la un grafic complet , adică toate vârfurile sunt conectate; numărul de clica unui grafic este numărul de noduri ale celei mai mari clică sale. Numărul cromatic al unui grafic este cel mai mic număr de culori necesar pentru a exista o colorare a acestui grafic, adică o funcție care asociază cu fiecare vârf al graficului o culoare, astfel încât doi vârfuri conectate printr-o margine să aibă culori diferite (numărul cromatic este întotdeauna mai mare sau egal cu numărul de clicuri). În fine, Graficul complement al G este graful având aceleași înălțimi ca G și în care două vârfuri sunt conectate dacă și numai dacă acestea nu sunt în G .
Cu aceste definiții, un grafic perfect este un grafic pentru care fiecare subgraf indus are un număr de clicuri egal cu numărul său cromatic.
Multe clase de grafice sunt perfecte, de exemplu grafice bipartite , grafice cu cabluri și grafice de comparabilitate . În lucrările din 1961 și 1963, unde a definit aceste grafice pentru prima dată, Claude Berge a observat că un grafic perfect nu poate conține o gaură ciudată, adică un grafic indus care este un ciclu de ordin impar. Mai mare de 5, deoarece acestea au 2 pentru numărul de clicuri și 3 pentru numărul cromatic. De asemenea, un grafic perfect nu poate conține un ciudat anti gaura (adică o gaură a graficului complementar) , deoarece un anti-gaura de 2 k + 1 vârfuri are k pentru numărul de clicuri și k + 1 pentru numărul cromatice (dacă k > 1 ). Graficele care nu au nici găuri, nici anti-găuri au fost numite grafice Berge .
Berge a conjecturat că aceste grafice erau perfecte (și, prin urmare, că graficele lui Berge s-au identificat cu grafice perfecte), care a fost numită conjectura (puternică) a grafului perfect, până la demonstrarea sa în 2002, unde a devenit
Teorema graficului perfect - Un grafic este perfect dacă și numai dacă nici el, nici complementul său nu conțin un subgraf indus care este un ciclu de ordin impar ≥ 5.
Această caracterizare fiind aplicată identic unui grafic și complementului său, rezultă imediat din acesta următorul rezultat mai slab:
Teorema graficului perfect slab - Dacă un grafic este perfect, complementul său este, de asemenea, perfect.
Acest ultim rezultat, de asemenea conjecturat de Claude Berge, a fost demonstrat în 1972 de László Lovász . Teorema graficului perfect este, din acest motiv, uneori cunoscută sub numele de teorema graficului perfect puternic .
Dovada teoremei de Maria Chudnovsky , Neil Robertson , Paul Seymour și Robin Thomas (în 2002) urmează o schemă conjecturată în 2001 de Conforti , Gérard Cornuéjols , Robertson, Seymour și Thomas, conform căreia orice grafic Berge este compus din mai multe grafice simple prin intermediul a patru construcții distincte, reducând în cele din urmă la grafice perfecte de cinci tipuri posibile. Un grafic Berge minim imperfect nu poate fi descompus în acest fel, ceea ce arată că un contraexemplu al teoremei este imposibil. Acest plan de atac preia o presupunere anterioară a descompunerii structurale care sa dovedit a fi eronată.
Cele cinci clase de grafice perfecte care servesc ca bază pentru aceste descompuneri structurale sunt grafice bipartite , grafice adjuvante ale graficelor bipartite, grafice complementare ale graficelor bipartite și apendicele lor și grafice „dublu separate”. Putem vedea cu ușurință că graficele bipartite sunt perfecte: orice subgraf indus non-trivial are 2 pentru numărul cromatic și pentru numărul de clicuri. Perfectiunea graf bipartit suplimentare și alte adjuncții lor grafice sunt ambele echivalente cu Kőnig teoremă care leagă dimensiunile cuplajului maxim , stabilitate maximă și minimă acoperire pentru grafice bipartite. Perfecțiunea graficelor atașate graficelor bipartite este echivalentă cu faptul că acestea din urmă au un indice cromatic egal cu gradul lor maxim, rezultat demonstrat și de Kőnig. Arătăm că graficele „dublu separate” sunt, de asemenea, perfecte.
Cele patru tipuri de descompuneri utilizate în dovadă sunt joncțiunile 2 și complementele lor, partițiile antisimetrice echilibrate și perechile omogene (în 2006, Chudnovsky a simplificat dovada teoremei grafice perfecte arătând că descompunerile în perechi omogene ar putea fi eliminate din această listă ).
O joncțiune 2 este o partiție a vârfurilor unui grafic în două subseturi astfel încât marginile care se conectează între ele formează două grafuri bipartite complete fără vârfuri comune. Un grafic care admite o joncțiune cu 2 poate fi descompus în două subgrafe induse numite blocuri prin înlocuirea unuia dintre cele două subseturi printr-o cale minimă a acestui set conectând unul dintre graficele bipartite complete la celălalt, iar graficul este perfect dacă și numai dacă cele două blocuri sunt perfecte. Astfel, un grafic imperfect minim având o joncțiune 2 se identifică cu unul dintre blocurile sale; arătăm apoi că acest bloc este un ciclu de ordine impar și, prin urmare, că graficul nu este un grafic Berge; același raționament permite să arate că un grafic imperfect minim al cărui complement admite o joncțiune 2 nu este un grafic Berge.
O partiție antisimetrică (în) este o partiție a vârfurilor grafului în două subseturi inducând respectiv un subgraf neconectat și complementul unui subgraf; Chvátal a presupus că un grafic Berge minim imperfect nu ar putea admite o partiție antisimetrică. Chudnovsky a introdus câteva constrângeri tehnice suplimentare, demonstrând astfel conjectura lui Chvátal pentru partițiile antisimetrice „echilibrate”.
O pereche omogenă este un fel de descompunere modulară (în) a unui grafic. Este o partiție a graficului în trei subseturi de vârfuri, V 1 , V 2 și V 3 , astfel încât V 1 și V 2 împreună să aibă cel puțin trei vârfuri și V 3 cel puțin două vârfuri și că pentru fiecare vârf v de V 3 și fiecare i din {1,2}, fie v este adiacent tuturor vârfurilor lui V i , fie este adiacent niciunei. Un grafic Berge minim imperfect nu poate avea o pereche omogenă.
Demo-ul că tot graficul Berge admite o descompunere a celor patru (sau este unul dintre cele cinci tipuri de bază) urmează o analiză prin descompunere dacă (în) , în funcție de prezența unor configurații în grafic: un stent , subgraf care poate fi descompus în trei căi induse (cu anumite constrângeri suplimentare), complementul unui expansor sau, în final, al unei roți adecvate , configurație apropiată de un grafic al roții , format dintr-un ciclu indus și un „butuc” de vârf adiacent la cel puțin trei vârfuri ale ciclul (cu unele constrângeri suplimentare). Orice grafic Berge conține cel puțin una dintre aceste trei configurații și, pentru fiecare dintre aceste trei cazuri, arătăm că este descompozibil; aceasta completează dovada teoremei.