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