В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 34
Текст из файла (страница 34)
Ребра аида (а, о) называются лсгшизк Одинаковые пары в Х называются крагшзми (нлн параллельными) рсбрамн. Количество одинаковыя лар (а, ю) в Х называется «рагиаггзю ребра (о, ю). Про множесмю У и набор Х будем говорить, чтооии определяют ераф с кратными реб-1 лами и петлями (или лсеадгмраф) О= (У, Х). Псевдограф без петель из- 161 зывается графом с кратным» ребрамн (или мухзтизра()ам). Ес ли в наборе Х нн одна пара не встречаетсн более одного раза„ то му.зьтнграф б= (У, Х) называется эрифии Если пары в ва.
боре Х являипся упорядоченными,то граф называется ориенгиразаи«ым (кратка †арзраф). Ребра орграфа называются ду. эами. Если пары в наборе Х являются неупорядоченными, то граф называется «эоригигираааниым графом (яли просто графом). Ребра в неориентированном графе (в отличие от дуг в ор. графе) будем обозначать (а,ю). Неориентированные графы бу. дем обозначать буквой б илп б с индексами (например, бз, бз. .), а орграфы — буквой 0 нли О с нндексамн (например,бз, бь ..).
Кроме того, договоримся обозначать вершины буквами о, и,ю (без индексов нлн с индексами), а ребра н дуги †буква х, у, а (без индексов иля с иидеисами). Всюду далее будем соответствующую некоторому графу гео. метрическую конфигурацию, в которой вершины изображенм кружочкаии, а ребра — линиями, соединяющнмя соответствующие вершины, называть иаабражеиием этого графа. Прн изображении орграфа направления дуг будем отмечать стрелками„ прнмыкаюшимв к их концам. Пример 4.1.
Пусть У (зз, оз, оз, о,), Х=(хз=(ш, оз), хз=(оз, оз), хз=(оз, из), хз=(оз, аз)). Тогда б=(1', Х)— ориентированный псевдограф, изображение которого приведено на рис. 4.2. Промер 42. Пусть У=(оз, оэ, оз. оз, аз), Х=(хз=(оь оэ), хз=(оз. оз). Хз=(оз, оз), хз=(оз, оз)). ТогДа б (У, Х)— неорнентярованный граф (нлн просто граф), изображение которого дано на рис. 4.3. Рас.
4З зз ц — "аРас.4З ' 1; Приведеы ряд понятий и определений для орнеитироввнньш н неориентярованных графов. Там, где это не оговорено особо, те же понятия и определения переносятся без изменений на ориентированные н неорнентнрованные псевдографы. 4.1.1. Смажнасть, инцндевтность, степени Если х= (а, ю) †реб графа.
то вершины и, ю называются «оицами ребра х; в этом случае также говорят, что ребра х' соединяет вершины о,ю. Есин х= (о, ю) †ду орграфа, то вершина о называагсн началом, а вершина ю — концом дуги х; в атом случае гешке говорят, что дуга х исходит из вершины о я заходит в вершину ю.
1ЗЗ Всаи вершина о является концом (началом или концом) ребра дуги) х, то юворят, что о и х шщыдеигнвс $„ шниы о, ю графа 6 (У, Х) вазыьаюгсн смешимми, если (е. ш)аиХ. Двв ребра называются смежными, если они име. чот общую вершину. Стешшью вершины о графа 6 называется число б(о) ребер графа 6, инцндентпых вершине о. Вершина графа, имеющая степень О, называется изолироешиюй, а степень 1 — висячей. Замееаиие 4.1. В случае неорнентироваиною псевдографа обычио считается, что вклад каждой петли, ннцндентной некоторой вершине о, в б(о) равен 2 (тогда как вклад любого другого ра, инцндентною веригине о. равен 1).
омустеллною исхода (захода) вершным и орграфа () иззываешя число б+ (о) (б-(о)) дуг орграфа (), исходящих из вершины о (заходящих в вершину о). Эамачание 4.2 В случае ориентированного псевдографа вклад каждой петли, ннцндентной некоторой вершине о, равен 1, как в бг(о), так и в Ь-(о).
Пример 4.3. 1. 9 графе 6 (см, пример 4.2) концами ребра х, являются вершины иг, ое; вершниа ов иицядентна ребрам хг, хь хв! степень вершвйы о, равна 3. т. е. б(ос) =3; вершины аь оч смежные, ребра хь х, смежные; вершина о, висячая; вершина ов иэодяроваяная. 2. В ориентированном псевдографе (см. пример 4.1) дуга хг иск(щит мв вершинм оч и заходит в вершину оч; вершина ог ницндевтив дугам хч, хм хч, ха б+(ов) =2, б-(о,) =3. Количество вершин и ребер в графе 6 обозначам соответственно через п(6) н т (6), а количеспю вершин и дуг в орграфе Ю вЂ” через л(О) я ш(О). Умирмдмме4.( Д л лхбого ше дол Р б еы е и л л еечс б(о) вш(О).
(4.1) ешУ Равснсшо (4.1) гплвшсл очеввдвын слсдсгввеы того, ччо вклад ванного ребра в сумму вв левай чести (4.6 ранен 2. Приведем также соответствующее утверждение для орграфа. шмш ымв ал.д л аш ор юшл ю,ащ ( и «леши роев спш бч (о) ~ б- (о) ш (О) (4.2) ошУ ему Деевевчсльсгво (42) очевндво.
43.2. 2(аемарфизвь пгмееморфизм Графы 6ч (Уь Хг) и 6ч= (Ул. Хс) называются изоморфными, если существует биективное (взаимно однозначное) отображеиие чр)Уг-ь)'в. сохраняющее смежность, т. е, (о, ю)шХг«=ь .е:.(р(о), р(м))шде. Соответственно орграфы Вг=(Уь Хч) и (аэ Оэ= (Уь Хэ) называются изоморфными, если существует бнектнвное отображена р: Угь.рэ такое, что (о, ээ)шкас ь(р(о), П(ю))шХ2. (ч.3) Замечание 4.8.
Из определений слелует, что иэомарфв ..тра. фы (орграфы) отличаютс» лишь обозначением вершин. Приведем следующие очевидные свойства изоморфизма. 1) если графы 6,=(Уь Х|), 6,=()'э, Хэ) иэоморфпы н Э: Уг У» — биективпое отображение, сохраняющее сменцмкть, то: а) Уошу, б(о)=б(г?(о)); б) ш(6',) гн(6,), п(6э)= =п(6»); 2) если орграфы Р>=(Уь Х1), Оэ=(У», Хэ) изоморфггы и и: Уг-ьУэ — биективное отображение, удовлетворяющее (43), то: а) Уошр~ б'(о)=б+(П(о)), б-(и)=б (р(о)); б) ю(0)) =гл(0э), п(Ог)=л(Рэ). Замечание 4.4.
Для псевдографов определение взоморфйрмв несколько усложняется. Псевдогрзфы Ог (Уь Х1), Оэ= (Уэ, Хэ) называются изоморфными, если существуют два таких биебчивных отображения П:УсьУэ, ф:Хендэ, что Ух=(о, ы1(шХ, ф(х) =(гр(о), ф(ю)). это оаначает дополнительное требопарне на сохранение кратностей соответствующих ребер. Аналопгтдо ориентированные псышографы О1=(уь Х~), Оэ=(уэ, Хэ) иазываютск изоморфными, селя существуют такие бяепгрвнме отображения яы У~ Уг,,р: Х, Хэ, что ух=(о, ю) адХг ф(4)(— =(р() и( ))'. 1 Йетрудно показать эквивалентность прнведеняых опйедвэевий изоморфизма для случая, когда в Рь 6, (в Оь Р,) огрутствуют кратные ребра (дуги].
гн Пример 4я. Графы, изображенные нз ряк 43, а, б, нзомбрфны, но онн не нэоыорфиы графу, язображенному на рпс,4.4,а (почеэгу?). Отметим, что нзоморфнзм графов (орграфов) являетсп отношением эквивалентности на множестве графов (орграфрв). Операция лодразбизиил (кзиэлсчэнил) дрэи (и, о) в орграфе О= (У, Х) состоит в удалении иэ Х дуги (и, о), добавлении к У новой вершины ы н добавлении к Хэ((и, о)) двук дуг (и, ы), (ы, и). Аналогично определяется операции подраэбирпкя ребра в графах.
Орграф О, называется аэдразбиеииэл орграфа Рь ссди.орг граф О1 можно получить из Оэ путем последовательного применения операции подраэбиепяя дуг. Аналогично апределжтсв подразбиенве графа. ркс, 4,4 Пример 4.6. Граф, изображенный на рнс. 4.5, и, является подразбненнем графа, нэображеанош на рис. 4.5, б. Орграфы Рь Р, (графы Оь Оэ) называются голеоморфлылгг, если супгесгвуют их яолразбнения, явзяющиесн изоморфными. Пример 4.6. Графы, изображенные на рис. 4.5, гомеоморфны. 4Д.5. 6(аршруты, ну Введем попятив ларигррта для графа О= (Р, Х) (и соответственно понятие луги для орграфа Р=((г, Х)).
Последовательность пгхгсг~ Фз -«Ащы (4.4) (где Дрв!, пишК г=-1, ... й+1, хзчыХ, (=1, ..., й), в кошрог) чередуются вершины и ребра (дугй) и для каждого 1=1, ..., й ребро (луга) х, имеет вид (еи с,ег) ((с„озы]), называется маршрутом, соединяющим верпншы ог. оеы (путем нз ь, в оа.,). При этом о, назмвается начальной, сзы †«анечнсд вершинами маршрута (ггути) (4Я), а остальные вершины — внутренними Олва и та же вершина может одновременно оказаться начальной, конечной и внутренней.
Последовательность вершин в маршруте определяет нэ ребрах, входящих в маршрут, ориентацию. Заметим в этой связи, что ориентацию некоторого ребра х (о, ю) всегда можно указать при заяясн его как пары вершин. Например, запись (о, ю) указывает на то, что ребро к ориентировано от вершины о к вершине ю. Прныер 4.7. 1. Послеловательиосгь п,хгсехэо,х,о,— маршрут, соелнияюпгий вершины оь оэ в графе О (см. пример 42). 2. Последаватольпость пгхеогхзогхчоэ — путь из о, в ез в орнгнтпрованном псевдографе Р (см. нрггнер 4.1). Замечание 4.6.
Последовательность (4.4) можно однозначно восгеаноанть по вослелователыгосгн аглае.-хе (4.5) (еслн (4.4) — маршрут, предпшчагаегся, по в последовательности (4.5) дополнительно указывается ориентация ребер, определяемчя маргпрутом (4.4)], а следовательно. вместо (4.4) можно использовать более короткую запись (45).
Отметим далее, что в случае, когда в последовашльности (4.4) хь ..., х» имеют крзтноши, равные 1. ее можно однозначно восстановить по последовательности вершин о~с,...сэ „ (4.6) э следоазтельна, вместо (4 4) также можно использовать более коротную запись 14.6]. В общем случае вместо последовательности (4.4) можно использовать сокрашеввую последовательность, в которой опушены все хг кратности 1. ге Пример 4.8. 1. Последовательности шх,хо шюгю,ю,— сокращенные занков маршрута, врнвеленного в примере 4.7, п. 1. 2.
Последовательности х,хэхь шх юэогюэ — сокращенные за. пнсп пути, прпведеняого в прямере 4.7. п. 2. Пусть .с,хг...хь — маргпрут в графе б (см. замечаяне 4.3) н для некоторзб псслсдователыгостн номеров и, ..., 1„где г~1, 1(1,<й« м(4, хг,хг,...х! снова является маршрутом в графе Тв Тогла хг, хг, ...х, взвываете» лодллрглрртол маршру.
та х,хь..хь Пря этом будем пгворвть, что маршрут хг, л„...х! выделен яз ыаршрута хыь..хь Аналчогпчно определяется лодлрть, аьщеленный вз пути орграфа. Чнсло ребер (дуг) в маршруте (путя) яазываек» дляпоа маршрута (путя). Марпгрут (путь) (4.4) называется эллккугмм, еслл его на. чвльна» вершнпа совпадает с конечноя, т. е. если ю~=ю ы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
