INTUIT.ru::Интернет-Университет Информационных Технологий

Интернет-Университет Информационных Технологий

http://www.INTUIT.ru

Графы и их применение

2. Лекция: Некоторые определения теории графов
Определения и примеры. Удаление ребер, мосты. Деревья. Перечисление деревьев.

Определения и примеры

Матрицей смежности графа с множеством вершин $\{v_{1} \dts$ $v_{n}\}$ (соответствующей данной нумерации вершин) называется матрица ${A=(a_{ij})}$ размера $n\times n$ , в которой элемент $a_{ij}$ равен числу ребер в , соединяющих $v_{i}$ и $v_{j}$ . Можно получить несколько различных матриц смежности данного графа, меняя обозначения его вершин. Это приведет к изменению порядка строк и столбцов матрицы . Но в результате всегда получится симметричная матрица из неотрицательных целых чисел, обладающая тем свойством, что сумма чисел в любой строке или столбце равна степени соответствующей вершины. Каждая петля учитывается в степени вершины один раз. Обратно, по любой заданной симметричной матрице из неотрицательных целых чисел легко построить граф, единственный с точностью до изоморфизма, для которого данная матрица является матрицей смежности. Отсюда следует, что теорию графов можно свести к изучению матриц особого типа.

Матрицей инциденций простого графа с множеством вершин $e_{1},\ldots$ , $e_{m}$ называется матрица $A=(a_{ij})$ размера $m\times n$ , у которой $a_{ij}^{} = 1$ , если вершина $v_{j}$ инцидентна ребру $e_{i}$ , и $a_{ij} = 0$ , в противном случае.

Граф, у которого множество ребер пусто, называется вполне несвязным или пустым графом. Будем обозначать вполне несвязный граф с вершинами через $N_{n}$ . Простой граф, в котором любые две вершины смежны, называется полным графом. Полный граф с вершинами обычно обозначается через $K_{n}$ . Граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом. Если степень каждой вершины равна , то граф называется регулярным степени . Регулярные графы степени 3 называются также кубическими, или трехвалентными графами. Каждый вполне несвязный граф является регулярным степени , а каждый полный граф $K_{n}$ — регулярным степени . Среди регулярных графов особенно интересны платоновы графы — графы, образованные вершинами и ребрами пяти правильных многогранников — платоновых тел: тетраэдра, куба, октаэдра, додекаэдра и икосаэдра.

Объединение и соединение двух графов. Существует несколько способов соединения двух графов для образования нового, большего графа. Рассмотрим два из них. Пусть даны два графа $G_{1} =(V(G_{1}),E(G_{1} ))$ , $G_{2} =(V(G_{2}),E(G_{2}))$ , причем множества $V(G_{1}),V(G_{2})$ не пересекаются. Тогда объединением $G_{1} \bigcup G_{2}$ графов $G_{1},G_{2}$ называется граф с множеством вершин $V(G_{1})\bigcup V(G_{2})$ и семейством ребер $E(G_{1} )\bigcup E(G_{2}).$ Можно также образовать соединение графов $G_{1},G_{2}$ , обозначаемое $G_{1}+ G_{2}$ , взяв их объединение и соединив ребрами каждую вершину графа $G_{1}$ с каждой вершиной графа $G_{2}^{}$ .

Пример матрицы смежности. Пусть дан граф

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

$\begin{pmatrix} {1} & {1} & {1} & {0} \\ {1} & {0} & {2} & {1} \\ {1} & {2} & {0} & {1} \\ {0} & {1} & {1} & {0} \end{pmatrix}$

Обхватом графа называется длина его кратчайшего цикла. Множество ребер графа называется независимым, если оно не содержит циклов, то есть никакая совокупность ребер из не образует цикла. Диаметром $\delta$ связного графа называется максимальное возможное расстояние между любыми двумя его вершинами. Центром графа называется такая вершина , что максимальное расстояние между и любой другой вершиной является наименьшим из всех возможных. Это расстояние называется радиусом . Таким образом,

$r=\min \limits_{v} (\max \limits_{w} d(v,w)),$

где — расстояние между и .

Удаление ребер, мосты

При удалении ребра $\{a,b\}$ из графа получается граф с теми же вершинами, что и граф , и всеми ребрами, кроме ребра $\{ a,b\}$ . При удалении ребра из связного графа новый граф может оказаться как связным, так и несвязным. Ребро $\{ a,b\}$ называется мостом графа , если в графе, полученном после удаления из ребра $\{ a,b\}$ , вершины и оказываются несвязными. Существует несколько признаков мостов. Известно, что признак какого-то объекта может заменить его определение, то есть по признаку можно распознать объект. Рассмотрим признаки мостов.

Ребро $\{ a,b\}$ является мостом в том и только в том случае, если $\{a,b\}$ — единственный путь, соединяющий вершины и .
Ребро $\{a,b\}$ является мостом в том и только в том случае, если найдутся две вершины и , такие, что каждый путь, соединяющий их, содержит и .
Ребро $\{a,b\}$ является мостом в том и только в том случае, если оно не принадлежит ни одному циклу.

Докажем справедливость третьего признака.

Прямая теорема. Если ребро $\{a,b\}$ не принадлежит ни одному циклу, то $\{ a,b\}$ — мост.

Так как ребро $\{a,b\}$ не принадлежит ни одному циклу, при его удалении не останется пути, связывающего и , то есть $\{a,b\}$ является мостом.

