Dürerův graf - Dürer graph
V matematický pole teorie grafů, Dürerův graf je neorientovaný graf s 12 vrcholy a 18 hranami. Je pojmenován po Albrecht Dürer, jehož 1514 rytina Melencolia I. zahrnuje vyobrazení Dürer je solidní, a konvexní mnohostěn mít Dürerův graf jako svůj kostra. Dürerova pevná látka je jednou ze čtyř dobře zakryté jednoduchý konvexní mnohostěn.
Dürer je solidní
Dürerova tělesa je kombinačně ekvivalentní a krychle se dvěma protilehlými vrcholy zkrácen,[1] ačkoli Dürerovo zobrazení není v této podobě, ale spíše jako zkrácené kosočtverec nebo trojúhelníkový zkrácený lichoběžník.[2] Přesná geometrie tělesa zobrazená Dürerem je předmětem nějaké akademické debaty s různými hypotetickými hodnotami pro jeho ostré úhly v rozmezí od 72 ° do 82 °.[3]
Graficko-teoretické vlastnosti
| Dürerův graf | |
|---|---|
 Dürerův graf | |
| Pojmenoval podle | Albrecht Dürer |
| Vrcholy | 12 |
| Hrany | 18 |
| Poloměr | 3 |
| Průměr | 4 |
| Obvod | 3 |
| Automorfismy | 12 (D6) |
| Chromatické číslo | 3 |
| Chromatický index | 3 |
| Vlastnosti | Krychlový Rovinný dobře zakryté |
| Tabulka grafů a parametrů | |
Dürerův graf je graf tvořený vrcholy a hranami Dürerova tělesa. Je to kubický graf z obvod 3 a průměr 4. Stejně jako jeho konstrukci, stejně jako kostru Dürerova tělesa, lze získat použitím a Transformace Y-Δ na opačné vrcholy a krychlový graf, nebo jako zobecněný Petersenův graf G(6,2). Jako s každým graf konvexního mnohostěnu, Dürerův graf je a 3-vrchol připojený jednoduchý rovinný graf.
Dürerův graf je a dobře pokrytý graf, což znamená, že všechny jeho maximální nezávislé množiny mají stejný počet vrcholů, čtyři. Je to jeden ze čtyř dobře pokrytých kubických polyedrických grafů a jeden ze sedmi dobře pokrytých 3 spojených kubických grafů. Jediné další tři dobře kryté jednoduchý konvexní mnohostěny jsou čtyřstěn, trojúhelníkový hranol, a pětiúhelníkový hranol.[4]
Dürerův graf je Hamiltonian, s LCF notace [-4,5,2,-4,-2,5;-].[5] Přesněji řečeno, má přesně šest Hamiltonovských cyklů, přičemž každý pár může být do sebe mapován symetrií grafu.[6]
Symetrie
The automorfická skupina jak Dürerův graf, tak Dürerovo těleso (buď ve formě zkrácené krychle, nebo ve formě zobrazené Dürerem) je izomorfní s dihedrální skupina objednávky 12: D6.
Galerie
Chromatický index Dürerova grafu je 3.
Chromatické číslo Dürerova grafu je 3.
Dürerův graf je Hamiltonian.
Poznámky
- ^ Weisstein, Eric W. „Dürer's Solid“. MathWorld.
- ^ Weber (1900).
- ^ Weitzel (2004).
- ^ Campbell & Plummer (1988); Campbell, Ellingham & Royle (1993).
- ^ Castagna & Prins (1972) připisovat důkaz Hamiltonicity třídy zobecněných Petersenových grafů, které zahrnují Dürerův graf, Ph.D. Ph.D. práce G. N. Robertsona na University of Waterloo.
- ^ Schwenk (1989).
Reference
- Campbell, S. R .; Ellingham, M. N.; Royle, Gordon F. (1993), „Charakterizace dobře pokrytých kubických grafů“, Journal of Combinatorial Mathematics and Combinatorial Computing, 13: 193–212, PAN 1220613.
- Campbell, Stephen R .; Plummer, Michael D. (1988), "Na dobře pokrytých 3-polytopech", Ars Combinatoria, 25 (A): 215–242, PAN 0942505.
- Castagna, Frank; Prins, Geert (1972), „Každý zobecněný Petersenův graf má zbarvení Tait“, Pacific Journal of Mathematics, 40: 53–58, doi:10,2140 / pjm.1972.40.53.
- Schwenk, Allen J. (1989), "Enumerace hamiltonovských cyklů v některých zobecněných Petersenových grafech", Journal of Combinatorial Theory, Řada B, 47 (1): 53–59, doi:10.1016/0095-8956(89)90064-6, PAN 1007713.
- Weber, P. (1900), Beiträge zu Dürers Weltanschauung — Eine Studie über die drei Stiche Ritter, Tod und Teufel, Melancholie und Hieronymus im Gehäus, Strassburg. Jak uvádí Weitzel (2004).
- Weitzel, Hans (2004), „Další hypotéza o mnohostěnu rytiny A. Dürera Melencolia I“, Historia Mathematica, 31 (1): 11–14, doi:10.1016 / S0315-0860 (03) 00029-6.