Закрыть ... [X]

Связанными называются две вершины графа для которых

связанными называются две вершины графа для которых Лекции по теории графов
скачать (704.2 kb.)
Доступные файлы (7):
Лекция 1

Вводная лекция

1. Графы. Определение

Граф G задается множеством точек или вершин х1, хг,..., хп (которое обозначается через X) и множеством линий или ребер а1,а2,..., ат (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (X, А).

Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом (рис. 1.1 (а)). Если ребра не имеют ориентации, то граф называется неориентированным (рис. 1.1(6)). В случае когда G =(X, А) является ориентированным графом и мы хотим пренебречь направленностью дуг из множества А, то неориентированный граф, соответствующий G, будем обозначать как

В этой книге, когда дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т. е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй). Так, например, на рис. 1.1(а) обозначение относится к дуге а1, а — к дуге а2.

Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин X и соответствия Г, которое показывает, как между собой связаны вершины. Соответствие Г называется отображением множества X в X, а граф в этом случае обозначается парой G =(X, Г).

Для графа на рис. 1.1(а) имеем , т. е. вершины являются конечными вершинами дуг, у которых начальной вершиной является х1.


x2

Рис. 1.1.(а) Ориентированный граф, (б) Неориентированный граф, (в) Смешанный граф.

В случае неориентированного графа или графа, содержащего и дуги, и неориентированные ребра (см., например, графы, изображенные на рис. 1.1(6) и 1.1(в)), предполагается, что соответствие Г задает такой эквивалентный ориентированный граф, который получается из исходного графа заменой каждого неориентированного ребра двумя противоположно направленными дугами, соединяющими те же самые вершины. Так, например, для графа, приведенного на рис. 1.1(6), имеем и т. д.

Поскольку представляет собой множество таких вершин , для которых в графе G существует дуга , то через естественно обозначить множество вершин , для которых в G существует дуга . Отношение принято называть обратным соответствием. Для графа, изображенного на рис l.l(a), имеем

и т. д.

Вполне очевидно, что для неориентированного графа для всех .

Когда отображение Г действует не на одну вершину, а на множество вершин , то под понимают объединение,

т. е. является множеством таких вершин , что для каждой из них существует дуга в G, где . Для графа, приведенного на рис. 1.1(а), и .

Отображение записывается как . Аналогично «тройнoe» отображение записывается как и т. д. Для графа, показанного на рис. 1.1(а), имеем:

и т.д.

Аналогично понимаются обозначения и т. д

2. Пути и маршруты

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

Так, на рис. 1.2 последовательности дуг

(1.1)

(1.2)

(1 3)

являются путями.

Рис. 1.2.

Дуги имеющие общие концевые вершины, называются смежными. Две вершины и называются смежными, если какая-нибудь из двух дуг и или обе одновременно присутствуют в графе. Так, например, на рис. 1.2 дуги , как и вершины и , являются смежными, в то время как дуги или вершины не являются смежными.

Ориентированной цепью (или, короче, орцепъю) называется такой путь, в котором каждая дуга используется не больше одного раза. Так, например, приведенные выше пути (1.1) и (1.2) являются орцепями, а путь (1.3) не является таким, поскольку дуга в нем используется дважды.

Простой орцепъю называется такой путь, в котором каждая вершина используется не более одного раза. Например, путь (1.2) является простой орцепью, а пути (1.1) и (1.3) — нет. Очевидно, что простая орцепь является также орцепью, но обратное утверждение неверно. Например, путь (1.1) является орцепью, но не простой орцепью, путь (1.2) является орцепью и простой орцепью, а путь (1.3) не является ни орцепью, ни простой орцепью. Маршрут есть неориентированный «двойник» пути, и это понятие рассматривается в тех случаях, когда можно пренебречь направленностью дуг в графе. Таким образом, маршрут есть последовательность ребер в которой каждое ребро исключением, возможно, первого и последнего ребер, связано с ребрами своими двумя концевыми вершинами. Последовательности дуг

(1.4)

(1.5)

и

(1.6)

в графе, изображенном на рис. 1.2, являются маршрутами; черта над символом дуги означает, что ее ориентацией пренебрегают, т. е. дуга рассматривается как неориентированное ребро.

Точно так же, как мы определили орцепи и простые орцепи, можно определить цепи и простые цепи. Так, например, маршрут (1.4) есть цепь и простая цепь, маршрут (1.5) — цепь, но не простая цепь, а маршрут (1.6) не является ни цепью, ни простой цепью.

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

2.1. Веса и длина пути

Иногда дугам графа G сопоставляются (приписываются) числа — дуге ставится в соответствие некоторое число , называемое весом, или длиной, пли стоимостью (ценой) дуги. Тогда граф G называется графом со взвешенными дугами. Иногда веса (числа vi) приписываются вершинам xi графа, и тогда получается граф со взвешенными вершинами. Если в графе веса приписаны и дугам, и вершинам, то он называется просто взвешенным.