Обратная теорема. Если ребро $\{a,b\}$ — мост, то $\{a,b\}$ не принадлежит ни одному циклу.

Если бы ребро $\{a,b\}$ принадлежало циклу, то при удалении ребра $\{a,b\}$ остался бы второй путь, связывающий и , то есть ребро $\{a,b\}$ не было бы мостом. Следовательно, $\{a,b\}$ не принадлежит циклу.

Деревья

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

Пример. Кубок по настольному теннису разыгрывается по олимпийской системе. Встречи проводятся без "ничьих". К очередному туру допускается только победившая в предыдущем туре команда. Проигравшие команды выбывают из игры. Для завоевания кубка команда должна победить во всех турах. На участие в розыгрыше кубка поданы заявки от команд.

Схема проведения игр изображается графом

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

Какую информацию можно получить с помощью этого дерева?

Непосредственно с него считываются:

Число всех участников розыгрыша кубка (число вершин нижнего "яруса").
Число этапов проведения розыгрыша (число "ярусов" из вершин в дереве, не считая нижнего).
Число команд, участвующих в финала, в финала, в финала (число вершин, соответственно, в четвертом сверху ярусе, в третьем сверху ярусе, во втором сверху ярусе).
Число матчей, которые придется сыграть командам для выявления обладателя кубка (число вершин в графе без нижнего "яруса"). Хотя это число легко определяется и без дерева. (В каждом матче выбывает одна команда. Для того чтобы была выявлена команда-победительница, остальные должны выбыть из соревнования. Поэтому число матчей равно числу команд без одной, а именно ).

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

Пример.

Изображен лес, состоящий из четырех компонент, каждая из которых является деревом.

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

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

В общем случае обозначим через произвольный граф с вершинами, ребрами и компонентами. Применяя описанную выше процедуру к каждой компоненте , получим в результате граф, называемый остовным лесом. Число удаленных в этой процедуре ребер называется циклическим рангом или циклическим числом графа и обозначается через $\gamma (G)$ . Мы видим, что $\gamma (G)=m-n+k$ и является неотрицательным целым числом. Таким образом, циклический ранг дает меру связности графа: циклический ранг дерева равен нулю, а циклический ранг циклического графа равен единице. Удобно также определить коциклический ранг или ранг разреза графа как число ребер в его остовном лесе. Коциклический ранг обозначается через $\chi (G)$ и равен .

Теорема 2.1 Дерево с вершинами имеет ребро.

Доказательство Для того чтобы из одного дерева , не являющегося изолированной вершиной, получить два дерева с теми же вершинами, необходимо удалить из одно ребро. Для образования трех деревьев необходимо удалить из два каких-нибудь ребра. Самое большее, из дерева с вершинами можно получить деревьев, каждое из которых является изолированной вершиной. Для этого необходимо удалить ребро из дерева . Итак, действительно, в дереве с вершинами — ребро.

Перечисление деревьев

Теория перечисления графов занимается разработкой методов подсчета числа неизоморфных графов, обладающих тем или иным свойством. Вероятнее всего, эта теория возникла в 70-х годах девятнадцатого столетия и связана с именем Кэли, который пытался найти число насыщенных углеводородов $C_{n}H_{2n+2}$ , содержащих данное число атомов углерода. Как он обнаружил, эта задача сводится к подсчету числа деревьев, у которых степень каждой вершины равна либо четырем, либо единице. Сейчас многие задачи по перечислению графов решены.

Рассмотрим несколько определений

Помеченный граф с вершинами — это граф, у которого все вершины "помечены" целыми числами от 1 до . Более точно, определим распределение меток в графе с вершинами как взаимно однозначное соответствие между множеством вершин и множеством $\{1\dts n\}$ ; тогда помеченным графом называется пара $\{G,\varphi\}$ , где — граф, а $\varphi$ — распределение меток в . Числа $1\dts n$ будем называть метками графа и обозначать вершины через $v_{1} \dts v_{n}$ . Назовем два помеченных графа $(G_{1},\varphi_{1}),(G_{2},\varphi_{2})$ изоморфными, если существует изоморфизм между $G_{1}$ и $G_{2}$ , сохраняющий распределение меток в этих графах.

Пример. Различные распределения меток в дереве с четырьмя вершинами:

Внимательное изучение рисунка позволяет заметить, что второе помеченное дерево является просто перевернутым первым, а отсюда следует, что эти два помеченных дерева изоморфны. С другой стороны, ни одно из них не изоморфно третьему помеченному дереву — достаточно посмотреть на степень вершины $v_{3}$ . Следовательно, общее число различных распределений меток в данном дереве должно равняться , поскольку "переворот" любого распределения меток не приводит к новому объекту. Аналогично, общее число различных распределений меток в дереве, изображенном на рисунке, должно равняться четырем, так как его центральная вершина может быть помечена четырьмя различными способами, каждый из которых однозначно определяет распределение меток. Отсюда следует, что число всех (неизоморфных) помеченных деревьев с четырьмя вершинами равно шестнадцати. Рассмотрим теорему Кэли, обобщающую этот результат на помеченные деревья с вершинами.

Теорема2.2(Кэли, 1889) Существует ровно $n^{n-2}$ различных помеченных деревьев с вершинами.

Доказательство теоремы: Moon J.W. Counting labeled trees, Canadi\-an Math. Congress, Montreal, 1970.