Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 42

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 42)

Среди пар графов, изображенных на рис. 6.1 — 6.5, указать пары изоморфных и пары неизоморфных графов. Ответ обосновать. Рис. 6.2 Рис, 6.1 Рис. 6.3 Рис. 6.5 Рис. 6.4 1.35. Ц Пусть С и Н не имеют петель и кратных ребер, являются двухсвязными, содержат по 6 вершин и по 8 ребер. Пусть, кроме того, граф С имеет ровно 2 вершины степени 2, а граф Н ровно 4 вершины степени 3. Изоморфны ли графы С и Н? 2) Известно, что 6-вершинные графы С и Н не имеют петель и кратных ребер, двухсвязны, содержат по 10 ребер и удовлетворяют следующему условию: степень одной вершины в каждом из них равна 4 (1 < 4 < 5), а степени всех остальных вершин равны 4з (дз < е?з). Показать, что графы С и Н изоморфны.

1.36. Выяснить, существуют ли в графах, изображенных на рис. 6.6, подграфы, гомеоморфные графу С: 14 Г. П. Гаврилов, А. А. Сапоженко 210 Гл. Ъ7. Графы и сети Рис. 6.6 Рис. 6.7 Ц С = Кл (рис. 6.7,а); 2) С = Кв (рис. 6.7,б); 3) С = Кзз (рис. 6.7, в). 1.37.

Пусть и нечетное число, не меньшее 3, и В," подмножество всех вершин куба В", имеющих вес й (см, гл, 1, з Ц. Пусть ф— — подграф куба В", порожденный множеством В"„ь 0 Э Вь (ит1~/я' Ц Построить по одному совершенному паросочетанию в графах Сз и Св. 2) Показать, что в графе Ст существует совершенное паросочетание. 1.38. Ц Привести пример связного однородного графа степени 4, не имеющего петель и кратных ребер и не содержащего остовного простого цикла.

2) Локазатгь что всякий однородный псевдограф степени 4 можно представить в виде объединения двух реберно непересекающихся 2-факторов. 2. Ориентированные графы. Ориенпеированный псевдогуаф С = С('г; Х) определяется непустым (конечным) множеством г' и набором Х упорядоченных пар элементов из 1с. Элементы множества )г называются вершинами, а элементы набора Х дугами (или ориентированными ребрами) ориентированного псевдографа С(г; Х).

В наборе Х могут встречаться пары вида (и, и), называемые петлями, и одинаковые пары, называемые кратными (или параллельными) дугами. Пары (и, о) и (и, и) считаются одинаковыми лишь в том случае, когда и = о. Ориентированным мультиграфом называется ориентированный псевдограф, не содержащий петель. Если в ориентированном псевдографе нет ни петель, ни кратных дуг, то он называется ориентированныи графом (или, короче, орграфом). Направленным гра- З'1. Основные понятия теории графов 211 фом называется такой орграф, который не имеет симметричных пар ориентированных ребер (т.е.

множество Х у направленного графа не может содержать одновременно и дугу (и, о), и противоположно направленную дугу с»и,и)). Пусть х = (и, и) дуга ориентированного псевдографа. Вершину и называют началом или начальной вершиной, а вершину о концом или конечной вершиной дуги х. В этом случае говорят также, что дуга х исходит из вершины и и заходит в вершину о. Если вершина о является началом или концом дуги х, то говорят, что и и х инцидентны.

Нолустеленью исхода вершины о псевдографа С называется число дуг псевдографа С, исходящих из вершины о. Полустепень исхода вершины о обозначается через од(о) или д»(о). Аналогично полу- степенью захода вершины о (обозначения: Ы (о) и с1 (о)) павывается число дуг псевдографае заходящих в вершину о. Заменяя каждук» упорядоченную пару (и, о) из набора Х ориентированного псевдографа С(1», Х) неупорядоченной парой Ги, о), состоящей из тех же элементов и и о, получаем псевдограф Н = (Ъ; Х"), ассоциированный с ориентированным псевдографом С(Ъ", Х). Ориентированные псевдографы С»Я, Х») и Сз()з, Хз) называются изоморфными., если существуют два таких взаимно однозначных соответствия ун Ъ» +» 7~ и уч Х» е» Хз, что для всякои дуги х = (и, о) е Х» справедливо соотношение ф(х) = (у»(и), у»(о)).

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

