Основные виды графов. Примеры графов Что называется графом

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 непосредственно используются для проектирования реляционных баз...

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

Пример

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

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

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

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

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

Рис.3

Рис. 4

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

Пример

Рис.5

Пример

Рис.6.

Пример

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

Пример

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

Рис.7.

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

Пример

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

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

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

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

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

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

Пример

Рис.8.

Пример

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

Рис.9

Пример

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

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом . (рис.2 )

Графы, в которых не построены все возможные ребра, называются неполными графами . (рис.3 )

Графы, в которых построены все возможные ребра, называются полными графами . (рис.4 )

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

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

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

Степени вершин и подсчет числа ребер.

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

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

На рисунке 5 изображен граф с пятью вершинами.

Степень вершины А обозначим Ст.А.

На рисунке:
Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст.Г= 2, Ст.Д= 0.

Сформулируем некоторые закономерности, присущие определенным графам.

Закономерность 1. Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.

Закономерность 2. Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.

Эта закономерность справедлива не только для полного, но и для любого графа.

Число нечетных вершин любого графа четно .

Заметим, что если полный граф имеет n вершин, то количество ребер будет равно n(n-1)/2.

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

Эйлеровы графы.

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

Такими графы названы в честь учёного Леонарда Эйлера .

Закономерность 3. (вытекает из рассмотренной нами теоремы).
Невозможно начертить граф с нечетным числом нечетных вершин.

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

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

Закономерность 6. Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком ».

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

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

На рисунке 7, очевидно, изображен несвязный граф.

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

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

Такое ребро в теории графов (после удаления которого граф из связного превращается в несвязный) называется мостом .

Примерами мостов на рисунке 7 могли бы служить ребра ДЕ, A3, ВЖ и др., каждое из которых соединяло бы вершины «изолированных» частей графа. (рис.8 )

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

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

Деревья.

Деревом называется любой связный граф, не имеющий циклов.

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

Если все вершины цикла разные, то такой цикл называется элементарным (или простым) циклом.

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

В графе на рис.9б два цикла: 1-2-3-4-1 и 5-6-7-5.

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

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

Висячей вершиной называется вершина, из которой выходит ровно одно ребро (рис.10 ).
(кружком обведены висячие вершины).

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

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

Всякое ребро в дереве является мостом.

Действительно, после удаления любого ребра дерева, оно «распадается » на два дерева.

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

(о висячей вершине). В каждом дереве есть висячая вершина.

. В дереве число вершин на одну больше числа ребер.

Изоморфизм. Плоские графы и теорема Эйлера.

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

Докажем, что графы изображенные на рисунке 11 изоморфны.

Пронумеруем вершины первого и второго графов от 1 и до 4 (рис.12 ).

В первом графе соединены вершины 1 и 2, 2 и 3, 3 и 4, 1 и 4, 1 и 3, 2 и 4; заметим, что во втором графе также соединены вершины 1 и 2, 2 и 3, 3 и 4, 1 и 4, 1 и 3, 2 и 4, следовательно, данные графы изоморфны.

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

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

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

Эйлера. Для правильно нарисованного связного плоского графа имеет равенство: V-E+F=2, где V – число вершин, E - число рёбер, F – число кусков.(равенство V -E+F=2 обычно называют формулой Эйлера) .

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

Понтрягина – Куратовского . Граф является плоским тогда и только тогда, когда он не содержит (в топологическом смысле) графа с шестью вершинами типа «домики-колодцы» и полного графа с пятью вершинами.

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

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

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

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

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

Граф, на рёбрах которого расставлены стрелки, называется ориентированным .

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

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

Так, на рисунке 15 изображен ориентированный граф АБВГД. Степени входа и выхода некоторых его вершин такие:
Ст.вх.А=2, Ст.вых.А=1 Ст.вх.В=2, Ст.вых.В=0 Ст.вх.Д=1, Ст.вых.Д=3.

Путем, в ориентированном графе от вершины А1 к вершине An называется последовательность ориентированных ребер A1A2, A2A3, ..., Аn-1Аn, в которой конец каждого предыдущего ребра совпадает с началом следующего и каждое ребро встречается в этой последовательности только один раз.

На рисунке.15 показаны примеры путей в ориентированном графе. Причем, первые два пути простые - ни одна из вершин не содержится в нем более одного раза. Третий путь не является простым,т. к. через вершину Г путь «проходил » дважды.

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

