ГРАФОВ ТЕОРИЯ

— раздел математики, изучающий графы и те их обобщения (транспортные сети, гиперграфы и др.), на которые распространяются некоторые из основных понятий и методов, относящихся к графам.

До возникновения общей теории графы встречались под разными названиями в матем. задачах развлекательного характера, в теории электр. цепей, в химии, физике, биологии, социологии, а также в некоторых разделах математики, в первую очередь алгебре и топологии. Т. к. существует широкий круг объектов и явлений реального мира, которые могут быть истолкованы в терминах Г. т., возникновение общей теории абстрактных графов представляется естественным. Интенсивное развитие Г. т. обусловлено в основном запросами практики; важную роль сыграли в становлении Г. т. многочисленные исследования, связанные с проблемой четырех красок, а также идея метода чередующихся цепей.

Одной из первых работ, относящихся к Г. т., является работал. Эйлера (1736), однако основоположником Г. т. считают венгерского математика Д. Кёнига, автора первой монографии (1936), в которой графы рассматриваются как абстрактные матем. объекты и где заложены основы общей Г. т. Наибольший вклад в дальнейшее развитие Г. т. внесли венгерские, амер., канадские, нем., франц., чехословацкие и др. математики, а также советские, из которых можно отметить Л. М. Лихтенбаума (1900—1968), А. А. Зыкова (р. 1922) и В. Г. Визинга (р. 1937).

Основываясь на систематизации и обобщении ряда идей и приемов комбинаторно-логич. характера, относящихся в значительной мере к поискам оптим. решений различных дискретных задач, Г. 7. вместе с, комбинаторным анализом представляет интенсивно развивающийся специфический раздел совр. математики, тесно соприкасающийся с такими ее разделами, как алгебра, топология, теория чисел, вероятностей теория, логика математическая, программирование математическое и др.

В соответствии с наиболее общим определением графа для задания графа достаточно знать мн-во его вершин ребер и мн-во тех упорядоченных троек хаиха. на которых истинно высказывание . В случае обыкновенных графов или Бержа графов достаточно знать мн-во X и мн-во тех неупорядоченных (соотв. упорядоченных) пар для которых истинно . Граф, у которого оба мн-ва конечны (конечный граф) и можно задать матрицей инциденций строки которой отвечают вершинам графа столбцы — ребрам , а элемент несет информацию о типе ребра (дуга, петля или звено) и об отношении этого ребра к вершине дуга, заходящая дуга, инцидентная петля, инцидентное звено или неинцидентное ребро). Для задания графа часто пользуются квадратной матрицей смежности у которой как строки, так и столбцы отвечают вершинам графа , а элемент несет информацию о к-вах ребер каждого типа, соединяющих вершины в случае обыкновенного графа достаточно положить при при , а в случае графа Бержа положить при при Для графов общего вида в качестве используют

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

Установить тождественность двух конечных графов с одними и теми же мн-вами X и U нетрудно при любом из перечисленных способов задания. Напротив, проблема изоморфизма (задача выяснения того, существует ли взаимно однозначное соответствие мн-в X и X вершин обыкновенных графов L (X, U) и L (X, U), при которой каждому ребру графа L соответствует ребро графа L и наоборот) даже в случае обыкновенных графов проста лишь чисто теоретически. Напр., для выяснения изоморфности двух обыкновенных графов и в случае требуется, вообще говоря, сравнений матрицы смежности одного из них со всеми матрицами смежности второго, получаемыми друг от друга всевозможными перестановками рядов (одновременными одинаковыми перестановками строк и столбцов). Еще труднее проблема изоморфного вхождения, когда для двух графов L и L необходимо установить, изоморфен ли L к.-л. части графа L. Практически эффективное решение этих двух проблем в общем виде не найдено, но опо осуществимо для многих спец. классов графов или при тех или иных ослаблениях постановки — напр., если речь идет не об изоморфизме данных графов, а лишь о наличии у них общих свойств (в частности, совпадении тех или иных характеристик), или об оценке вероятности того, что граф содержит часть данного вида.

