Дополнительный граф

Cтраница 2

Очевидно, что матрица В, перестановочна также с единичной матрицей / и, следовательно, матрицей В / - / - В, которая является матрицей смежности ребер дополнительного графа. [16]

Граф и его клики. [17]

Если предположить, что граф Г ( X, U, Ф) простой, то полностью зависимые множества ( клики) в Г становятся максимально независимыми множествами в дополнительном графе Г, верно и обратное. [18]

Заметим, что если Я ц - 2, то в дополнительном графе 9 выполнено равенство Я ц и симметрическая схема является дополнительной к схеме, получаемой, исходя из дополнительного графа. [19]

Рассмотрим обыкновенный граф с п вершинами. Дополнительный граф получается, если из полного ( обыкновенного) графа с п вершинами вычеркнуть все ребра, содержащиеся в исходном графе. Граф является само-дополнительным, если он изоморфен своим дополнением. Так, например, граф на рис. 4.9 самодополнительный. [20]

Аналогично проводится расчет, если pi и р2 не смежны. Стало быть, дополнительный граф Г тоже сильно регулярен. [21]

Отсюда следует, что дополнительный граф к сильно регулярному графу также является сильно регулярным. [22]

Этот граф является неплоским, а его дополнительный граф, очевидно, плоский. Снова рассмотрим подграф Понтрягина - Куратовского 2-го типа с двумя изолированными вершинами. [23]

Однако при решении задачи на ЭВМ приходится строить дополнительный граф размещения. Для этого удаляются ребра ( 3, 5) и ( 7, 5) как инцидентные общей вершине цепей и не принадлежащие цепям. Вершина 5 раздваивается, как и в предыдущем примере, на две - 5 и 5 с соответствующей заменой ребер. Это лишний раз подтверждает сделанный выше вывод о геометрической совместности схемы. [24]

Предположим, что G пе имеет разделяющих вершин. Если Н не совпадает с целым графом, то он имеет некоторую соединяющую вершину а, в которой есть реб - pji дополнительного графа Я. [25]

Дополнительный граф к графу G определяется как граф G с множеством вершин V ( G) V ( G), в котором две вершины соединены ребром тогда и только тогда, когда они не соединены ребром в графе G. Разбиение V ( G) на k подмножеств, каждое из которых независимо, называется k - раскрашиванием графа G. Отметим, что это соответствует покрытию k кликами вершин дополнительного графа. Наименьшее k, для которого граф G допускает - раскрашивание, называется его хроматическим числом. [26]

Задача объединения электростанций состоит в том, чтобы спроектировать систему связей, имеющую минимальную общую стоимость и удовлетворяющую требованиям по dt для всех станций. Очевидно, она эквивалентна следующей задаче теории графов. Можно также искать подграф, имеющий максимальную взвешенную сумму ребер, каждая вершина которого имеет степень не больше п - d - 1, а затем взять дополнительный граф. [27]

Параллельно определяется общая топология сети синхронизации - основной граф синхронизации. На этом этапе осуществляется многовариантное проектирование, поскольку проектирующий специалист должен сделать выбор технического решения в многопараметрической задаче: важными параметрами оказываются параметры генераторов и каналов передачи и распределения синхросигналов. В результате создается основа синхросети. Затем, исходя из требований надежности в системе синхронизации, определяется общий уровень резервирования, т.е. количество дополнительных графов или участков графа синхронизации. В результате проектируется полная синхросеть. Эта система подвергается всестороннему анализу по параметрам синхросигналов на каждом участке, параметрам надежности и возможности появления петель в процессе резервного переключения с одного источника на другой. При необходимости ( например, для устранения вероятности появления петель в системе) может измениться как резервная, так и основная топология синхросети. Таким образом, процесс проектирования этого этапа является многопараметрическим и итерационным. [28]

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

Этот граф является неплоским, а его дополнительный граф, очевидно, плоский. Снова рассмотрим подграф Понтрягина - Куратовского 2-го типа с двумя изолированными вершинами. Полученный граф является плоским. Можно показать, что его дополнительный граф также является плоским. [30]

Страницы: 1 2