Cтраница 3
Характеристика nfts задается различными величинами, например: площадью перекрытия зон реализации цепей а & и as; числом пересечений полных подграфов цепей аь. [31]
Необходимое и достаточное условие, при котором граф является смежностным, состоит в том, что существует разбиение его ребер на полные подграфы такое, что пет вершины графа, принадлежащей более чем двум подграфам. [32]
Легко проверить, что ни один из девяти графов, приведенных на рис. 8.3, не допускает разбиение множества ребер на полные подграфы, удовлетворяющее указанному выше условию. Окончательный результат вытекает из того, что каждый порожденный подграф реберного графа сам должен быть реберным графом. [33]
Граф G является реберным графом некоторого графа тогда и только тогда, когда граф G может быть описан как такое объединение полных подграфов, что ни одна вершина из G не принадлежит более чем двум из этих полных подграфов. [34]
Например, графом, дополнительным к полному двудольному графу Kp q, будет граф Кр Kq - граф, состоящий из двух полных подграфов на двух непересекающихся подмножествах по р и q вершин, соответственно. [35]
Там, где задача раскраски усложнена дополнительными условиями одноцветности вершин, эффективным может оказаться и подход, предполагающий нахождение наибольшего пустого или полного подграфа, а затем группирование около вершин, вошедших в этот подграф, остальных вершин заданного графа. С помощью этого подхода, как показано в [26], можно решить такие задачи, как минимизация длины кода состояний асинхронного автомата, сжатие таблицы переходов автомата ( по строкам и столбцам), параллельная декомпозиция автомата, упрощение системы булевых функций, описывающих асинхронный автомат. Точно так же можно решать и все остальные задачи, перечисленные выше. Из рассмотренных здесь подходов к решению задач логического проектирования данный подход единственно пригоден для решения таких задач абстрактного синтеза автоматов, как минимизация числа состояний синхронного автомата и его декомпозиция. [36]
Кроме того, каждое значение t 6 V ( G) встречается точно в Y yi из множеств At, ибо Y, индуцирует полный подграф и поэтому все его элементы имеют разные цвета. [37]
Многие задачи распознавания, традиционно считавшиеся трудными ( например, задача определения, является ли данный граф гамнльтоновым, задача о существовании в данном графе полного подграфа с заданным числом вершин и др.), как оказалось, весьма тесно связаны друг с другом. [38]
Продолжая исследования Хайнала и Шураньи [129], Дирак [97] и Гал-лаи [121] устанавливают достаточные условия возможности разбиения множества вершин графа на заданное число попарно непересекающихся подмножеств, порождающих полные подграфы; в эти условия входит ограничение сверху числа внутренней устойчивости данного графа, а также требование такого типа, чтобы каждый его элементарный цикл длины 3 имел хотя бы одну хорду или чтобы этому условию удовлетворяли по крайней мере все циклы нечетной длины. [39]
Следует заметить, что, используя рассмотренный выше алгоритм выделения семейства максимальных внутренне устойчивых подмножеств множества вершин графа ( максимальных пустых подграфов), можно выделять семейство Ф максимально полных подграфов. Для этого необходимо в матрице смежности R графа все единичные элементы заменить на нулевые и наоборот. В результате получим R и применяем алгоритм 1 без изменений. [40]
Так как в любой x ( G) - раскраске графа G есть одноцветный класс, содержащий по, крайне мере pl % ( G) вершин, то существует полный подграф графа G, у которого не менее p / x ( G) вершин. Таким образом, х ( Сг) p / x ( G), откуда следует доказываемое неравенство. [41]
Тот же автор предлагает [71] новое доказательство теоремы Ту-рана о графе с наибольшим числом ребер при данном числе вершин и данной плотности, а Эрдеш выводит [111] верхнюю оценку количества полных подграфов с заданным числом вершин у графа, имеющего данные количества вершин и ребер; только после выхода обеих работ их авторы узнали, что еще в 1949 году А. А. Зыков [23] дал простое доказательство теоремы Турана ( не подозревая, в свою очередь, что сама теорема уже известна) и впервые получил упомянутый результат, содержащийся в работе Эрдеша. [42]
Теорема 2.8. Граф G является графом клик тогда и только тогда, когда он содержит семейство F полных подграфов, объединение которых дает G, таких, что если любая пара этих полных подграфов некоторого подсемейства F имеет непустое пересечение, то пересечение всех множеств из F также не пусто. [43]
В этом случае получаем граф G ( X, U), состоящий из двух кусков GI ( Xit L / i) и G2 ( Х2, Uz), где на множестве Xi образован полный подграф, а на 2 - пустой. [44]
По аналогии с числом внутренней устойчивости, характеризующим максимальное количество не смежных между собой вершин графа, введем понятие числа внутренней полноты x ( G), которое определяет максимальное количество вершин графа G, образующих полный подграф. [45]