В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич - Лекции по теории графов (1083735), страница 54
Текст из файла (страница 54)
Таким образом, доказана Т е о р е м а 67.1. Подмножество вершин В орграфа является базой тогда и только тогда, когда В состоит из вершш*, принадлежащих базовым компонент м, причем в каждую базовую компоненту входит ровно одна вершина из В. 299 Понятие ядра для ориентированных графов вводится так же, как и для неориентированных. Мнохоество Я вершин орграфа С называется доминирующим, если для любой вершины и~ УС~Я существует такая вершина е = Я, что (о, ю)с АС. Напомним, что мноноество Я называется независимым, если никакие две о~ щ Рис.
97А Рис. 67.2 вершины из Я не смежны. Множество вершин Я, являющееся одновременно и независимым, и доминирующим, называется ядром орграфа. Орграф, изображенный на рис. 67.1, имеет два ядра: В~ = (он оз)ю о2 = (о2, о4). Не в каждом орграфе есть ядро, в чем нетрудно убедиться, рассмотрев орграф, изображенный на рис. 67.2. Рассмотрим одно достаточное условие существования ядра. Теорема 67.2. Каждый орграф, не имеющий яонтурое нечетной длины, обладает ядром. с. Пусть С вЂ” орграф, в котором нет контуров нечетной длины. Для любого подмножества вершин Ит — УС положим Г(РУ) = () Г(ю)' Ит. Определим рекуррентно две системы подмножеств Во, Вь Вм ...
и Уо, Ун Ум ... мнояоества УС. В качестве Во возьмем любую из баз орграфа С и положим Уо Я~, У1 =Во О Г(Во). Пусть уже определены В; 1 и У,. В качестве Во возьмем какую-либо базу подграфа С< = С вЂ” Уь удовлетворяющую условию В, — Г(Г(В,,РУ,,), и положим У,+1= У,6В,0 Г(В1). 294 Покажем, что нужная база действительно существует.
Пусть  — база в С„содержащая вершину о Ф Ф Г(Г(В,-») »)»»»). Поскольку В»» — база в С, », то вершина»» достижима из какой-либо вершины в»= — В»», и в графе 6, » существует (ю, в)-путь Ь (рис. 67.3). Этот путь содержит по меньшей мере по одной вершине из вь, ги»,~ Ю Рве. 67.3 Г(В»») и из Г(Г(В, »)»У» 1). Пусть и — последняя вершина пути Ь, принадлея»ащая можеству Г(Г(В, »)»»»»). Тогда все вершины, достия»имые из вершины и, достижимы и из и, т. е. В' =(В~о)0 и — также база. Будем проводить такие замены вершин до тех пор, пока не получим нужную базу В».
Поскольку Го = Г» с ... = Г» ~ Г»+» ~ ... и множество УС конечно, то для некоторого индекса и» верно равенство Р = РС. Положим () В»=В »аз и покажем, что Я вЂ” ядро орграфа С. Из построения множества Я вытекает, что оно доминирующее, ибо если оФ Ф Я, то»» ы Г(В„) Ю„для некоторого индекса й. Осталось показать, что множество Я неаависимо. Пусть, напротив, в Я есть две смежные вершины и и э, и аз Вт, о»н В,. Так как в базе смежных вершин нет, то р т'-- »7. Будем считать, что р ( д.
Из правила построения множеств В, следует, что (и, о)ФАС, (о, и)= — А6. По этой же причине существует путь Е = (хр» др» хр».\» др+»» ° .» х»-»» д»»» х»» в) 295 (рис. 67.4), где х, = и, х> — = Вь у> ш Г(В;) Ю> () = р, д — 1) . Из минимальности базы В, следует равенство и = л .
Но тогда путь Ь оказывается контуром нечетной длины, что зр Г(брдм 6 Г(6 ) Ч В, Г(6 )'Чо, 6 Рнс. 67.4 противоречит условию теоремы. Тем самым доказана независимость множества о'. Итак, множество Я являетсн независимым и домииирующим одновременно, т. е. Я вЂ” ядро. < У П Р А )К Н Е Н И Я 1. Докажите теоремы 65Л и 65.2. 2. Покажите, что в орграфе без контуров всегда есть вершина с нулевой полустепенью захода и вершина с нулевой полустепепью исхода. 3. Декан<кто, что пара векторов (3>, 2) и( 3, 2>, 1) является графической, и постройте ее реализацию. 4.
Постройте ориентированный граф, длк которого вектор (3', 2') лвлеетск как списком полустепеней исхода вершин, так и списком полустепеней захода вершин. 5. Докажите, что следующие свопства орграфа 6 эквивалентны; 1) 6 — бесконтурный граф; 2) граф 6 н его конденсация 6* изоморфны; 3) каждый маршрут орграфа 6 является путем; 4) вершины орграфа 6 можно упорядочить так, что его матрица смежности будет верхней треугольной матрицсй.
6, Полустепень исхода вершины турнира называется количеством очесе вершины. Докажите, что в любом турнире расстояние от вгршппы с максимальным количеством очков до любой другой верпшны равно 1 или 2. 7. Докажите, что в транэнтивном турнире существует ровно один гамильтонов путь.
8. Докажите, что ребра л>об>ого неориентированного графа мол<- ко так ориентировать, что в полученном орграфе ~>Г>(и) — 3-(и)) ( ( 1 для л>обой вершины ю 9. Покажите, что любой турнир либо явлкетсл сильным, либо может быть превращен в сильный сменой ориентации только однон дуги, 296 10. Докажите, что неориентированный граф С является основанием некоторого сильного орграфа тогда и только тогда, когда С связен и не имеет мостов. 11. Трангигивныи гаяыканиги срграфа С называется орграф С, для которого РС = )гС, а (и, и) ш АС тогда и только тогда, когда в орграфе 6 вершина и достижима из и.
Трангитивная редукция орграфа 6 определяется как орграф с наименьшим числом дуг, траизитивпое аамыкапие которого совпадает с трапзитнвпым аамыьаннем орграфа 6. Покажите, что если орграф пе имеет контуров, то его трапзнтивная редукция единственна. 12, Пусть С вЂ” орграф без петель с и вершинами и т дугами. Докажите, что если 6 является связным но не сильным орграфом, то и — 1 < т < (и — 1)г, а если 6 — сильный орграф, то п < < т < п(н — 1). 13 Докажите, что в орграфе порядка п, для любых двух несмежных вершин и и и которого верно неравенство б(и) + д(и) ) ) 2п — 3, существует гамильтонов путь.
14. Орграф Ь(6), вершины которого соответствугот дугам орграфа 6 н (и, и) шАД(6) тогда и только тогда, когда соответствуюгдне дуги порождают в С маршрут, называется ргбгрным орграФом. Выразите число вершин и число дуг ребсрного орграфа й(6) через аналогичные параметры орграфа С. 15. 1(елочислепная функция у(и) ) О, и ш )гС, называетсн угункцигй Гранди орграфа 6, если для любой вершины и значение у(и) совпадает с минимальным из тех неотрицательных целых чисел, которые не принадлежат множеству (у(и): и ш Г(и)). Покажите, что если каждый подграф орграфа С обладает ядром, то существует функция Грапди орграфа 6. Глава Х1 Гиперграфъг Гиперграф — это такое обобщение простого графа, когда ребрами могут быть не только двухэлементные, но и любые подмножества вершин. Подобные объекты в математике известны давно, однако введение термина «гиперграфе связано с успешным распространением на них ряда важных понятий и методов теории графов. Отметим, что понятиями, близкими понятию «гиперграф», являются понятия сети (см.
]32]) и блок-схемы (см. ]30]). Матроиды, которым посвящена гл. П1, представляют собой специальный класс гиперграфов. 5 68. Основные определения и свойства Пусть У вЂ” конечное непустое множество, д' — некоторое семейство непустых (необязательно различных) подмножеств множества У. Пара (У, ю) называется гиперграфом с множеством вершин У и множеством ребер Ю. Заметим, что матроид естественно рассматривать как гиперграф, ребрами которого служат циклы этого матроида и только они. Свободный матроид превращается при этом в пустой, т.
е. не имеющий ребер гиперграф. Тривиальный матроид оказывается гиперграфом, ребра которого — все одноэлементные подмножества вершин. Равные подмножества в Ю называются кратными ребрами гиперграфа. Множество вершин и семейство ребер гиперграфа П обозначаются символами УН и го Н соответственно. Число ]УН] вершин гиперграфа Н называется его порядкам и обозначается через ]Н].
Если ]10 = и, 'коН] = т (с учетом кратности ребер), то Н называется (и, т)-гиперграгбом. Если вершина о я У принадлежит ребру в е ю, то будем говорить, что они инуидентны. Каждой вершине о ш У гиперграфа Н сопоставим множество ю (о) всех лихи а цидентных ей ребер. Число (В'(и) ) называется степенью вершины и, а ~е) — степенью ребра е.
Поскольку ребрами гиперграфа могут быть лишь непустые подмножества вершин, то степень любого ребра не меньше единицы, т. е. ~е~ ~ з. Вершина гиперграфа, не инцидентная никакому ребру, называется изолированной. Две вершины с и и гиперграфа Н назовем смежными, если существует ребро е = ЖН, которое содержит обе эти О' Рис. 688 вершины. Два ребра е' и е" гиперграфа Н назовем смелсными, если е' П е" ~ И, На рисунке ребро е удобно изображать сплошной линией, окружающей все вершины иа е, если !е! ) 2 или !е~ = 1. Если же !е! = 2, то такое ребро е будем изображать линией, соединяющей две вершины этого ребра, как и в случае обычных графов.
На рис. 68.1 изображен гиперграф с множеством вершин У= Ьи из, ..., сд) и множеством ребер ас = (ез = Ьь из, сз), ез —— Ьз, са, из, са), ез = Ьа, сн сз), еа = Ьз, из), ез = Ьд), еа = ЬаН. Если в гнперграфе Н нет кратных ребер и степень любого ребра е равна Ь (~е~ = Ь), то гиперграф Н называется Ь-однорсдным (Ь-униформным). Ясно, что всякий простой граф является 2-однородным гиперграфом. Тем самым граф — частный случай гиперграфа. Любому (и, лз)-гиперграфу Н=(зт, 8') без изолированных вершин можно сопоставить (яз, п)-гиперграф Н* = (зт*, с'*), в котором Гв = ас, а ас * — семейство всех множеств ас (с), о = — зт. Гиперграф Н" называется двойственным к Н. На рис. 68.2 изображен гиперграф, двойственный к гиперграфу рис.
68 з. Очевидно, что (Н*)в =Н для любого гиперграфа Н, не имеющего изолированных вершин. 299 Для любого гиперграфа Н =(зг, Ю) определим граф инциденций — двудольный граф К(11) с множеством вершин уз 6 д' и множеством ребер ((и, е):(и, е)гн Р Х й, и е), Граф К(Н) называется кенигоеым представлением гиперграфа Н. На рнс. 68.3 изображено кенигово представление К(Н) гиперграфа Н, приведенного на рис.
68.1. ез ег Ь« Р с. 66.6 Рвс. 66.2 Очевидно, что К(Не) получается из К(Н) лишь переменой множеств»з и д местами, причем все ребра сохраняются; таким образом, К(Н*) ~ К(Н). В гиперграфе Н =()з, «з ) цепью длины 1 ~ 0 или (ип ип~)-цепью называется такая последовательность иь еь из, ез, ..., еь и,«ь что: 1) все вершины иь из, ..., и,„ь кроме, возмоя«но, крайних, различны; 2) ен ем ..., ез — различные ребра Н; 3) и„и,«з ~ е, для любого з = 1, й Здесь н далее под различными ребрами гиперграфа Н подразумеваются различные члены семейства ЖН (как подмножества онп могут совпадать; например, на рис. 68.4 е~ и ез — различные ребра).
Еслв 1) 1 и ипз = иь то цепь называется циклом. Заметим, что для соответствующих понятий графа мы добавили слово «простой» (простой цикл, простая цепь). 1!а рнс. 68.4 из, ез, из, е«, ип ез, из и ип еь им ез, из— цепи, а из, еь и«, ез, ин е«, из, ез, из и иь еь из, е-„из, е«, ин ез, и«, еи и~ — циклы. Очевидно, что существует оиекция между цепями (циклами) гипорграфа П =-(»', го) и простыми цепями (простыми циклами) его кенигова представления, концы которых принадлежат мнол«еству Зг.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
