ГРАФЫ

Графы возникли в восемнадцатом столетии, когда известный мате­матик, Леонард Эйлер, пытался решить теперь уже классическую задачу о Кенигсбергских мостах. В то время в городе Кенигсбер­ге было два oстровa, соединенных семью мостами с берегами реки Преголь и друг с другом так, как показано на рис. 7.1. 3адача со­стоит в следующем: осуществить прогулку по городу таким образом, чтобы, пройдя ровно по одному разу по каждому мосту, вернуться в то же место, откуда начиналась прогулка. Решая эту задачу, Эйлер изобразил Кенигсберг в виде графа, отождествив его вершины с частями города, а ребра - с мостами, которыми связаны эти части. Как мы покажем в § 7.1, Эйлеру удалось доказать, что искомого маршрута обхода города не существует.

Рисунок 7.1. Схема старого Кенигсберга

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

Графы и терминология

На рис. 7.1 изображены семь мостов Кенигсберга так. как они были расположены в восемнадцатом столетии. В задаче, к которой oбpa­тился Эйлер, спрашивается: можно ли найти маршрут прогулки, ко­торый проходит ровно один раз по каждому из мостов и начинается и заканчивается в одном и том же месте города?

Модель задачи - это граф, состоящий из множества вершин и множества ребер, соединяющих вершины. Вершины А, В, С и D символизируют берега реки и острова, а ребра а,в , c ,d, f и g обозначают семь мостов (см. рис. 7.2). Искомый маршрут (если он существует) соответствует обходу ребер графа таким образом, что каждое из них проходится только один раз. Проход ребра, очевидно, соответствует пересечению реки по мосту.

Рисунок 7.2. Модель задачи о мостах Кенигсберга

Граф, в котором найдется маршрут, найдется маршрут, на­чинающийся и заканчивающийся в одной вершине, и проходящий по всем ребрам графа ровно один раз, называется зйлеровым графом. Последовательность вер­шин (может быть и с повторениями), через которые проходит иско­мый маршрут, как и сам маршрут, называется эйлеровым циклом . Эйлер заметил, что если в графе есть эйлеров цикл, то для каждого ребра, ведущего в какую-то вершину, должно найтись другое ребро, выходящее из этой вершины 1 , и получил из этого простого наблюдсния такой вывод: если в данном графе существует эйлеров цикл, то к каждой вершине должно подходить четное число ребер.

Кроме того, Эйлеру удалось доказать и противоположное утвер­ждение, так что граф, в котором любая пара вершин связана не­которой последовательностью ребер, является Эйлеровым тогда и только тогда, когда все его вершины имеют четную степень. Степенью вершины v называется число δ(v) ребер, ей инцидентных 2 .

Теперь совершенно очевидно, что в графе, моделирующем задачу о мостах Кенигсберга, эйлерова цикла найти нельзя. Действитель­но, степени всех его вершин нечетны: δ(B ) = δ(С) = δ(D) = 3 и δ(A ) = 5. С легкой руки Эйлера графы, подобные тому, который мы исследовали при решении задачи о мостах, стали использовать­ при решении многих практических задач, а их изучение выросло в значительную область математики.

Простой граф определяется как пара G = (V, Е), где V - ко­нечное множество вершин, а Е - конечное множество ребер, при­чем не может содержать петель (ребер, начинающихся и закан­чивающихся в одной вершине) и кратных ребер (кратными назы­ваются несколько ребер, соединяющих одну и ту же пару вершин). Граф, изображенный на рис. 7.2. не является простым, поскольку, например, вершины А и В соединяются двумя ребрами (как раз эти ребра и называются кратными).

Две вершины u и v в простом графе называются смежными , если они соединяются каким-то ребром е , про которое говорят, что оно инцидентно вершине u (и v). Таким образом, мы можем предста­влять себе множество Е ребер как множество пар смежных вершин, определяя тем самым нерефлексивное, симметричное отношение на множестве V. Отсутствие рефлексивности связано с тем, что в простом графе нет петель, т. е. ребер, оба конца которых находятся в одной вершине. Симметричность же отношения вытекает из того факта, что ребро е , соединяющее вершину и с v, соединяет и v с и (иначе говоря, ребра не ориентированы, т. е. не имеют направления). Единственное ребро простого графа, соединяющее пару вершин u и v, мы будем обозначать как иv (или vи).

Логическая матрица отношения на множестве вершин графа, котopoe задается его ребрами, называется ,матрицей смежности. Симметричность отношения в терминах матрицы смежности М озна­чает, что М симметрична относительно главной диагонали. А из-за нерефлексивности этого отношения на главной диагонали матрицы М стоит символ «Л».

