Vi. Элементы теории графов. Основные понятия теории графов. Определение Графом



Скачать 86.73 Kb.
Дата08.10.2012
Размер86.73 Kb.
ТипДокументы
Часть VI. Элементы теории графов.
§1. Основные понятия теории графов.
Определение 1. Графом называется совокупность 2-х множеств Х и У. Х - это множество точек, называемых вершинами графа, а У - это множество линий попарно соединяющие вершины и называемые ребрами или дугами.
Это определение можно сформулировать иначе: графом называется непустое множество точек (вершин) и отрезков (ребер), оба конца которых принадлежат заданному множеству точек.

В дальнейшем вершины графа мы будем обозначать латинскими буквами A, B, C, D. Иногда граф в целом будем обозначать одной заглавной буквой.

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


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

§2. Свойства вершин и ребер графа.
Определение 1. Ребра, имеющие одинаковые концевые точки называется параллельными .
Определение 2. Ребро, концевые вершины которого совпадают, называется петлей .
Определение 3. Вершина и ребро называются инцидентным друг другу, если вершина является для этого ребра концевой точкой .
Определение 4. Две вершины, являющиеся концевыми для некоторого ребра, называются смежными .
Определение 5. Два ребра, инцидентные одной и той же вершине называется смежными ребрами .

Определение 6. Степенью вершины называется число ребер, инцидентных ей: , причем, если , то вершина называется висячей , если , то вершина называется изолированной .

Пример:



Теорема. В графе G сумма степеней всех его вершин - число четное, равное удвоенному числу ребер.



Пример:



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

Пример:

Построить полный граф для пяти вершин (n=5), число ребер равно .










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

Например, на графе :

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



Определение 3. Цикл называется простым, если он не проходит ни через одну вершину графа более одного раза.
Теорема. Для того чтобы граф представлял собой простой цикл, необходимо и достаточно, чтобы каждая его вершина имела степень равную двум, т.е. .
Определение 4. Граф называется связным, если для любых двух его вершин существует соединяющий их путь, в противном случае граф - не связный: , .
Определение 5. В общем случае несвязный граф является совокупностью связных графов, называемых компонентами.



,, - компоненты графа G.

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

Граф может быть задан:

  1. Рисунком.

  2. Перечислением вершин и ребер:

.

  1. Матрицей.

Пример: Пусть граф G имеет 4 вершины и 4 ребра, т.е. и . Задать граф можно:

  1. Рисунком:

  2. Перечислением вершин и ребер:






3) Матрицей:



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





  1. для ориентированных графов задается матрица инцидентности, элементы которой находят по формуле:



Пример: Построить матрицу инцидентности для графа:



Замечание: Граф может быть задан и матрицей с весами на ребрах:

- если матрица симметричная, то граф неориентированный,

- если матрица несимметричная, то граф ориентированный.


§5. Деревья.
В экономике используется два вида графов: деревья и сети.

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


Теорема 1. Граф G является деревом тогда и только тогда, когда он не содержит циклов и при соединении ребром произвольных двух его не смежных вершин получается граф, имеющий ровно один цикл.
Теорема 2. Граф G с «n» - вершинами является деревом тогда и только тогда, когда G - не связный граф и число ребер его равно (n-1).
§6. Основные задачи теории графов.
Развитие теории графов в основном обязано большому числу всевозможных приложений. Из всех математических объектов графы занимают одно из первых мест в качестве формальных моделей реальных систем.

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


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





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

Алгоритм задачи коммивояжера используется:

  1. для выбора кратчайшего маршрута почтальона;

  2. для составления проекта строительства дорог по минимальной стоимости, которую нужно проложить между «n» - городами;

  3. для выбора маршрутов автотранспорта при кольцевой доставке товара;

  4. для планирования производства на конвейерах;

  5. для расположения станций техобслуживания для «n» - населенных пунктов и т. д.




  1. Задача о назначениях: состоит в распределении «n» - претендентов на «n» - должностей (на каждую должность по одному). Алгоритм решения этой задачи используется:

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

  2. для наилучшего распределения экипажей самолетов и т.д.

Математически все эти задачи – частный случай распределенных задач линейного программирования.

Пример задачи коммивояжера 1:

Пусть задан неориентированный граф дорог и расстояний между городами.

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




Допустимые решения:



Оптимальные решения:



- оптимальный путь для коммивояжера, т.е.


Пример задачи коммивояжера 2:

Пусть задан ориентированный граф расстояний между городами.

Построить дерево и найти кратчайший маршрут.







- оптимальное решение.

Пример 3:

Дана симметричная матрица попарных расстояний между городами.

    1. построить граф, дерево графа, найти допустимые пути и оптимальный путь обхода всех городов;

    2. проверить теорему ;

    3. указать путь для задачи коммивояжера.







Оптимальное дерево: .
2)
3)


Похожие:

Vi. Элементы теории графов. Основные понятия теории графов. Определение Графом iconЭлементы теории графов
...
Vi. Элементы теории графов. Основные понятия теории графов. Определение Графом icon3 Начальные понятия теории графов Определение
Определение. Пусть и конечные множества,; отображение множества в множество одно и двухэлементных подмножеств множества. Тройку называют...
Vi. Элементы теории графов. Основные понятия теории графов. Определение Графом iconВопросы к экзамену Основные понятия теории графов (определение графа, виды графов, смежность, инцидентность, кратность ребер, степень вершины). Примеры
Способы задания графов. Матричный способ задания. Свойства матриц смежности и инцидентности. Привести примеры
Vi. Элементы теории графов. Основные понятия теории графов. Определение Графом iconЛекция 11: Графы и деревья
...
Vi. Элементы теории графов. Основные понятия теории графов. Определение Графом iconМетодические указания к самостоятельным и семинарским занятиям по теории графов Москва 2006
Предназначены для решения задач по теории графов как при самостоятельном изучении теории графов, так и при решении задач на семинарах...
Vi. Элементы теории графов. Основные понятия теории графов. Определение Графом iconПрограмма элективного курса Элементы теории графов и комбинаторики Учитель
Курс “Элементы теории графов и комбинаторики” является дополнительным к стандартному курсу математики 5 класса для образовательных...
Vi. Элементы теории графов. Основные понятия теории графов. Определение Графом iconОсновные понятия теории графов граф и его виды
Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин «граф» впервые ввел в 1936 году венгерский математик...
Vi. Элементы теории графов. Основные понятия теории графов. Определение Графом iconОсновные понятия теории графов
Д. Кенига только в 1936 г., но многочисленные прикладные задачи и головоломки (которые, кстати, поддавались формулировкам в терминах...
Vi. Элементы теории графов. Основные понятия теории графов. Определение Графом iconЭлементы теории графов.  1: Определение графа. Ориентированные и неориентированные графы
Определение 1: Совокупность двух множеств точек и линий, между элементами которых определено отношение инцидентности, называется...
Vi. Элементы теории графов. Основные понятия теории графов. Определение Графом iconТеория графов и ее приложения
Основные понятия. Графы неориентированные и ориентированные. Способы задания графов. Матрицы смежности и инцидентности графа. Понятие...
Разместите кнопку на своём сайте:
ru.convdocs.org


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