При рассмотрении пути , представленного последовательностью дуг за его вес (или длину, или стоимость) принимается число , равное сумме весов всех дуг, входящих в , т.е.

Таким образом, когда слова «длина», «стоимость», «цена» и «вес» применяются к дугам, то они эквивалентны по содержанию, и в каждом конкретном случае выбирается такое слово, которое

Рис. 1.3.

ближе подходит по смыслу и совпадает с принятым в литературе.

Длиной (или мощностью) пути называется число дуг, входящих в него.

3. Петли, ориентированные циклы и циклы

Петлей называется дуга, начальная и конечная вершины которой совпадают. На рис. 1.3, например, дуги являются петлями.

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

Так, например, в графе, приведенном на рис. 1.3, последовательности дуг

(1.7)

(1.8)

(1.9)

являются замкнутыми путями.

Пути (1.7) и (1.9) являются замкнутыми простыми орцепями (контурами, или простыми орциклами), поскольку в них одна и та же вершина используется только один раз (за исключением начальной и конечной вершин, которые совпадают), а путь (1.8) не является контуром, так как вершина х1 используется в нем дважды. Контур, проходящий через все вершины графа, имеет особое значение и называется гамильтоновым контуром. Конечно, не все графы обладают гамильтоновыми контурами. Так, например, контур (1.9) является гамильтоновым контуром графа, приведенного на рис. 1.3, а граф на рис. 1.2 не имеет гамильтоновых контуров, поскольку не существует такой дуги, для которой х1 была бы конечной вершиной.

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

На рис. 1.3 маршруты

(1.10)

и

(1.11)

4. Степени вершины

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

Таким образом, на рис. 1.3 полустепень исхода вершины x6, обозначаемая через , равна , и полустепень захода вершины x6, обозначаемая через , равна .

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

(1.12)

где п — число вершин и т — число дуг графа G.

Для неориентированного графа G=(X, Г) степень вершины xi определяется аналогично — с помощью соотношения , связанными и когда не может возникнуть недоразумений, мы будем обозначать степень вершины xi через di.

5. Подграфы

Пусть дан граф G=(X, А). Остовным подграфом Gp графа G называется граф (X, Ар), для которого . Таким образом, остовный подграф имеет то же самое множество вершин, что и граф G, но множество дуг подграфа Gp является подмножеством множества дуг исходного графа.

Граф на рис. 1.4(б) — остовный подграф Gp графа G, изображенного на рис. 1.4(а).

Пусть дан граф G = (X, Г). Порожденным подграфом 2) G3, называется граф , для которого и для каждой вершины . Таким образом, порожденный подграф состоит из подмножества вершин множества вершин исходного графа и всех таких дуг графа G, у которых конечные и начальные вершины принадлежат подмножеству X3. Часто бывает удобно обозначать подграф G3 просто символом ; мы будем в дальнейшем использовать такое обозначение, если нет опасности внесения путаницы.

На рис. 1.4(в) показан порожденный подграф графа, приведенного на рис. 1.4(а), содержащий только вершины и дуги, которые их связывают.

Рис. 1.4. (а) Граф, (б) Остовный подграф, (в) Порожденный подграф, (г) Подграф.

Соединяя приведенные выше два определения, можно сформулировать определение подграфа. Граф, показанный на рис. 1.4(г), является подграфом графа, приведенного на рис. 1.4(а).

Рассмотрим граф, вершины которого представляют сотрудников некоторого учреждения, а дуги — линии связи между сотрудниками. Тогда граф, представляющий только наиболее важные каналы связи данного учреждения, является остовным подграфом; граф, который подробно представляет линии связи только какой-то части этого учреждения (например, отделения), является порожденным подграфом, а граф, который представляет только важные линии связи в пределах отделения, является подграфом.

6. Типы графов

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

Рис. 1.5 (а) Симметрический граф, (б) Антисимметрический граф, (в) Полный симметрический граф, (г) Полный антисимметрический граф.

Граф (X, А) называется симметрическим, если в множестве дуг А для любой дуги существует также противоположно ориентированная дуга .

Антисимметрическим графом 1) называется такой граф, для которого справедливо следующее условие: если то в множестве А нет противоположно ориентированной дуги, т. е. . Очевидно, что в антисимметрическом графе нет петель.

На рис. 1.5(а) показан симметрический граф, а на рис. 1.5(б)-антисимметрический граф.

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

Комбинируя приведенные выше определения, можно дать определения полного симметрического графа (пример такого графа см. на рис. 1.5(в)) и полного антисимметрического графа (один из таких графов показан на рис. 1.5(г)). Граф последнего типа часто называют также турниром.

Неориентированный граф G=(X, А) называют двудольным, если множество его вершин X может быть разбито на такие два подмножества Ха и Хb, что каждое ребро имеет один конец в Ха,с другой в Хb. Ориентированный граф G называется двудольным, если его неориентированный двойник —двудольный граф. Легко доказать следующее утверждение.