Пример 7.1. Нарисуйте граф G(V, Е) с множеством вершин V = {а, Ь, с, d, е} и множеством ребер E = {ab, ae, bc, bd, ce, de}. Выпишите его матрицу смежности.

Решение. Граф G показан на рис. 7.3.

Рисунок 7.3.

Его матрица смежности имеет вид:

Для восстановления графа нам достаточно только тех элементов матрицы смежности, которые стоят над главной диагональю.

Подграфом графа G = (V, E) называется граф G’ = (V’, E’), в котором E’ C E и V’ C V.

Пример 7.2 Найдите среди графиков H, K и L, изображенных на рис. 7.4, подграфы графа G.

Решение. Обозначим вершины графов G, H и K как показано на рис. 7.5. Графы H и K – подграфы в G, как видно из наших обозначений. Граф L не является подграфом в G, поскольку у него есть вершина индекса 4, а у графа G такой нет.

Маршрутом длины k в графе G называется такая последовательность вершин v 0 , v 1 , …, v k , что для каждого i = 1, …, k пара v i – 1 v i образует ребро графа. Мы будем обозначать такой маршрут через v 0 v 1 … v k . Например 1 4 3 2 5 – это маршрут длины 4 в графе G из примера 7.2.

G H

K L

Рисунок 7.4.

Циклом в графе принято называть последовательность вершин v 0 , v 1 , … , v k , каждая пара которых является концами одного ребра, причем v 0 = v 1 , а остальные вершины (и ребра) не повторяются. Иными словами, цикл – это замкнутый маршрут, проходящий через каждую свою вершину и ребро только один раз

1 2 1 2 3

Рисунок 7.5

Пример 7.3. Найдите циклы в графе G из примера 7.2.

Решение. В этом графе есть два разных цикла длины 5:

1 3 2 5 4 1 и 1 2 5 4 3 1

Мы можем пройти эти циклы как в одном направлении так и в другом, начиная с произвольной вершины цикла. Кроме того, в графе есть три разных цикла длины 4:

1 2 5 4 1, 1 2 3 4 1 и 2 5 4 3 2,

и два цикла длины 3:

1 2 3 1 и 1 3 4 1.

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

Граф, называют связным, если любую пару его вершин соединяет какой – нибудь маршрут. Любой общий граф можно разбить на подграфы, каждый из которых окажется связным. Минимальное число таких связных компонент называется числом связности графа и обозначается через c (G ) . Вопросы связности имеют важное значение в приложениях теории графов к компьютерным сетям. Следующий алгоритм применяется для определения числа связности графа.

Алгоритм связности.

Пусть G = (V, E) – граф. Алгоритм предназначен для вычисления значения c = c (G ), т.е. числа компонент связности данного графа G.

V’ :=V;

while V’≠ ø do

Выбрать y Є V ’

Найти вершины, соединяющие маршрутом с у;

Удалить вершину у из V ’ и

соответствующие ребра из Е;

c := c +1;

Пример 7.4. Проследите за работой алгоритма связности на графе, изображенном на рис. 7.6.

Рисунок 7.6.

Решение. Смотри табл. 7.1.

Таблица 7.1.

Итак, c (G ) = 3. Соответствующие компоненты связности приведены на рис. 7.7.

5

4. Представление информации в форме графа

Вы, вероятно, имеете представление о компьютерных сетях. Возможно, компьютеры в школьном кабинете информатики объединены в локальную сеть или вы работали в Интернете, или пользовались услугами электронной почты. Понятно, что сеть образуется только тогда, когда компьютеры каким-либо образом соединены между собой каналами передачи данных. Размещение абонентов сети (подключённых к ней компьютеров или других систем автоматической обработки данных) и способ их соединения друг с другом называется конфигурацией сети. Продемонстрировать различные типы конфигураций вычислительных сетей можно, например, с помощью таких информационных моделей, как графы. Граф - совокупность точек, соединённых между собой линиями. Точки называют вершинами графа. Они могут изображаться точками, кружочками, прямоугольниками и пр. Линии, соединяющие вершины, называются дугами (если задано направление от одной вершины к другой) или рёбрами (если направленность двусторонняя, то есть направления равноправны). Две вершины, соединенные ребром (дугой) называются смежными. Вершины и рёбра графа могут характеризоваться некоторыми числовыми величинами. Например, может быть известна длина ребра или «стоимость прохождения» по нему. Такие характеристики называют весом, а граф называется взвешенным.

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

На рис.3 представлены различные типы конфигураций локальных вычислительных сетей (ЛВС), являющиеся информационными моделями структур ЛВС, представленными в виде графов:

Шинная конфигурация, когда к незамкнутому каналу с некоторыми интервалами подключаются отдельные абоненты (К) информация от абонента-источника распространяется по каналу в обе стороны;

