Härän pää | |
---|---|
Huiput | 5 |
kylkiluut | 5 |
Säde | 2 |
Halkaisija | 3 |
Ympärysmitta | 3 |
Automorfismit | 2 ( Z / 2 Z ) |
Kromaattinen numero | 3 |
Kromaattinen indeksi | 3 |
Ominaisuudet |
Tasokuvaajan yksikköetäisyyskaavio _ |
Härän pää on tasomainen suuntaamaton graafi , jossa on 5 kärkeä ja 5 reunaa kolmion muodossa, jossa on kaksi erillistä riippuvaa reunaa [1] .
Graafin kromaattinen luku on 3, kromaattinen indeksi 3, säde 2, halkaisija 3 ja ympärysmitta 3. Kaavio on lohko , halkaistu , kynsitön , kärki -1-yhdistetty ja 1 - reuna - kytketty .
Kaavio ei sisällä härkäpäitä, jos pää ei sisällä luotua alagraafia . Kuvaajat ilman kolmioita eivät sisällä härän päitä, koska jokainen pää sisältää kolmion. Vahva olettamus täydellisistä graafista todistettiin graafisille ilman härkäpäitä jo kauan ennen yleismuotoisten graafien todistetta [2] , ja on olemassa hyvin tunnettu algoritmi täydellisten graafien tunnistamiseen ilman härkäpäitä polynomisella kulkuajalla [ 3] .
Maria Chudnovskaya ja Samuel Safra tutkivat härkäpäisiä kaavioita yleisemmässä muodossa ja osoittivat, että jokaisella sellaisella graafilla täytyy olla joko suuri klikki tai suuri riippumaton joukko (eli Erdős-Hajnalin olettamus pätee härkäpääkaavioihin ) [4] ja kehitti yleisen teorian tällaisten graafien rakenteesta [5] [6] [7] .
Härän pään kromaattinen polynomi on . Kaksi muuta kuvaajaa vastaavat kromaattisesti härän päätä.
Kuvaajan ominaispolynomi on .
Kuvaajan Tatta-polynomi on .