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 является мостом тогда и только тогда, когда ас не принадлежит ни одному циклу.
Обсуждение Справочник по математике для экономистов
Комментарии, рецензии и отзывы