Кольцевая конфигурация, когда каждый абонент непосредственно связан с двумя соседними абонентами, а информация передаётся по замкнутому кольцу, чаще всего в одну сторону;

Звездообразная конфигурация, в центре которой находится центральный коммутатор (ЦК), который последовательно опрашивает абонентов и предоставляет им право на обмен данными;

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

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

Рис.3 Различные типы конфигураций локальных вычислительных сетей

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

Рис. 4 Различные изображения одного и того же графа

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

На рис.5 представлены модели молекул бутана и изобутана, каждая из которых имеет формулу С4Н10, то есть состоит из 4 атомов углерода и 10 атомов водорода. Имея одну и ту же формулу, бутан и изобутан имеют различные химические свойства, так как способы соединения атомов (структура молекул) различны. Расположение атомов в молекуле при различных способах их соединения хорошо представимо графом.

Рис.5 Модели молекул бутана и изобутана

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

Рассмотрите граф понятий темы «Четырёхугольники» из курса геометрии (рис.6). Не правда ли, хорошая «шпаргалка»?

Рис.6. Граф понятий темы «Четырёхугольники»

В практической деятельности модели в форме графов часто используются для представления видов и порядка выполнения работ. Возможно, вам знакомы такие термины, как «сетевой график работ», «сетевой график строительства». Часто наряду со словесным или табличным описанием сетевые графики сопровождаются и изображением в виде графа, вершинами которого являются конкретные виды работ, а дугами задаётся возможный порядок их выполнения.

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

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

Графы, представленные на рис.7 могут быть описаны, например, следующими способами. Символическая запись: а(1,2) b(l,4) c(2,4) d(3,5) e(4,5) ,(3,4)

Табличная запись:

Рис.7. Графы, имеющие одинаковые описания в виде таблицы и символической записи

Представление данных в форме дерева

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

Модель управления предприятием (школой, театральным коллективом и т. д.) очень удобно представлять в виде дерева.

Вам хорошо известно понятие «родословное дерево» и вы можете изобразить в такой форме ваши родственные отношения.

Каталог файлов на диске, также как и библиотечный каталог - примеры информационных моделей в форме дерева. Дерево - это граф, предназначенный для отображения таких связей между объектами, как вложенность, подчиненность, наследование и т. п.

Строится он следующим образом

Сначала рисуем «главную» вершину, которая не зависит ни от одной другой вершины. Эта вершина называется корнем дерева и является единственной вершиной 1-го уровня. Далее добавляем вершины 2-го уровня. Их может быть сколько угодно, и все они обязательно связаны с корнем - вершиной 1-го уровня, но не связаны между собой. На следующем шаге добавим вершины 3-го уровня. Каждая из них будет связана ровно с одной вершиной 2-го уровня (больше ни с одной другой вершиной). К любой вершине 2-го уровня может быть подсоединено сколько угодно вершин 3-го уровня (в том числе, ни одной). Следующий шаг - добавка вершин 4-го уровня, каждая из которых будет связана ровно с одной вершиной 3-го уровня (и не связана больше ни с чем). И так далее. На каждом шаге добавляем вершины очередного уровня, каждая из которых будет связана ровно с одной вершиной предыдущего уровня и не будет иметь никаких иных связей. Полученный граф напоминает ветвящийся куст, который «растет сверху вниз»: верхние уровни имеют меньшие номера, нижние - большие. Вообще говоря, дерево может быть и неориентированным графом, но чаще дерево ориентировано, причем дуги направлены от верхних вершин к нижним. Верхняя вершина называется предком для связанных с ней нижних вершин, а нижние вершины - потомками соответствующей верхней вершины. На любом дереве существует единственная вершина, не имеющая предка, - корень - и может быть сколько угодно вершин, не имеющих потомков, - листьев. Все остальные вершины имеют ровно одного предка и сколько угодно потомков. Если не принимать во внимание направленность связей, то в дереве из любой вершины можно по линиям дойти до любой другой вершины, причем по одному единственному пути. В виде дерева удобно изображать системы, в которых нижние вершины в каком-то смысле «подчинены» верхним. Верхняя вершина может изображать начальника, нижние - подчиненных; верхняя - систему, нижние - ее компоненты; верхняя - множество объектов, нижние - входящие в него подмножества; верхняя вершина - предка, нижние - потомков и т. д. Формализация в случае построения дерева (иерархического графа) сводится к выявлению основного (главного, центрального) элемента рассматриваемого объекта (вершина нулевого уровня, которую часто называют корнем), элементов, которые находятся в непосредственном подчинении от основного (вершины 1-го уровня). Затем определяются вершины, находящиеся в непосредственном «подчинении» от вершин 1-го уровня (вершины 2-го уровня) и так далее. Изображать построенное дерево отношений можно в любом направлении - это уже дело эстетического вкуса разработчика модели. В научной и учебной деятельности с помощью деревьев часто представляют классификацию изучаемых объектов.

