Komplett graf - Complete graph

Komplett diagram
K 7 , en komplett graf med 7 hörn
Hörn	n
Kanter	${\ displaystyle \ textstyle {\ frac {n (n-1)} {2}}}$
Radie	${\ displaystyle \ left \ {{\ begin {array} {ll} 0 & n \ leq 1 \\ 1 & {\ text {annars}} \ end {array}} \ höger.}$
Diameter	${\ displaystyle \ left \ {{\ begin {array} {ll} 0 & n \ leq 1 \\ 1 & {\ text {annars}} \ end {array}} \ höger.}$
Omkrets	${\ displaystyle \ left \ {{\ begin {array} {ll} \ infty & n \ leq 2 \\ 3 & {\ text {annars}} \ end {array}} \ right.}$
Automorfismer	n ! ( S n )
Kromatiskt tal	n
Kromatiskt index
Spektrum	${\ displaystyle \ left \ {{\ begin {array} {lll} \ emptyset & n = 0 \\\ left \ {0^{1} \ right \} & n = 1 \\\ left \ {(n-1) ^{1},-1^{n-1} \ right \} & {\ text {annars}} \ end {array}} \ right.}$
Egenskaper
Notation	K n
Tabell över grafer och parametrar

I det matematiska området grafteori är ett komplett diagram ett enkelt oriktat diagram där varje par distinkta hörn är förbundna med en unik kant . En komplett digraph är en riktad graf där varje par distinkta hörn är förbundna med ett par unika kanter (en i varje riktning).

Själva grafteorin dateras typiskt från Leonhard Eulers arbete från 1736 om Königsbergs sju broar . Men ritningar av kompletta grafer, med deras hörn placerade på punkterna i en vanlig polygon , förekom redan på 1200 -talet i Ramon Llulls arbete . En sådan teckning kallas ibland för en mystisk ros .

Egenskaper

Hela grafen på hörn markeras med . Vissa källor hävdar att bokstaven i denna notation står för det tyska ordet komplett , men det tyska namnet för en fullständig graf, vollständiger Graph , innehåller inte bokstaven , och andra källor säger att notationen hedrar Kazimierz Kuratowskis bidrag till grafteori . ${\ displaystyle n}$${\ displaystyle K_ {n}}$${\ displaystyle K}$${\ displaystyle K}$

${\ displaystyle K_ {n}}$har kanter (en triangulär antal ), och är en regelbunden kurva av grad . Alla kompletta grafer är sina egna maximala klickningar . De är maximalt anslutna eftersom den enda hörnskärningen som kopplar bort grafen är den fullständiga uppsättningen hörn. Den komplementgraf av en komplett graf är en tom graf . ${\ displaystyle n (n-1)/2}$ ${\ displaystyle n-1}$

Om kanterna på ett komplett diagram får en orientering , kallas det resulterande riktade diagrammet för en turnering .

${\ displaystyle K_ {n}}$kan brytas ned i träd som har hörn. Ringels gissning frågar om hela grafen kan brytas ned i kopior av något träd med kanter. Detta är känt för att vara tillräckligt stort . ${\ displaystyle n}$${\ displaystyle T_ {i}}$${\ displaystyle T_ {i}}$${\ displaystyle i}$${\ displaystyle K_ {2n+1}}$${\ displaystyle n}$${\ displaystyle n}$

Antalet alla distinkta vägar mellan ett specifikt par hörnpar anges av ${\ displaystyle K_ {n+2}}$

${\ displaystyle w_ {n+2} = n! e_ {n} = \ lfloor en! \ rfloor,}$

där refererar till Eulers konstant , och ${\ displaystyle e}$

${\ displaystyle e_ {n} = \ sum _ {k = 0}^{n} {\ frac {1} {k!}}.}$

Antalet matchningar för de kompletta graferna anges av telefonnumren

1, 1, 2, 4, 10, 26, 76, 232, 764, 2620, 9496, 35696, 140152, 568504, 2390480, 10349536, 46206736, ... (sekvens A000085 i OEIS ).

Dessa siffror ger det största möjliga värdet av Hosoya -indexet för en -vertex -graf. Antalet perfekta matchningar av den fullständiga grafen (med jämn) ges av dubbelfaktorn . ${\ displaystyle n}$${\ displaystyle K_ {n}}$${\ displaystyle n}$ ${\ displaystyle (n-1) !!}$

De korsande numren upp till är kända, med att kräva antingen 7233 eller 7234 korsningar. Ytterligare värden samlas in av projektet Rectilinear Crossing Number. Rätlinjiga korsningsnummer för are ${\ displaystyle K_ {27}}$${\ displaystyle K_ {28}}$${\ displaystyle K_ {n}}$

0, 0, 0, 0, 1, 3, 9, 19, 36, 62, 102, 153, 229, 324, 447, 603, 798, 1029, 1318, 1657, 2055, 2528, 3077, 3699, 4430, 5250, 6180, ... (sekvens A014540 i OEIS ).

Geometri och topologi

Interaktiv Csaszar -polyhedronmodell med hörn som representerar noder. I SVG -bilden , flytta musen för att rotera den.

En komplett graf med noder representerar kanterna på en - simplex . Geometriskt bildar K ₃ kantuppsättningen av en triangel , K ₄ en tetraeder , etc. Császár -polyhedronen , en icke -konvex polyeder med topologin för en torus , har den fullständiga grafen K ₇ som sitt skelett . Varje grannpolytop i fyra eller flera dimensioner har också ett komplett skelett. ${\ displaystyle n}$${\ displaystyle (n-1)}$

K ₁ till K ₄ är alla plana grafer . Varje planritning av ett komplett diagram med fem eller fler hörn måste dock innehålla en korsning, och den icke -plana fullständiga grafen K ₅ spelar en nyckelroll i karakteriseringarna av plana grafer: enligt Kuratowskis sats är en graf plan om och bara om den innehåller varken K ₅ eller den fullständiga bipartitdiagrammet K _3,3 som en underavdelning, och enligt Wagners sats gäller samma resultat för grafiska minderåriga i stället för underavdelningar. Som en del av Petersen familjen , K ₆ spelar en liknande roll som en av de förbjudna minderåriga för länkfri inbäddning . Med andra ord, och som Conway och Gordon bevisat, är varje inbäddning av K ₆ i tredimensionellt utrymme inneboende, med åtminstone ett par länkade trianglar. Conway och Gordon visade också att varje tredimensionell inbäddning av K ₇ innehåller en Hamiltonisk cykel som är inbäddad i rymden som en icke-enkel knut .

Exempel

Kompletta grafer på hörn, mellan 1 och 12, visas nedan tillsammans med antalet kanter: ${\ displaystyle n}$${\ displaystyle n}$

K 1 : 0	K 2 : 1	K 3 : 3	K 4 : 6
K 5 : 10	K 6 : 15	K 7 : 21	K 8 : 28
K 9 : 36	K 10 : 45	K 11 : 55	K 12 : 66

Se även

• Fullt anslutet nätverk , i datanätverk
• Komplett bipartitdiagram (eller biclique ), en speciell bipartitgraf där varje hörn på ena sidan av tvåpartiet är ansluten till varje hörn på den andra sidan

Referenser

externa länkar

• Weisstein, Eric W. "Komplett diagram" . MathWorld .