Меню Главная Случайная статья Настройки Цикл (граф) Материал из https://ru.wikipedia.org Цикл — граф, состоящий из единственного цикла, или, другими словами, некоторого числа вершин, соединённых замкнутой цепью. Граф-цикл с n вершинами обозначают как Cn. Число вершин в Cn равно числу рёбер и каждая вершина имеет степень 2, то есть любая вершина инцидентна ровно двум рёбрам. Содержание 1 Терминология 2 Свойства 3 Ориентированный граф-цикл 4 См. также 5 Примечания 6 Ссылки Терминология Граф-цикл имеет много синонимов. Используют термины простой граф-цикл и циклический граф, хотя последний термин употребляется не часто, поскольку он может относиться к графам, не являющимся ациклическими. Иногда употребляются термины цикл, многоугольник или n-угольник. Цикл с чётным числом вершин называют чётным циклом, а с нечётным числом вершин — нечётным циклом. Свойства Граф-цикл: связен 2-регулярен эйлеров гамильтонов раскрашиваем в два цвета тогда и только тогда, когда он имеет чётное число вершин. Граф является двудольным тогда и только тогда, когда он не имеет нечётных циклов (в качестве подграфов) (Кёниг, 1936). рёберно-2-раскрашиваем тогда и только тогда, когда он имеет чётное число вершин. Вершинно-раскрашиваем в 3 цвета и рёберно-3-раскрашиваем для любого числа вершин. с постоянным расстоянием единица Вдобавок: Поскольку графы-циклы можно нарисовать в виде правильных многоугольников, симметрии цикла с n вершинами те же самые, что и у правильного многоугольника с n сторонами, то есть диэдрическая группа порядка 2n. В частности, существуют симметрии, переводящие любую вершину в любую другую вершину и любое ребро в любое другое ребро, так что n-цикл является симметричным графом. Ориентированный граф-цикл Ориентированным графом-циклом называется ориентированная версия графа-цикла, в котором все дуги направлены в одном и том же направлении. В ориентированном графе множество дуг, которые содержат хотя бы одну дугу из каждого ориентированного цикла, называется разрывающим множеством дуг[англ.]. Подобным образом, множество вершин, содержащих по меньшей мере одну вершину из каждого ориентированного цикла, называется разрезающее циклы множество вершин. Ориентированный граф-цикл имеет постоянную полустепень захода 1 и постоянную полустепень исхода 1. Ориентированные графы-циклы являются графами Кэли для циклических групп (см., например, Тревизана [Trevisan]). См. также Полный двудольный граф Путь (теория графов) Полный граф Примечания Some simple graph spectra Архивная копия от 1 июля 2014 на Wayback Machine. win.tue.nl Ссылки Weisstein, Eric W. Cycle Graph (англ.) на сайте Wolfram MathWorld. (обсуждение как 2-регулярных графов-циклов, так и групповые концепции циклических диаграмм[англ.]) Люк Тревизан[англ.], Characters and Expansion.