В теории графов циклический граф или круговой граф — это граф , состоящий из одного цикла , или, другими словами, некоторого числа вершин (не менее 3, если граф простой ), соединенных в замкнутую цепь. Циклический граф с n вершинами называется C n . [2] Число вершин в C n равно числу ребер , и каждая вершина имеет степень 2; то есть каждая вершина имеет ровно два инцидентных ей ребра.
Если , то это изолированный контур .
Существует много синонимов для «циклического графа». К ним относятся простой циклический граф и циклический граф , хотя последний термин используется реже, поскольку он может также относиться к графам, которые просто не являются ациклическими . Среди теоретиков графов также часто используются цикл , многоугольник или n -угольник . Термин n -цикл иногда используется в других ситуациях. [3]
Цикл с четным числом вершин называется четным циклом ; цикл с нечетным числом вершин называется нечетным циклом .
Циклический график — это:
Кроме того:
Подобно платоновым графам , графы циклов образуют скелеты диэдров . Их двойственными являются дипольные графы , которые образуют скелеты осоэдров .
Ориентированный циклический граф — это направленная версия циклического графа, в которой все ребра ориентированы в одном направлении.
В ориентированном графе набор ребер, содержащий хотя бы одно ребро (или дугу ) из каждого направленного цикла, называется набором дуг обратной связи . Аналогично, набор вершин, содержащий хотя бы одну вершину из каждого направленного цикла, называется набором вершин обратной связи .
Направленный циклический граф имеет равномерную степень захода 1 и равномерную степень исхода 1.
Направленные графы циклов — это графы Кэли для циклических групп (см., например, Тревизана).
