Графов теория. История возникновения теории графов

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

Граф – это совокупность двух множеств: множества точек, которые называются вершинами , и множества ребер А . Каждый элемент есть упорядоченная пара элементов множества , вершины и называются концевыми точками или концами ребра а . Граф называется конечным , если множества R и конечны.

Это определение графа должно быть дополнено в одном важном отношении. В определении ребра можно принимать или не принимать во внимание порядок расположения двух его концов. Если этот порядок несущественен, т. е. если , то говорят, что a есть неориентированное ребро ; если же этот порядок существенен, то a называется ориентированным ребром (ориентированное ребро часто называется дугой ). В последнем случае называется также начальной вершиной , а – конечной вершиной ребра a . Граф называется неориентированным , если каждое его ребро неориентировано, и ориентированным , если ориентированы все его ребра. В ряде случаев естественно рассматривать смешанные графы, имеющие как ориентированные, так и неориентированные ребра.

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

Число ребер, инцидентных одной вершине , будем обозначать через . Это число называется локальной степенью или просто степенью графа в вершине . В случае ориентированного графа G обозначим через и число ребер, соответственно выходящих из вершины и входящих в . Эти числа называются локальными степенями G в . Если все числа конечны, то граф называется локально-конечным . Вершина степени 1 называется висячей . Вершина степени 0 называется изолированной .

Рисунок 14.1.

На рис. 14.1 и – параллельные ребра, – петля; вершина и ребро инцидентны друг другу; – смежные вершины, – смежные вершины; степень вершины равна трем, – висячая вершина, – изолированная.

Теорема 14.1. В графе G сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа: , где n – число вершин графа, m – число его ребер.

Учебное издание

Ююкин Николай Алексеевич

ЛР № . Подписано в печать

Уч. Изд. л.. , .

Воронежский государственный технический университет

394026 Воронеж, Московский просп. 14

СПРАВОЧНИК МАГНИТНОГО ДИСКА

Кафедра высшей математики и физико-математического моделирования

Н.А. Ююкин

ДИСКРЕТНАЯ МАТЕМАТИКА Часть 1. Элементы теории графов

Учебное пособие

Н.А. Ююкин

ДИСКРЕТНАЯ МАТЕМАТИКА Часть 1. Элементы теории графов

Учебное пособие

Воронеж 2004

ВВЕДЕНИЕ

Данное пособие может быть использовано в курсе “Дискретная математика” студентами ВГТУ, обучающимися по специальностям:

090102 – Компьютерная безопасность;

090105 – Комплексное обеспечение информационной безопасности автоматизированных систем;

090106 - Информационная безопасность телекоммуникационных систем.

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

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

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

в орграфах; анализ графа цепи Маркова; алгоритмы поиска кратчайших путей в графах; задача поиска гамильтонова цикла

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

Целью курса является формирование у студентов теоретических знаний, практических умений и навыков в области моделирования процессов и явлений в естествознании и техни-

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

Достижению данной цели служат следующие задачи:

изучить максимально широкий круг понятий теории графов;

получить навыки решения учебных и практических задач;

овладеть методами оптимизации;

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

Дисциплина “Дискретная математика” относится к числу прикладных математических дисциплин. Она основывается на знаниях, приобретенных студентами при изучении дисциплин “Алгебра” и “Математическая логика и теория алгоритмов”. Знания и навыки, полученные при изучении дисциплины “Дискретная математика” используются при изучении общепрофессиональных и специальных дисциплин.

1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ.

1.1. Задачи теории графов.

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

Первые задачи теории графов были связаны с решением развлекательных задач и головоломок.

Первая задача . Задача о Кенигсбергских мостах была поставлена и решена Эйлером в 1786 году. Город располагался на берегах и двух островах реки Преголи. Острова между собой и берегами были связаны семью мостами, как показано на рисунке.

Возникал вопрос: можно ли выйдя из дома, вернуться обратно, проходя по каждому мосту ровно один раз?

