XIX Белоусов А.И., Ткачев СБ. Дискретная математика (1081422), страница 46

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

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

~ Следствие 5.1. Если вершина неориентированного графа содержится в некоторой замкнутой цепи, то она содержится и в некотором цикле. Если вершина ориентированного графа содержится в некотором замкнутом пути, то она содержится и в некотором контуре. Замечание 5.3. Следствие 5.1 перестает быть верным для произвольной цепи с совпадающими концами. Например, для неориентированного графа, состоящего из двух вершин е~, ез и единственного ребра (еп еэ) цепь е~, ез, е~ с совпадающими концами не содержит цикла.

Перейдем теперь к понятию подграфа. Формулируется это понятие одновременно для неориентированных и ориентированных графов (с учетом различий в терминологии). Определение 5.1. Неориентированный (ориентированный) граф С~ = (1~и Е~) называют подграфом неориентированного (ориентированного) графа 0 = (7; Е), если ~~ С 1' и Е~ С Е. Будем испольэовать обозначение 0~ С С, аналогичное обозначению включения для множеств.

Замечание 5.4. Так как в определении 5.1 пара С~ = Я,Е~) есть неориентированный (ориентированный) граф, то для лю- 284 5. ТЕОРИЯ ГРАФОВ бого ребра (и, е) Е Е1 (дуги (н, е) Е Е1) предполагается, конечно, что и, е е Уп поскольку иначе пару (У1, Е|) нельзя будет считать неориентированным (ориентированным) графом. Если хотя бы одно из указанных двух включений в определении 5.1 строгое, то С1 называют собственным подграфом графа С; если У1 = У, то С1 называют остповным подграфом графа С. Подграф С1 неориентированного (ориентированного) графа С называют подграфом, порожденным множестпвом вериьнн У1 С У, если каждое ребро (дуга) тогда и только тогда принадлежит Е1 С Е, когда его (ее) концы принадлежат У1.

Часто в случае, если множество вершин У1 подразумевается, говорят просто о порожденном подграфе. Отметим, что подграф графа С, порожденный множеством вершин У1, в отличие от произвольного подграфа графа С с множеством вершин Уп должен включать все ребра (дуги), концы которых принадлежат множеству Уп Подграф С1 С С называют максимальным подграфом, обладающим данным свойством Р, если он не является собственным подграфом никакого другого подграфа графа С, обладающего свойством Р. Например,на рис. 5.7 подграфы Сп Сз, Сз являются максимальными ациклическими подграфами графа С.

Отметим, что они также являются собственными и остовными подграфами указанного графа. Оз 0 О, О2 Рис. Ь.Т Следующее важное понятие снова введем параллельно для рассматриваемых двух видов графов. 285 5. Ь Остюлыые олределелил Ориентированные графы Неориентированные графы Ориентированный граф называют связнььн, если для любых двух его вершин и, о вершина е достижима вз вершины и влн вершина и достижима вз вершины е (и =~' е или е ~' и). Неориентированньтй граф назы- вают связным, если любые две его вершины и в е соединены це- пью (ит=~' е).

Колтпонентпа связностпи (вли просто номпонентпа) ориенти- рованного графа — это макси- мальный связный подгрзф. Компонентов связностпи (или просто номпонентпа) неориентированного графа — это его максимальный связный подграф. Пример 5.3. Граф, изображенный на рис. 5.2, не является связным. Он состоит из трех компонент. Эти компоненты порождены тремя классами эквивалентности по отношению достижимости, указанными в примере 5.1. Связными являются все графы, изобрает женные на рис. 5.7.

Ориентированный граф на рис. 5.8 связный, а ориентированные графы на рис. 5.3 о, и 5.9 не являются связными. В ориентирооз ванном графе на рис. 5.3 вершины оз и оз не достижимы одна из другой, а в ориенти- В неориентированном графе две вершины, соединенные цепью, связаны отношением достижимости, которое является эквивалентностью. Поэтому компонента такого графа — это подграф, порожденный некоторым классом эквивалентности вершин по отношению достижимости. Поскольку каждая компонента неориентированного графа порождается некоторым классом эквивалентности вершин, то две различные компоненты не пересекаются, т.е. не имеют ни общих вершин, ни общих ребер.

Так как отношение достижимости в ориентированном графе не является эквивалентностью, то компоненты ориентированного графа могут пересекаться. 286 5. ТЕОРИЯ ГРАФОВ Рис. 9.9 рованном графе на рис. 5.9 взаимно не достижимы, например, вершины оз и ое. В ориентированном графе, изображенном на рис. 5.9, имеются две компоненты связности: С1 и Сг, которые пересекаются. Для ориентированного графа можно определить также понятия сильной и слабой связности. Определение 5.2. Ориентированный граф называют си вьмо связным, если для любых двух его вершин и и е вершина е достижима из вершины и и вершина и достижима из вершины е (и =ь' е и о ~" и).

Впмомпоиемтпа ориентированного графа— это его максимальный сильно связный подграф. Если и =~' о и е =~'и, то говорят, что и и е связаны отношением еэпимкоб доспиажпмосши. Это бинарное отношение рефлексивно, симметрично и траизнтивно, т.е. является отношением эквивалентности. Следовательно, две различные бикомпоненты не пересекаются, т.е. не имеют ни общих вершин, ни общих ребер. Пример 5.4.

а. В ориентированном графе, изображенном на рис. 5.3, бикомпонентой является подграф См порожденный множеством вершин (ем ез, оз). Действительно, эти вершины взаимно достижимы, поэтому ориентированный граф 01 сильно связный. Так как из вершин е4, ез, ее ни одна из вершин ем 287 бп. Основные определевяа ддз, ез не достижима, то выделенный сильно связный подграф 6 д является максимальным. б. В ориентированном графе, представленном на рис. 5.9, имеются четыре бикомпоненты Вд, Вз, Вз и В4. Это подграфы, порожденные соответственно множествами вершин (ед), (ддз, ез), (е4, св) и (ее, ет).

Отметим, что подграф, порожденный множеством 1ед), не содержит ни одной дуги. Тем не менее этот подгрзф — бикомпонента, поскольку каждая вершина достижима сама из себя (по пути длины О). Определение 5.3. Неориентированный граф Сд = Я, Ед) называют ассоцпироеаммььи с ориентированном графом С = = (1; Е), если его множество вершин совпадает с множеством вершин ориентированного графа С, а пара (и, е) образует ребро тогда и только тогда, когда дд ф е и из и в е или из е в и ведет дуга, т.е.

