Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Граф теориясының математикалық саласында Тютте-Коксетер графы, немесе Тютте сегіз қосқабырғасы, немесе Кремона-Ричмонд графы — 30 төбесі және 45 қабырғасы бар 3-ретті граф. 8 периметрі бар ең кішкентай кубтық граф ретінде, ол қосқабырға және Мур графы болып табылады. Ол екі бөлікті, және жалпыланған төртбұрыш W2-нің Леви графы ретінде құрастырылуы мүмкін (Кремона-Ричмонд конфигурациясы деп белгілі). Граф Уильям Томас Тютте және Х.С.М. Коксетердің құрметіне аталған; оны Тютте (1947) ашқан, бірақ оның геометриялық конфигурациялармен байланысын екі автор да бірлесіп жариялаған екі мақалада зерттеген (Тютте 1958; Коксетер 1958а). Барлық кубикалық қашықтығы тұрақты графтар белгілі. Тютте-Коксетер – мұндай 13 графтың бірі. Оның қиылысу саны 13, кітап қалыңдығы 3 және кезек саны 2.
In the mathematical field of graph theory, the Tutte–Coxeter graph or Tutte eight cage or Cremona–Richmond graph is a 3 regular graph with 30 vertices and 45 edges. As the unique smallest cubic graph of girth 8, it is a cage and a Moore graph. It is bipartite, and can be constructed as the Levi graph of the generalized quadrangle W2 (known as the Cremona–Richmond configuration). The graph is named after William Thomas Tutte and H. S. M. Coxeter; it was discovered by Tutte (1947) but its connection to geometric configurations was investigated by both authors in a pair of jointly published papers (Tutte 1958; Coxeter 1958a). All the cubic distance regular graphs are known. The Tutte–Coxeter is one of the 13 such graphs. It has crossing number 13, book thickness 3 and queue number 2.
Құрылыстар мен автоморфизмдер
Тютте-Коксетер графы — Сильвестрдің (1844) еңбегіне негізделген Коксетердің (1958b) сипаттамасы бойынша, 6 төбесі бар толық K6 графының 15 жағына 15 толық сәйкестікті байланыстыратын екі жақты Леви графы. Әрбір төбе жаққа немесе толық сәйкестікке сәйкес келеді, ал байланысқан төбелер жақтар мен сәйкестіктер арасындағы инциденттік құрылымды көрсетеді. Осы құрылымға сүйене отырып, Коксетер Тютте-Коксетер графының симметриялық граф екенін көрсетті; оның 1440 автоморфизмдер тобы бар, оларды алты элементтен тұратын пермутациялар тобының автоморфизмдерімен анықтауға болады (Коксетер 1958b). Бұл топтың ішкі автоморфизмдері K6 графының алты төбесін ауыстыруға сәйкес келеді; бұл ауыстырулар Тютте-Коксетер графында екі жақты бөлімінің әр жағындағы төбелерді ауыстыру арқылы әрекет етеді, екі бөліктің әрқайсысын жиын ретінде өзгеріссіз қалдырады. Сонымен қатар, пермутациялар тобының сыртқы автоморфизмдері екі жақты бөлімінің бір жағын екіншісімен ауыстырады. Коксетер көрсеткендей, Тютте-Коксетер графындағы бес жаққа дейінгі кез келген жол осындай бір автоморфизм арқылы кез келген басқа жолмен эквивалентті.
The Tutte–Coxeter graph is the bipartite Levi graph connecting the 15 perfect matchings of a 6 vertex complete graph K6 to its 15 edges, as described by Coxeter (1958b), based on work by Sylvester (1844). Each vertex corresponds to an edge or a perfect matching, and connected vertices represent the incidence structure between edges and matchings. Based on this construction, Coxeter showed that the Tutte–Coxeter graph is a symmetric graph; it has a group of 1440 automorphisms, which may be identified with the automorphisms of the group of permutations on six elements (Coxeter 1958b). The inner automorphisms of this group correspond to permuting the six vertices of the K6 graph; these permutations act on the Tutte–Coxeter graph by permuting the vertices on each side of its bipartition while keeping each of the two sides fixed as a set. In addition, the outer automorphisms of the group of permutations swap one side of the bipartition for the other. As Coxeter showed, any path of up to five edges in the Tutte–Coxeter graph is equivalent to any other such path by one such automorphism.