Исходный граф

Cтраница 1

Исходный граф О может быть трехсвязным. Тогда мы будем говорить, что он содержит ровно один 3-блок, который совпадает с самим графом О. [1]

Простое преобразование графа, представляющее Х - применение. [2]

Исходный граф показан слева, а преобразованный - справа. [3]

Неплоский граф. [4]

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

Исходный граф преобразовать к / - графу, удаляя z - ветви, и построить лес / - графа. [6]

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

Исходный граф G может быть задан матрицей либо списком смежности. Матричное представление является избыточным. Для алгоритма определения планарности используется модифицированная форма списка смежности LS, где каждой вершине ставятся в соответствие номера ребер, инцидентных рассматриваемой вершине, например, запись 1 ( 1 2) означает, что ребро инцидентно вершинам х и х и имеет номер 1, причем в список смежности некоторой вершины Xi не включаются номера вершин от х до Xi - включительно. [8]

Иногда исходный граф удается преобразовать таким образом, что процесс упрощения его значительно ускоряется. [9]

Когда исходный граф не содержит в качестве подграфа граф Гк, то для любой пары вершин графа существует раскраска графа в К цветов, при которой эти вершины несоцветны, что обеспечивает многокомпонентную ЛГ-раскраску вершин графа. Таким образом, граф Гк является запрещенной фигурой многокомпонентной К-раскраски вершин графа. [10]

Нумерация вершин графа. [11]

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

Деревья графа.| Неплоские графы. [13]

Если исходный граф является несвязным, то деревья образуются для каждой несвязной части графа. Совокупность деревьев несвязного графа называют лесом этого графа, формула (2.58) справедлива и для несвязного графа с общим количеством ветвей пв, если яд и тгх - общее число ветвей и хорд деревьев в лесу. [14]

Поскольку исходный граф структуры m - го класса Тт ( / т) конечен, то количество шагов разработанного алгоритма синтеза также конечно. [15]

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