В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 2
Текст из файла (страница 2)
Однако этот результат более ста лет оставался единственным результатом теории графов. Лишь в середине Х1Х века инженер-электрик Г. Кирхгоф разработал теорию деревьев для исследования электрических цепей, а математик Л. Кали в связи с описанием строения углеводородов решил перечислительные задачи для трех типов деревьев. К этому не периоду относится появление знаменитой пробчемы четырех красок. Родившись яри решении головоломок и занимательных игр (задачи о шахматпом коне, о ферзях, вкругосветное яутешествиез, аадачи о свадьбах и гаремах и т. п.), теория графов стала в настоящее время простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем.
Графы буквально вездесущи. В виде графов мо~кпо, например, интерпретировать схемы дорог и электрические цепи, географические карты и молекулы химических соединений, связи между людьми и группами людей. За последние три десятилетия теория графов превратилась в один из наиболее бурно развивающихся разделов математики. Это вызвано запросами стремительно расширяющейся области приложений. В теоретико-графовых терминах формулируется большое число задач, связанных с дискретными объектами. Такие задачи воз- пикают при проектировании интегральных схем и схем управления, при исследовании автоматов, логических цепей, блок-схем программ, в экономике и статистике, химии и биологии, в теории расписаний и дискретной оптимизации.
Таким образом, теория графов становится одной из существепных частей математического аппарата кибернетики, языком дискретной математики. В значительной степени через теорию графов происходит ныне проникновение математических методов в науку и технику. Все это привело к тому, что теория графов появилась и в учебных планах наших университетов и технических вузов. Глава л Начальные понятия 5 $. Определение графа Термин аграф» впервые появился в книге выдающегося венгерского математика Д. Кенига в 1936 г., хотя начальные задачи теории графов восходят еще к Эйлеру (Х'1т»П в.).
Пусть )л — непустое множество, Р" — множество всех его двухэлементных подмножеств. Пара ()т, Е), где Е— произвольное подмяв»кество множества )ты', называется графом (неориентированным зрафом), В этой книге рассматриваются только конечные графы, т. е. мноялество )т предполагается конечным, хотя в определении графа конечность этого множества не требуется. Элементы множества )т пазыва»отся вершиналш графа, а элементы множества Š— ребрал»и.
Итак, граф— это конечное мнон ество )т вершин и множество Е ребер, Е ж Р'. Множества вершин и ребер графа С обозначаются символами ИС и ЕС соответственно. Вершины и ребра графа называются его элементами. Число ~ )тС) вершин графа С называется его порядком и обозначается через )С!.
Если )С) = и, )ЕС) = т, то С называ1от (и, т)-графом. Говорят, что две вершины и и о графа смежны, если множество (и, о) является ребром, и не сллежны в противном случае. Если е = (и, о) — ребро, то вершины и и о называют его концами. В этой ситуации говорят также, что ребро е соединяет вершины и и и. Такое ребро обозначается символом ио. Два ребра называются смежнылш, если они имеют общий конец. Вершина о и ребро е называются инцидентными, если о является концом ребра е (т. е. е = ии), и не инцидентными в противном случае.
Заметим, что смежность есть отношение между однородными элементами графа, тогда как инцидентность является отношением между разнородными элементами. Множество всех вершин графа 6, смежных с некоторой вершиной о, называется окружением вершины о и обозначается через Ус(о) или просто Х(о). Графы удобно изображать в виде рисунков, состоящих нз точек и линий, соединяющих некоторые нз этих точек. Прн этом точки соответствуют вершинам графа, а соединяющие пары точек липин — ребрам.
В качестве иллюстрации рассмотрим граф 6, изображенный на рпс. 1.1. Это (5, 6)-граф, )т6 = (1, 2, 3, 4, 5), Е6 = ((1, 2), (1, 5), (2, 3), (2, 4), (2, 5), (4, 5)). Вершины 1 п 2 ~ ~лАЙ Рис. 1.1 Рис. 1.2 смежны, а '1 и 3 не смежны. Вершина 1 и ребро (1, 2) нпцндептяы. У(2)= (1, 3, 4, 5). Приведем примеры некоторых графов специального вида, Граф 6 называется полным, если любые дзе его вершины смежны, т. е, Е6 =()т6)'".
Полный граф порядка и обозначается символом К, число ребер в нем равно (" =- к (п — 1) На рнс. 1.2 изображены графы К„, п -.- 5. Граф называется пустым, если в нем нет ребер. Пустоп граф порядка п обозначается через 0„. Па рпс, 1.3 показаны простые циклы С„(п = 3, 4) и простые цепи Р„(п = 2, 3, 4). Очевидно, что Кз = Рм Рис. 1.4 а Кз = Сз На рис. 1.4 приведены два изображения про- стого цикла Сз На рис. 1.5 изображены колеса И'„(и = 3, 4, 5). Заметим, что И» К4 и ~И ~ =и+ 1. На рис.
1.6 изображен граф Петерсена. Красивыми примерами являются графы пяти платоновых тел (т. е. правильных многогранников): тетраэдра, куба, октаэдра, додекаэдра, икосаэдра (рис. 1.7). Ниже неоднократно используются термины вразбиение» и «покрытие». Набор подмножеств множества Я называется покрытием множества Я, если объединение этих Рве. 1.6 Рис. 1.6 подмножеств совпадает с Я. Покрытие называется разбиением, если никакие два из входящих в него подмножеств не пересекаются.
Граф называется двудольным, если существует такое разбиение множества его вершин на две части (доли), что концы каждого ребра принадлежат разным частям. Если при этом любые две вершины, входящие в разные доли, смежны, то граф называется полным двудольным. Полный двудольный граф, доли которого состоят из р и из д вершин, обозначается символом К„,. При р = 1 получаем звезду Кит Очевидно, что К~ ~ = К» = Рп К~ » = =Рэ, Ка»=С» На рис. 1.8 изображены звезда К~э и полный двудольный граф К»,».
Заметим, что одна из долей двудольного графа может быть пустой. Так, О~ — двудольный граф с одной пустой долей, О» можно трактовать как двудольный граф с двумя одновершинными долями или как двудольный граф, одна из долей которого содержит две вершины, а другая является пустым множеством. Аналогично двудольным определяются й-дальный н полный й-дельный графы для й=3, 4, ... На рис. 1.9 приведен трехдольный граф.
Легко подсчитать число всех графов с фиксированным множеством вершин 1т. Эти графы различаются своими ребрами, и потому их число равно количеству подмножеств в )т, т. е. 2, где и =!И. Однако эти графы (и) 11 не всегда следует различать. Как в применениях теории графов, так и в самой этой теории чаще существенно лишь то, что есть объекты (вершины графа) и связи между объектами (ребрами). С этих позиций графы, которые получаются один из другого изменением наименований вершин, разумно пе различать. Оформим эти соображения в виде следующего определения. Пусть С н Н вЂ” графы, а ~р; РС РН вЂ” бнекцня.
Если для любых вершин и и и графа С их образы ~9(и) Рвс. 09 Рвс. 08 и ~р(и) смежны в Н тогда и только тогда, когда и и а смежны в С, то зта биекция называется изоморфизмом графа С на граф Н. Если такой изоморфизм существует, то мы пишем С = — Н (тогда и Н вЂ” = С) и говорим, что графы С и Н изоморфны. Например, трн графа, представленные на ряс. 1.10, изоморфны (почему?), а графы на рис. 1.11 не изоморфны (почему?). Вопрос о том, изоморфпы ли два данных Рас. 1ЛО графа, в общем случае оказывается сложным (см., например, [18] ).
Очевидно, что отношение изоморфизма графов является эквивалентностью, т. е. оно симметрично, транзитивно и рефлексивно. Следовательно, миан<естес всех графов разбивается на классы так, что графы из одного класса попарно изоморфны, а графы из разных классов не изоморфпы. Изоморфные графы естественно отождествлять, т. е. считать совпадающими (их можно изобразить одним рисунком). Они могли бы различаться конк- тЗ ротной природой своих элементов, но именно это игнорируется при введении понятия «граф».
В некоторых ситуациях все же приходится различать изоморфные графы, и тогда полезно понятие «помеченный граф». Граф порядка п называется помеченным, если его вершинам присвоены некоторые метки, например, номера 1, 2, ..., п. Отождествив кан«дую из вершин графа с ее номером (и, следовательно, множество вершин — с множеством чисел (1, 2, ..., и!), определим Рис. бИ равенство помеченных графов 6 и Н одного и того же порядка: 6 = П тогда, когда Е6 = ВН. На рис. 1.12 изображены три разных помеченных графа.
При необходимости подчеркнуть, что рассматриваемые графы различаются лишь с точностью до изоморфизма, говорят; «абстрактный граф». Строго говоря, аб- Л Л л Рве. б!2 страптпый (или непомеченный) граф — это класс изоморфных графов. Число д„непомеченных графов порядка п определяется сложно. Известна формула Лойа е -2 (и!, (".) /, дающая асимптотику числа д . Эта формула означает, что две функции е(п) = д и ~(п) = 2 ! и)асимитотиче- (.")(, еки равны, т.
е. !!ш д(п)>/(и) = 1 (см. книгу [29], где излагается целый ряд результатов, связанных с числом графов, имеющих те или иные предписанные свойства). 14 Как отмечалось выше, верно Утверждение 1.1. Число 1„помеченных графов ь) порядка и равно 2 ' . Итак, число помеченных графов порядка и «примерно» в и! раз больше числа непомеченных. Этот факт кажется интуитивно ясным: существует ровно п| пометок множества, состоящего из и вершин. Однако последнее отнюдь не означает, что из каждого непомеченного графа получается п1 помеченных.
Например, все пометки пустого графа приводят к одному и тому же помеченному графу; простая цепь Рг порождает трп, а пе шесть помеченных графов (рис. 1.12). Но все же, как правило, кая«дый непомеченный граф приводит к и! помеченным графам. Для произвольного графа С следугощим образом определяется дополнительный граф (или дополнение) С: ГС = РС, и любые две несовпадающие вершины Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