Классифицирование - распределение объектов по классам в зависимости от их общих признаков, фиксирующее закономерные связи между классами объектов в единой системе данной отрасли знания.

Классификация (от лат. classis - разряд + facere - делать) - система соподчиненных понятий (классов объектов, явлений) в какой-либо отрасли знания, составленная на основе учёта общих признаков объектов и закономерных связей между ними.

Классификация позволяет ориентироваться в многообразии объектов и является источником знания о них. Очень важен выбор основания классификации - то есть признака, на основании которого объекты разбиваются на классы. Выбор разных оснований приводит к разным классификациям.

На рис.8 вы видите классификацию, предложенную Григорием Великим, которая призвана была показать, что человек имеет что-то общее со всеми видами существующих в мире вещей, и поэтому его справедливо называют «вселенной в миниатюре». Обратите внимание, что объекты здесь разбиваются всегда на два класса. Такая классификация носит название дихотомической.

Рис.8. Классификация «того, что есть» Григория Великого

Представленная на рис.9 классификация принтеров построена с использованием различных оснований деления

Рис.9 Классификация принтеров

Важным видом исторических классификаций является построение родословных или генеалогических деревьев. Они бывают самого разного вида: с указанием только прямых потомков (рис.10); с включением жён (мужей) и их родственников и др.

Рис.10 Родословное дерево великих и удельных князей Владимирских и Московских, XIII-XIV века (фрагмент)

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

Формализация текстовой информации:

Облегчает и ускоряет процесс её обработки;

Позволяет получить количественные оценки;

Обеспечивает однозначность понимания текста;

Способствует лучшему восприятию сведений, содержащихся в тексте;

Помогает сравнить по формальным критериям ситуацию, описанную в тексте, с реальной и принять правильное решение.

Формализовать можно как оформление текста, так и его содержание.

Формализация оформления сводится к использованию бланков, формуляров, шаблонов заранее определённой и часто законодательно утверждённой стандартной формы.

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

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

Целью формализации содержания текста является его однозначное понимание. Это очень важно в юридической практике, в научной и управленческой деятельности, например, при формулировании определений, составлении законов, договоров, приказов, распоряжений и т.п.

Таблицы - удобная для анализа и обработки и наглядная форма представления информации. Таблицы, в которых отражается одно свойство, характеризующее два или более объектов, называются таблицами типа «объект-объект». Таблицы, в которых отражаются несколько свойств объекта, а все объекты принадлежат одному множеству, называются таблицами вида «объект-свойство». Комбинирование в одной таблице нескольких таблиц вида «объект-объект» и «объект-свойство» позволяет построить таблицы более сложного вида, например, «объекты-свойства-объекты». Таблица характеризуется:

Названием (а если таблиц несколько, то ещё и номером),

Количеством столбцов и их названиями (заголовками столбцов),

Количеством строк и их названиями (заголовками строк),

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

В случае многоуровневых заголовков строк и столбцов уровни заголовков столбцов называются ярусами, уровни заголовков строк - ступенями.

Основными элементами таблицы являются:

Записи - строки таблицы, которые могут содержать данные разного типа, но относящиеся чаще всего к одному объекту;

Поля - столбцы таблицы, содержащие, как правило, данные одного типа;

Реквизиты - конкретные значения, находящиеся в ячейках таблицы на пересечении строк и столбцов.

Этапы приведения к табличному виду:

1. анализ информации и выделение объектов, о которых идет речь;

2. выделение свойств объектов и/или отношений между ними;

3. определение того, можно ли объекты объединить в некоторые подмножества, и в зависимости от этого определение количества уровней и ступеней в заголовках;

4. определение общего количества столбцов и порядка их расположения;

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

6. выбор порядка размещения строк и определение названия каждой строки таблицы;

7. занесение в ячейки таблицы реквизитов-данных (построчно или по столбцам).

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

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

Выявление всех элементов объекта;

Определение характеристик элементов (названий, номеров, весов и т. п.);

Установление наличия и вида связей (односторонняя или двухсторонняя) между элементами;

Определение характеристик связей - весов рёбер и дуг;

Выбор формы изображения вершин и рёбер, ввод условных обозначений в случае необходимости;

Представление выделенных элементов и связей в графическом виде.

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

