Цикл (граф)

Для графа-цикла используются также другие названия: простой граф-цикл и циклический граф, хотя последний термин употребляется нечасто, поскольку он может относиться к графам, не являющимся ациклическими. Иногда употребляются термины цикл, многоугольник или n-угольник. Цикл с чётным числом вершин называют чётным циклом, а с нечётным числом вершин — нечётным циклом.

Граф-цикл:

• связен;
• 2-регулярен;
• эйлеров;
• гамильтонов;
• раскрашиваем в два цвета тогда и только тогда, когда он имеет чётное число вершин. Граф является двудольным тогда и только тогда, когда он не имеет нечётных циклов (в качестве подграфов) (Кёниг, 1936)^[3];
• рёберно-2-раскрашиваем тогда и только тогда, когда он имеет чётное число вершин;
• вершинно-раскрашиваем в 3 цвета и рёберно-3-раскрашиваем для любого числа вершин.;
• является графом единичных расстояний.

Кроме того:

• поскольку графы-циклы можно нарисовать в виде правильных многоугольников, симметрии графа-цикла с n вершинами те же самые, что и у правильного многоугольника с n сторонами, то есть диэдрическая группа порядка 2n. В частности, существуют симметрии, переводящие любую вершину в любую другую вершину и любое ребро в любое другое ребро, так что граф-цикл на n вершинах является симметричным графом.

Ориентированным графом-циклом называется ориентированная версия графа-цикла, в которой все дуги направлены в одном и том же направлении.

В ориентированном графе множество дуг, которые содержат хотя бы одну дугу из каждого ориентированного цикла, называется разрывающим множеством дуг. Подобным образом, множество вершин, содержащих по меньшей мере одну вершину из каждого ориентированного цикла, называется разрезающим циклы множеством вершин.

Ориентированный граф-цикл имеет постоянную полустепень захода 1 и постоянную полустепень исхода 1.

Ориентированные графы-циклы являются графами Кэли для циклических групп^[4].