Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 43
Текст из файла (страница 43)
Пары (и, о) и (и, и) считаются одинаковыми лишь в том случае, когда и = о. Ориентированньия мультиграфом называется ориентированный псевдограф, не содержащий петель. Если в ориентированном псевдографе нет ни петель, ни кратных дуг, то он называется ориентированныи графом (или, короче, орграфом). Направленным гра- З 1.
Основные понятия теории графов 211 фом называется такой орграф, который не имеет симметричных пар ориентированных ребер (т.е. множество Х у направленного графа не может содержать одновременно и дугу (и, о), и противоположно направленную дугу с»и,и)). Пусть х = (и, и) дуга ориентированного псевдографа. Вершину и называют началом или начальной вершиной, а вершину о концом или конечной вершиной дуги х. В этом случае говорят также, что дуга х исходит из вершины и и заходит в вершину о. Если вершина о является началом или концом дуги х, то говорят, что и и х инцидентны. Нолустеленью исхода вершины о псевдографа С называется число дуг псевдографа С, исходящих из вершины о. Полустепень исхода вершины о обозначается через од(о) или д»(о).
Аналогично полу- степенью захода вершины о (обозначения: Ы (о) и с1 (о)) павывается число дуг псевдографае заходящих в вершину о. Заменяя каждук» упорядоченную пару (и, о) из набора Х ориентированного псевдографа С(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. Доказать, что если полустепень исхода каждой вершины ориентированного псевдографа положительна, то в нем существует ориентированный цикл. (Петля считается ориентированным циклом длины 1.) 1.47.
Пусть орграф С (без петель и кратных дуг) является по меныпсй мере слабо связным. Пусть )г = (сы вг, ..., п„) — — множество его вершин (п > 2), Н' (с1) — с? (нз) = 1, 4+(сз) — с? (вг) = — 1, ем~'(в,) = сз (р,) при у = 3, ..., п. Доказать, что в орграфе С существует ориентированная (ны сг)-цепь, содержащая все его дуги. 214 Га. 11 Графы и сети 1.48.
1) Доказать, что ориентированный псевдограф, имеющий не менее 2 вершин, сильно связен тогда и только тогда, когда в нем существует ориентированный остовный замкнутый маршрут. 2) Можно ли в приведенном утверждении заменить замкнутый маршрут циклом'? 1.49. Доказать, что слабо связный псевдограф является сильно связным тогда и только тогда,, когда в нем существует ориентированный замкнутый маршрут, содержащий каждую дугу псевдографа хотя бы один раз.
1. 50. Пусть ориентированный псевдограф С можно представить в виде объединения некоторых его ориентированных замкнутых маршрутов Мы Мз,..., Ма (Й > 1), удовлетворяющих условию: каждые два соседних маршрута М и Мсы (1 ( ф ( й — 1) имеют хотя бы одну общую вершину. Показать, что псевдограф С сильно связсн. 1.51. 1) Привести пример 7-вершинного орграфа без петель и кратных дуг, опровергающий следующее утверждение: если полу- степени исхода и захода любой вершины орграфа положительные и четные, то для каждой вершины орграфа найдется контур, содержащий ее. 2) Показать, что орграфа без петель и кратных дуг, имеющего менее 7 вершин и опровергающего приведенное выше утверждение, не существует.
1.52. Доказать, что в конденсации С* произвольного ориентированного псевдографа С контуры отсутствуют. 1.53. Доказатгь что если ориентированный псевдограф С нс является сильно связным, то он будет односторонним тогда и только тогда, когда его конденсация С* имеет ориентированную остовную цепь. 1.54. Бескантурнььи ориентированным мультиграфом называется мультиграф, не содержащий контуров. Доказатгч что в бесконтурном ориентированном мультиграфе существует вершина с нулевой полустопонью исхода. 1.55. Доказать, что ориентированный псевдограф изоморфен своей конденсации тогда и только тогда, когда он является бесконтурным орграфом (не имеющим петель и кратных дуг).
1.56. Пусть С слабо связный ориентированный псевдограф, не являющийся односторонним. Доказать, что в С не существует такой вершины, удаление которой дает сильно связный псевдограф. 1.57. Доказать, что слабо связный орграф является растущим деревом тогда и только тогда, когда лишь одна его вершина имеет нулевую полустепень захода, а полустепень захода любой из остальных верьтин равна 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