Дерево - особый вид графа, применяемый при моделировании объекта, элементы которого находятся в отношении иерархии (подчинения и соподчинения). Корнем дерева называется вершина, соответствующая основному (центральному, главному, родовому) элементу моделируемого объекта. Листьями дерева называют вершины графа, у которых нет «подчинённых» вершин. Формализация при построении дерева сводится к выявлению основного элемента рассматриваемого объекта (вершина нулевого уровня - корень дерева), элементов, которые находятся в непосредственном подчинении у основного элемента (вершины 1-го уровня), элементов, находящихся в непосредственном подчинении у вершин 1-го уровня (вершины 2-го уровня) и т. д. Классификация - система соподчинённых понятий (классов объектов, явлений) в какой-либо отрасли знания, составленная на основе учёта общих признаков объектов и закономерных связей между ними. Представляется чаще всего в виде иерархического графа (дерева) или таблицы. Реляционная (табличная), сетевая (графовая) и иерархическая (древовидная) модели являются основными для представления данных в базах данных. Программные комплексы, которые позволяют создавать, обновлять, сохранять базы данных и обслуживать запросы пользователей к ним, называются соответственно реляционной, сетевой, иерархической системой управления базами данных (СУБД). Большинство существующих автоматизированных баз данных являются базами данных реляционного типа.

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

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

Локальных моделей, которые относительно легко могут быть отображены в любую систему баз данных. Наиболее распространенным средством моделирования данных являются диаграммы "сущность-связь" (ERD). С их помощью определяются важные для предметной области объекты (сущности), их свойства (атрибуты) и отношения друг с другом (связи). ERD непосредственно используются для проектирования реляционных баз...

Лекция 4. Графы

4.1.Графы. Определение, виды графов

4.2. Свойства графов

Программные положения

Существует несколько причин нарастания интереса к теории графов. Неоспорим тот факт, что теория графов применяется в таких областях, как физика, химия, теория связи, проектирование вычислительных машин, электротехника, машиностроение, архитектура, исследование операций, генетика, психология, социология, экономика, антропология и лингвистика. Эта теория тесно связана также со многими разделами математики, среди которых - теория групп, теория матриц, численный анализ, теория вероятностей, топология и комбинаторный анализ. Достоверно и то, что теория графов служит математической моделью для всякой системы, содержащей бинарное отношение. Графы действуют притягательно и обладают эстетической привлекательностью благодаря их представлению в виде диаграмм. Хотя в теории графов много результатов, элементарных по своей природе, в ней также громадное изобилие весьма тонких комбинаторных проблем, достойных внимания самых искушенных математиков. (Ф.Харари «Теория графов»)

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

Литература

Контрольные вопросы

1. Что такое граф?
2. Что называют вершиной и ребром графа?

3. Можно ли обвести данную схему, не отрывая карандаша и не проходя дважды никакие ребра

1. Может ли сумма степеней вершин графа быть нечетным числом?
2. Можно ли организовать турнир между 11 командами, так, чтобы каждая сыграла ровно 5 матчей?

6. Покажите равносильность определений из п.4.1.(6) (что описывают один и тот же объект)

7.Покажите, что изоморфны графы

8. Покажите, что изоморфизм есть отношение эквивалентности на графах.

9.На какое минимальное количество частей нужно разделить кусок проволоки, чтобы из нее можно было сделать каркас куба

10. Покажите, что граф является планарным

Графы. Определение, виды графов

Отцом теории графов является Л.Эйлер A707-1782), решивший в 1736 г. широко известную в то время задачу, называвшуюся проблемой кёнигсбергских мостов.

В городе Кенигсберге было два острова, соединенных семью мостами с берегами реки Преголя и друг с другом так, как показано на рис. 4.1.(1) (A,D – острова, B,C – берега реки). Задача состояла в следующем: найти маршрут прохождения всех четырех частей суши, который начинался бы с любой из них, кончался бы на этой же части и ровно один раз проходил по каждому мосту. Легко, конечно, попытаться решить эту задачу эмпирически, производя перебор всех маршрутов, но все попытки окончатся неудачей. Л.Эйлеру удалось найти решение этой задачи заключается в доказательстве невозможность такого маршрута.

Для доказательства того, что задача не имеет решения, Эйлер обозначил каждую часть суши точкой (вершиной), а каждый мост - линией (ребром), соединяющей соответствующие точки. Получился «граф». Этот граф показан на рис. 4.1.(2), где точки

отмечены теми же буквами, что и четыре части суши на рис. 4.1(1). Утверждение о несуществовании «положительного» решения у этой задачи эквивалентно утверждению о невозможности обойти специальным образом граф, представленный на рис. 4.1(2).

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

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

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

Определение 4.1(1)

Граф есть конечное множество V, называемое множеством вершин, и множество Е двухэлементных подмножеств множества V. Множество Е называется множеством ребер. Элемент множества Е называется ребром. Граф обозначается G(V, E). Элементы а и b множества V называются соединенными, или связанными ребром {а, b}, если .

