Граф-цикл

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск
Цикл
Изображение
Вершин

n

Рёбер

n

Обхват

n

Автоморфизмы

2n (Dn)

Хроматическое число

3 если n нечётно и 2, если чётно

Хроматический индекс

3 если n нечётно и 2, если чётно

Спектр

{2 cos(2 k π / n), k=1, ... ,n}[1]

Свойства

2-регулярный
вершинно транзитивен
рёберно транзитивен
с постоянным расстоянием единица
гамильтонов
эйлеров

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

Терминология[править | править вики-текст]

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

Свойства[править | править вики-текст]

Граф-цикл:

Вдобавок:

Ориентированный граф-цикл[править | править вики-текст]

Ориентированный граф-цикл длины 8

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

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

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

Ориентированные графы-циклы являются графами Кэли для циклических групп (см., например, Тревизана (Trevisan)).

Смотрите также[править | править вики-текст]

Ссылки[править | править вики-текст]

Внешние ссылки[править | править вики-текст]