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



Скачать 258.99 Kb.
страница1/5
Дата11.10.2012
Размер258.99 Kb.
ТипЗанятие
  1   2   3   4   5
Занятие 4
Содержание занятия:


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

Рис. 4а 3

Основные понятия потоков в графах. 5

Теорема о максимальном потоке. 5

Алгоритмы определения потоков. 6

Замена оборудования. 8

Составление расписания движения грузового судна 9

Алгоритм максимального потока. 9

Рис.9 Рис.10 11

Выбор оптимального плана. 12

Иерархические системы 12

Вопросы на понимание содержания занятия 13

Практическое задание 13



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


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

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

  1. Построить модель сложной системы, как совокупности простых систем.

  2. Составить формальные процедуры для получения качественных характеристик системы.

  3. Указать механизм воздействия компонентов управляющей системы с целью описания последней в терминах ее основных характеристик.

  4. Определить, какие данные необходимы для исследования системы.

  5. Провести начальные исследования управляющей системы и составить предварительное расписание работы ее компонентов.

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

Р
P

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


p

Q
gif" align=left hspace=12>



R


R




T

S

T

S




Рис. 1 Рис. 2

Точки P,Q,R,S и T называются вершинами, линии называются ребрами, а вся диаграмма называется графом (обратите внимание на то, что точка пересечения линий PS и QT не относится к вершинам графа, так как она не является ни общей точкой двух проводов, ни перекрестком дорог.) Степенью вершины называется число ребер, концом которых является эта вершина

P

P

Q

Q
Граф представляет собой совокупность узлов (вершин) и соединяющих их ветвей (ребер).





R

R


T

T

S

S


Рис.3

Рис.4

Очевидно, что граф, изображенный на рис. 3 может описывать и другие ситуации. Например, если обозначит через P, R, Q и T футбольные команды, то наличие ребра между двумя вершинами можно трактовать, как состоявшуюся встречу соответствующих двух команд (так, согласно рис.3 команда P уже сыграла с с S, но еще не сыграла с R); в этом случае степенью вершины будет число матчей, сыгранных соответствующей командой.

Рассмотренные ситуации можно описать и другим графом, изображенным на рис 4. Заметим, что полученный при этом граф по-прежнему дает нам представление о том, как соединены провода в электрической цепи, есть ли прямая дорога от одного перекрестка к другому и какие футбольные команды встречались друг с другом; потеряна только информация, касающаяся “метрических свойств” (длина дороги, прямолинейность провода и т.д.). Исходя из этого, любые два графа, которые представляют одну и ту же ситуацию, будут считаться по существу одинаковыми. Более точно, будем говорить, что два графа изоморфны, если существует взаимно однозначное соответствие между их вершинами, обладающее тем свойством, что две вершины соединены ребром в одном графе тогда и только тогда, когда соответствующие им вершины соединены в другом. Граф, о котором шла речь до сих пор, “простой” в том смысле, что в нем любую пару вершин соединяет не более чем одно ребро. Если ребер больше, то их называют кратными. Если ребро идет из вершины в эту же вершину, то его называют петлей. Графы, не содержащие петель и кратных ребер, будем называть простыми. Если учитывать направленность ребер (например, считать, что по каждой из дорог возможно только одностороннее движение), то граф будет называться ориентированным или орграфом. Много внимания уделяется в теории графов изучению различного рода цепей; под цепью понимается последовательность идущих друг за другом ребер. Граф, в котором любые две вершины соединены цепью, называется связным графом. Связные графы, в которых существует одна и только одна цепь, соединяющая каждую пару вершин, называют деревьями. Всякий граф, который можно так нарисовать на плоскости, что он не будет содержать пересечений (ребер), называется планарным графом.

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

Пара (V(G),E(G)) называется простым графом, если V(G) - непустое конечное множество элементов, называемых вершинами(или узлами, или точками), а E(G) - конечное множество неупорядоченных пар различных элементов из V(G), называемых ребрами (или линиями). Иногда V(G) называют множеством вершин, а E(G) - множеством ребер. Часто бывает удобно отменить условие о том, что ребро должно соединять две различные вершины, и допустить существование петель, т.е. ребер, соединяющих вершину с ней самой. Граф у которого могут быть пели и кратные ребра называется общим графом или просто графом. Графом G называется пара (V(G), E(G)), где V(G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G) (необязательно различных) называемых ребрами. Две вершины v и w графа G называются смежными, если существует соединяющее их ребро (т.е. ребро вида {v,w}); при этом вершины v и w называются инцидентными этому ребру (а ребро - инцидентным этим вершинам). Аналогично, два различных ребра графа G называются смежными, если они имеют по крайне мере одну общую вершину. Степенью (или валентностью) вершины v графа G называется число ребер, инцидентных v; степень вершины v обозначается через (v). При вычислении степени вершины v обычно учитывают петлю в v два раза. Вершина степени 0 называется изолированной вершиной, вершина степени 1 называется висячей или концевой вершиной.