На рисунке 15 приведены примеры ориентированных циклов в последних двух графах. Цикл, как и любой другой путь в графе, имеет длину, которая определяется числом ребер в этом пути.

Так, на рисунке 16 пути от А к Д могут быть различны и иметь различную длину.
Первый путь имеет длину 2, второй - 3,
а третий - 4.

Длина «кратчайшего пути» между двумя вершинами называется расстоянием между ними. Так расстояние между вершинами А и Д на графе рисунка 16 равно 2; записывают так: S(АД)=2.

Если в ориентированном графе нельзя «пройти» от одной вершины до другой, то расстояние между ними называют бесконечным(обозначают значком бесконечности). Так, расстояние между вершинами Б и Д графа, представленного на рисунке 17 бесконечно: S(БД) = ∞

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

Графы в информатике являются способом определения отношений в совокупности элементов. Это основные объекты изучения

Базовые определения

Из чего состоит граф в информатике? Он включает множество объектов, называемых вершинами или узлами, некоторые пары которых связаны т. н. ребрами. Например, граф на рисунке (а) состоит из четырех узлов, обозначенных А, В, С, и D, из которых B соединен с каждой из трех других вершин ребрами, а C и D также соединены. Два узла являются соседними, если они соединены ребром. На рисунке показан типичный способ того, как строить графы по информатике. Круги представляют вершины, а линии, соединяющие каждую их пару, являются ребрами.

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

Модели сетей

Графы в информатике служат сетевых структур. На следующем рисунке представлена структура интернета, тогда носившего название ARPANET, в декабре 1970 года, когда она имела лишь 13 точек. Узлы представляют собой вычислительные центры, а ребра соединяют две вершины с прямой связью между ними. Если не обращать внимания на наложенную карту США, остальная часть изображения является 13-узловым графом, подобным предыдущим. При этом действительное расположение вершин несущественно. Важно, какие узлы соединены друг с другом.

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

Маршруты

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

Эта идея мотивирует определение маршрута как последовательности вершин, связанных между собой ребрами. Иногда возникает необходимость рассматривать маршрут, содержащий не только узлы, но и последовательность ребер, их соединяющих. Например, последовательность вершин MIT, BBN, RAND, UCLA является маршрутом в графе интернета ARPANET. Прохождение узлов и ребер может быть повторным. Например, SRI, STAN, UCLA, SRI, UTAH, MIT также является маршрутом. Путь, в котором ребра не повторяются, называется цепью. Если же не повторяются узлы, то он носит название простой цепи.

Циклы

Особенно важные виды графов в информатике - это циклы, которые представляют собой кольцевую структуру, такую как последовательность узлов LINC, CASE, CARN, HARV, BBN, MIT, LINC. Маршруты с, по крайней мере, тремя ребрами, у которых первый и последний узел одинаковы, а остальные различны, представляют собой циклические графы в информатике.

SRI, STAN, UCLA, SRI является самым коротким, а SRI, STAN, UCLA, RAND, BBN, UTAH, SRI значительно больше.

Фактически каждое ребро графа ARPANET принадлежит к циклу. Это было сделано намеренно: если какое-либо из них выйдет из строя, останется возможность перехода из одного узла в другой. Циклы в системах коммуникации и транспорта присутствуют для обеспечения избыточности - они предусматривают альтернативные маршруты по другому пути цикла. В социальной сети тоже часто заметны циклы. Когда вы обнаружите, например, что близкий школьный друг кузена вашей жены на самом деле работает с вашим братом, то это является циклом, который состоит из вас, вашей жены, ее двоюродного брата, его школьного друга, его сотрудника (т. е. вашего брата) и, наконец, снова вас.

Связный граф: определение (информатика)

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

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

Компоненты

Если графы в информатике не связаны, то они естественным образом распадаются на набор связанных фрагментов, групп узлов, которые являются изолированными и не пересекающимися. Например, на рисунке изображены три таких части: первая - А и В, вторая - C, D и Е, и третья состоит из оставшихся вершин.

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

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

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

Максимальная компонента

Существует метод качественной оценки компонентов связности. Например, есть всемирная социальная сеть со связями между двумя людьми, если они являются друзьями.

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

Глобальная сеть друзей

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

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

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

Катастрофа слияния компонент

