Cтраница 3
Пусть G - граф, не содержащий клешней. Выберем в нем любую вершину а и проверим, регулярная ли она. Это просто означает проверку того, индуцирует ли множество N ( a) двудольный граф в дополнении графа G, и эта проверка может быть выполнена за полиномиальное время. [31]
Решетчатый граф L2 ( m) ( m 2) имеет своими вершинами множество 5XS, где 5 - множество мощности т; две вершины этого графа смежны тогда и только тогда, когда они имеют общую координату. Объединение k непересекающихся полных графов на m вершинах каждый ( k, m - 1) также образует сильно регулярный граф T ( k, т) с параметрами п mk, а т - 1, с т - 2, а О, причем всякий сильно регулярный граф с d Q имеет такую форму. Граф Г ( &, 2) называется лестничным графом. Дополнение графа T ( k m) называется полным k - дольным графом. Если q - степень простого и 7l ( mod4), то граф ТЪли P ( q) имеет в качестве вершин элементы поля GF ( q), и две его вершины смежны тогда и только тогда, когда их разность есть ненулевой квадрат. Это сильно регулярный граф с параметрами п q, a ( q - l) / 2, c ( q - 5) / 4, d ( q - 1) / 4, изоморфный своему дополнению. [32]
В геометрических теориях приходится иметь дело с целым рядом конкретных графов. Группы этих графов были найдены Каньо. Эта задача сразу сводится к предыдущим случаям, так как граф Дезарга оказывается дополнением графа Петерсена, а граф Паппа имеет дополнение, которое состоит из трех компонент, являющихся треугольниками. [33]
Главы I-IV посвящены методам теории графов, на которых основано решение задач логического проектирования автоматов. В них рассматриваются теоретико-множественные и алгебраические операции над ориентированными графами, определяются свойства операций и основные алгебраические структуры, которые они образуют по аналогии с известными структурами множеств. Решаются задачи разложения графов по алгебраическим и теоретико-множественным операциям. Доказываются теоремы о разложении графов по различным операциям, формулируются алгоритмы разложения, даются оценки числа разложимых графов, а также решается задача отыскания минимального дополнения неразложимых графов до разложимых. Главы V-IX посвящены изложению логического проектирования автоматов и вычислительных структур с помощью методов теории графов. Здесь излагается алгебра абстрактных автоматов, которая на абстрактном уровне описывает различные виды соединений автоматов при построении схем сложных автоматов, и проблема декомпозиции абстрактных автоматов, которая заключается в представлении сложного абстрактного автомата совместной работой более простых абстрактных автоматов. Решается задача общей декомпозиции, позволяющая любой абстрактный автомат представлять работой элементарных абстрактных автоматов с минимальным числом связей между ними, и задача декомпозиции автомата на заданные блоки, которая приводит к представлению автомата в виде однородной структуры заданных стандартных блоков, соединенных между собой последовательно, параллельно или произвольным образом. Описывается декомпозиционный метод синтеза автоматов, основанный на решении задачи общей декомпозиции автоматов, исключающий этап структурного синтеза и приводящий к единому сквозному синтезу автоматов, который решает задачи логического проектирования на абстрактном уровне. [34]
Имея выбранную 2-схему с К k - 1 как возможный потенциал для D ( T p), мы знаем все ребра Г за исключением тех, которые соединяют различные блоки. Таким образом, эта задача схожа с задачей расширения данной схемы. Всякий блок должен быть смежен v - k другим блокам, и эти смежные блоки не должны пересекаться ( поскольку граф не содержит треугольников); кроме того, если два несмежных блока имеют х общих точек, то k - х блоков должны быть смежны обоим. Иногда случается, что точно v - k блоков не пересекаются с любым заданным блоком. Тогда конструкция определена однозначно: два блока смежны тогда и только тогда, когда они не пересекаются. Два примера этого, где результирующий граф сильно регулярен, представляют парная схема на пяти точках и единственная 3 - ( 22, 6 1) - схема. Эти графы получаются как дополнение графа Клебша ( п16) и графа Хигмана - Симса ( п100) соответственно. Имеются графы на 56 и 77 вершинах, построенные в последней главе. GF ( 9); во втором случае блоки смежны, если они не пересекаются, но не параллельны. [35]