Подграфы и части графа. Операции над графами

⇐ ПредыдущаяСтр 8 из 27Следующая ⇒

Граф G ' = á M ', R ' ñ называется подграфом графа G = á M , R ñ , если M ' ⊆ М и R ' = R ∩ (М ')2. Граф G ' называется частью графа G , если М ' ⊆ М и R ' ⊆ R ∩ (М ')2.

Пример 2.1. Граф G ' = á {1, 2, 3}, {[1, 2], (1, 3), [2, 3] ñ (рис. 4.9 б ) является подграфом графа G = {{1, 2, 3, 4}. á [1, 2], (1, 3), [1, 4], [2, 3], [3, 4]} ñ (рис. 4.9 а ), а граф G " = á {1, 2, 3}, {[1, 2], (3, 2)} ñ (рис. 4.9 в ) — частью графа G .

Рассмотрим некоторые основные операции, производимые над графам».

Операцией добавления к графу G = á M , R ñ вершины а образуется граф á {М ∪ {а }, R ñ . Операция добавления дуги ( a , b ) к графу G состоит в образовании графа á М ∪ {а, b }, R ∪ {( a , b )} ñ . Под операцией удаления дуги ( a , b ) яз графа G понимается операция, заключающаяся в удалении пары ( a , b ) из множества дуг R в результате получается граф á {М, R ( a , b )} ñ . Операция удаления вершины а из графа G заключается в удалении вершины a вместе с инцидентными ей дугами:

Рис. 4.9

Операция отождествления вершин а и b графа G = á M , R ñ состоит в удалении из графа G вершин а и b и присоединении новой вершины а ', дуг (а ', с ), если (а, с ) ∈ R или ( b , с ) ∈ R , и дуг (с, а '), если (с, а ) ∈ R или (с, b ) ∈ R :

Говорят, что построенный граф получается из графа G отождествлением вершин a и b . В случае, когда a и b соединены дугой, операцию отождествления вершин а и b называют стягиванием дуги (а, b ).

Пример 2.2. Из графа G . показанного на рис. 4.10, добавлением вершины 5 образуется граф G 1, добавлением дуги (3, 1) — граф G 2, удалением дуги (3, 2) — граф G 3, удалением вершины 2 — граф G 4, отождествлением вершин 1 и 4 — граф G 5, стягиванием дуги (2, 3) — граф G 6.

Дополнением графа без петель G = á M , R ñ называется граф

Рис. 4.10

Маршруты

Пусть G = á M , R ñ — граф. Последовательность

a 1, u 1, a 2, u 2, …, un, an+1 (4.1)

где a 1, a 2, …, an+1∈ М , u 1, u 2, …, un∈ R , называется маршрутом, соединяющим вершины a 1 и ап+1(( a 1, ап + 1 )-маршрутом ), если ui= ( ai, ai + 1 ), i = 1, 2,..., п (рис. 4.18).

Очевидно, что маршрут (4.1) можно задать последовательностью a 1, …, ап + 1 его вершин, а также последовательностью u 1, …, u пдуг. Число п дуг в маршруте (4.1) называется его длиной.

Пусть G — неорграф. Маршрут (4.1) называется цепью, если все ребра [ a 1, a 2],..., [ an, an+1] различны, и простой цепью, если все его вершины кроме, возможно, первой и последней, различны. Маршрут (4.1) называется циклическим, если a 1= an+1. Циклическая цепь называется циклом, а циклическая простая цепь — простым циклом. Неорграф без циклов называется ациклическим. Минимальная из длин циклов неорграфа называется его обхватом.

Рис. 4.18

Пример 3.1. Рассмотрим граф, изображенный на рис. 4.19. В нем на боры (1, 2), (1, 2, 4, 7), (3, 4, 5, 6) являются простыми цепями; (1, 2, 4, 7, 8, 4) — цепь, не являющаяся простой; (1, 4, 7, 8, 4. 2) — маршрут, не являющийся цепью; (1, 2, 4, 7, 8, 4, 1) — цикл, не являющийся простым: (1, 2, 4, 1) — простой цикл. Обхват этого графа равен 3.

Пусть G — граф, возможно, ориентированный. Маршрут (4.1) называется путем, если все его дуги различны. Путь (4.1) называется контуром, если a 1= an+1. Граф, не имеющею контуров, называется бесконтурным. Вершина b называется достижимой из вершины а, если существует (а, b )-путь.

Степени вершин

Степенью или валентностью вершины а неорграфа G называется число ребер, инцидентных вершине а, т. е. число ребер, концом которых является вершина а (при этом петли считаются дважды). Если G — орграф, то степени его вершин определяются как степени вершин в соответствующем неорграфе F ( G ). Аналогично вводится понятие степени вершины в мулътиграфах. Степень вершины a будем обозначать через degGa или просто deg a. Вершина степени 0 называется изолированной, вершина степени 1 — концевой или висячей.

Пример 6.1. Вершины графа G , изображенного на рис. 4.28, имеют следующие валентности: deg l = deg 2 = deg 3 = 1 (т. е. l, 2, 3 — висячие вершины), deg 4 = 5, deg 5 = 0 (т. е. 5 — изолированная вершина).

Рис. 4.28

Рассмотрим сумму степеней всех вершин графа. Поскольку каждое ребро входит и эту сумму дважды, справедливо

Утверждение 6.1 (лемма о рукопожатиях). Сумма степеней всех вершин графа, является четным числом и равна удвоенному числу ребер.

Пусть G — бесконтурный орграф. Полустепенью исхода deg +а вершины а называется число дуг, исходящих из а. Полустепенью захода deg –а вершины а называется число дуг, которые заходят в вершину а. Справедливо соотношение deg a = deg +a + deg –a .

Раскраски графов

Пусть G = á M , R ñ — неограф без петель. Pac краской (вершин ) графа G называется такое задание цветов вершинам G , что если [а, b ] ребро, то вершины а и b имеют различные цвета. Хроматическим числом χ ( G ) графа G называется минимальное число цветов, требующееся для раскраски G .

Пример 14.1. Так как в полном графе Кплюбые две различные вершины связаны ребром, то χ (Кп) = п.

Многие: практические задачи сводятся к построению раскрасок графов.

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

2. Рассмотрим граф G , вершины которого — страны, а ребра соединяют страны, имеющие общую границу. Числу χ ( G ) соответствует наименьшее число красок, необходимых для раскраски карты так, чтобы никакие две соседние страны не были окрашены в один цвет.

Существуют и практические задачи, связанные с раскраской ребер в мультиграфе.

Раскраска ребер в мультиграфе G может быть определена с помощью раскраски вершин так называемого реберного мультиграфа. L ( G ). Для произвольного неориентированного мультиграфа G = á M , U , P ñ реберным мулътиграфом L ( G ) называется тройка á U , М, Р ' ñ , где Р ' ⊆ U × M × U , и выполняется ( u , a , v ) ∈ Р ' тогда и только тогда, когда в мультиграфе G вершина, а является концом ребер и и v . Раскраской ребер мультиграфа G называется раскраска вершин мультиграфа L ( G ).

Пример 14.3. Проводится монтаж аппаратуры. Чтобы не перепутать проводники, необходимо их окрасить таким образом, чтобы два проводника, идущие к одной плате, имели разные цвета. В этом случае вершинами являются платы, а ребрами — проводники.

Неорграф G называется бихроматическим, если χ ( G ) = 2. Неорграф G = á М , R ñ называется двудольным, если множество всех ребер графа G образует разрез графа G , т. е. для некоторого разбиения множества вершин {М 1, М 2} концы любого ребра принадлежат разным частям разбиения.

Теорема 14.1. Пусть G — неорграф без петель, имеющий хотя бы одно ребро. Тогда следующие условия эквивалентны:

1. G — дихроматический граф;

2. G — двудольный граф;

3. G не содержит, циклов нечетной длины.

Следствие 14.2. Если G — лес, то χ ( G ) ≤ 2.

Оценим хроматическое число графа G через его параметры. Обозначим через deg ( G ) максимальную степень вершин графа G .

Теорема 14.3. Для любого неорграфа G без петель выполняется неравенство χ ( G ) ≤ deg ( G ) + 1.

Рассмотрим простой алгоритм построения раскраски, который во многих случаях приводит к раскраскам, близким к минимальным.

Алгоритм последовательной раскраски.

1. Произвольная вершина а 1графа G принимает цвет 1.

2. Если вершины a 1, ..., aiраскрашены l цветами 1, 2, ..., l . l ≤ i , то новой произвольно взятой вершине; ai + 1 припишем минимальный цвет, не использованный при раскраске вершин из множества {а j| p ( ai + 1, aj) = 1, j < i }.

Для некоторых классов графов последовательная раскраска является минимальной. В общем случае это не так.

Планарные графы

Неорграф G называется планарным, если его можно изобразить на плоскости так, что никакие два ребра не будут иметь общих точек, кроме, может быть, общего конца этих ребер. Такое изображение графа на плоскости называется плоским. Таким образом, если граф имеет плоское изображение, то он является планарным.

Пример 15.1. Граф К 4(рис. 4.48а) планарен, поскольку может быть изображен, как показано па рис. 4.48 б.

Рис. 4.48

Граф, описанный в примере 14.2 является планарным. Также планарным является граф, вершины которого — отверстия печатной платы, а ребра — проводники печатной платы, соединяющие отверстия.

Рассмотрим операцию подразбиения ребра в графе G = á М , R ñ . После подразбиения ребра [ a , b ] ∈ R получается граф G ' = á М ', R ' ñ , где М ' = М ∪ [ a , b ], R ' = ( R {[ a , b ]) ∪ {[ a , ab ], [ ab , b ]}, т. е. ребро [ a , b ] заменяется на ( a , b )- цепь длины два. Два графа называются гомеоморфными, если их можно получить из одного графа с: помощью последовательности подразбиений ребер.

Не всякий неорграф является планарным. Критерий планарности описывает

Теорема 15.1 (теорема Понтрягина — Кураторского). Граф G планарен тогда и только тогда , когда G не содержит подграфа , гомеоморфного К 5или К 3, 3(рис. 4.49 ).

Эквивалентная форма критерия планарности описана в следующей теореме.

Теорема 15.2. Тогда и только тогда неорграф G планарен , когда G не содержит подграфов , стягиваемых (т. е. получаемых последовательностью отождествлений вершин, связанных ребрами) к графу К 5или К 3, 3(рис. 4.49 ).

Рис. 4.49

Цит. по: Элементы дискретной математики: учебник /
С.В. Судоплатов , Е.В. Овчинникова. — М.: ИНФРА-М;
Новосибирск: НГТУ, 2003. — С. 114–124, 130–131, 153–154. — (Серия «Высшее образование»).

Изоморфизм графов

Для ориентированного графа (V , Е ) множество Е дуг можно рассматривать как график бинарного отношения непосредственной достижимости, заданного на множестве вершин.

В неориентированном графе (V , Е ) множество Е ребер является множеством неупорядоченных пар. Для каждой неупорядоченной пары {u , v } ∈ Е можно считать, что вершины u и v связаны симметричным бинарным отношением ρ , т. е. {u , v } ∈ ρ и {v , u } ∈ ρ .

Таким образом, с каждым неориентированным и ориентированным графом связано бинарное отношение ρ . Это отношение будем называть отношением смежности.

С алгебраической точки зрения как ориентированный, так и неориентированный граф можно рассматривать как модель, сигнатура которой состоит из одного бинарного отношения: В классической теории графов изучаются преимущественно конечные модели такого рода.

При указанном подходе различия между ориентированным и неориентированным графами проявляется только в свойствах отношения смежности ρ . Если это отношение симметрично, то граф называют неориентированным, и с этой точки зрения неориентированный граф можно считать частным случаем ориентированного.

Применяя к данному частному случаю моделей общие понятия гомоморфизма и изоморфизма …, мы можем сформулировать следующие определения.

Определение 5.14. Отображение h : V 1→ V 2множества вершин графа G 1= (V 1, ρ 1) в множество вершин графа G 2= (V 2, ρ 2) называют гомоморфизмом графов (графа G 1в граф G 2), если для любых двух вершин, смежных в первом графе, их образы при отображении h смежны во втором графе, т. е. если

Биективный гомоморфизм h , такой, что любые две вершины смежны в первом графе тогда и только тогда, когда их образы смежны во втором графе, т. е.

называют изоморфизмом графов G 1и G 2(графа G 1на граф G 2), а графы G 1и G 2— изоморфными, что записывают в виде G 1≅ G 2.

Гомоморфизм графов, который является эпиморфизмом, называется также гомоморфизмом одного графа на другой.

Возвращаясь к нашему определению графа посредством двух множеств: множества вершин V и множества ребер (дуг) Е, получим следующие варианты определений гомоморфизма и изоморфизма.

Гомоморфизм неориентированного графа G 1= (V 1, Е 1) в неориентированный граф G 2= (V 2, Е 2) есть такое отображение h : V 1→ V 2, что для любых двух вершин первого графа, соединенных ребром, их образы при отображении h также соединены ребром, т. е.

Гомоморфизм ориентированного графа G 1= (V 1, Е 1) в ориентированный граф G 2= (V 2, Е 2) есть такое отображение h : V 1→ V 2, что для любых двух вершин u , v первого графа, таких, что есть дуга, ведущая из u в v , из вершины h (u ) тоже ведет дуга в h (v ), т. е.

Изоморфизм неориентированного графа G 1на неориентированный граф G 2есть такая биекция h : V 1→ V 2, при которой две вершины u и v графа G 1соединены ребром тогда и только тогда, когда соединены ребром их образы h (u ) и h (v ), т. е.

Аналогично изоморфизм ориентированного графа G 1на ориентированный граф G 2есть такая биекция h : V 1→ V 2, при которой в ориентированном графе G 1из вершины u ведет дуга в вершину v тогда и только тогда, когда в ориентированном графе G 2из образа h (u ) вершины и ведет дуга в образ h (v ) вершины v , т. е.

Цит. по: Дискретная математика: учебник для вузов /
А.И. Белоусов , С.Б. Ткачев; под ред. В.С. Зарубина, А.П. Крищенко. —
3-е изд., стереотип. — М.: Изд-во МГТУ им. Баумана, 2004. — С. 341–343. —
(Сер. Математика в техническом университете; Вып. XIX).

Говорят также: упорядоченная п-ка (например, упорядоченная тройка, четверка, пятерка и т. д.).

Нефедов В.Н. Курс дискретной математики / В.Н. Нефедов, В.А. Осипова. — М: Издательство МАИ, 1992. — 264 с.

Непорожнев И.П. Элементы дискретной математики / Учеб.-метод. пособие. — Пермь: ПВВКИКУ, 1994. — 38 с.

Нефедов В.Н. Курс дискретной математики / В.Н. Нефедов, В.А. Осипова. — М: Издательство МАИ, 1992. — 264 с.

При таком подходе в неориентированном графе могут быть петли, если отношение р содержит некоторые элементы диагонали, в частности является рефлексивным.

АЛГЕБРА И ТОПОЛОГИЯ

⇐ Предыдущая 3 4 5 6 789 10 11 12 Следующая ⇒