Udda graf

Udda graf
$O_{3}=KG(5,2)$ är Petersen-grafen
Vertices	${\tbinom {2n-1}{n-1}}$
Kanter	$n{\tbinom {2n-1}{n-1}}/2$
Diameter	$n-1$
Omkrets	3 för $O_{2}$ 5 för $O_{3}$ 6 annars
Egenskaper	Distanstransitiv
Notation	O n
Tabell över grafer och parametrar

Den udda grafen $O_{4}=KG(7,3)$

Inom det matematiska området grafteori är de udda graferna en familj av symmetriska grafer med hög udda omkrets, definierade från vissa uppsättningssystem . De inkluderar och generaliserar Petersen-grafen .

Definition och exempel

Den udda grafen $O_{n}$ har en vertex för var och en av $(n-1)$ -elementdelmängderna av a $(2n) -1)$ -elementuppsättning. Två hörn är sammankopplade med en kant om och endast om motsvarande delmängder är disjunkta . Det vill säga, $O_{n}$ är Kneser-grafen $KG(2n-1,n-1)$ .

$O_{2}$ är en triangel, medan $O_{3}$ är den välbekanta Petersen-grafen .

De generaliserade udda graferna definieras som avståndsregelbundna grafer med diameter $n-1$ och udda omkrets $2n-1$ för vissa $n$ . De inkluderar de udda graferna och de vikta kubgraferna .

Historik och applikationer

Även om Petersen-grafen har varit känd sedan 1898, dateras dess definition som en udda graf till arbetet av Kowalewski (1917), som också studerade den udda grafen $O_{4}$ . Udda grafer har studerats för deras tillämpningar i kemisk grafteori , vid modellering av skiftningar av karboniumjoner . De har också föreslagits som en nätverkstopologi vid parallell beräkning .

Notationen $O_{n}$ för dessa grafer introducerades av Norman Biggs 1972. Biggs och Tony Gardiner förklarar namnet på udda grafer i ett opublicerat manuskript från 1974: varje kant av en udda graf kan tilldelas unikt element som är " udda man ut ", dvs inte en medlem av någon delmängd som är associerad med de hörn som faller in på den kanten.

Egenskaper

Den udda grafen $O_{n}$ är regelbunden av graden $n$ . Den har ${\tbinom {2n-1}{n-1}}$ hörn och $n{\tbinom {2n-1}{n-1}}/2$ kanter. Därför är antalet hörn för $n=1,2,\dots$

1, 3, 10, 35, 126, 462, 1716, 6435 (sekvens A001700 i OEIS ).

Avstånd och symmetri

Om två hörn i $O_{n}$ motsvarar mängder som skiljer sig från varandra genom att $k$ element tas bort från en uppsättning och läggas till $k$ olika element, då de kan nås från varandra i $2k$ steg, där varje par utför en enda tillägg och borttagning. Om $2k<n$ är detta den kortaste vägen ; annars är det kortare att hitta en väg av denna typ från den första uppsättningen till en uppsättning som är komplementär till den andra, och sedan nå den andra uppsättningen i ett steg till. Därför är diametern för $O_{n}$$n-1$ .

Varje udda graf är 3-bågstransitiv : varje riktad trekantsbana i en udda graf kan omvandlas till varje annan sådan väg genom en symmetri av grafen. Udda grafer är avståndstransitiva , därav regelbundna avstånd . Som avståndsregelbundna grafer definieras de unikt av sin skärningsmatris: inga andra avståndsregelbundna grafer kan ha samma parametrar som en udda graf. Men trots sin höga grad av symmetri är de udda graferna $O_{n}$ för $n>2$ aldrig Cayley-grafer .

Eftersom udda grafer är regelbundna och kanttransitiva , är deras vertexanslutning lika med deras grad, $n$ .

Udda grafer med $n>3$ har omkrets sex; men även om de inte är tvådelade grafer , är deras udda cykler mycket längre. Specifikt har den udda grafen $O_{n}$ en udda omkrets $2n-1$ . Om en $n$ -regelbunden graf har diameter $n-1$ och udda omkrets $2n-1$ , och bara har $n$ distinkta egenvärden , den måste vara avståndsregelbunden. Avståndsregelbundna grafer med diameter $n-1$ och udda omkrets $2n-1$ är kända som generaliserade udda grafer och inkluderar de vikta kubgraferna såväl som de udda graferna sig själva.

