Teoria grafurilor extreme

Teoria grafurilor extreme este o ramură a teoriei grafurilor . Teoria grafurilor extreme studiază proprietățile extreme (maxime sau minime) ale grafurilor care îndeplinesc anumite condiții. Extremalitatea se poate referi la diferite invariante ale graficului , cum ar fi ordinea, dimensiunea sau circumferința. Într-un sens mai abstract, teoria studiază modul în care proprietățile globale ale unui graf afectează substructurile locale ale grafului [1] .

Exemple

De exemplu, o întrebare simplă în teoria grafurilor extreme este „Care grafice aciclice n -vertice au numărul maxim de muchii?” Graficele extreme pentru această întrebare vor fi arbori n -vertex cu n  − 1 muchii [2] . O întrebare tipică mai generală este: Având în vedere o proprietate grafică P , un invariant u [3] , și un set de grafice H , dorim să găsim valoarea minimă m astfel încât orice grafic din H care are u mai mare decât m are proprietatea P . În exemplul de mai sus , H era mulțimea de grafice cu n vârfuri, P era proprietatea de a fi un ciclu și u era numărul de muchii din grafic. Astfel, orice grafic cu n vârfuri și mai mult de n  − 1 muchii trebuie să conțină un ciclu.

Unele rezultate funcționale în teoria grafurilor extreme sunt întrebări de tipul celor menționate mai sus. De exemplu, întrebarea câte muchii ale unui graf cu n vârfuri trebuie să fie în graf, astfel încât acesta să conțină în mod necesar o clică de dimensiunea k ca subgraf este răspunsă de teorema lui Turan . Dacă în loc de clicuri într-o întrebare similară se întreabă despre grafuri multipartite complete, răspunsul este dat de teorema Erdős-Stone .

Istorie

Teoria grafurilor extreme, în sensul cel mai strict, este o ramură a teoriei grafurilor care este îndrăgită și dezvoltată în Ungaria.

—  Bollobas, 2004

Teoria grafurilor extreme a apărut în 1941 când Turan și-a demonstrat teorema definind grafuri de ordin n care nu conțin un graf complet K k de ordin k și sunt extremale în raport cu dimensiunea (adică cu cât mai puține muchii posibil) [4] . Următorul an pivot a fost 1975, când Szémeredi și-a demonstrat teorema , un instrument important pentru atacarea problemelor extreme [4] .

Densitatea graficului

Un rezultat tipic al teoriei grafurilor extreme este teorema lui Turan . Teorema răspunde la următoarea întrebare. Care este numărul maxim posibil de muchii într-un graf nedirecționat G cu n vârfuri care nu conține K 3 (trei vârfuri A , B , C cu muchii AB , AC , BC , adică un triunghi) ca subgraf? Graficul bipartit complet , în care părțile diferă cu cel mult 1, este singurul grafic extremal cu această proprietate. Numărul conține

coaste. Întrebări similare au fost ridicate pentru diferite alte subgrafe ale lui H în loc de K 3 . De exemplu, problema Zarankiewicz întreabă despre cel mai mare graf (după numărul de muchii) care nu conține un graf bipartit complet fix ca subgraf, iar teorema conturului par întreabă despre cel mai mare graf care nu conține chiar cicluri de lungime fixă. Turan a găsit și cel mai mare grafic (unic) care nu conține K k , care poartă numele lui, și anume graful Turan . Acest grafic este o unire completă de mulțimi independente „k-1” și are un maxim

coaste. Cel mai mare grafic cu n vârfuri care nu conține C 4 are

coaste.

Condiții minime de grad

Teoremele menționate dau condiții pentru apariția obiectelor mici în interiorul unui grafic (posibil) mare. Ca extreme opuse, se poate căuta o condiție care forțează existența unei structuri care acoperă toate vârfurile. Dar graficul

muchiile pot avea vârfuri izolate, deși aproape toate muchiile posibile sunt prezente în grafic, ceea ce înseamnă că chiar și graficele foarte dense pot să nu aibă structura de interes care acoperă toate vârfurile. O condiție simplă bazată pe numărarea muchiilor nu oferă informații despre modul în care muchiile sunt distribuite în grafic, așa că adesea o astfel de condiție dă rezultate neinteresante pentru structuri foarte mari. În schimb, introducem noțiunea de grad minim. Gradul minim al unui grafic G este definit ca

Specificarea unui grad minim mare înlătură obiecția că ar putea exista vârfuri „patologice”. Dacă gradul minim al unui grafic G este 1, de exemplu, atunci nu pot exista vârfuri izolate (chiar dacă G conține foarte puține muchii).

Rezultatul clasic este teorema lui Dirac , care afirmă că orice grafic G cu n vârfuri și grad minim cel puțin n/2 conține un ciclu hamiltonian .

Vezi și

Note

  1. ↑ Diesel, 2010 .
  2. ↑ Bollobás, 2004 , p. 9.
  3. ↑ În general, o proprietate a unui grafic și a unui invariant sunt una și aceeași.
  4. ↑ 1 2 Bollobás, 1998 , p. 104.

Literatură