Например, после прибытия европейских исследователей в цивилизации Западного полушария примерно полтысячелетия назад произошел глобальный катаклизм. С точки зрения сети это выглядело так: пять тысяч лет глобальная социальная сеть, вероятно, состояла из двух гигантских компонент - одной в Северной и Южной Америке, а другой - в Евразии. По этой причине технологии развивалась независимо в двух компонентах, и, что еще хуже, так же развивались и болезни человека и т. д. Когда две компоненты, наконец, вошли в контакт, технологии и заболевания одной быстро и катастрофически переполнили вторую.

Американская средняя школа

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

Расстояние и поиск в ширину

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

Для этого следует определить длину маршрута, равную числу шагов, которые он содержит от начала до конца, т. е. число ребер в последовательности, которая его составляет. Например, маршрут MIT, BBN, RAND, UCLA имеет длину 3, а MIT, UTAH - 1. Используя длину пути, можно говорить о том, расположены ли два узла в графе близко друг к другу или далеко: расстояние между двумя вершинами определяется как длина самого короткого пути между ними. Например, расстояние между LINC и SRI равно 3, хотя, чтобы убедиться в этом, следует удостовериться в отсутствии длины, равной 1 или 2, между ними.

Алгоритм поиска в ширину

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

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

Все друзья объявляются находящимися на расстоянии 1.
Все друзья друзей (не считая уже отмеченных) объявляются находящимися на расстоянии 2.
Все их друзья (опять же, не считая помеченных людей) объявляются удаленными на расстояние 3.

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

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

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

Мир тесен

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

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

Теория «шести рукопожатий» впервые экспериментально исследовалась Стенли Милгрэмом и его коллегами в 1960-е годы. Не имея какого-либо набора данных социальных сетей и с бюджетом в 680 долларов он решил проверить популярную идею. С этой целью он попросил 296 случайно отобранных инициаторов попробовать отослать письмо биржевому брокеру, который жил в пригороде Бостона. Инициаторам были даны некоторые личные данные о цели (включая адрес и профессию), и они должны были переслать письмо лицу, которого они знали по имени, с теми же инструкциями, чтобы оно достигло цели как можно быстрее. Каждое письмо прошло через руки ряда друзей и образовало цепочку, замыкавшуюся на биржевом брокере за пределами Бостона.

Среди 64 цепочек, достигших цели, средняя длина равнялась шести, что подтвердило число, названное два десятилетия ранее в названии пьесы Джона Гэра.

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

Основные вопросы:

Сведения из истории графов. Граф и
его элементы.
Пути и маршруты в графах
Связные графы. Деревья
Операции над графами.

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

История возникновения графов

Впервые основы теории графов
появились в работах Леонарда
Эйлера (1707-1783;
швейцарский, немецкий и
российский математик) , в
которых он описывал решение
головоломок и математических
развлекательных задач.
Теория графов началась с
решения Эйлером задачи о
семи мостах
Кёнигсберга.

Издавна среди жителей Кёнигсберга была распространена такая загадка:
как пройти по всем мостам (через реку Преголя), не проходя ни по одному
из них дважды? Многие пытались решить эту задачу как теоретически, так и
практически, во время прогулок. Но никому это не удавалось, однако не
удавалось и доказать, что это даже теоретически невозможно.
На упрощённой схеме части
города (графе) мостам
соответствуют линии (дуги
графа), а частям города -
точки соединения линий
(вершины графа).
В ходе рассуждений Эйлер пришёл к
следующим выводам: Невозможно пройти
по всем мостам, не проходя ни по одному из
них дважды.

История возникновения графов

Термин "граф" впервые появился в книге
венгерского математика Д. Кенига в 1936 г., хотя
начальные важнейшие теоремы о графах
восходят к Л. Эйлеру.

В основе теории лежит понятие графа.

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

Состав графа

Граф состоит из вершин, связанных линиями. Вершины
графа обозначают латинскими буквами A, B, C, D или
цифрами.
Направленная линия (со стрелкой) называется дугой.
Линия ненаправленная (без стрелки) называется ребром.
Линия, выходящая из некоторой вершины и входящая в
неё же, называется петлей.
дуга
А
ребро
В
петля
С

Ориентированный граф -

граф, вершины которого соединены дугами. С
помощью таких графов могут быть представлены
схемы односторонних отношений.
Юра
Аня
Маша
Коля
Витя

