În teoria graficelor , duritatea („ toughness ” în engleză) este o măsură a conexiunii unui grafic.
Se spune că un grafic G este t- greu pentru un număr real dat t dacă, pentru orice număr întreg k > 1 , G nu poate fi împărțit în k componente conectate prin eliminarea vârfurilor mai mici decât tk . De exemplu, un grafic este 1-hard dacă numărul de componente conectate obținut prin eliminarea unui set de vârfuri este întotdeauna cel puțin la fel de mare ca numărul de vârfuri eliminate. Duritatea unui grafic este cel mai mare număr t pentru care este t- solid; este un număr finit pentru toate graficele finite, cu excepția graficelor complete , care, prin convenție, au tenacitate infinită.
Noțiunea de duritate a graficului a fost introdusă pentru prima dată de Václav Chvátal în 1973. De atunci, au fost publicate multe lucrări despre duritate; un articol de recenzie din 2006 al lui Bauer, Broersma & Schmeichel enumeră 99 de teoreme și 162 de articole pe această temă.
Eliminarea k vârfuri dintr-un grafic de cale poate împărți graficul rămas în cel mult k + 1 componente conectate. Maximul raportului dintre numărul de componente și numărul de vârfuri șterse se obține prin îndepărtarea unui vârf din interiorul căii care îl împarte în două componente. Prin urmare, căile sunt12-greu. Pe de altă parte, eliminarea k vârfurilor dintr-un grafic de ciclu lasă cel mult k componente conectate și uneori lasă exact k componente conectate, astfel încât un ciclu să fie 1- dur.
Dacă un grafic este t- dur, atunci obținem, fixând k = 2 este că orice set de 2 t - 1 vârfuri poate fi eliminat fără a împărți graficul în jumătate. Cu alte cuvinte, un grafic t- hard este, de asemenea , conectat la 2 t -summit .
Chvátal 1973 a observat că orice grafic de ciclu și, prin urmare, orice lanț hamiltonian este 1- dur; prin urmare, a fi 1- dur este o condiție necesară pentru ca un grafic să fie hamiltonian. El a conjecturat că există un prag t astfel încât orice grafic t- hard să fie hamiltonian. Conjectura inițială a lui Chvátal cu t = 2 ar fi dat o dovadă a teoremei lui Fleischner, dar a fost infirmată de Bauer, Broersma și Veldman în 2000. Existența unui prag de duritate mai mare pentru graficele hamiltoniene este o problemă deschisă.
Testarea dacă un grafic este 1- hard este co-NP -complet. Cu alte cuvinte, problema deciziei al cărei răspuns este „da” pentru un grafic care nu este 1-solid și „nu” pentru un grafic care este 1-dur, este NP-completă . Este același lucru pentru orice număr rațional pozitiv fix q : testați dacă un grafic este q -dur este co-NP-complet.