11.2. связные графы

11.2. связные графы

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

Любой несвязный граф является совокупностью связных графов. Эти графы обладают тем свойством, что никакая вершина одного

из них не связана путем ни с кахой / / оР7

вершиной другого. Каждый из этих / / I

графов называется компонентой граJ V У V

фа G. На рис. 11.3 изображен несвязный граф G с компонентами GlP G2,

G3. Каждая компонента является

связным графом. Р"^ 1!-э

Теорема 11.3. Для того чтобы граф G представлял собой простой цикл, необходимо и достаточно, чтобы каждая его вершина имела степень 2.

Ребро а называется мостом графа G, если граф, получившийся из G после удаления ребра а (такой граф обозначается Ga), содержит больше компонент, чем граф G.

Теорема 11.4. Ребро а. графа G является мостом тогда и только тогда, когда ас не принадлежит ни одному циклу.