Экстремальное дерево

123456

Лекция 16,17.

Программирование на сетях.

Вопросы:1. Основные понятия теории графов.

2. Экстремальное дерево.

3. Матричное задание графов. Упорядочение вершин.

4. Нахождение кратчайшего маршрута между вершинами графа.

5. Сети и потоки на сетях. Постановка задачи о максимальном потоке.

6. Понятие разреза. Теорема Форда-Фалкерсона. Алгоритм решения задачи о

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

7. Элементы сетевого планирования.

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

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

Формально граф определяется заданием двух (конечных) дискретных множеств: множеством вершин Х = {х1, …, хn} и множеством линий связи между ними

U = {u1,…,um}.

Линии связи ui называют ребрами, если не указана их ориентация, и – дугами, если задано направление связи.

и2
и1
и4
х2
х1
х3
х4
х5
и3
и5
и6
и7
орграф
Граф с дугами называют ориентированным графом (орграфом), - с ребрами – неориентированным.

неориентированный граф
Пример. а) б)

Вершины хi и хj, связанные дугой/ребром uk, называют концевыми вершинами этой дуги/ребра. Если концевые вершины совпадают, то дуга/ребро называется петлей. Дуги/ребра с одинаковыми концевыми вершинами называются параллельными. Граф без петель и параллельных линий связи называют простым.

Концевые вершины хi и хj одной дуги/ребра или дуги up и uq с общей вершиной называют смежными.

Если вершина хi является концевой для дуги/ребра uk, то эти xi и uk инцидентны: вершина хi инцидентна дуге/ребру uk, а дуга/ребро uk – вершине хi.

Т.о., смежность – отношение связанности между однородными элементами (вершинами или дугами/ребрами), а инцидентность – между разнородными (вершинами и дугами/ребрами).

Вершина, не имеющая отношений смежности, называется изолированной.

Графы с одинаковым отношением инцидентности называются изоморфными.

Пример.

Изоморфные графы отличаются только геометрической конфигурацией.

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

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

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



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

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

Пример.

Экстремальное дерево

Неориентированный связный граф без циклов называется деревом. При составлении дерева используется минимальное число ребер, чтобы граф был связным. Дерево на множестве п вершин всегда содержит т = п – 1 ребер. При включении в дерево любого дополнительного ребра образуется цикл. Построим все неизоморфные деревья с пятью вершинами:

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


9305962160177115.html
9306011850071511.html
    PR.RU™