Иначе говоря, граф – это схема, состоящая из точек, некоторые из которых соединены отрезками.

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

Определения 4.1(2)

Если {а, b} - ребро, тогда вершины а и b называются концами ребра {а, b}. Ребро {а, b} называют также инцидентным к вершинам а и b. Обратно, говорят, что вершины а и b инцидентны к ребру {а, b}. Две вершины называются смежными (соседними ), если они являются концами ребра, или, что то же самое, если они инцидентны к одному ребру. Два ребра называются смежными, если они инцидентны к общей вершине.

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

Если в графе все вершины соседние, граф называется полным .

Граф с одной вершиной и без ребер (состоящий из 1 точки – вершины), называется тривиальным.

Определение 4.1(3)

Степенью вершины v обозначается deg(v), называется количество ребер, инцидентных этой вершине (исходящих из нее).

Вершина степени 0 (то есть из вершины не исходит ни одного ребра, это «одинокая» точка) называется изолированной.

Вершина степени 1 называется висячей.

Вершины могут быть четными и нечетными.

Определения 4.1.(4)

Путь (между вершинами) – последовательность ребер и промежуточных вершин, их соединяющая

Длина пути – количество ребер, входящих в путь

Простой путь – путь, в котором все ребра и вершины различны

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

Примеры 4.1(1).

1. Граф с множеством вершин V = {а,b,с} и множеством ребер Е {{а, b}, {b, с}} может быть изображен, как показано на рисунке 4.1(4) (Простой) путь между вершинами a и c включает ребра {a,b}, {b,c} и вершину c

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

2. Граф, у которого V = {a,b,c,d,e} и Е = {{а, b}, {а, е}, {b, е}, {b, d}, {b, с}, {с, d}},

может быть изображен диаграммой, показанной на рис. 4.1.(5). Граф содержит два цикла {b, e, a}, {b, c, d}.

3. На рис. 4.1.(6)вершины а и с – смежные и е 1 , е 2 и е 3 - смежные ребра, вершины а и f смежными не являются, а е 2 и е 5 не являются смежными ребрами. Вершины b, с и d имеют степень 2, в то время как вершины a и f имеют степень 3.

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

В первом случае все вершины должны иметь четные степени, во втором – четными должны быть все вершины, кроме входа и выхода.

Пример 4.1.(2)

Можно ли пройти граф на рис. 4.1(4), не пропуская и не проходя дважды никакие ребра?

Степени всех вершин четны, кроме вершин с и j со степью 3. Соответственно, единственный путь обхода – имеющий вершины c и j началом и концом (или наоборот)

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

Определение 4.1(5)

Ориентированный граф или орграф G , который обозначается через G(V, Е) состоит из множества V вершин и множества Е упорядоченных пар элементов из У, называемого множеством ориентированных ребер или просто ребер, если понятно, что граф ориентирован. Элемент множества Е называется ориентированным ребром. Если , то а называется начальной вершиной ребра (а, b), b называется конечной вершиной.

Пример 4.1(3)

Орграф, у которого V = {а, b, с, d] и Е = {(а, b), (b, с), (с, с), (c, d), (d,b),(c,d),(d,a)} изображен на рис.

Определение 4.1.(6)

Рассмотрим несколько равносильных определений графа дерево.

1) Это связный граф, не имеющий циклов (о свойстве связности см 4.2.)

2) Граф, в котором любые 2 вершины соединены простым путем

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

4) Граф, в котором ребер на 1 меньше, чем вершин

Примеры деревьев:

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

Свойства графов

Теорема 4.2(1).

Сумма степеней вершин графа всегда четная.

Доказательство

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

Теорема 4.2.(2)

В любом графе количество вершин нечетной степени четно.

Доказательство

Доказательство проведем методом от противного: предположив, что теорема не верна, найдем противоречие, из которого будет следовать, что теорема справедлива. Если теорема не верна, то имеется нечетное количество вершин, степени которых нечетны. Но сумма степеней вершин с четными степенями четна. Сумма степеней всех вершин есть сумма степеней вершин с нечетными степенями плюс сумма степеней вершин с четными степенями. Поскольку сумма нечетного числа и четного числа есть число нечетное, сумма степеней всех вершин нечетная. Но это противоречит теореме 4.1(1), поэтому мы пришли к противоречию. Следовательно, делаем вывод, что теорема справедлива.

Пример 4.2.(1)

Можно ли организовать футбольный турнир между 7 командами так, чтобы каждая сыграла ровно по 3 матча?

