17) Циклы в графе. Цикломатическое число в графе.

Циклом графа называют путь, в котором первая и последняя вершины совпадают. При этом длиной пути (или цикла) называют число составляющих его рёбер. Заметим, что если вершины u и v являются концами некоторого ребра, то согласно данному определению, последовательность (u,v,u) является циклом. Чтобы избежать таких «вырожденных» случаев, вводят следующие понятия.

Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются. Несложно видеть, что:

• Всякий путь, соединяющий две вершины, содержит элементарный путь, соединяющий те же две вершины.
• Всякий простой неэлементарный путь содержит элементарный цикл.
• Всякий простой цикл, проходящий через некоторую вершину (или ребро), содержит элементарный (под-)цикл, проходящий через ту же вершину (или ребро).
• Петля — элементарный цикл.

Цикломатическое число графа (Cyclomatic number, circuit rank) — для неориентированного графа  число , равное мощности множества фундаментальных циклов или, что то же, числу хорд относительно каркаса  графа ; дляорграфа цикломатическое число неориентированного графа, получающегося заменой дуг ребрами.

Другое название — Цикломатический ранг.