stringtranslate.com

График цикла

В теории графов циклический граф или круговой граф — это граф , состоящий из одного цикла , или, другими словами, некоторого числа вершин (не менее 3, если граф простой ), соединенных в замкнутую цепь. Циклический граф с n вершинами называется C n . [2] Число вершин в C n равно числу ребер , и каждая вершина имеет степень 2; то есть каждая вершина имеет ровно два инцидентных ей ребра.

Если , то это изолированный контур .

Терминология

Существует много синонимов для «циклического графа». К ним относятся простой циклический граф и циклический граф , хотя последний термин используется реже, поскольку он может также относиться к графам, которые просто не являются ациклическими . Среди теоретиков графов также часто используются цикл , многоугольник или n -угольник . Термин n -цикл иногда используется в других ситуациях. [3]

Цикл с четным числом вершин называется четным циклом ; цикл с нечетным числом вершин называется нечетным циклом .

Характеристики

Циклический график — это:

Кроме того:

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

Направленный циклический граф

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

Ориентированный циклический граф — это направленная версия циклического графа, в которой все ребра ориентированы в одном направлении.

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

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

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

Смотрите также

Ссылки

  1. ^ Некоторые простые графические спектры. win.tue.nl
  2. ^ Дистель (2017) стр. 8, §1.3
  3. ^ "Problem 11707". Amer. Math. Monthly . 120 (5): 469–476. Май 2013. doi :10.4169/amer.math.monthly.120.05.469. JSTOR  10.4169/amer.math.monthly.120.05.469. S2CID  41161918.

Источники

Внешние ссылки