Нет, так как, если мы составим граф с 7 вершинами, и попытаемся вывести по 3 ребра из каждой вершины. Согласно теореме 4.2(2), такой граф построить невозможно.

Определение 4.2(1).

Изоморфными называются графы одинаковой структуры. Два графа G и Н изоморфны (записывается или иногда G=H), если между их множествами вершин существует взаимно однозначное соответствие, сохраняющее смежность. Например, G и H на рис. 4. 2(2) изоморфны при соответствии .

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

Заметим, что изоморфизм есть отношение эквивалентности на графах.

Определения 4.2(2)

Граф называется связным , если в нем между любыми двумя вершинами есть путь.

Компонента связности – часть графа, которая сама по себе связна, но ее нельзя расширить так, чтобы она осталась связной

Связностью x=x(G) графа G называется наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу. Из определения следует, что связность несвязного графа равна 0, а связность связного графа, имеющего точку сочленения, равна 1. Полный граф нельзя сделать несвязным, сколько бы вершин из него ни удалять.

Рис. 7.1

II. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ

§ 7. Основные определения и типы графов

1. Основны е понятия

Пусть V – конечное непустое множество и Е {{u , v } u ,v V , u ≠ v } – множество его двухэлементных подмножеств. Пара G = (V, E ) называется графом . Множество V = V (G ) при этом называется множеством вершин графа G, а его элементы – вершинами; множество Е = Е (G ) называется множеством ребер графа G , а его элементы – ребрами. И вершины, и ребра графа G называются его элементами. Поэтому если u – вершина графа G , а е – ребро G , то вместо u V (G ), e E (G ) можно писать u G , e G .

Если e = {u , v } – ребро графа G (пишут также е = uv ), то вершины u и v называются концами ребра е .

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

Вершины u и v графа G называется смежными , если {u , v } E (G ), т.е. если они соединены ребром. Два ребра, в свою очередь, называются смежными , если они имеют общий конец. Если вершина v является концом ребра e , то v

и e называются инцидентными .

Мощность V (G ) множества вершин V (G ) называется порядком графа G и обозначается G . Если V (G ) = n и E (G ) =m , то граф G называется (n,m ) -графом .

2. Основные типы графов

Граф называется пустым , если E (G) = , т.е., если в нем нет ребер. Пустой граф порядка n обозначается 0 n . Граф 0 1 называется тривиальным . Граф, в котором любые две вершины соединены ребром, называется полным . Полный граф порядка n обозначается K n (рис. 7.2 – 7.5).

Граф такого вида, как на рис. 7.6, называется простой цепью . Простая цепь порядка n обозначается P n (на рис. 7.6 изображена цепь P 4 ). Простая цепь P n имеет n – 1 ребер.

Рис. 7.9

Замкнутые цепи, т.е. такие графы как на рис. 7.7, называются простыми циклами . Простой цикл порядка n обозначается C n (на рис. 7.7 изображена простая цепь С 7 ). Понятно, что простая цепь C n имеет столько же ребер, сколько и вершин, т.е. n .

Графы, такие как на рис. 7.8, называются колесами. Колесо порядка n +1 обозначается W n (на рис. 7.8 изображено колесо W 7 ); оно имеет 2n ребер.

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

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

Полный двудольный граф с n вершинами в одной доле и с m вершинами – в другой обозначается K n,m . См. примеры, приведенные на рис. 7.10 – 7.12.

Графы K 1, n называется звездными графами, или звездами.

Легко видеть, что граф K n,m является (n+m, nm )- графом, т.е. имеет n+m вершин и nm ребер.

Понятно, что существуют графы, которые можно одновременно отнести к нескольким типам. Например, K 3 = C 3 , K 2 = P 2 , K 2, 2 = C 4 , K 4 = W 3 .

3. Обобщения понятия графа

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

Рис. 7.16

когда необходимо допускать существование нескольких ребер между одной и той же парой вершин. Такие ребра называются кратными . Граф с кратными ребрами называется мультиграфом (рис. 7.14). Графы, соответствующие исходному определению (в тех случаях, когда нужно подчеркнуть, что в них отсутствуют кратные ребра), называются простыми графами (рис. 7.13). Кроме того, порой приходится рассматривать ребра вида {v, v }, соединяющие вершину v саму с собой. Такие ребра называются петлями . Мультиграф с петлями называется псевдографом (рис. 7.15.).

Пара (V , E ), где V – непустое множество, а E V 2 , называется ориентированным графом (или кратко: орграфом ). Ребра такого графа представляют собой ориентированные (т.е. упорядоченные) пары вида

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

Дуги (u , v ) и (v , u ), соединяющие одну и ту же пару вершин, но имеющие противоположные направления, называются симметричными .

Можно рассматривать не только простые орграфы, но также ориентированные мульти- и псевдографы.

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