Взвешенный граф

Это граф, рёбрам или дугам которого поставлены
в соответствие числовые величины (они могут
обозначать, например, расстояние между городами
или стоимость перевозки).
Вес графа равен сумме весов его рёбер.
4
B
C
2
3
2
A
1
E
D
A
B
C
D
Е
A B C D Е
3 1
4
2
3 4
2
1
2 2
Таблице (она называется весовой
матрицей) соответствует граф.

Если
ребро графа G соединяет две его
вершины V и W, (т.е. V ,W X), то говорят,
что это ребро им инцидентно.
Две вершины графа называются смежными,
если существует инцидентное им ребро: на
рисунке смежными являются вершины А и В,
А и С.
А
С
В

Если граф G имеет ребро, у которого начало
и конец совпадают, то это ребро называется
петлёй. На рисунке ребро q(С, С) – петля.
q
E
С
A
D
B

Два ребра называются смежными, если они
имеют общую вершину.
На рисунке смежными являются, например,
рёбра х1 и х2 с общей вершиной С.
D
х5
х1
F
С
х4
х2
G
х7
х3
E
х6
B
H
A

Рёбра, которые начинаются в одной и
той же вершине, заканчиваются также
в одной и той же вершине, называются
кратными, или параллельными.
Количество одинаковых пар вида
(V , W) называется кратностью ребра (V , W)
Число рёбер, инцидентных вершине А,
называется степенью этой вершины и
обозначается deg(A) (от англ. degree –
степень).

На рисунке кратными являются, например,
рёбра х1(А, В), х2(А, В). Вершинам А и С
инцидентны рёбра х3, х4, х5. Следовательно,
ребро АС имеет кратность, равную 3, а ребро
АВ – кратность, равную 2.
А
х4
х1
х3
С
х2
х5
В

На рисунке вершина А имеет степень,
равную 1, вершина С – 4, вершина D – 2.
Записывается это в виде: deg(A)=1, deg(C)=4,
deg(D)=2.
D
х5
х1
F
С
х4
х2
G
х7
х3
E
х6
B
H
A

Вершина графа, имеющая степень, равную нулю,
называется изолированной.
Граф, состоящий из изолированных вершин,
называется нуль-графом.
Вершина графа, имеющая степень, равную 1,
называется висячей.
Граф, не имеющий ребер (дуг), называется
пустым.
E
C
A
D
B
На рисунке вершина
Е – изолированная:
deg(E)=0.

На рисунке вершины А, В, Е, G, H – висячие.
D
х5
х1
F
С
х4
х2
G
х7
х3
E
х6
B
H
A

Теорема 1. В графе G V , X сумма
степеней всех его вершин – число чётное,
равное удвоенному числу рёбер графа:
n
deg(V) 2m
i 1
i
Количество ребер в любом графе равно
половине суммы степеней его вершин.
где n V
- число вершин;
m X - число рёбер графа.

Вершина называется чётной (нечётной),
если её степень – чётное (нечётное) число.
На рисунке deg(D)=2, deg(F)=3, значит у
графа вершина D является чётной, а F –
нечётной.
х5
D
х1
F
С
х4
х2
G
х7
х3
E
х6
B
H
A

Задача. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью

другими?

Теорема 2. Всякий (неориентированный)
граф содержит четное число нечетных
вершин.
Следствие. Невозможно начертить граф с
нечётным числом нечётных вершин.
Граф G называется полным,
если любые две его различные
вершины соединены одним и
только одним ребром.

Задача. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 - по 4 друга, а 10 - по 5 друзей?

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

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

Закономерность 3.
Закономерность 4.
Число нечетных
Невозможно
вершин любого
графа четно.
начертить граф с
нечетным числом
нечетных вершин.

Закономерность 5.
Закономерность 6.
Если все вершины
Граф, имеющий всего
графа четные, то
можно не отрывая
карандаш от бумаги
(«одним росчерком»),
проводя по каждому
ребру только один раз,
начертить этот граф.
Движение можно
начать с любой
вершины и закончить
его в той же вершине.
две нечетные
вершины, можно
начертить, не
отрывая карандаш
от бумаги, при этом
движение нужно
начать с одной из
этих нечетных
вершин и закончить
во второй из них.