..., х„з, о„ы х„ы и„(г» > 2) удовлетворяла условию: каждая дуга х, (1 < 1 < и — 1) имеет вид (о,, оь»»), т.е. вершина о, являотся началом дуги х„а вершина оьы . ее концом. Считается, что ориентированный (и., о)-маршрут ориентирован от своей первой вершины а, к своей последней вершине о. Длиной маршрута называешься число дуг в нем. Расстоянием р(и, о) от вершины и до вершины о называется длина кратчайшего (и, о)-маршрута. Ориентированный маршрут называется путем., а ориентированный простой цикл нонн»у1»ом. Ориентированная простая остовная цепь называется еамилыпоновым путем (или гамильтоновой цепью). Гамильтоновым контуром называется остовный контур ориентированного пссвдографа.

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

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

Аналогично односторонняя компонента првдставляет собой «максимальный» (по включению) односторонний пссвдограф-подграф псевдографа С, а слабая компоненгпа «максимальный» (по включению) слабый пссвдограф-подграф в С. Пусть у = ~Яы Яз,..., Яи) -- множество всех сильных компонент ориентированного псевдографа С. Кон<)внсаиией С* ориентированного псевдографа С называется такой орграф (без петель и кратных дуг), у которого множеством вершин является множество у, а дуга (Яп Я ) присутствует в орграфе С" тогда и только тогда, когда в псевдографе С существует хотя бы одна дуга, исходящая из некоторой вершины компоненты Я, и заходящая в какую-нибудь вершину компоненты Я, (1 у: )).

Если С = С(1с., Х) -" ориентированный пссвдограф, то обратный к нему ориенгппрованный псевдограф С' задается тгм же множеством вершин Ъ" и таким множеством дуг Х', что дуга (и, о) принадлежит Х' тогда и только тогда, когда дуга (и, и) принадлежит Х. Воршина о орионтированного псевдографа С называется ишпочником, если из нее достижима любая другая вершина псевдографа С.

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

в1. Основные понятом теорин графов 213 1.39. Построить все попарно неизоморфные орграфы (без петель и кратных дуг), содержащие: 1) 3 вершины и 3 дуги, 2) 3 вершины и 4 дуги; 3) 4 вершины и 3 дуги. Сколько среди них сильно связных, односторонне связных и слабо связных? 1.40. Изобразить все попарно неизоморфные ориентированные псевдографы, содержащие: 1) 2 вершины и 2 дуги; 2) 2 вершины и 3 дуги; 3) 3 вершины и 2 дуги. Сколько среди них сильно связных, односторонне связных и слабо связных? 1А1. Построить все попарно неизоморфные направленные графы, имеющие: 1) 3 вершины и хотя бы одну дугу; 2) 4 вершины и 4 дуги; 3) 5 вершин и 3 дуги.

Сколько среди них сильно связных, односторонне связных и слабо связных? 1.42. Построить все попарно неизоморфные турниры с; 1) 3 вершинами; 2) 4 вершинами. Сколько среци них сильно связных, односторонне связных и слабо связных? 1АЗ. Изобразить все попарно неизоморфные турниры с 5 вершинами, содержащие вершину с нулевой полустепенью захода и вершину с нулевой полустепенью исхода.

Для каждого из них построить конденсацию. 1.44. Построить все попарно неизоморфные растущие деревья с: 1) 4 вершинами; 2) 5 вершинами; 3) б вершинами, не содержащие ориентированных цепей длины, превосходящей 3. 1.45. 1) Доказать, что в и-вершинном (и, > 3) сильно связном орграфе (без петель и кратных дуг) число дуг (обозначим его через т) удовлетворяет неравенствам и < ш < п(н — 1). 2) Доказатгн что в и-вершинном (и > 2) слабо связном орграфе (без петель и кратных дуг), не являющемся сильно связным, число дуг (обозначим его через ш) удовлетворяет неравенствам п — 1 < гп < (и — 1)з. 1.46. Доказать, что если полустепень исхода каждой вершины ориентированного псевдографа положительна, то в нем существует ориентированный цикл.

Характеристики

Список файлов книги