Спирина, М.С. Дискретная математика

связности для вершин графа: две вершины называются связными, если существует маршрут между ними. Понятно, что связность между вершинами является бинарным отношением. Это отноше­ ние будет отношением эквивалентности. Действительно, отноше­ ние связности обладает известными свойствами (см. подразд. 1.6), т.е. оно: • рефлективно — каждая вершина (включая изолированные) связна сама с собой; • симметрично — любой маршрут ( V , ..., V") можно предста­ вить в обратном порядке: ( V”, ..., К'); • транзитивно — если вершина V соединена с вершиной V маршрутом М\(ХЬ Хр), а вершина V соединена с вершиной V" маршрутом М2(Хр+1, ..., Х „), то вершина К соединена с вершиной V" маршрутом М2(Хи ..., Хр, Хр+1, ..., Х„), в котором сначала идут все ребра маршрута Ми а затем все ребра маршрута М2. Граф G можно разбить на непересекающиеся подмножества V, по признаку связности. Вершины одного множества являются связ­ ными между собой, а вершины различных множеств — несвязны. Тогда все подграфы У, (классы эквивалентности) графа G назы­ вают связными компонентами, или компонентами связности. Связ­ ный граф имеет одну компоненту связности. Доказано, что в конечном связном графе всегда можно по­ строить ориентированный цикл, проходящий через каждое реб­ ро по одному разу в двух направлениях. Такой цикл называют способом обхода всего графа и используют при решении многих прикладных задач. В частности, разработаны специальные алго­ ритмы обхода ребер графа, которые можно использовать при ре­ шении задач вида «поиска выхода из лабиринта». В лабиринте дорожки служат ребрами графа, а их разветвления, начало дви­ жения (вход) и конец (выход) — вершинами графа. Если вход и выход принадлежат одной компоненте связности, то такой ла­ биринт принципиально проходим, если разным — то непрохо­ дим. Во втором случае не поможет даже мифологическая «нить Ариадны». Теорема 2.3. Для того чтобы связный граф G являлся простым циклом, необходимо и достаточно, чтобы каждая его вершина имела степень, равную 2. Ребро ( V, W) связного графа G на­ зывается мостом, если после его удале­ ния G станет несвязным и распадется на два связных графа G' и G". На рис. 2.4 мост (СЕ) разделил связный граф С7 на два различных связных графа: G' с вершинами ( A,B,C,D ) и G” с верши­ нами ( Е, F, G, Н, I). Также мостом явля­ ется ребро ВС. Рис. 2.4. Граф (?7с мостами ВС и СЕ 74