Закономерность 7.
Граф, имеющий более
двух нечетных
вершин, невозможно
начертить «одним
росчерком». Фигура
(граф), которую можно
начертить не отрывая
карандаш от бумаги,
называется
уникурсальной.

Пути и маршруты в графах

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

В качестве примера рассмотрим орграф,
представленный на рисунке. Одним из существующих
путей, соединяющих вершины 1 и 3, является
последовательность вершин 1, 2, 1, 4, 3. Единственным
простым путем для той же пары вершин является
последовательность 1, 4, 3. Пути из вершины 1 в
вершину 5 для того же графа не существует.

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

Путь называется замкнутым, если
начальная и конечная вершины совпадают.
Замкнутый путь называется циклом, если все
его вершины (кроме начальной и конечной)
различны.
Рассмотрим граф. Для него путь 2, 1, 6, 5, 4, 1,
2 является замкнутым; а путь 1, 6, 5, 4, 1
является циклом.

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

На рисунке HCDFD – маршрут длиной 4.
Обозначение: |HCDFD|=4. Маршрут принято
задавать
как
последовательность
рёбер,
поскольку это удобно при наличии кратных
рёбер.
х
D
х1
5
F
С
х4
х2
G
х7
х3
E
х6
B
H
A

В графе на рисунке (t, s, p, r), (u, s, t, r) – циклы
длиной 4, (r, t, q, s, u) – цикл длиной 5, (t, s, u, r, t, s, p, r)
– 8-цикл, (p, u) – 2-цикл, петля (q) – 1-цикл.
E
q
C
s
A
p
t
D
r
B
u

Операции над графами

Одноместные операции
1. Удаление ребра графа - при этом все вершины графа
сохраняются
2. Добавление ребра графа между двумя
существующими вершинами.
3. Удаление вершины (вместе с инцидентными
ребрами).
4. Добавление вершины (которую можно соединить с
некоторыми вершинами графа).
5. Стягивание ребра - отождествление пары вершин, т.е.
удаление пары смежных вершин, и добавление новой
вершины, смежной с теми вершинами, которые были
смежны, хотя бы одной из удаленных вершин)
6. Подразбиение ребра с- удаление ребра и добавление
новой вершины, которая соединяется ребром с каждой из
вершин удаленного ребра.

Операции над графами

Двуместные операции
Объединением графов G1 (V1 , X 1) и G2 (V2 , X 2)
называется граф G G1 G2 , множество вершин
которого V V1 V2 , а множество рёбер X X 1 X 2 .
Пересечением графов G1 и G2 называется
граф G G1 G2 , для которого X X 1 X 2 множество рёбер, а V V1 V2 - множество вершин.
Кольцевой суммой двух графов называется граф
G G1 G2 , порождённый множеством вершин
т.е.
V V1 V2 и множеством рёбер (X1 X 2) \ (X1 X 2) ,
множеством рёбер, содержащихся либо в G1 , либо в
G2 , но не в G1 G2 .

V4
V2
х3
х2
V3
х4
V1
х1
V5
х2
х7
х3
х4
х4
V1
х7
V1
G=G1UG2
V3
х4
V5
х2
V1
х3
G=G1∩G2
V2
х1
G2
V4
V2
х5 х6
х6
V3
V1
V4
V3
V4
х5
х3
х1
G1
V2
V5
V2
V4
х5 х6V
3
х7
G=G1 G2

Применение графов

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

Применение графов

Лабиринт - это граф. А исследовать его - это найти
путь в этом графе.
дальше

Использует графы и
дворянство.
На рисунке приведена
часть генеалогического
дерева
знаменитого
дворянского рода Л. Н.
Толстого. Здесь его
вершины – члены этого
рода, а связывающие их
отрезки – отношения
родственности,
ведущие от родителей к
детям.
дальше

Применение графов

Графами являются блок – схемы программ для
ЭВМ.
дальше

Применение графов

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

Применение графов

Типичными графами на картах города
являются схемы движения городского
транспорта.
дальше

Выводы

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

Также по теме

Как приготовить зеркальную глазурь для торта — рецепты в домашних условиях

Апельсиновые булочки без яиц Домашние булочки без яиц

Сонник ванная без воды. Потоп в ванной. Мнение психолога З. Фрейда

Самые влиятельные символы в истории человечества

К чему снятся крысы и мыши?