Элементы теории графов

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

Выполнила:

студентка группы 13 122

Бронникова Вера.

Проверила:

Е.Э. Стацевичуте Иркутск 2009

• Элементы теории графов
• Основные понятия теории графов
• Матрица смежности
• Матрица инцидентности
• Матрица инцидентности применяется при анализе решений
• Библиография

Элементы теории графов

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

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

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

Граф — система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий (геометрический способ задания графа — см. рисунок 1). Кружки называются вершинами графа, линии со стрелками — дугами, без стрелок — ребрами. Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным (рис.4); граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным (рис. 2,3).

Начало теории графов датируют 1736 г., когда Л. Эйлер решил популярную в то время «задачу о кенигсбергских мостах». Термин «граф» впервые был введен спустя 200 лет (в 1936 г.) Д. Кенигом.

Определение графа таково: задано конечное множество X, состоящее из n элементов (X = {1, 2,., n}), называемых вершинами графа, и подмножество V декартова произведения X хХ, то есть VcX 2, называемое множеством дуг, тогда ориентированным графом G называется совокупность (X, V) (неориентированным графом называется совокупность множества X и множества неупорядоченных пар элементов, каждый из которых принадлежит множеству X). Дугу между вершинами i и j будем обозначать (i, j). Число дуг графа будем обозначать m (V = (v 1, v 2,., v m)).

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

Можно привести ряд примеров приложений теории графов.

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

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

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

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

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

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

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

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

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

Например, у графа па рисунке 3 имеется 3 пути из V₁ в V₅: V₁V₂V₄V₅, V₁V₃V₂V₄V₅, V₁V₃V₄V₅. Длина первого равна 2+1+5=8, длина второго — 3+4+1+5=13, третьего — 3+3+5=11. Таким образом, первый из рассмотренных путей имеет наименьшую длину, т. е. является наикратчайшим из V₁ в V₅.

Граф, для которого (I, j) V следует (I, j) V называется симметрическим. Если из (I, j) V следует, что (I, j) V, то соответствующий граф называется антисимметрическим.

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

Рис. 1 Рис. 2 Рис. 3

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

Связный граф, в котором существует эйлеров цикл, называется эйлеровым графом.

В неориентированном графе степенью вершины i называется число di инцидентных ей ребер. Очевидно, dj < n — i, iX. Граф, степени всех вершин которого равны n — 1, называется полным. Граф, все степени вершин которого равны, называется однородным.

Вершина, для которой не существует инцидентных ей ребер (di=0) называется изолированной. Вершина, для которой существует только одно инцидентное ей ребро (di=1), называется висячей.

? d_{i = 2m}

Деревом называется связный граф без простых циклов, имеющий не менее двух вершин. Для дерева m=n-1, а число висячих вершин равно n_i =2+? (i-2) n_i. Легко показать, что в дереве любые две вершины связаны единственной цепью. Во многих задачах, связанных с графами, бывает полезно представление графа в виде таблицы, или матрицы.

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

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

Построение матрицы смежности следует рассмотреть на примерах. Построим матрицу смежности для ориентированного графа (рис.4).

Сначала запишем в строку и в столбец номера вершин данного графа

Рис. 4

Табл.1

Правило такое: если из вершины V_i в вершину V_j идет k дуг, то в таблице на пересечении строки с номером I и столбца с номером j стоит число k, в противном случае — 0.

Например, для рассматриваемого графа из V₁ в V₂ идет одна дуга, поэтому на пересечении первой строки и второго столбца стоит 1; а поскольку из V₂ в V₁ нет дуги, то на пересечении второй строки и первого столбца стоит 0. Из V₂ в V₄ идут две дуги, поэтому на пересечении второй строки и четвертого столбца ставится 2. Полученную матрицу обозначим через А:

В матрице смежности неориентированного графа на пересечении строки с номером i и столбца с номером j стоит число k, если вершины V_i и V_J соединены k ребрами, в противном случае стоит 0. Так для графа на рис. 6 матрица смежности задается матрицей В:

Рис.5

Матрица инцидентности

Матрица инцидентности (инциденций) представляет собой таблицу, у которой число строк равно числу вершин, а число столбцов — числу дуг (ребер) графа.

Пусть граф ориентирован. Тогда на пересечении строки с номером i и столбца с номером j стоит:

1, если вершина V_i является концом дуги U_j;

1, если вершина V_i является началом дуги U_j;

0 — в противном случае.

Например, для графа на рис. 7 матрицей инцидентности является матрица С:

Рис.6

Для неориентированного графа в матрице инцидентности на пересечении строки с номером i и столбца с номером j стоит 1, если вершина V_i принадлежит ребру U_j и 0 — в противном случае.

теория граф матрица инцидентность Например, для графа на рис. 8 матрицей инцидентности является матрица D:

Рис.7

Матрица инцидентности применяется при анализе решений

Рассмотрим матрицы смежности и инцидентности на примере графов, составленных мною.

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

1. Неориентированный граф:

Библиография

1. А. В. Ганичева, В. П. Козлов. Математика для психологов. — М.: Аспект Пресс, 2005

2. А. Н. Кричивец, Е. В. Шикин, А. Г. Дьячков. Математика для психологов. — М.: Флинта: Московский психолого-социальный институт, 2005

3. http://dmtsoft.ru // В. Н. Бурков, Д. А. Новиков ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ [Текст]