Ristikaavio
| Ristikaavio | |
|
Ristikaavion esitys. | |
| Pisteiden lukumäärä | 6 |
|---|---|
| Reunojen lukumäärä | 5 |
| Tutkintojen jakauma | 1 (4 kärkeä) 2 (1 kärki) 4 (1 kärki) |
| säde | 2 |
| Halkaisija | 3 |
| Mesh | ∞ |
| Automorfismit | 6 |
| Kromaattinen numero | 2 |
| Kromaattinen indeksi | 4 |
| Ominaisuudet |
Biparti Planar Etäisyys-yksikkö Shaft |
Risti kuvaaja on, on graafiteoria , kuvaaja, jossa on 6 pistettä ja 5 reunat.
Nimen ristikuvaajaa käytetään ISGCI-luokituksessa (tietojärjestelmä kaavioluokissa ja niiden osissa).
Ominaisuudet
Yleiset ominaisuudet
Halkaisija rajat kuvaaja, suurin epäkeskisyys sen kärjet, on 3, sen säde , vähintään epäkeskisyys sen kärjet, on 2. Sillä ei ole sykli , sen silmäkoko on siis ääretön.
Se on asyklinen ja yhdistetty käyrä eli puu . Siksi se on 1- kytketty kärki ja 1- yhdistetty reuna , toisin sanoen se on kytketty ja sen irrottamiseksi riittää, kun siltä riistetään kärki tai reuna.
Koska ristikuvaaja on puu, se voidaan piirtää tasolle ilman, että sen reunat leikkaavat. Siksi se on tasomainen . Se on myös etäisyysyksikködiagrammi : se voidaan saada euklidisen tason pisteiden kokoelmasta yhdistämällä reunalla kaikki pisteparit, jotka ovat 1 etäisyydellä.
Väritys
Kromaattinen numero ristin kuvaaja on 2 Toisin sanoen, että on mahdollista värittää 2 väriä niin, että kaksi pistettä on kaari ovat aina eri värejä. Tämä määrä on vähäinen.
Kromaattinen indeksi ristin kuvaaja on 4. Siksi on 4-väritys reunojen kaavion siten, että molemmat reunat tapaus samaan kärki ovat aina eri värejä. Tämä määrä on vähäinen.
On mahdollista laskea ristikuvion erilliset värit. Tämä antaa toiminnon sallittujen värien määrästä riippuen. Se on polynomifunktio ja siihen liittyvää polynomia kutsutaan kromaattiseksi polynomiksi . Tämän polynomin aste 6 vähäisintäkään juuret kaikki positiivisia kokonaislukuja tai nolla ehdottomasti pienempi kuin 2. Se on yhtä suuri kuin: .
Algebralliset ominaisuudet
Automorphism ryhmä rajat kuvaaja on ryhmä, jotta 6 isomorfinen symmetriset ryhmä S 3 . Automorfismit vastaavat kaikkien asteen 1 kolmen kärjen kaikkia mahdollisia permutaatioita, jotka on yhdistetty asteen 4 ainutlaatuiseen kärkeen.
Tunnusomainen polynomi on vierusmatriisi rajat kuvaaja on: . Ristikaavio määritetään yksilöllisesti sen kuvaajaspektristä , sen vierekkäisyysmatriisin ominaisarvojen joukosta .
Katso myös
Sisäiset linkit
Ulkoiset linkit
- (en) Eric W. Weisstein , Cross Graph ( MathWorld )
Viitteet
- (in) ISGCI (Information System on Graph Class Inclusion and They) Luettelo pienistä kaavioista .