В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 46
Текст из файла (страница 46)
лов (иь ..., рг», являющуюся пнкловмм базисом мультнграфа б. Рассмотрим теперь вопрос о количестве элементов в циклоном базисе мультиграфа б. Для этого иам понадобнтсн. Утвсрждемие 4А2. луста (рь ..., рь), (тм., чь» — систсмьг циклов мультиграфа б такие, что й'.мй, каждый цикл из системы (т1ь ..., т1ь') являгтсл линейной каибиначивй циклов 1и, ..., кь Тогда система Чиклса (Чь ..., Чь'» нв является независимой. Согласно условиям утверждении 4.42 для некоторых асгчш(ь где!=1, ..., й, ) 1, ..., й', имеем ан1и + ... + аыиь; (4.32) Чь'=лайк~+... +аз'Ыи. Рассмотрим матрицу размерности й'Хй. Пусть г — ранг матрицы А, Аг= [а'ь ...
ща), 1=1, ..., й',— стоокн матрицы А. Тогда г(й(А; а слеловагельно, аекоторан строка в А (например, перван) нвлнетсв линейной комбинацией остальных строк, т. е. А, адАр + ... + аь'Аьб (4.33) где «ь ..., аь'щ() (с учетом того, чю Аь ..., Аь'щО", где 11 линейное пространство над полем 4»). Из (4 32), (4.33) получаем Чщ = атчт+., +аа'Чьд т.
е. система циклов Чь ..., тэь' не является независимой. Из утверждения 4.42 следует, что ющнчсство элементов в циклоном базисе муаьтиграфа 6 — величина постояннан, не зависящая от выбора циклового базиса и равная максимальному числу элементов в независимых системах циклов мультиграфа 6. Ниже (см. теорему 4.5) будет показано, по этв величина совпадает с геометрической харахтеристиной мультиграфа б. а именно: количество элементов циклового базиса равно ч(6) = гл(6) — л(6) + р(б) (в частности, ч(6) = 0 для ацнклнчесного мультиграфа б), прв этом ч(6) называетси Чикломатичгским числом мультиграфа б. Напомним, что ранее цикломатическое число было введено длн связною мультиграфа 6 (т.
е при р(6) !). В дальнейшем нам понадобится также следующее вспомогательное утверждение. 216 Утверждение 4.43. Если М (рь ..., рь) — цпклоаой базис мультигрофа 6, Н (тп, ..., »1ь) — система циклов яульгигршуа 6 такая, что каждый цикл ив М является линейной «омбинацией циклов пз Н, то Н вЂ” цикловой базис пульгиерпфа 6. Заменяю что наждый цикл мультнграфа 6 является линейной комбинацией циклов иэ М, а зиачит, н циклов из Н.
Покажем теперь независимость системы Н. Предооложим. что эта система ие является независимой. Тогда пека»орый цикл и» являстсн линейной комбниапией остальных циклов из Н. Пусть длн определенности 1=й. Тогда каждый цикл из М ивлнется ли. иейной комбинацией циклов пь ° ° .Оь-ь а следовательно, в силу утверждения 4.42 получаем, что система М ие явлиется независимой, а это противоречит исходным предположениям. Покажем теперь, что если мультиграф 6 пе нвляется ациклическим, то в нем существует цикловой базис, сосгошцяй из простых циклов. Предварительно докажем слепуюп»ие простые утвержденна. Утверждение 4.44.
Пусть р — цикл в мультигрофе 6, в котором все веришкы попарно раэяи мы. Тогда» 1) либо цике и имеет вшу и охшхо, где х = (о, и), о чь ш, и при этом С(р) О; 2) либо 1» — простой цикл и при этап С(р) чьй. Если в цикле р все ребра попарно различны, то выполняегси утверждение 2. В противнои случае пусть 1» о»х о»х» ... оьхьо», (4.34) глс Д>2, и при некоторых 1, ! справедливо равенство х»=хь где х» = (оь и»+,), хт = (оь о»»»), 1щ!()мй (для общности обозначений в слУчае)=й полагаем о»», вь+ о»). ПРедположнм, что 1)1+ 1. Тогда согласно условиим утвержденна 4А4 выполннися неравенство ин.» ть оь а следовательно, в силу равенства к, х» имеем и» о», о»+» = огм, что противоречит условиям доказываемого утверждении. Танин образом, 1»+ 1. и тогда х» = (о», о»+,), хь = кн-» (о»+ь о»»Д, а значит, в силу равенства х» = хт имеем о» о;+ь откуда согласно условиям доказываемого утверждения и в силу (4.34) справедливо 1 1, 1+ +1=а.
а следовательно. 3=2, р=о»х,отх»оь где х»=(о», от), о, чьоь При этом, очевидно, С(р) О. Утверждение 4.43. Пусть р — цикл в лультиграфе 6, и— проктвольнав вершшш, содержащаяся в р. Тогда р является линейной коябиноцией некоторьы циклов пультиграфа 6, в каждый иэ когорык вершина о либо не вм»диг, либо входит ровно один )юз. Показательство будем проводить индукцией по Д вЂ” длине цикла р. При Д 2 всякая аерщииа, содержащвнся я цикле р, вкодит в него ровно одна раз. Предположим, что при некотором 317. лый доказываемое утверждение справедливо лли любого цикла длины жй — 1.
Докажем его для произвольного цикла р и,х,отхт ... сьхьа, длины й. Пусть 1 — минимальный номер такой, что о~ = а. Разберем нетривиальный случай, ногда вершина иг входит в р более одного раза. Пусть ) — минимальный нз ио. мероа среди г+2, ..., й такой, что ог = пь Рассмотриы циклы (считаем, что 1)1; случай, когда 1=1, аиалогичен) и, а~х ... аьлхк,о1хг ... сьхгол гтз=сгх~ ...
аг,х, ~оь Очевидно, чта р = гп + рт. Пря этом по услоемям выбора номера 1 вершнва о = ог встречается в р, ровно одни раз. Заметим, что длина цикла п~ равна й+1 — Д где й+1 — )мй — 2, а слеиоваткчьнгь по иидуктнвному предположению цинл р, является линейной комбинацией некоторых циклов, в каждый из которых вершина о либо не входит, лабо входит равно один раз, откуда в силу р П, + рг и вытекает справедливость доказываемого утверждения. Испозьзун утверждения 4А4, 4А5, пакажеы, что справедливо Утверждение 4А5.
Пусть р — цикл е мультиерафе 6 юкой, что с(п) им О, тогдп и яалштсл линейной комбинацией лргжгмх гузке аз. Испачьзуя утверждение 445, па.тучаем, что и можно предста. вить в валс лпней~юй номбниации циклов, в каждом нэ ноторых нсе вершкны попарно различны. Ио тогда пз утверждении 4.44 следует, что в указанную линейную комбшгацню войдут простые кикты и р является их линейной комбинацией. Теперь докажем, что справеллива Теорема 4А.
Пусть б — мульгшреф, не леллюн(ийся плинло«еским. Тогда е 6 суи(естаует циклоеой Базис, элементами «отарого яоззютсл простые циклы. Согласно утверждению 4.41 в 6 существует цнк.юной базис (иь ... р.), где тж1. Используя утвержление 4АБ, получаем, чта пажлый цикт и, является линейной комбинацией иеноторых проСтма ииКтае П„, ..., 1твм (1=1, ..., Ч). ДаЛЕЕ, ИСПОЛЬЗУЯ ПРОЦЕСС, описанный прв доказательстве утверждения 4.41, выделяеы нэ ПРаетЫХ ЦНКава иь ).=1, ..., Ггл 1 1, ..., т, ИсэаВНСИМУЮ Сиетсир циклон такую.
что любой цикл р~т явииется се линейной комбинацией. указанная система простых циклов, очевидно, будет шпжопым бааисач мультиграфа 6. Докажем теперь теорему а числе элементов в циклоном базя се чультпграфа. Теорема 4.5. Количества элементов е цикюеом базисе мула. твгробш 6 (р, Х) соеладеет с его цикломатическим чшлогг «(6) лг(6) — л(6) +р(б). В частности, для ацггхличесшш музьтиграфа т(6) = О. 2!8 Доказательство проведем индукпией па количшчву ребер в мультнграфе 6.
Обозначим через ч(6) количество элементов в циклоном базисе ыультяграфа О, при этом, если 6 — ациклнческий мультнграф, та положим ч(6) = О. Покажеы, что ч(б) (О). Бпзгго индукции. Если т(6) = О, то, очевидно, выполннется равеиство р(6) л(6), а слелавательио, ч(б) =О. С другой стороны, поскольку т(б) = О, ямсем ч(б) О, т. е в этом случае равенство ч(6) ч(6) выполняется. Индуктивный шол. Прелполажим, что при некотором ты 1 доказываемое равенство справедливо для всякого мультнграфа с т — 1 ребранн. Докажем ею справедливость и для произвольною мультнграфа 6 такого, что гв(б) = т. Удалив нз 6 произвольное ребро х (оставив без изменения вершины), получим мультиграф 6' такой, что т(0') гл — !.
Возможны случанг а) ребро л соединяет некоторые всршвны аь оь прннадлежашяе рачли гимн компонентам связности мультиграфа 0', б) ребро х соеднняст зве различвыс вершикы оь оь прннадлежашне ланой компоненте связности мульгиграфа О( В случае «а», очевидно, выполняется равенство л(0') = л(0), т(6') = т(0) — 1. р(6') = р(6) + 1, а следовательио, ч(6') = ч(0). Но тогда, если мы докажем, чта (4.35) (6) -ч(6), то, жшпользовавшнсь тем, что по индуктивному нрелпозожснаю ч(6') =»(б'), получим ч(б) ч(б) ч(6) -т(0). Таким образом, осталась доказать равенство (4.35). Если 6 — ациплическнй мутьтиграф, та мультнграф 6' тен более является апиклнческим, и югда ч(6) = О = ч(6'), т. е.
равенство (435) выполняетса. Пусть теперь мультвграф б пг являетсн ацпкличсским. Возьмем произвольный цнкловой базис (рь ..., р,), где ч(6) ъ 1, мультиграфа 6, састоншнй нз простых пнклов (см. теорему 44). Покажем, что вь .... в, — циклы в б'. Предположим противное: пусть, например, р; зе явлнетсн циклон в 65 Но тогда в, прохалит через ребро х, т, е., скажем, имеет вид р~ = о х,а»х» ... Шхэаь где х = х, (оь о»). В силу того, чта рг — простой цикл, имеем Х,чвл, 1 2, ..., Л. СЛЕЮВатеп»яа, О»Х, ... ЪХ»аг — ЦЕПЬ В 0'. соединяющая вершины оь аь а это противоречит тому, что вершины оь э, принадлежат различным помюнентам сея»кости мультиграфа 65 Таким образом, (вь ... р.) — независимая система циклов мультиграфа 6' такая, что любой цикл в О, а сле- 14 21В довательно, и в 0' является линейной комбинацией циклов этой системы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