Характеристика графов — это ф-ция, относящая каждому графу элемент некоторого фиксированного мн-ва (чисел, векторов, многочленов, матриц, разбиений, класса тех или иных алгебр, систем и т. д.) и, как правило, изоморфная, т. е. принимающая на изоморфных графах одинаковые значения. К важнейшим числовым характеристикам обыкновенного графа относятся: к-во вершин ребер т компонент (см. Графов связность) цикломатическое число полных и пустых -вершинных подграфов плотность неплотность (число внутренней устойчивости) е гаг (L) вершин степени i (т. е. инцидентных ровно i ребрам); степень а графов ребрами и цикломатиче-ским числом таких раскрасок вершин ровно i цветами, при которых никакие две смежные (соединенные ребром) вершины не окрашены одинаково; хроматическое число ); число Хадвигера (степень гомоморфизма) наибольшее к-во вершин полного графа, в который можно превратить граф L (или какой-либо его подграф) при помощи стягивания ребер; хроматический класс (хроматический индекс) X (L) — наименьшее к-во цветов, которым можно раскрасить ребра графа так, чтобы никакие два смежных (т. е. имеющих общую инцидентную вершину) ребра не оказались одного и того же цвета; всесмежность (число внешней устойчивости) р (L) — наименьшее к-во вершин такого подграфа L, что всякая не принадлежащая ему вершина L смежна хотя бы с одной вершиной из L. Некоторые характеристики (радиус, диаметр и др.) связаны с метрикой графа — т. е. ф-цией, относящей каждой паре вершин х и у расстояние между ними — некоторое число напр., длину кратчайшей из цепей, соединяющих , а другие — с различными представлениями графов. Из числовых характеристик можно составлять различные многочленные характеристики, напр., размерностный многочлен распределительный (хроматический) многочлен и др., где z — формальная переменная.

Для ориентированных графов характеристиками являются к-во простых орциклов заданной длины (см. Цикл графа), к-во ядер (см. Игра на графе), к-ва баз и бикомпонент, а также многие числа, связанные с орметрикой (уточнением понятия расстояния от одной вершины до другой, учитывающим направления дуг). Некоторые характеристики неориентированного графа обусловлены возможностью ориентировать его ребра заданным образом. Характеристикой графа может быть и некоторая алгебр, система — группа автоморфизмов, полугруппа эндоморфизмов и т. п. Примерами неизоморфных характеристик могут служить к-во простых цепей заданной длины между данной парой вершин графа и матрица таких к-в для всех пар его вершин. Многие из перечисленных характеристик переносятся на графы общего вида.

Практически эффективно вычислимую систему изоморфных характеристик, которая определяла бы граф с точностью до изоморфизма, указать не удается. Осн. задачами относительно характеристик одного и того же графа являются выражения и оценки одних характеристик через другие (особенно важно находить точные оценки сверху и снизу для таких трудно вычислимых характеристик, как через легко вычислимые и др.). Так, для обыкновенных графов: если а и граф L не содержит полных а (-вершинных подграфов, то верхняя оценка для не может быть ф-цией одной лишь оценка тривиальна); оценка тривиальна); были найдены точные верхние и нижние оценки для , точная верхняя для и точная верхняя для через ; точная нижняя оценка для через

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

Оптимальные (экстремальные) и критические графы и разницу между ними рассмотрим на конкретном примере. Пусть класс обыкновенных -вершинных графов плотности таких, что добавление любого ребра (без добавления вершин и изменения положения прежних ребер) приводит к увеличению плотности, подкласс тех из них, которые при заданных и имеют наибольшее возможное к-во ребер. Тогда графы из критические относительно добавления ребра, а графы из оптимальные (в данном случае максимальные) по ребер (на рис. 1 приведены соответствующие примеры для При фиксированных класс состоит из единственного (с точностью до изоморфизма) графа и к тому же графу приводит замена плотности хроматическим числом у, напротив, классы с одинаковыми числовыми значениями и у различны. Вообще оптим. граф характеризуется тем, что числовое значение одной из его характеристик является наибольшим (или наименьшим) возможным при фиксированных значениях заданной системы других характеристик, а критический граф — тем, что применение к нему любой операции определенного типа обязательно увеличивает (или обязательно уменьшает) заданную характеристику.

Операция разборки относит графу L один или несколько графов каждый из которых в каком-то смысле проще исходного (напр., содержит меньше вершин или меньше ребер). С каждой такой операцией можно связать класс характеристик Ф, удовлетворяющих рекуррентному соотношению

где заданная ф-ция, и начальным условиям; для «простейших» графов к которым данная операция разборки неприменима, значения известны. Во многих случаях можно без существенной потери информации о графз считать, что ф-ция линейна, т. е.

где числа и значения являются образующими элементами некоторого кольца К. Осн. задачи для данного класса L графов и заданной операции разборки: а) найти условие Q (в виде системы соотношений между образующими кольца К), необходимое и достаточное для того, чтобы характеристика Ф была изоморфной; б) установить канонический вид, к которому с помощью соотношений Q приводится общее выражение ; в) выяснить смысл (используя термины структуры графа L) коэфф. канонического представления . Напр., если L — класс обыкновенных графов с линейно упорядоченным мн-вом вершин, подграф графа порожденный всеми вершинами L, смежными с первой, а подграф, полученный из L удалением первой вершины, то, очевидно, размерностный многочлен

