Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Ненаправленный граф с 14 вершинами
Undirected graph with 14 vertices
В математической области теории графов граф Хевуда — это ненаправленный граф с 14 вершинами и 21 ребром, названный в честь Перси Джона Хевуда.
In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.
Комбинаторные свойства
Граф кубический, и все циклы в графе содержат шесть или более рёбер. Любой меньший кубический граф имеет циклы меньшей длины, поэтому этот граф является 6-клетью — наименьшим кубическим графом с длиной окружности 6. Это дистанционно-транзитивный граф (см. перепись Фостера) и, следовательно, дистанционно-регулярный. В графе Хевуда существует 24 совершенных паросочетания; для каждого паросочетания множество рёбер, не входящих в паросочетание, образует гамильтонов цикл. Например, на рисунке показаны вершины графа, расположенные на цикле, при этом внутренние диагонали цикла образуют паросочетание. Разделяя рёбра цикла на два паросочетания, мы можем разбить граф Хевуда на три совершенных паросочетания (то есть, раскрасить его рёбра в 3 цвета) восемью различными способами. В графе Хевуда содержится 28 шестивершинных циклов. Каждый 6-цикл пересекается ровно с тремя другими 6-циклами; среди этих трёх 6-циклов каждый из них является симметричной разностью двух других. Граф, в котором на каждый 6-цикл приходится одна вершина, а между каждой парой непересекающихся 6-циклов — одно ребро, является графом Коксетера.
The graph is cubic, and all cycles in the graph have six or more edges. Every smaller cubic graph has shorter cycles, so this graph is the 6 cage, the smallest cubic graph of girth 6. It is a distance transitive graph (see the Foster census) and therefore distance regular. There are 24 perfect matchings in the Heawood graph; for each matching, the set of edges not in the matching forms a Hamiltonian cycle. For instance, the figure shows the vertices of the graph placed on a cycle, with the internal diagonals of the cycle forming a matching. By subdividing the cycle edges into two matchings, we can partition the Heawood graph into three perfect matchings (that is, 3 color its edges) in eight different ways. There are 28 six vertex cycles in the Heawood graph. Each 6 cycle is disjoint from exactly three other 6 cycles; among these three 6 cycles, each one is the symmetric difference of the other two. The graph with one node per 6 cycle, and one edge for each disjoint pair of 6 cycles, is the Coxeter graph.
Алгебраические свойства
Автоморфическая группа графа Хейвуда изоморфна проективной линейной группе PGL2(7), группе порядка 336. Она действует транзитивно на вершинах, на ребрах и на дугах графа. Следовательно, граф Хейвуда является симметричным графом. У него существуют автоморфизмы, переводящие любую вершину в любую другую вершину и любое ребро в любое другое ребро. Более того, граф Хейвуда является 4-дугово транзитивным. Согласно переписи Фостера, граф Хейвуда, обозначенный как F014A, является единственным кубическим симметричным графом на 14 вершинах. Его книжная толщина равна 3, а номер очереди — 2. Характерный многочлен графа Хейвуда — это единственный граф, обладающий таким характерным многочленом, что делает его графом, определяемым своим спектром.
The automorphism group of the Heawood graph is isomorphic to the projective linear group PGL2(7), a group of order 336. It acts transitively on the vertices, on the edges and on the arcs of the graph. Therefore, the Heawood graph is a symmetric graph. It has automorphisms that take any vertex to any other vertex and any edge to any other edge. More strongly, the Heawood graph is 4 arc transitive. According to the Foster census, the Heawood graph, referenced as F014A, is the only cubic symmetric graph on 14 vertices. It has book thickness 3 and queue number 2. The characteristic polynomial of the Heawood graph is It is the only graph with this characteristic polynomial, making it a graph determined by its spectrum.