Дискретная математика

129 являются связанными между собой. Таким образом, исходный граф можно представить в виде объединения связных подграфов; G=UG(^). i где G(V) - непересекающиеся связные подграфы данного графа, которые Называются компонентами связности или просто компонентой графа G. Ясно, что компонента связности графа G — это его максимальный связный подграф. Таким образом, мы имеем. Теорема 5.3. Каждый (неориентированный) граф представляется j единственным образом как объединение своих компонент связности. i Эта теорема позволяет сводить большинство задач, касающихся графов, к слутаю связных графов. Пусть G = (V,X) - граф. Для определения числа г компонент можно использовать следующий алгоритм; begin V~V; r.= 0; while F V 0 do begin Выбрать u e F'; Найти все вершины, соединённые цепями с и\ Удалить вершину и из V' и соответствующие рёбра изХ; Г= ГТ-]; end end f ~ ~ Теорема 5.4. Если в графе <7 ровно две вершины VHU имеют 1;ечетную | I локальную степень, то эти вершины связанные. | Доказательство. Представим G=[jG(F,), где CfF, ) - компонента. I Пусть ve GfVi). По доказанной ранее теореме каждый граф имеет четное число вершин нечетной степени. Тшс как это свойство должно вьшолняется н для GfV/i), то и должно принадлежать GfFtJ, следовательно, v и и являются вершинами связного графа, поэтому они связаны. На рис, 5.10 приведены графы с двумя и с шестью компонентами связности (компонентами). Ориентированный граф называется связным, если для любых двух егс вершин V и м вершина и достижима из вершины v или вершина v достижим из вершины и.