Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Граф, в котором все пары вершин автоморфны.
Graph where all pairs of vertices are automorphic
В математической области теории графов, вершинно-транзитивный граф – это граф G, в котором для любых двух вершин u и v графа G существует автоморфизм f
In the mathematical field of graph theory, a vertex transitive graph is a graph G in which, given any two vertices and of G, there is some automorphism
такой, что
such that
Другими словами, граф является вершинно-транзитивным, если его группа автоморфизмов действует транзитивно на его вершины. Граф является вершинно-транзитивным тогда и только тогда, когда его дополнение также вершинно-транзитивно, поскольку действия групп идентичны. Каждый симметричный граф без изолированных вершин является вершинно-транзитивным, и каждый вершинно-транзитивный граф является регулярным. Однако не все вершинно-транзитивные графы симметричны (например, рёбра усечённого тетраэдра), и не все регулярные графы вершинно-транзитивны (например, граф Фрухта и граф Тице).
In other words, a graph is vertex transitive if its automorphism group acts transitively on its vertices. A graph is vertex transitive if and only if its graph complement is, since the group actions are identical. Every symmetric graph without isolated vertices is vertex transitive, and every vertex transitive graph is regular. However, not all vertex transitive graphs are symmetric (for example, the edges of the truncated tetrahedron), and not all regular graphs are vertex transitive (for example, the Frucht graph and Tietze's graph).
Конечные примеры
К конечным графам, обладающим вершинной транзитивностью, относятся симметричные графы (такие как граф Петерсена, граф Хейвуда, а также вершины и рёбра платоновых тел). Конечные графы Кейли (например, циклы, связанные кубами) также вершинно транзитивны, как и вершины и рёбра архимедовых тел (хотя симметричны лишь два из них). Поточник, Спига и Веррет составили полный перечень всех связных кубических вершинно транзитивных графов с числом вершин не более 1280. Хотя любой граф Кейли является вершинно транзитивным, существуют и другие вершинно транзитивные графы, которые не являются графами Кейли. Наиболее известный пример — граф Петерсена, но можно построить и другие, в том числе линейные графы краевых транзитивных недвудольных графов с нечётной степенью вершин.
Finite vertex transitive graphs include the symmetric graphs (such as the Petersen graph, the Heawood graph and the vertices and edges of the Platonic solids). The finite Cayley graphs (such as cube connected cycles) are also vertex transitive, as are the vertices and edges of the Archimedean solids (though only two of these are symmetric). Potočnik, Spiga and Verret have constructed a census of all connected cubic vertex transitive graphs on at most 1280 vertices. Although every Cayley graph is vertex transitive, there exist other vertex transitive graphs that are not Cayley graphs. The most famous example is the Petersen graph, but others can be constructed including the line graphs of edge transitive non bipartite graphs with odd vertex degrees.
Свойства
Крайняя связность связного вершинно-транзитивного графа равна степени d, а вершинная связность будет не меньше 2(d + 1)/3.
The edge connectivity of a connected vertex transitive graph is equal to the degree d, while the vertex connectivity will be at least 2(d + 1)/3.