Cтраница 1
Простые графы, для которых известно обобщенное число Рамсея. [1]
Максимальные m - простые графы типа II, удовлетворяющие условиям (5.1) - (5.4) и (6.1), мы будем называть ( п, т, и, х, у ] - графами. [2]
Максимальные / n - простые графы, содержащие при фиксированном k максимальное число ребер, называются экстремальными. [3]
В этом разделе рассматриваются только простые графы. Таким образом, в частности, насыщенный граф должен быть связным. [4]
Таким образом, п-клики являются простыми графами. Очевидно, что нуль-графы являются 0-кликами, графы-вершины являются 1-кликами, а графы-звенья - 2-кликами. На рис. 1.1.4 ( 1) - ( 111) показаны 3-клики, 4-клики и 5-клики соответственно. [5]
Прежде чем исследовать максимальные m - простые графы, докажем две леммы. [6]
Заметим, что по определению деревья и леса являются простыми графами. [7]
В теории графов существует много задач, в которых рассматриваются только простые графы. Поэтому некоторые авторы используют термин граф именно для простых графов. [8]
Все упомянутые до сих пор результаты этого параграфа применимы к произвольным плоским графам; далее ограничимся простыми графами. [9]
Пусть п - неотрицательное целое число, а О и Я - некоторые я-клики. Они являются простыми графами. Следовательно, по теореме 1.2 С и Я изоморфны. [10]
Мы укажем только основную идею некоторых из наиболее быстрых алгоритмов для построения всех стягивающих деревьев, так как в них используется мощный и изящный метод: при решении задачи для сравнительно сложного графа последний разбивается на несколько более простых, и та же самая задача рекурсивно решается для каждого из этих более простых графов. Чтобы гарантировать конечность процесса, достаточно простые графы не разбиваются дальше и для них задача решается непосредственным перебором. [11]
Мы будем рассматривать графы, обозначаемые G, которые описывают только голые молекулярные скелеты, т.е. молекулярные структуры, при изображении которых атомы водорода опускаются. Графы, описывающие голые углеродные скелеты углеводородов или, в более общем случае, гомоядерные скелеты, являются простыми графами или мультиграфами [21] в зависимости от выбранного нами способа представления кратных связей. В настоящей работе мы будем рассматривать вершинно - и реберно-взвешенные графы, которые, конечно, сводятся к обычным графам, когда весовые коэффициенты вершин и ребер отсутствуют. [12]
Оптимальная декомпозиция абстрактных автоматов решает задачу кодирования состояний автоматов и приводит к синтезу функциональных схем с минимальной комбинационной частью. Поскольку декомпозиция автоматов основана на разложении графов, то вполне понятно то внимание, которое уделяется в книге вопросам разложения сложных графов на более простые графы. Заметим, что задача разложения поставлена и решена для абстрактных графов и поэтому в принципе может быть распространена на любые объекты и системы, которые можно задавать в виде графов, не ограничиваясь только приложением ее в теории автоматов и вычислительных машин. [13]
Подграфом полного графа называется любой граф, содержащийся в полном графе в том смысле, что все вершины и ребра подграфа принадлежат полному графу. Нетрудно видеть, что любой полный граф является подграфом любого полного графа с большим числом вершин. Многие простые графы имеют свои собственные названия. На рис. 108 представлены четыре семейства графов: маршруты, циклы, звезды и колеса. [14]
Аналогичные рассуждения позволяют доказать, что если п - целое число, большее 2, то любые два п-цикла изоморфны. На случай п 1 и п 2 этот результат распространяется тривиальным образом. Но так как 1-цикл и 2-цикл не являются простыми графами, то теорема 1.2 для этих графов неприменима. Если С и Я суть 2-циклы ( как показано на рис. I. [15]