Определения теории графов. Задачи оптимизации на графах

Графом G называют пару множеств (V,E), где V={1,2,..,n} – множество пронумерованных вершин, т. е. V={V₁,V₂,…,V_n }, а E={e} – набор упорядоченных или неупорядоченных пар вершин e={v_i,v_j}. Неупорядоченная пара вершин, называется ребром, а упорядоченная - дугой.

Граф содержащий только рёбра(дуги), называется неориентированным ( ори­ен­ти­ро­ванным). Граф, содержащий кратные ребра, называется мультиграфом.

Вершины V₁, V₂ называются смежными, ели они образуют ребро или дугу e={V₁,V₂}. Говорят, что V₁, V₂ инциденты ребру (дуге) e.

Каждому n-вершинному графу соответствует матрица смежности n x n C=||C_ij||, C_ij= количество ребер, соединяющих вершины i и j. (С_ii = 0; симметрична относительно диагонали;)

Граф G¢=(V¢,E¢) называется частью графа G=(V,E), если V¢ÍV, E¢ÍE.

Часть G¢ графа G называется суграфом, если V¢= V, E¢ÌE. G¢ называется подграфом, если V¢ÌV, а E’ содержит все ребра инцидентные v_i,v_jÎV¢.

|V|, |E| - величины показывающие количество вершин и ребер графа соответственно.

По количеству ребер можно выделить следующие виды:

1. E_n |V| = n, |E| = 0 – пустой граф (груда);
2. Противоположный Е_n, K_n полный граф (клика), у которого все вершины попарно смежны. Число ребер в n-мерной клике n(n-1)/2;
3. Имеющие вид многоугольников – циклы.

Связный граф не содержащий циклов называется деревом.

Остовным деревом графа называется связный суграф этого графа не содержащий циклов.

Задачи оптимизации на графах:

1. Задача о минимальном остовном дереве;

Дан n вершинный граф, каждому ребру которого ставится в соответствие c_ij. Множеством допустимых решений явл. Мн-во остовных деревьев данного графа. Необходимо найти такое ОД:

Алгоритм Краскала

Исходные данные: связный взвешенный граф с n >0 вершинами.

1. построить пустой граф с n вершинами;
2. k =0;
3. если k = n -1, то конец;
4. k = k +1;
5. найти k -ое по возрастанию весов ребро графа;
6. если добавление ребра в граф не приводит к появлению цикла, то добавить его;
7. перейти к шагу 3.

КОНЕЦ

2. Задача раскраски графа;

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

3. Задача о кратчайшем пути между парой вершин;

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

41.