Ekstrem grafteori

Ekstremal grafteori er en gren af ​​grafteori . Ekstrem grafteori studerer de ekstreme (maksimum eller minimum) egenskaber ved grafer , der opfylder visse betingelser. Ekstremalitet kan henvise til forskellige grafinvarianter , såsom rækkefølge, størrelse eller omkreds. I en mere abstrakt forstand studerer teorien, hvordan en grafs globale egenskaber påvirker grafens lokale understrukturer [1] .

Eksempler

For eksempel er et simpelt spørgsmål i ekstremal grafteori "Hvilke n -vertex acykliske grafer har det maksimale antal kanter?" Ekstremgraferne for dette spørgsmål vil være n -vertex træer med n  − 1 kanter [2] . Et mere generelt typisk spørgsmål er: Givet en grafegenskab P , en invariant u [3] og et sæt af grafer H , ønsker vi at finde minimumsværdien m , således at enhver graf i H , der har u større end m , har egenskaben P . I eksemplet ovenfor var H sættet af grafer med n toppunkter, P var egenskaben ved at være en cyklus, og u var antallet af kanter i grafen. Enhver graf med n toppunkter og mere end n  − 1 kanter skal derfor indeholde en cyklus.

Nogle funktionelle resultater i ekstremal grafteori er spørgsmål af den ovenfor nævnte art. For eksempel besvares spørgsmålet om, hvor mange kanter af en graf med n toppunkter, der skal være i grafen, så den nødvendigvis indeholder en klike på størrelsen k som undergraf , af Turans sætning . Hvis man i stedet for kliker i et lignende spørgsmål bliver spurgt om komplette multipartite grafer, er svaret givet af Erdős-Stone-sætningen .

Historie

Ekstrem grafteori, i strengeste forstand, er en gren af ​​grafteori, som er elsket og udviklet i Ungarn.

—  Bollobas, 2004

Ekstrem grafteori opstod i 1941, da Turan beviste sin sætning , der definerede grafer af orden n , der ikke indeholder en komplet graf K k af orden k og er ekstreme med hensyn til størrelse (det vil sige med så få kanter som muligt) [4] . Det næste afgørende år var 1975, da Szémeredi beviste sin teorem , et vigtigt værktøj til at angribe ekstreme problemer [4] .

Grafdensitet

Et typisk resultat af ekstremal grafteori er Turans sætning . Sætningen besvarer følgende spørgsmål. Hvad er det maksimalt mulige antal kanter i en urettet graf G med n hjørner, der ikke indeholder K 3 (tre hjørner A , B , C med kanter AB , AC , BC , dvs. en trekant) som en undergraf? Den komplette todelte graf , hvor delene afviger med højst 1, er den eneste ekstremalgraf med denne egenskab. Optælling indeholder

ribben. Lignende spørgsmål er blevet rejst for forskellige andre undergrafer af H i stedet for K 3 . For eksempel spørger Zarankiewicz-problemet om den største (efter antal kanter) graf, der ikke indeholder en fast komplet todelt graf som en undergraf, og den lige kontursætning spørger om den største graf, der ikke indeholder lige cyklusser af fast længde. Turan fandt også den (unikke) største graf uden K k , som er opkaldt efter ham, nemlig Turan-grafen . Denne graf er en komplet forening af "k-1" uafhængige sæt og har et maksimum

ribben. Den største graf med n toppunkter, der ikke indeholder C 4 , har

ribben.

Minimumsgradsbetingelser

De nævnte sætninger giver betingelser for fremkomsten af ​​små objekter inde i en (evt.) stor graf. Som modsatte yderpunkter kan man lede efter en tilstand, der fremtvinger eksistensen af ​​en struktur, der dækker alle hjørner. Men grafen

kanter kan have isolerede hjørner, selvom næsten alle mulige kanter er til stede i grafen, hvilket betyder, at selv meget tætte grafer måske ikke har den struktur af interesse, der dækker alle hjørner. En simpel betingelse baseret på kanttælling giver ikke information om hvordan kanterne er fordelt i grafen, så ofte giver en sådan betingelse uinteressante resultater for meget store strukturer. I stedet indfører vi begrebet minimumsgrad. Minimumsgraden af ​​en graf G er defineret som

Angivelse af en stor minimumsgrad fjerner indvendingen om, at "patologiske" hjørner kan eksistere. Hvis minimumsgraden af ​​en graf G for eksempel er 1, så kan der ikke være isolerede hjørner (selvom G indeholder meget få kanter).

Det klassiske resultat er Diracs sætning , som siger, at enhver graf G med n toppunkter og minimumsgrad mindst n/2 indeholder en Hamiltonsk cyklus .

Se også

Noter

  1. ↑ Diestel, 2010 .
  2. ↑ Bollobás, 2004 , s. 9.
  3. ↑ Generelt er en egenskab ved en graf og en invariant en og samme.
  4. ↑ 1 2 Bollobás, 1998 , s. 104.

Litteratur