Вторая задача . Задача о трех домах и трех колодцах. Имеется три дома и три колодца.

Требуется провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. Задача была

решена Понтрягиным и независимо от него Куратовским в

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

Многие результаты теории графов используются для решения практических задач науки и техники. Так, в середине 19 века Кирхгоф применил теорию графов для расчета сложных электрических цепей. Однако, как математическая дисциплина, теория графов сформировалась только в 30-ых годах 20го века. При этом графы рассматриваются как некоторые абстрактные математические объекты. Они применяются при анализе и синтезе цепей и систем, в сетевом планировании и управлении, исследовании операций, программировании, моделировании жизнедеятельности организма и других областях.

1.2. Основные определения.

Графом G= (V,E ) называется совокупность двух множеств - непустого множества вершинV и множества неупорядоченных и упорядоченных пар вершинE . В дальнейшем будут рассматриватьсяконечные графы , т.е. графы с конечным множеством вершин и конечным семейством пар. Неупорядоченная пара вершин называетсяребром , а упорядоченная -дугой .

Обычно граф изображается диаграммой : вершины - точками (или кружками), ребра – линиями произвольной конфигурации. На дуге дополнительно стрелкой указывается её направление. Отметим, что при изображении графа несуще-

ственны геометрические свойства ребер (длина, кривизна), а также взаимное расположение вершин на плоскости.

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

Говорят, что ребро (u,v ) соединяет вершиныu иv , а дуга(u,v) начинается в вершинеu и заканчивается в вершинеv , при этомu называетсяначалом , аv –концом этой дуги.

Пара вершин может соединяться двумя или более ребрами (дугами одного направления). Такие ребра (дуги) называются кратными . Дуга (или ребро) может начинаться или кончаться в одной и той же вершине. Такая дуга (ребро) называетсяпетлёй . Граф, содержащий петли, называетсяпсевдо графом . Граф, имеющий кратные ребра (дуги), называетсямультиграфом .

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

Граф, состоящий из одной изолированной вершины (K 1 ), называетсятривиальным .

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

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

1.3. Степени вершин графа.

Степенью (валентностью) (обозначениеd (v ) илиdeg (v )) вершиныv простого графаG называется число ребер или дуг инцидентных данной вершинеv . При подсчете валентности вершин псевдографа следует учитывать каждую петлю дважды.

Если степени всех вершин н-графа равныk , то граф называетсярегулярным (однородным) степениk . Если степень вершины равна0 , то она являетсяизолированной . Если степень вершины равна1 , то вершина называетсяконцевой (висячей, тупиковой).

Для орграфа число дуг исходящих из вершины v назы-

вается полустепенью исхода										(v ), а входящих –полустепе-
нью захода d							(v ), При этом справедливо соотношениеd (v )=
		(v )+			(v ).

Теорема Эйлера : Сумма степеней вершин графа равна

удвоенному количеству ребер, т.е.

d (vi )

			(v )

Где n – число вершин;m – число

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

1.4. Изоморфизм графов.

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

метками (номерами). Граф считается полностью заданным в строгом смысле , если нумерация его вершин и ребер фиксирована. При этом графыG 1 иG 2 называютсяравными (обозначениеG 1 =G 2 ) ,, если их множества вершин и ребер совпадают. Два графа или псевдографаG 1 = (V 1 ,E 1 ) иG 2 = (V 2 ,E 2 ) называют-

	изоморфными (обозначениеG				если существуют
	взаимно однозначных отображения: 1)				: V 1V 2
: E 1 E 2 такие, что для любых двух вершинu , v в графе
	справедливо соотношение ((u ,v )) ((u ), (v )) .
	Два простых графа (без петель и кратных ребер) G 1					и G 2

оказываются изоморфными, если существуют взаимно одно-

значное отображение

: V 1V 2

Такое что

(u ,v ) ((u ), (v )).

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

Рефлексивности -

G 1,

причем биекция

ставляет собой тождественную функцию.

Симметричности.

с биекцией

с биекцией