Теорема 1. Неориентированный граф G является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины.

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

Двудольный граф называют полным, если для любых двух вершин существует ребро . Если —число вершин множества —равно r и , то полный неориентированный двудольный граф обозначается через .

Граф G=(X, А) называется планарным, если он может быть нарисован на плоскости (или сфере) таким образом, что произвольные две дуги графа не пересекаются друг с другом. На рис. 1.6(а) показан полный граф К5, а на рис. 1.6(б)—полный двудольный граф К3,3, которые являются непланарными.

Рис. 1.6. Непланарные графы Куратовского. (a) K5. (б) K3,3.

7. Сильно связные графы и компоненты графа

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

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

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

Если для некоторой пары вершин орграфа не существует маршрута, соединяющего их, то такой орграф называется несвязным.

Граф приведенный на рис. 1.7(а), как легко проверить, сильно связанный. Граф, показанный па рис. 1.7(б), не является сильным (так как в нем нет пути из х1, в х3), но односторонне связный. Граф, изображенный на рис. 1.7(в), не является ни сильным, ни односторонним, поскольку в нем не существует путей от х2 к х5 и от х5 к х2. Он — слабо связный. Наконец, граф, приведенный на рис. 1.7(г), является несвязным.

Пусть дано некоторой свойство Р, которым могут обладать графы. Максимальным подграфом графа G относительно свойства Р называется порожденный подграф графа G, обладающий этим свойством и такой, что не существует другого порожденного подграфа , у которого , и который также обладает свойством Р. Так, например, если в качестве свойства Р взята сильная связность, то максимальным сильным подграфом графа С является сильный подграф, который не содержится в любом другом сильном подграфе. Такой подграф называется сильной компонентой графа С. Аналогично, односторонняя компонента представляет собой односторонний максимальный подграф, а слабая компонента — максимальный слабый подграф.

Рис. 1.7. (а) Сильно связанный граф, (б) Односторонне связный граф, (в) Слабо связный граф, (г) Несвязный граф.

Например, в графе G, приведенном на рис. 1.7(6), подграф является сильной компонентой графа G. С другой стороны, подграфы и не являются сильными компонентами (хотя и являются сильными подграфами), поскольку они содержатся в графе и, следовательно, не максимальные. В графе, показанном на рис. 1.7(в). подграф является односторонней компонентой. В графе, приведенном на рис. 1.7(г), оба подграфа и являются слабыми компонентами, и у этого графа только две такие компоненты.

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

8. Матричные представления

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

8.1. Матрица смежности

Пусть дан граф G, его матрица смежности обозначается через и определяется следующим образом:

, если в G существует дуга ,

если в G нет дуги .

Таким образом, матрица смежности графа, изображенного на рис. 1.8, имеет вид

Матрица смежности полностью определяет структуру графа. Например, сумма всех элементов строки матрицы дает полустепень исхода вершины , а сумма элементов столбца — полустепень захода вершины . Множество столбцов, имеющих 1 в строке ,. есть множество , а множество строк, которые имеют 1 столбце , совпадает с множеством .

Возведем матрицу смежности в квадрат. Пусть элемент матрицы А2 определяется по формуле

(1.14)

Слагаемое в уравнении (1.14) равно 1 тогда и только тогда, когда оба числа и равны 1, в противном случае оно равно 0.

Поскольку из равенств следует существование пути длины 2 из вершины к вершине , проходящего через вершину , то равно числу путей длины 2, идущих из в .

Рис. 1.8.

Аналогично если является элементом матрицы , то равно числу путей (не обязательно орцепей или простых орцепей) длины р, идущих от к .

8.2. Матрица инциденций

Пусть дан граф G с n вершинами и т дугами. Матрица инциденций графа G обозначается через и является матрицей размерности , определяемой следующим образом:

, если является начальной вершиной дуги ,

, если является конечной вершиной дуги ,

, если не является концевой вершиной дуги или если является петлей.

Для графа, приведенного на рис. 1.8, матрица инциденций имеет вид

Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец либо содержит один элемент, равный 1, и один – равный -1, либо все элементы столбца равны 0.

Если G является неориентированным графом, то его матрица инциденций определяется так же, как и выше, за исключением того, что все элементы, равные —1, заменяются на +1.


Лекция 1 Вводная лекция

Поделись с друзьями



Рекомендуем посмотреть ещё:



Теория графов: основные понятия и задачи Плетение на леске жгутом бисер

Связанными называются две вершины графа для которых Дискретная математика - Теория графов
Связанными называются две вершины графа для которых Глоссарий теории графов Википедия
Связанными называются две вершины графа для которых Дискретная математика. Лекция 13
Связанными называются две вершины графа для которых Основные понятия теории графов
Связанными называются две вершины графа для которых 2.3 Элементы теории графов
Связанными называются две вершины графа для которых Теория графов
Связанными называются две вершины графа для которых Mathmetod - Графы


ШОКИРУЮЩИЕ НОВОСТИ