Полученный граф

Cтраница 4

Полученный граф называется остатком первоначального графа. Вершина, входящая в остаточный граф, называется остаточной. Путь, если он связывает остаточную вершину с собой или с заданной остаточной вершиной и не проходит через любые другие остаточные вершины, кроме указанных, также является остаточным. [46]

Построим для рассматриваемого графа граф конденсации, или граф Герца, стянув все его бикомпоненты в вершины. Полученный граф является ациклическим и потому аранжируемым. [47]

Рассмотрим оптимальное разбиение на примере графа, приведенного на рис. 1.38 а, где zy - ветви показаны сплошными линиями, г-ветви - штриховыми и взаимно определенные - штрих-пунктирными. Рассматривая полученный граф ( если он несвязный, каждая часть рассматривается отдельно), относим к / - ветвям петли и параллельно соединенные ветви, после чего их сокращаем. Этот процесс продолжается до тех пор, пока в подграфе не будут устранены все петли и совокупности параллельных ветвей. Оставшиеся одиночные ветви относим к z - ветвям. [48]

При этом все входящие ( исходящие) в вершины х и у дуги заменяются дугами, входящими ( соответственно исходящими) в новую вершину. Из полученного графа удаляются все транзитивные дуги. [49]

Для этого каждый трех-полюсник ( рис. 9.21, а) заменяют его графом ( рис. 9.21, б), двухполюсные ветви схемы - отрезками линий. Для полученного графа цепи составляют матрицы А, В или Q. [50]

Иногда используют способ перехода от схемы к графу, когда контакты элементов отображаются вершинами графа G ( X, U), а соединения между ними - ребрами. При этом полученный граф представляет собой объединение полных подграфов, соответствующих узлам схемы. [51]

В этом случае полученный граф называется направленным графом, а его ребра - дугами ( фиг. [52]

Дополним граф Gv модуля [ Mv / K ] К - Mv фиктивными вершинами без информационных связей, соответственно изменив матрицу смежности Cv. Отображение д вершин полученного графа Gv, удовлетворяющее условиям (4.3.28) - (4.3.30), будет также удовлетворять условиям 2.1 и 2.2 утверждения: 4.3.1. Поэтому отображение д есть отображение вершин графа Gv в решетку R с горизонтальным сечением К, т.к. матрица смежности Cv PqCvPq будет иметь вид матрицы смежности решетки. [53]

Нетрудно убедиться, что полученный граф разрешает ЗИП / и сложность его такая лее, что и у исходного. [54]

Аналогичное заключение было получено в разд. Если удалить вершину v из графа, то полученный граф может быть раскрашен пятью цветами в силу предположения индукции. [55]

Двудольный граф, иллюстрирующий теорему Холла. [56]

Обозначим эти вершины через и и v и соединим и с каждой вершиной, соответствующей множеству Sit a v - со всеми вершинами, соответствующими элементам а. Тогда теорему 5.19 можно доказать, применив к полученному графу или теорему о максимальном потоке, или соответствующий реберный вариант теоремы Менгера. [57]

Страницы: 1 2 3 4