WikiSort.ru - Не сортированное

В теории графов рёберно-транзитивным графом называется граф G такой, что для любых двух рёбер e₁ и e₂ графа G, существует автоморфизм графа G, который отображает e₁ в e₂^[1].

Другими словами, граф рёберно-транзитивен, если его группа автоморфизма действует транзитивно на его рёбрах.

Примеры и свойства

Рёберно-транзитивные графы включает все полные двудольные графы ${\displaystyle K_{m,n}}$ , и все симметричные графы, такие как вершины и рёбра куба^[1]. Симметричные графы также вершинно-транзитивны (если они связны), но в общем случае рёберно-транзитивные графы не обязательно вершинно-транзитивны. Граф Грея является примером графа, который является рёберно-транзитивным, но не вершинно-транзитивным. Все такие графы являются двудольными^[1] и поэтому могут быть раскрашены всего в два цвета.

Рёберно-транзитивный граф, являющийся также регулярным, но не вершинно-транзитивным, называется полусимметричным. Граф Грея снова служит примером. Рёберно-транзитивный граф должен быть двудольным и либо полусимметричным, либо бирегулярным^[en][2].

См. также

• Рёберная транзитивность^[en] (в геометрии)

Примечания

Ссылки

• Weisstein, Eric W. Edge-transitive graph (англ.) на сайте Wolfram MathWorld.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка.