В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 35
Текст из файла (страница 35)
Замечание 4.б. Далее всюду пря подсчете числа вхожденнб всршвп в замкнутый маргпрут (путь) начальную п конечнуш вершины будем счвтать за одно вхож!ение этой вергпнкм в маршрут (путь]. Злэгечллпе 4.7 Прн эамкпутом маршруте (путп) х х ...хь обычно считается, что последовательности х,хг...хз, хгх- ..хьп, ... ..., хэх,хь..хь- — раэлнчлые вэлнсн одншо н того же мзршруга (путп). Незамк!гугый маршрут (путь). в котором есе ребра (дугч) попарно разлвчны, называется цепью. 11епь, в котород лсе верпшны попарно различны, называется щшиой целио. Замкнутый маршрут (путь), в котором все ребра (лугп! пг парнп различны,навывасгся циклом (коктррюл).
Цикл (контур), в котором все еершяны попарно разлнчаы (см. замечанне е.б), ншывается простым. Пример 4.9. Рассмотрпм граф б яв примера 4.2. Тогда: 1) о х юэх,югх,юз — маршрут длины 3, соеднняшщнй сь ю; это простая цепь. так каь все ребра н вершнвы попарно различны; 2) юэк ю,хшчхзю — замннутый маршрут длины 3; зтп аростоп цвнл, так как все ребра н вершины поларис раамжны; 3) ю~х,юьс,ю,к,ю,х,юэ — маршрут длпны 4, соеднняшщнй вер.
пгнны о . юг; это цепь, которая не являегс» простой, так как вер. шина ог встречается дважды; 4) ю,хшгхэюзх,ю,— маршрут длнны 3, соеднняющнв вершины юь юэ н не являшщнбся келью, так кан ребро х,= (оэ, с.) встречается дважды. ПримеР 420. Рассмотрим орнснтнрованный пссвдограф (Г нв примера 4.1. Тогда: !) ю,хгюэх вэ — путь длины 2 пз ю~ в щ; это проста» дспь, так кзк все луги я вершины попарно разлнчны; 2) юэхгог — и!шсгсй контур длины 1; !48 3) п,х,о,х,отхют — цепь из о, в оь длины 3, которая не является простой.
Нетрудно показать, что в псевдографах, мультиграфах я графах минимальная длина просгого цикла равна соответственно 1, 2 и 3 (каковы минимальные длины простых контуров а ориентированных псевдографах,мультиграфах и графах?). Утверждение 4.3. д псевдозрафе 6 (в ориентированном пгевдогрифе О) из полного цикла (замкнутого пути) мгхюю выделить Шюгтод Пипл (простой контур). Доказательство будем провалить для 6 (для О доказательство аналогично) индукцней по й — количеству ребер в цикле. При й=! всякий цикл является простим. Пусть при некотором 3~2 доказываемое утвержденяе справедливо для любою цикла длины (й — 1. Поиажем его справедливость для праизаольнога циила м=и,хй..окхьа, длины м Рассмотрим любые два номера г, 1, где ! (1<)~й, такие, что ог=оь Если таких номеров нет, то ипил и являетс» простым (па определению).
если же указанные номера кашлись, та рассматриваем пикл огхь..оыат га, длины 1 — 1~3 — 1, а из него в силу индуктивного предйоложенпя можно выделить простой цикл. Утверждение 4.4. Из всякого незамкнутого маршрута (пути) можно выделить простую цепь с теми же напольной и конечной вершинами. Доказательство будем проводить для маршрута (дли пути доказательство аналогично) индукцией по й — количеству ребер в маршруте. При й=! всякий маршрут являстшг простой цепью.
Пусть при некотором й)2 доказываеыос утверждение справедливо для любого маршрута длины ~3 †!. Покажем его справедливость для пранавольнаго маршрута т?=о,х,о, л„оьы где огчьгч+ь Длины й. РассмотРнм Два иомеРа 1, 1, гДе 1(1( (1(й+1, такнг, что ог=оь Если таккх номеров пет, то маршрут ц является простой цепью.
Если же указанные номера нашлись, то рассматриваем полмаршрут П'=о,к,от...хг,орби!+к.. ..льоььг (т. е. предполагаеы, что (чо1. (чей+1; случаи, когда 1=1 илп )=3+1, рассмотрите самостоятельно) длины ~й — 1, а из него в салу индуктивного предположения можно выделить простую цепь, соединяющую вершины оь оьы. Введем понятие композипии путей [маршрутов). Пусть и~=огх,оь..хь — ~оь пз=оьхьоььг...хг гш — пути в орграфе О, где йтм2, 1~2-?1. Назовем путь ,б)пг= —,,оь ..о.х"., о (очевидца, что п,Опз — путь в О) композицией путей ш, гы. Аналогично определяется иомпозицпя маршруюв.
4!.4. Матричное задание графов. ййатрицы смежности, кнцидеитнасти Пусть О=(У, Х) — орграф, где У=(оь ..., о ), Х (хг, ....х ). 1ет Матрицей смежности орграфа 0 называется квадратная матрица А(0) =[аз!] порядка л, у которой ,„(1, если (оь и,)шХ! [О, если (оь о;)шХ. Магрицей шщидеитнасги (нлн матрнцей ннцкденций) орграфа Р называется (л)(ш)-матрица В(0) = [Ьгт], у которой 1, если вершина и, является концом луги,тй 6|4= — 1, если вершина от является началом дуги хй О, если вершина ог не инцндснтиа дуге х!. Введем также матрицы смежностн н ннцидентностн для неорнентнрованнык графов. Пусть 6=(У, Х) — граф, гд* = о» ..., и ), Х= (х», х ).
(М'"" атрнцей смежности графа 6 называется квадратная магри. ца А(6)=[ага] порядка л. у которой [ 1, еслн (оь о!)шХ; [О, еслн (иь о!) шХ. Матрнцей ннцндентносгн графа 6 называется (и)(ш)-матрнца В(6)=[ЬО], у которой [ 1, если вершина гн ннцндентна ребру хй [О, если верпшиа и, не ннцндентна ребру х!. Пример 4.11. Для орграфа О, изображенного на рнс.
4.6, матрица А(0) прнводнтся в табл. 4.!а, а матраца В(0) — в табл. 4.1б. Пример 4Л2. Для графа 6, изображенного на рвс. 4.7, ыатря. цв А(6) прнводнтся в табл. 4.2а, а матрнца В(6) — в табл. 4.28. Залемгние 4.8. Матрицу смежности можно определить н для псевдографов. Тогда в случае орнентнрованного (неориентированного) псевдографа аи=д, где й — кратность дуге (ог, и!) (ребра (оь и!)) в атом псевдографе. Определение матрицы нн. цядентности без изменений переносится н на произвольные мультнгрзфы (ориентированные к неирнентнрованные) н даже нв неориентврованные псевдографы. Лрлмер 4.13. Для ориентированного псевдографа О, изображенного на рнс.
4.8,матрица А (О) приводятся в табл. 4.3. и, 1г Рас. 4.6 Рис. 4.6 166 тзбзиав Егб Тзбвчзз егз тзблчч 626 тзблиач 426 1збзчаз 43 а а г а 3 2 Нетрудно видеть, что матрица д (О) является симметричной дта любого неорнентированнага графа б.
Матрица А(й), где  — арграф, в Общем случае не «вдается симметричной (см. примеры Я.)! и Я, !3). По матрице смежности графа (орграфа) всегда можнО определить ребра графа (дуги орграфа) как пары ннцидевтных «и вершин, а вля игениогрвфов, кроме того, и кратиоотн ребер (луг). Однако, если ребра (дуги) были прааумераванм, та восстановить ил номера по матрице смежности невозможно. В шаы смысле матрица ннцндеатиасги оказмваепж а!шее информативной, чем матрипз смежности, поскольку иазвоаяет яолучнть полную ивфармаш!ю а ребрах (лугак), включан ик нумерацию. С помощью введеннык матриц удобно задавать графы (ар'раЯнг) для обработки на ЗВМ Однако следует отметить, что арв большом количестве вершин матрица смежности оюшмввегс» громоздкой и число элементов в ней может превысить до.
аусткмый объем оперативной памяти ЭВМ. То же можно скаЗбть и о матрице нвцндввтнасти, причем се размеры зависят, кроме топ!, и ат иолнчества ребер (дуг). ц 2622 гш Проведем очевидные свойства матриц смежности и иннидеиг'. ности: 1.
Сумма элементов матрипы А (О), где 0= (У, Х) — нуль. тиграф, У=(оь ..., о ), по (-б строке (нлп по 1-иу столбцу) равно б(аг). 2. Суммы элементов матрицы А(О), где О=(У, Х) — орн. енгпровапный псевдограф, У=(о!, ..., и ), по (-й строке н по ьму столбцу соответственно равны б+ (о!), б-(о,). 3. Пусть Π— ориентированный мультиграф с непусгым мио. жеством дуг.
Тогда э) сумма строк матрицы В(О) япляется нулевой строки(Ь б) любая строка матрицы В(О) является лннейпой комбипацпеб остальных строк; в) ранг матрицы В(О) не превосходит н(О) — 1; г) лля любого контура в О сумма столбцов матрицы В(01, шютвстствувщих дугам, входяШим в этот контур, равна нуле. вомт столбцу. 4. Пуси, 0 — мульт»граф с пепусгым множеством ребер Тогда при покоордннатнои сложении по модул!о 2г а) сумма строк матрииы В(0) является нулевой строкой; б) любая строка матрицы В(0) является суммой осгальньы строк; в) для любого цикла в 0 сумма столбцов матрицы В(0), соотиетствуюшнх ребрам, входяшнм в этот цикл, равна нуле. во»у столбцу.
Обозначим через Аь=(агэ!и] А-ю степень матрицы смежно. стп А=А(О) орграфа О (аналогичное обозначение вводим и для графа О). Утверждение 4.2. Элемент аиги матрицы Агг! ориентировав ного лсеадографа О=(У, К) (лсевдографа 0=((г, Х)), гдг У=(аь .,.. о ), равен числу всех путей (маршругоа) длшгы А из ш а ог (соединяюи(их оь ог). Дакэаэшэьшаа вэавеээ» дк О (энк О ова э»клети ею) впдувпвеА ш Д При А 1 свравелш.эссъь хакаэиааеиага угэерэшевэ» слеэгег иепанед сменка нэ оврехглеэа» нвтрниы А А(О), пэеююлашк», чта хакю»эюкю утвермдевке сирэаеээаво врв А К где Уж!.
Пахане» ега свзээеэ.»- шить в вии А А'+!. Обоэкэчии терек п(О. аг, аг, 1, гхе г ж 1, ииамсство путей длины г ээ иг в аг в ааиептяравэн!юи «севлаграфе О. Рээабье» эввшестэа этюя п(О. гн, иг, А + 11 на и гРУпп, пеРваЯ гРУппа — его иэо. нес!во П(О, иь а, эг, А'+ 11 путез с превпосгедвея вершвэоб аь этарэя гРУппа — »вашества П(О, аэ а, эг. А'+ 11 пУша с пэедэссэедвеа агава. юа э и т. д„л-» группа — »пшкества П(О, эг, и, иг, А'+1] ну~та Е абеэвасэеэиеа веэшпиаа э . Оьеэээва, чта савакупиость укаэанных гирю является рээбвевие»»паж~так П(О, иь иг, А'+ 11, а следовательно. (П(О, иь аь а'+ 1)1- Х (П(О, аь и, аь а+П(.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