~д = 1' и Ед = ((н, е): (и, е) Е Е или (е, и) Е Е, и ф е) . Таким образом, переход от ориентированного графа к ассоциированному с ним неориентированному графу состоит в „стирании" ориентации дуг ориентированного графа с учетом того, что все петли исчезают, а дуги (и, е) и (е, и) при и ф е переходят в одно и то же ребро (и, е).

Для ориентированного графа, изображенного на рис. 5.10, а, ассоциированный с ним неориентированный граф приведен на рис. 5.10, б. Отметим, что дуги (ед, ддз) и (ег, ед) переходят в ребро (ед, ег), а петля (дде, ев) исчезает. юг Рнс. 5.10 288 Б. ТЕОРИЯ ГРАФОВ Определение 5.4. Ориентированный граф называют слабо связным, если ассоциированный с ним неориентированный граф связный..Колеттонентпоб слабой свлэностпи (слабой нолтттонентпой) ориентированного графа называют его максимальный слабо связный подграф. Ориентированные графы, представленные на рис. 5.3, 5.9 и 5.8, являются слабо связными.

Ориентированный граф, изображенный на рис. 5.10, не является слабо связным, поскольку не являетсл связным ассоциированный с ним неориентированный граф. Ориентированный граф на рис. 5.10, а имеет две компоненты слабой связности. Соответственно ассоциированный с ним неориентированный граф на рис.

5.10, б имеет две компоненты связности. 5.2. Способы представлении До сих пор мы задавали ориеннтированньте и неориенптированные графы, изображая их с помощью рисунков. Можно задать граф как пару множеств, следуя определению, однако этот способ довольно громоздкий и представляет, скорее, теоретический интерес. Развитие алгоритмических подходов к анализу свойств графов требует иных способов описания графов, более пригодных для практических вычислений, в том числе с использованием ЭВМ. Рассмотрим три наиболее распространенных способа представления графов. Предположим, что все вершины и все ребра неориеннтированного графа или все вершины и все дуги (включая иентли) ориентпированного графа пронумерованы начиная с единицы.

Граф (неориентированный или ориентированный) может быть представлен в виде матрицы типа п х та, где тт — число вершин, а тн — число ребер (или дуг). Для неориентированного графа элементы этой матрицы задаются следующим образом: 1 1, для т-й вершины т'-е ребро инииденнтное; атт' = О, иначе. 289 6.2. Слособы аредставлеюгл Для оривктпировакиого графа элементы матрицы задаются так: 1, для т'-й вершины у-я дуга выходящая; -1, для т'-й вершины у-я дуга заходящая; О, иначе.

Матрицу (а;у) типа и х тп, определенную указанным образом, называют матприцей иицидекций. Пример 5.5. Для ориентированного графа, представленного на рис. 5.8, нумерация вершин уже задана. Зададим нумерацию дуг следующим образом: дуге (ом оз) присвоим номер 1, дуге (ом оз) — 2, дуге (ог, оз) — 3 и дуге (оз оз) — 4 Матрицу инциденций удобно заполнять по столбцам, записывал для Й-й дуги (о,, о ) 1 в т'-й и — 1 в у-й строках й-го столбца и О во всех остальный строках к-го столбца. В результате получим матрицу -1 О 1 -1 Несмотря на то что представление графа в виде матрицы инциденций играет весьма большую роль в теоретических исследованиях, практически этот способ весьма неэффективен. Прежде всего, в матрице в каждом столбце только два ненулевых элемента, что делает этот способ представления графа неэкономным при большом количестве вершин.

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

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