В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 3
Текст из файла (страница 3)
К13 смежны в С тогда н только тогда, когда ояп пе смежны в С (рпс. 1.13). Очевидно, что С =- С и С == г7, если С са Н. Граф, изоморфный свое»гу дополнению, называется салюдополнительным, Например, Еь Р«и Сг — самодополнительяые графы. Самодополпительяые графы составляют важный, хотя и экзотический, класс графов, определенным образом связанный с проблемой распознавания изоморфизма графов (см., например, [18[ ) . Иногда приведенное выше определение графа оказывается недостаточным и приходится рассматривать более общие объекты, в которых две вершины могут соединяться более чем одним ребром.
Так возникает понятие «мультпграф». Мультиграф — это пара ()т, Е), где У вЂ” ыепустое множество (веригин), а Š— семейство пед- множеств множества 1»со (ребер). Употребление термина «семейство» вместо «множество» означает, что элементы множества (»оэ могут в Е повторяться, т.
е. допускаются кратные ребра, Дальнейшее обобщение состоит в том, что кроме кратных ребер допускаются еще петли, т. е. ребра, соединяющие вершину саму с собой. Псевдограф — это пара ()», Рис. 1.14 Е), где 1» — непустое множество (вершин), а Š— некоторое семейство неупорядоченных пар вершин (ребер), не обязательно различных. На рнс. 1.14 изображены мультиграф и псевдограф. Изучаются такясе ориентированные графы. Тогда множество Р'" двухэлементпых подмножеств заменяется декартовым квадратом )»-, состоящим из упорядоченных пар элементов множества )».
Итак, ориентированный Рвс. 1Л6 Рис. 1А5 граф (или орграф) — это пара ()», А), где 1» — множество вершин, А — множество ориентированных ребер, которые называются дугами, А — 1»г. Если а =(ип из)— дуга, то вершины и~ и вг называются ее началом и кон»1ом соответственно.
На рисунке дуги отмечаются стрелками, указывающими направление от начала к концу (см. рис. 1.15). Аналогично определяется ориентированный мультиграф (см. рис. 1.16). Рассматр»гваются также смешанные графы, у которых есть и дуги, и неориентированные ребра. Для всех этих видов графов естественно вводится понятие изоморфизма как бнекцни между множествами вершин, сохраняющей смежность, кратности ребер, петли и направления дуг. Графы в смысле нашего первого определения называются еще простыми (или обыкновенными). Хотя часто для теории несущественно, какие из этих видов графов (простые, мульти- или псевдо-) рассматриваются, однако главный персонаж втой книги — простой граф.
Ради сокращения речи термин «граф» употребляется и в других ситуациях (например, вместо «мультиграф» или «ориентированный граф»), но подобные случаи либо специально оговариваются, либо ясны из контекста. $ 2. Подграфы Граф Н называется подгра4ом (или частью) графа 6, если )1Н вЂ” '= ГС, ЕН вЂ” ЕС. Если Н вЂ” подграф графа 6, то говорят, что Н содержится в 6. Подграф Н называется остовным подгра4ол«(или фактором), если «Н = = т'6. Если множество вершин подграфа Н есть У, а множество его ребер совпадает с множеством всех ребер графа 6, оба конца которых принадлежат У, то Н 1 Р 1 У 5 я и Рнс. 2Л называется подграфом, порожденным (или индуиированным) множеством Н, и обозначается через 6(У). Па рис. 2.1 изобрансены граф 6 и три его подграфа Нп Нг и Н», среди которых Н» является остовным, а ͻ— порождеяным.
Рассматриваются также подграфы, порожденные множествами ребер. Для Е' — ЕС множество ребер порожденного подграсра 6(Е') совпадает с Е', а множество вершин — с множеством концов ребер из Е'. Важный класс подграфов составляют подграфы, полученные в результате удаления вершин. Пусть о — вершина графа 6. Граф 6„= С вЂ” о получается из графа С в результате удаления вершины о и всех инцидентных ей ребер. Очевидно, что С, = 6()тС~Р). На рис. 2.2 изо- В, А.
Ниеличев и ЛР. »7 бражен подграф 6 — 5, полученный из графа С, представленного на рис. 2.1, удалением вершины 5. С графами 6„связана знаменитая гипотеза реконструируемости Келли — Улама. Для каждой вершины и~ )'С построим подграф 6, = 6— — и. Систему (С„: иш )»6) всех таких подграфов назовем колодой графа С и обозначим через Р(6). Например, если С = Рз, то Р(С) = (Кз, 1 К,, О,)'. Пусть ~ 6 ~ = п.
Перенумеруем в произвольном порядке вершины графа С числами 1, 2, ..., п и выпишем графы, входящие в колоду Р(С): Р(С)=(С», Си ..., 6„), 6,=6 — », 1=1, и. Пусть теперь Н вЂ” еще один граф порядка и. Если существует такая нумерация вершин графа Н, при которой С» — = Н, (» = 1, п), то колоды Р(С) и Р(Н) называются равными: Р(6) = Р(Н).
Например, Р(Кз) = Р(О») = = (О„О»). Граф Н называется реконструкцией графа С, если Р(Н) = Р(6). Граф 6 называется реконструируемым, если он изоморфен каждой своей реконструкции. Пе все графы реконструируемы: Оз и Кз являются реконструкциями друг друга. Гипотеза Келли — Улама утверждает, что зто единственное исключение. Гипотеза реконструируем ости (П. 1(еллн, С. Улам, 1945 г.). Всв гра»1»ы порядка н ) 2 реконстр»1ируез»ы. Несмотря на простоту формулировки, вот уже более сорока лот проблема не поддаотся решению.
Любопытно и то, что пет единого л»не»»»»я об истинности илп ложности гипотезы. Подтверждена рекоиструнруемость графов порядка и для 3 - н ( 10. Известно, что если граф С реконструируем, то дополнительный граф С также реконструируем. Гипотезу Келли — Улама часто называют гипотезон вершинной реконструируемости, Наряду с ней для графов, имеющих более трех ребер, существует гипотеза Харари реберной реконструируемости (1964 г.). Ояа формулируется аналогично вершинной.
ио вместо вершины удаляется ребро: для ребра е графа С подграф С, = С— — е получается из 6 в результате удаления ребра е (кои- цы ребра не удаляются, т. е. С вЂ” е является вставным подграфом). Гипотеза реберной реконструируемости подтверждена для многих классов графов, В частности, известно, что (п, т)-граф реберно реконструируем, если т > п(п — 1)/4 (Л. Ловас, 1972 г.) или 2" ' > пг (В. Мюллер, 1977 г.).
Пусть Х вЂ” множество каких-либо элементов графа С. Аналогично подграфу С вЂ” и определяется подграф С— — Х: нз С удаляются все вершины н ребра, входящие в Х, и каждое ребро, хотя бы один конец которого принадлежит Х. Если, например, Х = (в, еь е»), то С вЂ” Х= =((С вЂ” и) — е;) — еъ Порядок удаляемых элементов иесуществен, поэтому мол«но писать просто С вЂ” Х = = С вЂ” и — е~ — е».
$ 3. Операции над графами Удаление верзнины или ребра, а также переход к подграфу — это операции, с помощью которых можно из имеющегося графа получать другие графы с меньшим числом элементов. Известны также операции, позволяющие, наоборот, получать из имеющихся графов «большие» графы. Такова, например, операция добавления Рис. 3.1 ребра: если вершины и и и графа С не смежны, то можно определить граф С+ е, где е = иш Он получается из графа С добавлением ребра е. Здесь рассматриваются другие операции над графами, нужные для дальнейшего изложения. Одной из наиболее вая«пых является операция объединения. Граф Н называется объединением (или наложением) графов Е и С, если УН= ЪЕ0 ИС и ЕН= = ЕЕ 0 ЕС (рис.
3.1) . В этой ситуации пишут Н = Е 0 С. Объединение Е 0 С называется дизъюпктпь»м, если ГЕ П й РС = 8. Аналогично определяются объединение и дизъюнкгпое объединение любого множества графов, причем в последнем случае никакие два из объединяемых. графов не должны иметь общих вершин.
2« 1Ф Пусть 6;=($'ь Е,) ((=1, 2) — два графа, Произведением 61 Х Сз = 6 называется граф, для которого ГС = = 'г'1 Х г"з — декартово произведение множеств вершин (1 Ц) (1 иг! (1 из! [ х д, 0,) (2 ог) и,,) Рис. 3.2 О помощью операции произведения вводится важный класс графов — и-мерные кубы. п-мерный куб ()„определяется рекуррентно: ()~ = Кю С„= Кз Х ~)„ь п ) 1. Очевидно, что () — граф порядка 2", вершины которого можно представить (О, 1)-векторами длины п таким образом, что две вершины будут смежны тогда и только (10, 1) (1,1,1) (01! (1,1) (0,0) (1,0) (1,0,0! (110) Рис.
3.3 тогда, когда соответствующие векторы различаются ров- но в одной координате. Поскольку каждая вершина и- 20 исходных графов, а ЕС зом: вершины (иь из) и да и только тогда, когда в Сю или из=оп а и1 Очевидно, что (С! Х 62! = !61! ' )62), определяется следующим обра(иь оз) сме;кны в графе 6 тогили и1 = гь а из и оз смежны и щ смежны в 61 (рис. 3.2). )Е(6|Х Сз) ! = = !61! )ЕСз! + )Сз! )Е61!. м ерного куба инцидентна и ребрам, то число его ребер равно п2" '. На рис.
3.3 представлены кубь1 1тг и ()з. Еще одна важная операция — отождествление (или .слияние) вершин. Пусть и и о — две вершины графа С, Н = 6 — и — ш К графу Н присоединим новую вершину .и', соединив ее ребром с каяхдой из вершин, входящих в объединение окружений. вершин и и и в графе 6. Говорят, что построенный граф получается из графа 6 отождествлением вершин и и ш Рассматривается также операция стягивания ребра. Стягивание ребра ии означает отождествление смежных вершин и и ш На рис. 3.4 показаны граф 6 и граф, полученный из 6 стягивапием ребра (4, 2). Граф 6 называется стя г г д 1' д аиваемым к зрафу Н, если Н Ркс. 3.4 получается из С в результате некоторой последовательности стягиваний ребер.
Легко видеть, например, что граф Петерсена стягиваем к Кг и, стало быть, к любому К„с п ( 5. Очевидно, что любой непустой связный граф, отличный от Кь стягиваем к Кг. По уже пе любой связный граф стягивается к графу Кз. Например, простая цепь Р пе стягивается к Кз. Естественно возникает параметр д(6) — максимум порядков полных графов, к которым стягивается граф 6. Параметр ц(6) называется числом Хадвигера графа 6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