Oberoende uppsättningar och vertexfärgning

Låt $O_{n}$ vara en udda graf definierad från delmängderna av en $(2n-1)$ -elementuppsättning $X$ , och låt ${ \displaystyle x}$ vara vilken medlem som helst av $X$ . Sedan, bland hörnen för ${\displaystyle O_{n}} ,$ motsvarar exakt ${\displaystyle {\tbinom {2n-2}{n-2}}} punkter som$ innehåller $x$ . Eftersom alla dessa uppsättningar innehåller $x$ är de inte disjunkta och bildar en oberoende uppsättning av $O_{n}$ . Det vill säga, $O_{n}$ har $2n-1$ olika oberoende uppsättningar av storlek ${\tbinom {2n-2} {n-2}}$ . Det följer av Erdős–Ko–Rado-satsen att dessa är de maximala oberoende uppsättningarna av $O_{n}$ . det vill säga oberoendetalet för $O_{n}$ är ${\tbinom {2n-2}{n-2}}.$ Vidare måste varje maximal oberoende uppsättning ha denna form, så $O_{n}$ har exakt $2n-1$ maximalt oberoende uppsättningar.

Om $I$ är en maximal oberoende uppsättning, bildad av uppsättningarna som innehåller ${\displaystyle x},$ då är komplementet av $I$ uppsättningen av hörn som inte innehåller $x$ . Denna komplementära uppsättning inducerar en matchning i $G$ . Varje vertex i den oberoende mängden ligger intill $n$ hörn av matchningen, och varje vertex i matchningen är intill $n-1$ hörn i den oberoende mängden. På grund av denna sönderdelning, och eftersom udda grafer inte är tvådelade, har de kromatisk nummer tre: hörnen på den maximala oberoende uppsättningen kan tilldelas en enda färg, och ytterligare två färger räcker för att färga den komplementära matchningen.

Kantfärgning

Enligt Vizings teorem är antalet färger som behövs för att färga kanterna på den udda grafen $O_{n}$ antingen $n$ eller $n+1$ , och i fallet med Petersen-grafen $O_{3}$ är det $n+1$ . När $n$ är en potens av två är antalet hörn i grafen udda, av vilket det återigen följer att antalet kantfärger är $n+1$ . $O_{5}$ , $O_{6}$ och $O_{7}}$ displaystyle kan dock var och en kantfärgas med $n$ färger.

Biggs förklarar detta problem med följande berättelse: elva fotbollsspelare i den fiktiva staden Croam vill bilda ett par av femmannalag (med en udda man som ska fungera som domare) på alla 1386 möjliga sätt, och de vill schemalägga matcherna mellan varje par på ett sådant sätt att de sex matcherna för varje lag spelas sex olika dagar i veckan, med söndagar lediga för alla lag. Är det möjligt att göra så? I den här berättelsen representerar varje spel en kant av $O_{6}$ , varje veckodag representeras av en färg, och en 6-färgs kantfärgning av $O_{6}$ ger en lösning till spelarnas schemaläggningsproblem.

Hamiltonicitet

Petersen-grafen $O_{3}$ är en välkänd icke-hamiltonsk graf, men alla udda grafer $O_{n}$ för $n\geq 4$ är ​​kända att ha en Hamiltonsk cykel. Eftersom de udda graferna är vertextransitiva är de således ett av specialfallen med ett känt positivt svar på Lovász' gissning om Hamiltons cykler i vertextransitiva grafer. Biggs gissade mer allmänt att kanterna på $O_{n}$ kan delas upp i $\lfloor n/2\rfloor$ hamiltonska cykler som skiljer sig från kant. När $n$ är udda måste de överblivna kanterna bilda en perfekt matchning. Denna starkare gissning verifierades för $n=4,5,6,7$ . För ${\displaystyle n=8} förhindrar$ det udda antalet hörn i $O_{n}$ en 8-färgad kantfärgning från att existera, men utesluter inte möjligheten av en partition i fyra Hamiltonian cyklar.

externa länkar

• Weisstein, Eric W. , "Odd Graph" , MathWorld