Как правило, при изучении тех или иных вопросов, заранее оговаривается (или ясно из контекста) о каких графах идет речь. В этом случае их просто называют графами без приставок "мульти-", "псевдо-" и т.д.

4. Изоморфные графы

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

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

Определение . Два графа G и H называются изоморфными , если существует биекция f : V (G ) → V (H ), сохраняющая смежность, т.е. такое биективное отображение, при котором образы вершин v и u графа G смежны в H тогда и только тогда, когда u и v смежны в графе G . Отображение f , обладающее указанным свойством, называется

изоморфизмом.

Если графы G и H изоморфны, то пишут G H .

Например, все три графа на рис. 7.17-7.19 изоморфны друг другу (изоморфизм определяется нумерацией вершин).

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

В некоторых ситуациях все же приходится различать изоморфные графы и тогда возникает понятие "помеченный граф ". Граф порядка n называется помеченным, если его вершинам присвоены метки, например, номера 1, 2, 3, …, n . В этом случае вершины графа G отождествляют с их номерами, т.е. полагают, что V (G ) = {1, 2, 3, …, n }.

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

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

В своей жизни мы, так или иначе, соприкасались с объектами, имеющими структуру графа. К таким объектам относятся разного рода маршруты общественного транспорта: система метрополитена, автобусные маршруту и т.п. В частности, программисту знакома компьютерная сеть, также являющаяся графом (рис. 3.1). Общее здесь это наличие точек, соединенных линиями. Так в компьютерной сети точками являются отдельные серверы, а линиями – различные виды электрических сигналов. В метрополитене первое – станции, второе – туннели, проложенные между ними. В теории графов точки именуется вершинами, или узлами , а линии – ребрами, или дугами . Таким образом, граф – это совокупность вершин, соединённых ребрами.

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

Рисунок 3.1 – Компьютерная сеть

Это, по сути, граф. Пять компьютеров являются вершинами, а соединения (пути передачи сигналов) между ними – ребрами. Заменив компьютеры вершинами, мы получим математический объект – граф, который имеет 10 ребер и 5 вершин. Пронумеровать вершины можно произвольным образом, а не обязательно так, как это сделано на рисунке.

Вот некоторые важные обозначения, используемые в теории графов:

· G =(V , E ), здесь G – граф, V – его вершины, а E – ребра;

· |V | – порядок (число вершин);

· |E | – размер графа (число рёбер).

В нашем случае (рис. 1) |V |=5, |E |=10;

Когда из любой вершины доступна любая другая вершина, то такой граф называется неориентированным связным графом (рис. 3.1). Если же граф связный, но это условие не выполняется, тогда такой граф называется ориентированным или орграфом (рис. 3.2). Ребра орграфа принято называть дугами .

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

Рисунок 3.2 – Ориентированный граф

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

Ориентированные графы имеют следующую форму записи:

G =(V , A ), где V – вершины, A – направленные ребра.

Третий тип графов – смешанные графы (рис. 3.3). Они имеют как направленные ребра, так и ненаправленные. Формально смешанный граф записывается так: G =(V , E , A ), где каждая из букв в скобках обозначает тоже, что ей приписывалось ранее.

Рисунок 3.3 – Смешанный граф

На рисунке 3 изображен смешанный граф. Одни дуги направленные [(e , a ), (e , c ), (a , b ), (c , a ), (d , b )], другие – ненаправленные [(e , d ), (e , b ), (d , c )…].

Когда у ребра оба конца совпадают, т. е. ребро выходит из некоторой вершины F и входит в нее, то такое ребро называется петлей (рис. 3.4).

Рисунок 3.4 – Петли графа

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

Рисунок 3.5 – Изоморфные графы

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

В любом из рассмотренных нами графов имеется возможность выделить путь и, причем не один. Путь – это последовательность вершин, каждая из которых соединена с соседней вершиной посредством ребра. Если первая и последняя вершины совпадают, то такой путь называется циклом . Длина пути определяется количеством составляющих его ребер. Например, на рисунке 4.а путем служит последовательность [(e ), (a ), (b ), (c )]. Этот путь является подграфом, так как к нему применимо определение последнего, а именно: граф G’ =(V’ , E’ ) является подграфом графа G =(V , E ), только тогда когда V’ и E’ принадлежат V , E .

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

· матрица смежности;

· матрица инцидентности;

· список смежности;

· список ребер.

Использование двух первых методов предполагает хранение графа в виде двумерного массива (матрицы). Причем размеры этих массивов, зависят от количества вершин и/или ребер в конкретном графе. Так размер матрицы смежности n ×n , где n – число вершин, а матрицы инцидентности n ×m , n – число вершин, m – число ребер в графе.