Транзитивности.

G 1G 2

биекцией

1 ,а

с биекцией

то G G

с биекцией

2 (1) .

Теория графов - раздел математики, используемый в информатике и программировании, экономике, логистике, химии.

Что такое граф

Часто для описания строения систем используют графические схемы. Элементы в них изображают кружками, точками, квадратами и т. п., а связи между элементами - линиями или стрелками. При этом ни то, как изображаются элементы, ни длина или форма линий не важны - имеет значение только, какие элементы соединены. Итак, граф - это пара вида (A, M), где A - конечное множество вершин, а M - множество ребер - линий, связывающих некоторые вершины.

Основные понятия теории графов

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

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

Если вершины a и b - концы ребра (или начало и конец дуги) графа, то говорят, что вершины a и b инцидентны этому ребру (дуге), также ребро (дуга) инцидентно вершинам a и b. Если вершины a и b - концы ребра, то они (a и b) называются смежными.

Чаще всего рассматривают графы, ребра которых имеют один тип - являются ориентированными или нет.

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

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

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

Каждая вершина орграфа характеризуется:

• Полустепенью исхода. Это количество дуг, выходящих из нее.
• Полустепенью захода. Это количество дуг, которые входят в данную вершину.

Сумма полустепеней захода орграфа, а также сумма полустепеней исхода равны общему количеству дуг графа.

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

Вершина со степенью 0 называется изолированной.

Висячей вершиной является вершина со степенью 1.

Теория графов называет пустым графом такой, в котором нет ни одного ребра. Полный граф - это обыкновенный граф, в котором смежны любые 2 вершины.

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

Графы: изоморфизм

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

Пути и циклы

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

Теория графов в программировании используется для построения граф-схем алгоритмов.

Основные понятия теории графов.

Примеры использования теории графов.

История возникновения теории графов.

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

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

Д.Кёниг, предложил называть такие схемы "графами" и систематически изучать их свойства.

В совершенно различных дисциплинах приходится использовать аналогичные теоремы; так, понятие "матрицы инциденций", введенное Кирхгофом для изучения электрических цепей, было привлечено А.Пуанкаре в топологию при создании его "analysis situs"; понятие "точки сочленения", с давних пор известное в социологии, впоследствии появилось в электронике; все примеры такого рода перечислить невозможно. Чтобы можно было применять теорию графов в столь разнообразных областях, она должна быть в высшей степени абстрактной и формализованной.

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

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

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

Эта теория тесно связана также со многими разделами математики, среди которых - теория групп, теория матриц, численный анализ, теория вероят­ностей, топология и комбинаторный анализ.

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

Теория графов «открывалась» независимо много раз: её с полным основанием можно считать разделом прикладной ма­тематики. В самом деле, наиболее раннее известное упоминание этой теории встречается в работах Эйлера, и хотя проблему, кото­рой он занимался, можно рассматривать как обычную головоломку, псе же она возникла из практики.

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

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

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

Задача о кёнигсбергских мостах

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

В городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголя и друг с другом так, как показано на рисунке.

Задача состояла в следующем: найти маршрут прохожде­нии всех четырех частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту.

Легко, конечно, попытаться решить эту задачу эмпирически, производя перебор всех маршрутов, но все попытки окончатся неудачей.

Вклад Эйлера в решение этой задачи заключается в том, что он доказал невозможность та­кого маршрута.

Рисунок 1. Парк в городе Кенигсберге, 1736 г.

Рисунок 2. Граф к задаче о кенигсбергских мостах

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

Получился «граф». Этот граф показан на рисунке 2., где точки отмечены теми же буквами, что и четыре части суши.

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

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

Граф, показанный на рисунке, связный, но не каждая его вер­шина инцидентна (принадлежит) четному числу ребер.

Электрические цепи

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

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

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

Рисунок 3. Сеть N, соответствующий ей граф G .

