Härän pää (graafiteoria)
| 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 .
Laskee vapaaksi härän päistä
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] .
Kromaattiset ja karakteristiset polynomit
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 .
Muistiinpanot
- ↑ Weisstein, Eric W. Bull Graph Wolfram MathWorld -verkkosivustolla .
- ↑ Chvatal, Sbihi, 1987 , s. 127-139.
- ↑ Reed, Sbihi, 1995 , s. 171-178.
- ↑ Chudnovsky, Safra, 2008 , s. 1301–1310.
- ↑ Chudnovsky, M. (2008), Bultittomien graafien rakenne. I. Kolmireunaiset polut, joissa on keskuksia ja antikeskuksia , < http://www.columbia.edu/~mc2775/bulls1.pdf > Arkistoitu 3. maaliskuuta 2016 Wayback Machinessa .
- ↑ Chudnovsky, M. (2008), Bultittomien graafien rakenne. II. Elementary trigraphs , < http://www.columbia.edu/~mc2775/bulls2.pdf > Arkistoitu 4. maaliskuuta 2016 Wayback Machinessa .
- ↑ Chudnovsky, M. (2008), Bultittomien graafien rakenne. III. Globaali rakenne , < http://www.columbia.edu/~mc2775/bulls3.pdf > Arkistoitu 3. maaliskuuta 2016 Wayback Machinessa .
Kirjallisuus
- V. Chvatal, N. Sbihi. Bull-free Berge-kaaviot ovat täydellisiä // Graphs and Combinatorics . - 1987. - T. 3 , no. 1 . — S. 127–139 . - doi : 10.1007/BF01788536 .
- B. Reed, N. Sbihi. Täydellisten kaavioiden tunnistaminen härkättömästi // Grafit ja kombinatoriikka . - 1995. - T. 11 , no. 2 . - S. 171-178 . - doi : 10.1007/BF01929485 .
- M. Chudnovsky, S. Safra. Erdős–Hajnalin arvelu härkävapaille kaavioille // Journal of Combinatorial Theory . - 2008. - T. 98 , no. 6 . - S. 1301-1310 . - doi : 10.1016/j.jctb.2008.02.005 . Arkistoitu alkuperäisestä 25. kesäkuuta 2010.