Interested Article - Цикл (граф)

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

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

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

Свойства

Граф-цикл:

Вдобавок:

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

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

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

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

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

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

См. также

Примечания

  1. от 1 июля 2014 на Wayback Machine . win.tue.nl

Ссылки

  • Weisstein, Eric W. (англ.) на сайте Wolfram MathWorld . (обсуждение как 2-регулярных графов-циклов, так и групповые концепции )
  • , .
Источник —

Same as Цикл (граф)