Вместо этого он предложил простую, но эффективную методику (ставшую позднее стандартной процедурой), в соответствии с кото­рой достаточно ограничиться только независимыми простыми циклами графа, определяемыми любым из его «остовных деревьев». На рисунке 3 дан пример электрической цепи N, соответствующего ей графа G.

Химические изомеры

Занимаясь чисто практическими задачами органической химии, Кэли в 1857 г. открыл важный класс графов, называемых деревьями.

Он стремился перечислить изомеры предельных (насыщенных) углеводородов С n Н 2 n + 2 с данным числом n атомов углерода; рисунок 4.

Рисунок 4. Изобутан

В социальной психологии.

В 1936 г. психолог Курт Леви н высказал предположение, что «жизненное пространство» индивидуума можно представить с по­мощью планарной карты 1).

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

Рисунок 5. Карта и соответствующий ей граф.

Подчеркнем, что К.Леви н фактически имел дело с графами, как это видно из рисунка 5.

Эта точка зрения привела психологов На­учно-исследовательского центра групповой динамики к другой пси­хологической интерпретации графа, в которой люди представля­ются вершинами, а их отношения - ребрами. Такими отношениями являются, например, любовь, ненависть, общение, подчинение.

Предположение Левина относится только к планарным картам, поскольку он всегда рисовал свои рисунки на плоскости. В последствии идея К.Левина была развита в социометрических процедурах.

В теории организаций

Графы могут быть представлены не только в строгой классической форме. Так жизненный цикл компании И.Адизеса представлен следующим форме.

Рисунок 6. Жизненный цикл компании

Функциональная организационная структура построена по принципу распределения функций внутри организации и созда­ния сквозных подструктур по управлению функциями.

Производственные подразделения

Рис. Функциональная организационная структура

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

Такой теорией стала «Теория графов».

Основные понятия теории графов

Начнём с определения, однозначного определения теория графов не имеет, ниже представлены три определения, но существуют и другие.

Теория графов - раздел дискретной математики, исследующий свойства конечных множеств с заданными отношениями между их элементами.

Теория графов - раздел математики, особенность которого - геометрический подход к изучению объектов

Теория графов - математический язык для формализованного определения понятий, связанных с анализом и синтезом структур систем и процессов.

ГРАФОВ ТЕОРИЯ, раздел дискретной математики, в котором изучаются свойства графов и их обобщений. Графом называется пара (V, Е), где V - множество точек, называемых вершинами, и Е - множество пар вершин, причём если порядок, в котором перечислены вершины в паре, не важен, то эта пара вершин графа называется ребром, а если важен - дугой. Граф, содержащий только рёбра, называется неориентированным графом, или просто графом, а граф, содержащий только дуги, - ориентированным графом. На рисунке 1 - неориентированный граф с вершинами а, b, с, d и рёбрами (а, b), (b, с), (с, d), (а, d), (а, с), (b, d), на рисунке 2 - ориентированный граф с вершинами а, b, с, d, е, f и дугами (а, b), (b, с), (с, d), (d, е), (е, f), (f, а).

Исторический очерк. Первые задачи графов теории были связаны с решением математических задач развлекательного характера и головоломок (смотри Комбинаторные задачи классические). Одним из первых результатов графов теории был критерий существования обхода всех рёбер графа без повторений, полученный Л. Эйлером (1736) при решении задачи о Кёнигсбергских мостах (смотри Гамильтонов цикл). С середины 19 века появляются относящиеся к графов теории работы, содержащие результаты, связанные с различными приложениями математики. Так, Г. Кирхгоф (1847) для составления полной системы уравнений для токов и напряжений в электрических сетях (смотри Кирхгофа правила) предложил представлять такую сеть графом и находить в этом графе остовные деревья, что приводит к решению задачи выделения независимых систем уравнений. Деревом называется связный граф, не содержащий циклов (рис. 3), остовное дерево графа - это его подграф, представляющий собой дерево, множество вершин которого совпадает с множеством вершин графа.

