§2.5. Цикломатическое число.

 

1. Будем рассматривать подграфы, которые могут быть несвязными, но содержащие все вершины графа. Пусть G - граф, содержащий p занумерованных ребер (e₁,e₂,..,e_p)    Каждому подграфупоставим в соответствие p-мерный вектор из нулей и единиц:

             если  e_i H   и  a_i = 0 если           (характеристический вектор подграфа Н).Это соответствие, очевидно, взаимнооднозначное. Более того, сумме по модулю 2 подграфови- соответствует поразрядная сумма по модулю 2 их характеристических векторов. Над множеством коэффициентов {0, 1} множество всех подграфов образует линейное пространство: умножение любого подграфа Н на 1 дает Н, умножение на 0 - пустой подграф, т.е. подграф, не содержащий ребер и состоящий из одних изолированных вершин графа G. Нетрудно видеть, что пространство подграфов графа G и пространство характеристических векторов его подграфов изоморфны и имеют размерность р. Базисом может служить множество всех однореберных подграфов. Характеристический вектор каждого такого подграфа содержит ровно одну единицу, причем для разных подграфов - на разных местах.