28. Гамильтонов граф. Достаточные признаки существования гамильтонова цикла (связь с полнотой цикла, теоремы Оре и Дирака). Полугамильтонов граф.

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

Достаточный признак существования Гам.графа – любой полный граф является гамильтоновым.

Теорема Оре. Если число вершин n≥3 и для любой пары несмежных вершин сумма степеней d(x_i)+d(x_j) ≥n, граф будет гамильтовым.

n=4≥3 d(x_i)= d(x_j)=2 d(x_i)+d(x_j)=4 достаточный признак выполнен.

Теорема Дирака. Если число вершин n≥3 степень d(x_i) ≥n/2, граф будет гамильтоновым.n=4≥3 d(a)=2, d(c)=2=4/2 d(b)= d(d)=3≥4/2 => граф гамильтоновый.

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

29.Орграфы, турниры. Предки и потомки вершин. Алгоритм Фалкерсона разбиения орграфа на слои.

Орграфом  D  называется пара (V(D), A(D)), где V(D) непустое конечное множество элементов, называемых вершинами, а A(D)  — конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами ). Дуга, у которой вершина υ является первым элементом, а вершина ω — вторым, называется дугой из υ в ω (υ, ω) (дуги (υ, ω) и (ω,υ) различны). Хотя графы и орграфы — различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги.  V(D) и A(D) называются соответственно множеством вершин и семейством дуг орграфа D.

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

Алгоритм Форда–Фалкерсона решает зад. нахождения макс. потока в транспортной сети.

Идея алгоритма закл. в след.. Изначально величине потока присваивается значение 0: f(u,v) = 0 для всех u, υ € V. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.

30.Комбинаторная постановка задачи коммивояжера.

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

31. Постан-ка зад. Коммивояжера в виде задачи целочисленного программирования. Условие наличия одного цикла.

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

Коммивояжер должен посетить один, и только один, раз каждый из n городов и вернуться в исходный пункт. Его маршрут должен минимизировать суммарную длину пройденного пути.

Математическая модель задачи:

, ,

Условия неотрицательности и целочисленности:

, .

Добав-ся усл. прохождение маршрута ч/з все города, т.е. так называемое условие цикличности. Иначе, маршрут должен представлять собой замкнутую ломаную, без пересечений в городах-точках