Полная версия

Главная arrow Математика, химия, физика arrow Математика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>

б. ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ

Оптимизационные задачи на графах

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

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

Пусть задано некоторое непустое множество X и множество U, состоящее из пар элементов множества X. Пары во множестве U и элементы в парах могут повторяться. Множества X и U задают граф G{X, Y).

Рис. 6.1

Элементы множества X называют вершинами графа, элементы множества U—ребрами графа.

Если пары во множестве U повторяются, то граф G называют псевдографом, или графом с кратными ребрами.

Если элементы в парах множества U не упорядочены, то граф G называется неориентированным. Если они упорядочены, то граф G является ориентированным графом, или орграфом, а элементы множества U называют дугами.

Граф задается в виде точек и линий, их соединяющих. На рис. 6.1 приведен пример неориентированного графа.

Для этого графа множества вершин X и ребер U имеют следующий вид:

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

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

Если вершина является началом или концом ребра, то вершина и ребро называются инцидентными.

Степенью вершины называется число инцидентных ей ребер, степень вершины х обозначается d(x). Вершина, степень которой равна нулю, называется изолированной, а вершина, степень которой равна единице, — висячей, или тупиковой.

Для графа, представленного на рис. 6.1, изолированной является вершина х7: d(x7) = 0; тупиковой — вершина х6: d(x6) = 1; d(x2) = 2; d(x3) = 3; d(x4) = 2; d(x5) = 3; d(xj) = 3 (ребро (x15 x,) учитывается дважды).

Маршрутом в графе называется последовательность вершин и ребер, в которой конец предыдущего ребра совпадает с началом следующего (это не относится к первому и последнему ребру). Число ребер в маршруте определяет его длину. Пример маршрута для графа, представленного на рис. 6.1: (х^ х2; х3; х5; х4; х3; х2). Маршрут содержит шесть ребер, следовательно, его длина равна 6.

Цепью называется маршрут, в котором все ребра попарно различны. Пример цепи — (х4; х3; х2; хх; xt). Длина цепи 4.

Простой называется цепь, в которой все вершины попарно различны. Простая цепь — (д^; х2, х3; х4; х5).

Циклом {простым циклом) называется цепь (простая цепь), начало и конец которой совпадают. Для графа, представленного на рис. 6.1, простым циклом является последовательность (х3; х4; х5; х3).

Подграфом графа G называется граф Gx с множеством вершин Хх и множеством ребер Ux, такой, что Хх cl, [/, с U. Подграф называется собственным, если он отличен от самого графа.

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

Расстоянием между вершинами связного графа называется длина самой короткой цепи, соединяющей вершины.

Диаметром графа называется максимальное расстояние между его вершинами.

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

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

Деревом называется связный граф без циклов (рис. 6.2).

Рис. 6.2

Лесом называется граф без циклов, т.е. совокупность деревьев (рис. 6.3).

Рис. 6.3

Граф называется полным, если любые две его вершины соединены ребром. Полный граф с п вершинами обозначается К На рис. 6.4, а и б изображены графы К4 и К5 соответственно.

Рис. 6.4

Граф называется регулярным степени d, если все его вершины имеют степень d. Так, К4 — это регулярный граф степени 3; К, - это регулярный граф степени 4. Регулярный граф, все вершины которого имеют степень 1, называется пар о сочетанием.

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

Рис. 6.5

Гамильтоновой цепью называется простая цепь, содержащая все вершины графа. Пример гамильтоновой цепи для графа К,: (х{; х2; х3; х4; х5)

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

В ориентированном графе каждая дуга имеет направление, показанное стрелкой (рис. 6.5).

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

В основном все определения, данные для неориентированных графов, применимы для орграфов.

Вместо степени вершины вводится понятие полустепеней исхода и захода. Если вершина является началом дуги, то дуга называется исходящей из вершины, если концом — заходящей.

Полустепеныо исхода вершины х (обозначается d~(x)) называется число дуг, исходящих из этой вершины; полустепенъю захода d+(x) — число дуг, заходящих в вершину.

Рассмотрим граф, изображенный на рис. 6.5.

d~{xx) = 1, d+(xx) = 0;

d~(x2) = 1, d+(x2) = 1;

d~{x^) = 1, af+(x3) = 3; и т. д.

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

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

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

fl, если вершины i и j соединены ребром или дугой;

аг =

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

Для графа с кратными ребрами (дугами) вместо единицы записывается число ребер (дуг) между вершинами i и j.

Для неориентированного графа, представленного на рис. 6.1, матрица смежности имеет размерность 1x1 к записывается в виде

Слева и сверху матрицы выписаны номера вершин.

Для ориентированного графа, изображенного на рис. 6.5, матрица смежности имеет размерность 6 х 6 и записывается в виде

Матрицу смежности чаще применяют для задания неориентированного графа. Для задания ориентированного графа лучше использовать матрицу инцидентности.

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

  • 1, если вершина i является началом ребра j;
  • -1, если вершина i является концом ребра j;

b.. =

У 2, если вершина i— начало и конец ребра у;

О, если вершина /и ребро j не инциндентны.

Перенумеруем дуги графа, представленного на рис. 6.5 (рис. 6.6). Тогда матрица инцидентности будет иметь вид

Рис. 6.6

 
<<   СОДЕРЖАНИЕ ПОСМОТРЕТЬ ОРИГИНАЛ   >>