Graf uden trekanter

I grafteori er en trekantfri graf en urettet graf, hvor ingen tre hjørner danner en trekant af kanter. Trekantfrie grafer kan også defineres som grafer med kliknummer ≤ 2, grafer med omkreds ≥ 4, grafer uden genererede 3-cyklusser eller som lokalt uafhængige grafer.

Ved Turans sætning er en n -vertex trekantfri graf med det maksimale antal kanter en komplet todelt graf , hvor antallet af hjørner i hver del af grafen er så tæt som muligt.

En graf med 2n hjørner og ingen trekanter skal have færre kanter. $n^{2}+1$

Problemet med at finde trekanter

Problemet med at finde trekanter er problemet med at bestemme, om en graf indeholder trekanter eller ej. Hvis grafen indeholder en trekant, bliver algoritmen ofte bedt om at udlæse tre hjørner, der danner en trekant.

Det er muligt at kontrollere, om en graf med m kanter har trekanter i O( m 1,41 ) tid. [1] En anden fremgangsmåde er at finde sporet af matricen A 3 , hvor A er grafens nabomatrix . Sporet er nul, hvis og kun hvis der ikke er trekanter i grafen. For tætte grafer er denne simple matrixmultiplikationsalgoritme mere effektiv , fordi den reducerer tidskompleksiteten til O( n 2,373 ), hvor n er antallet af hjørner.

Som vist af Imrich, Klavžar og Mulder ( Imrich, Klavžar, Mulder 1999 ), er trekantfri grafgenkendelse ækvivalent i kompleksitet med mediangrafgenkendelse . Men i øjeblikket bruger de bedste mediangrafalgoritmer trekantgenkendelse som en underrutine og ikke omvendt.

Kompleksiteten af beslutningstræet eller kompleksiteten af forespørgslen af problemet, hvor forespørgsler til oraklet, der husker grafens tilstødende matricer, er lig med Θ( n 2 ). For kvantealgoritmer er den bedste nedre grænse dog Ω( n ), men den bedst kendte algoritme har et estimat på O( n 1,29 ) ( Belovs 2011 ).

Uafhængighedstallet og Ramsey-teorien

Et uafhængigt sæt af hjørner i en n -hjørne trekantfri graf er let at finde - enten er der et hjørne med mere end naboer (i hvilket tilfælde naboerne danner et uafhængigt sæt), eller alle hjørner har mindre end naboer (hvori tilfælde, at ethvert største uafhængige sæt skal have mindst hjørner) [2] . Denne grænse kan forbedres lidt - i enhver graf uden trekanter er der et uafhængigt sæt med toppunkter, og i nogle grafer uden trekanter har ethvert uafhængigt sæt toppunkter. [3] En måde at skabe tegonfrie grafer, hvor alle uafhængige mængder er små, er den trekantfri proces [ 4] , som skaber maksimale trekantfrie grafer ved sekventielt at tilføje tilfældigt valgte kanter, hvorved man undgår at skabe trekanter. Med en høj grad af sandsynlighed danner processen grafer med uafhængighedsnummer . Man kan også finde almindelige grafer med de samme egenskaber. [5] ${\sqrt {n}}$ ${\sqrt {n}}$ ${\sqrt {n}}$ ${\sqrt {n}}$ $\Omega ({\sqrt {n\log n)))$ $O({\sqrt {n\log n)))$ $O({\sqrt {n\log n)))$

Disse resultater kan også forstås som at sætte de asymptotiske grænser for Ramsey-tallene R(3, t ) i formen - hvis kanterne på en komplet graf med hjørner er farvet røde og blå, så indeholder enten den røde graf en trekant, eller der er ingen trekanter i den, og så skal der eksistere et selvstændigt sæt af størrelse t svarende til en klike af denne størrelse i den blå graf. $\Theta ({\tfrac {t^{2)){\log t)))$ $\Omega ({\tfrac {t^{2)){\log t)))$

Farvelægningsgrafer uden trekanter

Meget forskning i trekantfri grafer har fokuseret på graffarvning . Enhver todelt graf (det vil sige enhver tofarvebar graf) har ikke trekanter, og Grötzschs sætning siger, at enhver trekantfri plan graf kan være trefarvet. [6] Ikke-plane grafer uden trekanter kan dog kræve mere end tre farver.

Mycielski ( 1955 ) definerede en konstruktion, nu kaldet Mycielskian , som danner en ny trekantfri graf ud fra en anden trekantfri graf. Hvis en graf har kromatisk tal k , har dens Mychelskian kromatisk tal k + 1, så denne konstruktion kan bruges til at vise, at der kan kræves et vilkårligt stort antal farver for at farve en trekantfri ikke-plan graf. Især Grötzsch -grafen, en graf med 11 hjørner dannet ved at gentage Mycielskis konstruktion, er en trekantfri graf, der ikke kan farves med færre end fire farver, og er den mindste graf med disse egenskaber. [7] Gimbel og Thomassen ( Gimbel, Thomassen & 2000 ) og ( Nilli 2000 ) viste, at antallet af farver, der skal til for at farve enhver trekantfri m -linje graf er

O\left({\frac {m^{1/3}}{(\log m)^{2/3}}}\right)

og der er trekantfrie grafer med kromatiske tal, der er proportionale med denne grænse.

Der er også nogle resultater vedrørende sammenhængen mellem farvning og minimumsgraden af grafer uden trekanter. Andrásfai og Erdős ( Andrásfai, Erdős, Sós 1974 ) beviste, at enhver n -vertex trekantfri graf, hvor hvert toppunkt har mere end én nabo, skal være todelt. Dette er det bedst mulige resultat af denne type, da 5-cyklusen kræver tre farver, men har præcis naboer for hvert toppunkt. Opmuntret af dette resultat formodede Erdős og Simonovits ( Erdős, Simonovits 1973 ), at enhver trekantfri graf med n toppunkter, hvor hvert toppunkt har mindst naboer, kan farves med kun tre farver. Häggkvist ( 1981 ) tilbageviste imidlertid denne formodning ved at præsentere et modeksempel, hvor hvert hjørne af Grötsch-grafen er erstattet af et uafhængigt sæt af specielt valgt størrelse. Jin ( Jin 1995 ) viste, at enhver n -vertex trekantfri graf, hvor hvert toppunkt har mere end én nabo, kan være 3-farvet. Dette er det bedste resultat af denne type, da Haggquist-grafen kræver fire farver og har nøjagtige naboer for hvert toppunkt. Endelig beviste Brandt og Thomassé ( Brandt, Thomassé 2006 ), at enhver n -vertex trekantfri graf, hvor ethvert toppunkt har mere end 4 naboer, kan farvelægges med 4 farver. Yderligere resultater af denne art er umulige, fordi Hajnal [8] fandt eksempler på trekantfrie grafer med vilkårligt stort kromatisk tal og minimumsgrad for enhver . $2n/5$ $2n/5$ $n/3$ $10n/29$ $10n/29$ $n/3$ $(1/3-\epsilon )n$ $\epsilon > 0$

Graf uden trekanter

Problemet med at finde trekanter

Uafhængighedstallet og Ramsey-teorien

Farvelægningsgrafer uden trekanter

Links