u

z








v

w


Рис. 4а


Граф, изображенный на рис. 4а имеет одну висячую вершину, одну вершину степени 3, одну - степени 6 и одну - степени 8.

Подграфом графа G называется граф, все вершины которого принадлежат V(G), а все ребра принадлежат E(G).


z

v2


u


v1


v4




v

w

v3

Рис.4б Рис. 4с

Граф изображенный на рис. 4б является подграфом графа с рис. 4с.
Матрицей смежности графа G с множеством вершин {v1, ..., vn} называется матрица А = (аij) размера nxn, в которой элемент аij равен числу ребер в G, соединяющих vi и vj.

Матрица



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

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

Орграфом D называется пара (V(D),A(D)), где V(D) - непустое конечное множество элементов, называемых вершинами, A(D) - конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами). Дуга, у которой вершина v является первым элементом, а вершина w - вторым, называется дугой из v в w и обозначается (v, w). Маршрутом графа называется конечная последовательность ребер вида {v0,v1}, {v1,v2}, ... , {vm-1,vm}. Каждому маршруту соответствует последовательность вершин v0, v1, ... , vm; v0 называется начальной вершиной, vm - конечной вершиной. Длиной маршрута называется число ребер в нем. Маршрут называется цепью, если все его ребра различны, и простой цепью, если все вершины различны (кроме, может быть, v0=vm). Цепь или простая цепь замкнута, если v0=vm. Замкнутая простая цепь, содержащая по крайне мере одно ребро, называется циклом. Любой граф можно разбить на непересекающиеся связные подграфы, называемые компонентами (связности), задав следующее отношение эквивалентности на множестве его вершин: две вершины эквивалентны (или связаны), если существует простая цепь из одной в другую. Граф называется несвязным, если число его компонент больше единицы. Разделяющим множеством связного графа G называется такое множество его ребер, удаление которого приводит к несвязному графу.
  1   2   3   4   5

Похожие:

Основы теории графо iconВизуализация графо-аналитической модели вычислительного процесса
Рассматривается алгоритм визуализации графо-аналитических моделей вычислительных процессов в рамках сапр, на основе их формального...
Основы теории графо icon4тм-заочн. 2010/11 уч год основы теории колебаний основная литература 1
Культербаев Х. П. Основы теории колебаний. Основы теории, задачи для домашних заданий, примеры решений. Нальчик, 2003. 130 с
Основы теории графо icon2. Задача дисциплины
Изложить основы теории множеств и бинарных отношений, изложить основы теории вероятности и математической статистики. Изложить основы...
Основы теории графо iconПрограмма дисциплины дпп. Ф. 02. «Основы теоретической физики. Статистическая физика и термодинамика»
Гиббса, статистические распределения для равновесных ансамблей Гиббса, квантовые статистики идеального газа, элементы теории флуктуаций,...
Основы теории графо iconДревнегреческий математик
«Начала» (15 книг), содержащий основы античной математики, элементарной геометрии, теории чисел, общей теории отношений и метода...
Основы теории графо iconОсновы теории вероятностей и стохастических процессов
Натан А. А., Горбачев О. Г., Гуз С. А., Гасников А. В., Бурнаев Е. В основы теории вероятностей и стохастических процессов: Учебно-методическое...
Основы теории графо iconДревнегреческий математик (365-300 до н. э.)
«Начала» (15 книг), содержащий основы античной математики, элементарной геометрии, теории чисел, общей теории отношений и метода...
Основы теории графо iconОсновы теории второго иностранного языка
Программа дисциплины «Основы теории второго иностранного языка (немецкий язык)» / сост. В. И. Карпов. – М. Импэ им. А. С. Грибоедова,...
Основы теории графо iconЭкзаменационные вопросы по курсу "основы теории коммуникации"
Объект и предмет теории коммуникации. Соотношение предмета теории коммуникации с предметными областями смежных наук
Основы теории графо iconЛекция Теоретические основы омд. Пластическая деформация моно- и поликристалла. Основы дислокационной теории пластичности

Разместите кнопку на своём сайте:
ru.convdocs.org


База данных защищена авторским правом ©ru.convdocs.org 2016
обратиться к администрации
ru.convdocs.org