Основные понятия теории графов - Нахождение максимального потока в графе

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 год), хотя термин "граф" впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых.

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

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

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

Если (u, v) - некоторое ребро графа G, то вершины u и v называются смежными, а вершины u и ребро (u, v), также как вершина v и ребро (u, v), называются инцидентными друг другу. Степенью вершины v в графе G называется число ребер графа G, инцидентных вершине v.

Пример графа представлен на рисунке 1.

V3

V4

V1

V5

V2

V6

Рисунок 1- Пример графа

В данном примере

V = {v1, v2, v3, v4, v5, v6},

E = {(v1, v2), (v2, v3), (v1, v3), (v3, v4), (v4, v5), (v4, v6), (v5, v6)}

Пусть G = (V, E) - некоторый граф, u и v - его вершины. Маршрутом в графе G, соединяющим вершины u и v, называется конечная чередующаяся последовательность вершин и ребер вида v1, e1, v2, e2,...,eK-1, vK, где v1,...,vK из V, а e1,...,eK-1 из E. Маршрут называют цепью, если все его ребра различны. Цепь называют путем (или простой цепью), если все ее вершины кроме, быть может, концевых различны. Если начальная и конечная вершина пути совпадают, то его называют замкнутым путем или циклом.

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

Теперь мы можем определить особый класс графов - деревья. Деревом называется связный граф без циклов.

Ориентированным графом D называется пара (V, A), где V - непустое конечное множество, элементы которого называются вершинами графа, а A - конечное множество упорядоченных пар различных элементов из V, элементы множества A называются дугами.

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

Основанием ориентированного графа D = (V, A), называется граф G = (V, E), где E = A, то есть упорядоченные пары вершин заменяются на неупорядоченные.

Транспортной сетью называется конечный Связный орграф G(V, E) без петель, каждой дуге которого поставлено в соответствие некоторое неотрицательное число c(), называемое пропускной способностью дуги, и существует:

    1) ровно одна вершина, в которую не заходит ни одна дуга, называемая источником или началом сети; 2) ровно одна вершина, из которой не выходит ни одной дуги; эта вершина называется стоком или концом сети.

Потоком сети называется неотрицательная функция f(1) такая, что f(e) меньше или равно c(e). (Поток не может превышать пропускную способность дуги.)

Дуга называется насыщенной потоком f, если (Поток называется полным, если содержит насыщенную дугу f(e)=c(e).)

Разрезом L сети G(V, E) называется множество насыщенных дуг, отделяющих источник s от стока t.

Похожие статьи




Основные понятия теории графов - Нахождение максимального потока в графе

Предыдущая | Следующая