А.Кэли (1854) для подсчёта числа изомеров предельных углеводородов пришёл к задачам описания и перечисления деревьев, обладающих заданными свойствами. Термин «граф» утвердился в математике после выхода монографии немецкого математика Д. Кёнига (1936). Начиная со 2-й половины 20 века значительно расширились исследования в графов теории, в основном в силу развития дискретной математики и вычислительной техники. Задание графа равносильно заданию на элементах множества вершин V некоторого бинарного отношения. По этой причине, а также ввиду возможности наглядного представления графа в виде чертежа на плоскости, графовые модели используются при построении алгоритмов решения разнообразных задач как в математике и естествознании, так и в гуманитарных науках.

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

Особую роль при изучении графов играют матричные методы. Для графа G матрицей смежности А = A(G) = ||a ij || называется матрица, в которой a ij = 1, если в графе G вершина i связана с вершиной j ребром (или дугой в ориентированном графе) и a ij = 0 в противном случае. В первом случае говорят, что вершины i и j смежны, во втором случае - что они несмежны. Маршрутом в графе G называется последовательность ν 0 e 1 ν 1 ...ν n -1 e n ν n , состоящая попеременно из вершин и рёбер графа, в которой ребро е i соединяет вершины v i -1 и v i , i= l, ..., n; говорят, что этот маршрут связывает вершины v 0 и v n . Маршрут, в котором v 0 = v n , называется циклом. Маршрут называется цепью (соответственно, простой цепью), если все его рёбра (все его вершины) различны. При n≥ 1 элемент на месте (i, j) в матрице А n равен числу маршрутов длины n из вершины v i в вершину v j . Граф называется связным, если для любых его двух вершин существует маршрут, связывающий эти вершины. Для графа G с р вершинами и q рёбрами, в котором занумерованы как вершины, так и рёбра, рассматривается матрица инцидентности В(G), представляющая собой матрицу, состоящую из нулей и единиц с двумя единицами в каждом столбце; в столбце, соответствующем ребру, соединяющему вершины i и j, единица стоит в строках с номерами i и j. Говорят, что каждая из вершин i и j и соединяющее их ребро инцидентны, два ребра смежны, если они имеют общую инцидентную им вершину. Ранг матрицы инцидентности В(G) равен р 1 , если граф G является связным графом.

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

Задачи теории графов. Центральным в графов теории является раздел, изучающий структурные свойства графов. Одной из характеристик структуры графа является последовательность степеней его вершин. Степенью вершины неориентированного графа называется число инцидентных ей рёбер. Графическим разбиением чётного натурального числа n называется представление его в виде суммы р слагаемых n = ∑ p i =1 d i такое, что существует граф с р вершинами, степени которых равны d 1 ,...,d p . В графов теории известен эффективный алгоритм, позволяющий для данного упорядоченного набора чисел (d 1 ,...,d p) определить, существует ли граф с р вершинами v 1 ,...,v p , для которых последовательность степеней (d(v 1), ..., d(v p)) совпадает с этим набором. Подробно изучено другое важное структурное свойство - связность графа, а также вопросы, относящиеся к существованию в связном графе маршрутов определённого вида.

Специальным разделом структурной графов теории является факторизация графа, т. е. разложение графа G = (V, Е) на сумму факторов (подграфов) G 1 , ..., G m с некоторым заданным свойством, где G i = (V, Е i) и Е = Е 1 u...uЕ m - разбиение множества рёбер на непустые непересекающиеся подмножества. Наиболее распространённые виды факторизации: n-факторизация, где G i - однородные графы степени n (графы, степени всех вершин которых одинаковы и равны n), и древесная факторизация, где каждая компонента любого G i , i=1, ...,m, является деревом. Любой полный граф К 2 n , т. е. граф, в котором любые две вершины смежны, 1-факторизуем, но не 2-факторизуем; любой полный граф К 2 n+1 не является 1-факторизуемым, но представляется в виде суммы n факторов, являющихся циклами. Если при 1-факторизации речь идёт о возможности разбиения множества рёбер на подмножества, состоящие из попарно несмежных рёбер (при этом каждое из подмножеств есть 1-фактор), то всякое разбиение множества вершин графа на n подмножеств таких, что вершины из любых двух разных подмножеств попарно несмежны, определяет правильную раскраску графа в n цветов. Теория раскрасок графа возникла и развивалась в связи с четырёх красок задачей, которая получила решение лишь на рубеже 1970-80-х годов.

