Täydellinen kaavio

Täydellinen kaavio
K5{\ displaystyle K_ {5}}
Luokitus	Kei{\ displaystyle K_ {n}}
Pisteiden lukumäärä	ei{\ displaystyle n}
Reunojen lukumäärä	ei(ei-1)/2{\ displaystyle n (n-1) / 2}
Tutkintojen jakauma	(n-1) - säännöllinen
Halkaisija	1
Mesh	∞ jos n = 1 tai 2 3, jos n > 2
Kromaattinen numero	ei{\ displaystyle n}
Ominaisuudet	Hamiltonilainen , symmetrinen , säännöllinen

In graafiteoria , joka on täydellinen kaavio on yksinkertainen kaavio , jossa kaikki solmut ovat vierekkäin kaksi kaksi, toisin sanoen, että mikä tahansa pari erillisiä pisteiden ja on liitetty reuna. Jos kaavio on suuntautunut , sanomme sen olevan täydellinen, jos jokainen kärkipari on kytketty tarkalleen kahdella kaarella (yksi kumpaankin suuntaan).

Määritelmät

Täydellinen kaavio on kaavio, jonka pisteet ovat kaikki vierekkäin.

Jopa isomorfismi , on vain yksi täydellinen suuntaamaton verkko järjestyksen n , joka merkitään . Kei{\ displaystyle K_ {n}}

Kaaviossa G yksi, nimeltään napsauta osaa pisteistä, joka indusoi G: n täydellisen aligrafiikan . Suurimman koon klikkauksen löytäminen kaaviosta on klassinen ongelma kuvaajateoriassa . Se on NP-täydellinen .

Täydellisen kahdenvälisen kuvaajan käsite on myös olemassa. Mutta täydellinen kahdenvälinen kaavio ei ole täydellinen kaavio.

Ominaisuudet

Kohtien reunojen määrä on: Kei{\ displaystyle K_ {n}}

∑i=1ei(ei-i)=∑i=1ei-1i=ei(ei-1)2{\ displaystyle \ summa _ {i = 1} ^ {n} \ vasen (ni \ oikea) = \ summa _ {i = 1} ^ {n-1} i = {\ frac {n (n-1)} {2}}}.

Ensimmäinen termi saadaan havaitsemalla, että ensimmäisen kärjen poistaminen merkitsee reunojen poistamista, toisen kärjen poistamista, reunojen poistamista ja i: nnen kärjen reunojen poistamista. Toinen termi saadaan samalla operaatiolla merkitsemällä reunat niiden poistamisen sijaan, jokainen reuna merkitään sitten kahdesti ja teemme merkinnät kärkipisteillä (tämä on yleinen kaava asteen puolisummalle). Kei{\ displaystyle K_ {n}}ei-1{\ displaystyle n-1}ei-2{\ displaystyle n-2}ei-i{\ displaystyle ni}ei-1{\ displaystyle n-1}

Voimme myös saada tämän kaavan näkemällä reunojen lukumäärän erillisten parien lukumääränä, jotka voimme muodostaa solmuilla, toisin sanoen reunoilla, mikä on hyvin arvoista . ei{\ displaystyle n}(ei2){\ displaystyle {\ binom {n} {2}}}ei(ei-1)2{\ displaystyle {\ dfrac {n (n-1)} {2}}}

Täydellinen kaavio on symmetrinen  : se on kärkipiste-, reuna- ja kaaritransitiivinen. Tämä tarkoittaa, että sen automorfismiryhmä toimii siirtymävaiheessa kaikissa sen kärjissä, reunoissa ja kaarissa. Tämä automorfismien ryhmä on kardinaalia n! ja on isomorfinen symmetriselle ryhmälle . Kei{\ displaystyle K_ {n}} Sei{\ displaystyle S_ {n}}

Tunnusomainen polynomi täydellisen kuvaaja on: . Tämä tyypillinen polynomi hyväksyy vain kokonaiset juuret. Täydellinen kaavio on siis integraalikaavio, graafi , jonka spektri koostuu kokonaisluvuista. Kei{\ displaystyle K_ {n}}(x-ei+1)(x+1)ei-1{\ displaystyle (x-n + 1) (x + 1) ^ {n-1}}