удовлетворяет рекуррентному соотношению и начальному условию Установлено, что всякая изоморфная характеристика , для которой кольца К с образующими полностью определяется числами

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

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

графов, по операции декартова умножения) и не приводит к полному описанию всех графов (или хотя бы только всех обыкновенных). Однако нередко те или иные операции композиции оказываются полезными при описании классов спец. графов, напр., оптимальных (так, граф Турана есть произведение пустых - вершинных и пустых -вершинных обыкновенных графов, где или при построении графов с наперед заданными свойствами.

1. Графы: а — критический; б — оптимальный.

2. Операции композиции двух обыкновенных графов.

3. Сшивание двух обыкновенных графов по выделенному подграфу.

4. Перемещение ребер обыкновенного графа.

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

Операция преобразования переводит граф в другой граф, как правило, без упрощения или усложнения. По отношению к операции этого типа возникают вопросы нахождения инвариантных характеристик графа и вопрос о полноте систем таких характеристик (т. е. о возможности преобразования друг в друга двух графов с одной и той же системой последовательным применением операции). Напр., система степеней вершин обыкновенного графа полна относительно операции перемещения ребер, показанной на рис. 4.

Локальные свойства графов. Пусть — граф общего вида; звездой его вершины часть, образованная самой вершиной и всеми инцидентными ей ребрами (вместе с их вторыми концевыми вершинами).

Задавая все звезд по отдельности без указания, какие вершины разных звезд являются одной и той же вершиной графа L, получим локальную информацию об все свойства графа, основанные на такой информации, наз. локальными. Для обыкновенного графа вся локальная информация о нем исчерпывается системой чисел поэтому выражаемые через них характеристики тоже относятся к локальным; характеристики — не локальные. Многие обобщения локальных свойств можно назвать квазилокальными, напр., свойства, определяемые совокупностью окружений всех вершин обыкновенного графа (окружение вершины обыкновенного графа L — это его подграф, порожденный всеми смежными с вершинами L) или совокупностью всех его -вершинных подграфов (заданных с точностью до изоморфизма). Относительно второй совокупности до наст, времени не известно, всегда ли она определяет исходный граф L однозначно с точностью до изоморфизма (проблема Улама—Келли).

Единый алгоритм для решения всех вопросов Г. т. невозможен, однако конкретный вопрос для конкретного конечного графа всегда разрешим в конечное к-во шагов. Но решение может оказаться слишком громоздким, поэтому и в отношении конечных алгоритмов возникает проблема их практической эффективности, т. е. возможности существенно избежать полного перебора всех мыслимых случаев. К практически эффективным относятся, напр., метод чередующихся цепей и метод Форда — Фал-керсона в теории транспортных сетей. Напротив, некоторые задачи (напр., среди связанных с раскраской вершин) не допускают в общем случае практически эффективных алгоритмов, и тогда часто прибегают к таким приемам, которые для подавляющего большинства графов дают результат в приемлемое время. С этим связано широкое применение в Г. т. вероятностных и асимптотических методов, опирающееся на различные задачи подсчета графов (напр., найти к-ва неизоморфных обыкновенных графов с заданным к-вом вершин и ребер, заданными степенями вершин и др., а также аналогичные к-ва при дополнительном условии связности графов и т. п.), решаемые методами комбинаторного анализа.

Графы используются в сетевых методах планирования и управления, при построении граф-схем автоматов (см. Абстрактного автомата граф), в теории алгоритмов (см. Алгоритмов граф-схемы) и в др. разделах кибернетики.

Лит.: Зыков А. А. Реберно-вершинные функции и распределительные свойства графов. «Доклады АН СССР», 1961, т. 139, № 4; Ершов А, П., Кожухин Г. И. Об оценках хроматического числа связных графов. «Доклады АН СССР», 1962, т. 142, № 2; Визинг В. Г. Оценка числа внешней устойчивости графа. «Доклады АН СССР», 1965, т. 164, № 4; Зыков А. А. Теория конечных графов, т. 1. Новосибирск, 1969 [библиогр. с. 515-5423; КSnig D. Theorie der endlichen und unendlichen Graphen. Leipzig, 1936; Бepж К. Теория графов и ее применения. Пер. с франц. М., 1962 [библиогр. с. 293-302]; Ore О. The four-color problem. New York, 1967 [библиогр. с. 249-253]; Ope О. Теория графов. Пер. с англ. М., 1968 [библиогр. с. 325—338]; Sachs Н. Einfiihrung: in die Theorie der endlichen Graphen, т. 1, 2. Leipzig, 1970; Xapapи Ф. Теория графов. Пер. с англ. М.,1973 [библиогр. с. 269 - 286]. А.А.Зыков.