С графом G = (V, Е) естественно связывается целый ряд графов, например его подграфы, дополнительный граф, рёберный граф L(G). Рёберным для графа G с р вершинами и q рёбрами называется граф с множеством вершин Е, в котором две вершины соединены ребром тогда и только тогда, когда соответствующие рёбра смежны в G. Критерий того, что данный граф является рёберным графом, заключается в отсутствии у него подграфов, принадлежащих множеству из 9 конкретно указанных графов (с 4, 5 или 6 вершинами). Изучение специальных классов графов, выделяемых каким-либо определяющим признаком или структурным свойством, составляет одно из направлений теории графов.

Если граф задан бинарным отношением на множестве, то часто возникает вопрос о том или ином его конкретном представлении. Такого рода задачей является задача о планарности графа, т. е. о возможности представить его на плоскости рисунком, в котором нет пересечения рёбер. Наиболее известный критерий планарности даёт теорема Понтрягина - Куратовского: граф является планарным тогда и только тогда, когда он не содержит в качестве подграфа ни полного графа К 5 , ни двудольного графа К 3,3 . Граф G = (V, Е) называется двудольным, если допускается разбиение вершин множества V на два подмножества V 1 и V 2 , состоящие из попарно несмежных вершин, такой граф обозначается K n1 , n2 , где n i - число вершин в подмножестве V i , i = 1, 2.

Значительная часть исследований в графов теории составляют перечислительные и экстремальные задачи. Отдельный класс экстремальных задач - задачи о покрытии. Основными объектами исследования в задачах о покрытии являются четыре важнейшие теоретико-графовые константы: число вершинного покрытия α 0 , число рёберного покрытия α 1 , вершинное число независимости β 0 и рёберное число независимости ß 1 . Число вершинного покрытия графа G есть минимальное число вершин в покрывающем множестве, т. е. в таком множестве вершин, для которого каждое ребро графа G инцидентно хотя бы одной вершине этого множества. Вершинное число независимости графа G есть наибольшее возможное число элементов в независимом множестве, т. е. в таком множестве вершин, в котором любые две вершины несмежны. Аналогично определяются число рёберного покрытия и рёберное число независимости. Для любого связного графа G с р > 1 вершинами α 0 + ß 0 = α 1 + ß 1 = р, а для двудольного графа ß 1 = α 0 . Значения этих констант известны лишь для некоторых графов частного вида. К задачам о покрытии тесно примыкает теория доминирования. В ней рассматриваются доминирующие множества графа G = (V, Е), то есть такие подмножества D с V, что любая вершина из VD смежна хотя бы с одной из вершин D. Важнейшей константой графа является число доминирования - наименьшее возможное число вершин в его доминирующем множестве.

Лит.: Кönig D. Theorie der endlichen und unendlichen Graphen. N. Y., 1950; Берж К. Теория графов и ее применение. М., 1962; Зыков А. А. Теория конечных графов. Новосиб., 1969; Харари Ф. Теория графов. М., 1973; Басакер Р., Саати Т. Конечные графы и сети. М., 1974; Камерон П., Линт Д. Теория графов, теория кодирования и блок-схемы. М., 1980; Оре О. Теория графов. 2-е изд. М., 1980; Цветкович Д., Дуб М., Закс Х. Спектры графов. Теория и применение. К., 1984; Сачков В. Н., Тараканов В. Е. Комбинаторика неотрицательных матриц. М., 2000; Колчин В. Ф. Случайные графы. 2-е изд. М., 2004; Сачков В. Н. Введение в комбинаторные методы дискретной математики. 2-е изд. М., 2004.