Kaavio on pienin ei-tasomainen kaavio. Se käytetään karakterisointia tasomaisen kuvaajat ja Kazimierz Kuratowski ja Klaus Wagner . K5{\ displaystyle K_ {5}}

Oletuksia

Ristien lukumäärä

Merkitään matkojen määrää graafin , vähimmäismäärä ylitysten joukossa mahdollisimman tontit . A. Hill ja J. Ernest arvasivat arvon koko kaavion ristien lukumäärälle , jonka Richard K. Guy julkaisi vuonna 1960. Tiedämme, että aina on juoni, vs.r(G){\ displaystyle \ mathrm {cr} (G)}G{\ displaystyle G}G{\ displaystyle G}Kei{\ displaystyle K_ {n}}

op(Kei)≤14⌊ei2⌋⌊ei-12⌋⌊ei-22⌋⌊ei-32⌋{\ displaystyle {\ textrm {cr}} (K_ {n}) \ leq {\ frac {1} {4}} \ vasen \ lfloor {\ frac {n} {2}} \ right \ rfloor \ left \ lfloor {\ frac {n-1} {2}} \ oikea \ rfloor \ left \ lfloor {\ frac {n-2} {2}} \ right \ rfloor \ left \ lfloor {\ frac {n-3} {2 }} \ oikea \ rfloor}

risteykset (jatkoa A000241 on OEIS ). Oletetaan, että epätasa-arvo on itse asiassa tasa-arvo. Thomas L. Saaty teki itsenäisen saman olettamuksen vuonna 1964.

Saaty vahvisti edelleen, että tämä kaava antaa optimaalisen määrän ristityksiä n ≤ 10: lle ja Pan ja Richter ovat osoittaneet, että se on optimaalinen myös n = 11, 12: lle .

Galleria

Jokaiselle täydelliselle kuvaajalle, jossa on 1 - 12 kärkipistettä, ilmoitetaan sen reunojen määrä.

• K1{\ displaystyle K_ {1}} : 0 yksittäinen reunakaavio
  

• K2{\ displaystyle K_ {2}} : 1 reuna

• K3{\ displaystyle K_ {3}} : 3 kolmion kuvaajan reunaa
  

• K4{\ displaystyle K_ {4}} : 6 tetraedraalista kuvaajan reunaa
  

• K5{\ displaystyle K_ {5}} : 10
  kattoluunaa

• K6{\ displaystyle K_ {6}} : 15 reunaa

• K7{\ displaystyle K_ {7}} : 21 reunaa

• K8{\ displaystyle K_ {8}} : 28 reunaa

• K9{\ displaystyle K_ {9}} : 36 reunaa

• K10{\ displaystyle K_ {10}} : 45 reunaa

• K11{\ displaystyle K_ {11}} : 55 reunaa

• K12{\ displaystyle K_ {12}} : 66 reunaa

Huomautuksia ja viitteitä

1. (in) Reinhard Diestel , Graafiteoria [ vähittäiskaupan painokset ] , chap.  1.1 ("Perustiedot: Kaaviot") , s.  3.
2. RK Guy , "  A combinatorial problem  ", Nabla (Bulletin of the Malayan Mathematical Society) , voi.  7,1960, s.  68–72
3. TL Saaty , "  Risteysten vähimmäismäärä täydellisissä kaavioissa  ", Proceedings of the National Academy of Sciences of the United States of America , voi.  52,1964, s.  688-690 ( PMID  16591215 , PMCID  300329 , DOI  10,1073 / pnas.52.3.688 , Bibcode  1964PNAS ... 52..688S )
4. Shengjun Pan ja R. Bruce Richter , "  K 11: n risteysnumero on 100  ", Journal of Graph Theory , voi.  56, n °  22007, s.  128–134 ( DOI  10.1002 / jgt.20249 , Math Reviews  2350621 ).

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">