КАТЕГОРИИ: Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748) |
Алгоритмы на графах
3.1 Цель работы Закрепить знания основных алгоритмов теории графов. 3.2 Темы лабораторной работы № 3 1. Найти кратчайший путь в графе (алгоритм Дейкстры). 2. Найти наибольший поток в транспортной сети (алгортмя Форда-Фалкерсона) 3. Решение транспортной задачи по критерию стоимости. 4. Найти Эйлеров цикл в графе (алгоритм Флери). 5. Решение задачи коммивояжера. 6. Нахождение остова минимального веса (алгоритм Краскала).
3.3 Основные определения Граф определяется как множество двоек : где: – конечное счётное множество всех вершин, – конечное счётное множество всех дуг графа. Ориентированный граф (орграф) – граф, у которого рёбра ориентированы (со стрелками). Направленные рёбра называют дугами. Иначе граф неориентированный..
Граф, у которого вершины пронумерованы, называется помеченнымграфом.
1 c 2 · 5 a · · 3 4 · b e d· 6 7 · h f · g ·
Рисунок 3.1 – Ориентированный граф
Определение графа в терминах отображений: Граф – это упорядоченная пара G = (X, Г), где: Г: Х ® Х – отображение множества Х самого в себя.
Используя отображение, можно определить образы и прообразы: Г (f) = { Æ } – вершина, несвязанная с другими вершинами; Г (а) = {a} - множество всех вершин, смежных с а; Г (с) = {в,d,e} - множество вершин, в которые идут дуги из с.
Вершины, связанные между собой в графе дугами, называются связанными вершинами. Дуги, входящие в вершину и выходящие из вершины, называются инцидентными данной вершине. Дуга, которая выходит из вершины и возвращается в неё, называется петлёй. Граф, содержащий только часть дуг исходного графа, называется частичным графом. Граф, содержащий лишь часть вершин исходного графа с относящемися к нему дугами, называется подграфом.
Взвешенный граф – граф, у которого каждой дуге поставлено в соответствие конкретное число - вес дуги , в частном случае это длина дуги . Путь в графе – такая последовательность дуг, в которой конец предыдущей дуги совпадает с началом последующей: . Петля – путь, состоящий из одной дуги. Простой путь – путь, в котором каждая дуга встречается не более одного раза. Цикл (контур) – путь, в котором начальная вершина совпадает с конечной: . Длина пути – сумма длин дуг, составляющих данный путь: Полный граф – граф, в котором все вершины связаны друг с другом. · ·
· ·
Рисунок 3.2 – Полный граф Связный граф – граф, в котором есть путь из любой вершины в любую. Мультиграф – граф, у которого две вершины связаны более чем одной дугой. Псевдограф – граф, который содержит петлю. Изолированная вершина – вершина, которая не связана со всеми другими вершинами в графе. Двудольный граф – граф, у которого множество вершин является объединением двух непересекающихся множеств вершин , . Дуги могут объединять вершины различных множеств. Ациклический граф – граф, не содержащий петель.
Каждому неориентированному графу можно поставить в соответствие ориентированный граф с тем же множеством вершин, в котором каждое ребро заменено двумя ориентированными дугами, инцидентными тем же вершинам и имеющими противоположные направления. Такое соответствие называют каноническим. 3.4 Теоретические сведения
Дата добавления: 2015-08-31; Просмотров: 495; Нарушение авторских прав?; Мы поможем в написании вашей работы! Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет |