🗊Презентация Графы. Сети. Деревья

Графы: определения и примеры Графы: определения и примеры Путь в графе Решение логических задач Ориентированные графы Путь в орграфе Деревья Матрица смежности

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

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

Любому ребру соответствует ровно две вершины, а вот вершине может соответствовать произвольное количество ребер, это количество и определяет степень вершины. Изолированная вершина вообще не имеет ребер (ее степень равна 0). Любому ребру соответствует ровно две вершины, а вот вершине может соответствовать произвольное количество ребер, это количество и определяет степень вершины. Изолированная вершина вообще не имеет ребер (ее степень равна 0). Граф называется нуль – графом, если он состоит из изолированных вершин. Вершина графа называется висячей, если степень ее 1.

Теорема 1. В графе G(V,X) сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа. Теорема 1. В графе G(V,X) сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа. Пример. Пусть граф содержит 5 ребер, тогда степень этого графа равна r=5·2=10 Вершина называется четной, если  ее степень есть четное число и нечетной, если степень ее есть нечетное число. Теорема 2. Число нечетных вершин любого графа – четно. Следствие. Невозможно начертить граф с нечетным числом нечетных вершин.

Граф G называется полным, если любые две его различные вершины соединены одним и только одним ребром. Граф G называется полным, если любые две его различные вершины соединены одним и только одним ребром. Полный граф определяется только своими вершинами. Степень любой вершины полного графа, очевидно, равна k= п – 1, где п – число его вершин. Число ребер этого графа равно числу сочетаний из п по 2 Дополнением графа G(V, X) называется граф G‘(V, X‘), которой состоит из вершин первого графа и ребер, которые дополняют первый граф до полного графа.

Две вершины называются смежными, если они являются разными концами одного ребра. Две вершины называются смежными, если они являются разными концами одного ребра. Два ребра называются смежными, если они выходят из одной вершины.

Путь в графе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны. Например, в изображенном графе, есть два различных пути из вершины a в вершину с: adbc и abc. Путь в графе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны. Например, в изображенном графе, есть два различных пути из вершины a в вершину с: adbc и abc.

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

Длина пути - количество ребер, из которых этот путь состоит. Например, длина уже упомянутых путей adbc и abc - 3 и 2 соответственно. Длина пути - количество ребер, из которых этот путь состоит. Например, длина уже упомянутых путей adbc и abc - 3 и 2 соответственно. Расстояние между между вершинами u и v - это длина кратчайшего пути от u до v. Из этого определения видно, что расстояние между вершинами a и c в графе на рис. равно 2. Цикл - это замкнутый путь. Все вершины в цикле, кроме первой и последней, должны быть различны. Например, циклом является путь abda в графе на рис.

Орграф - это граф, все ребра которого имеют направление. Такие направленные ребра называются дугами. На рисунках дуги изображаются стрелочками ( рис.3)

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

Путь в орграфе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны, причем каждая вершина является одновременно концом одной дуги и началом следующей дуги. Например, в орграфе на рис. 3 нет пути, ведущего из вершины 2 в вершину 5. "Двигаться" по орграфу можно только в направлениях, заданных стрелками. Путь в орграфе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны, причем каждая вершина является одновременно концом одной дуги и началом следующей дуги. Например, в орграфе на рис. 3 нет пути, ведущего из вершины 2 в вершину 5. "Двигаться" по орграфу можно только в направлениях, заданных стрелками.

А)Нарисуйте граф системы «Компьютер», содержащий следующие вершины: процессор, оперативная память, внешняя память, клавиатура, дисплей, принтер. Соедините их направленными линиями(стрелками), обозначающими отношение «передает информацию». А)Нарисуйте граф системы «Компьютер», содержащий следующие вершины: процессор, оперативная память, внешняя память, клавиатура, дисплей, принтер. Соедините их направленными линиями(стрелками), обозначающими отношение «передает информацию». Б)К предыдущему графу добавьте пунктирные направленные линии, обозначающие отношение «управляет»(работой всех устройств управляет процессор).

Взвешенный (другое название: размеченный) граф (или орграф) - это граф (орграф), некоторым элементам которого (вершинам, ребрам или дугам) сопоставлены числа. Наиболее часто встречаются графы с помеченными ребрами. Числа-пометки носят различные названия: вес, длина, стоимость.

Длина пути во взвешенном (связном) графе - это сумма длин (весов) тех ребер, из которых состоит путь. Расстояние между вершинами - это, как и прежде, длина кратчайшего пути. Например, расстояние от вершины a до вершины d во взвешенном графе, изображенном на рис. 4, равно 6. Длина пути во взвешенном (связном) графе - это сумма длин (весов) тех ребер, из которых состоит путь. Расстояние между вершинами - это, как и прежде, длина кратчайшего пути. Например, расстояние от вершины a до вершины d во взвешенном графе, изображенном на рис. 4, равно 6.

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

Графически Граф, представленный на рис., состоит из множества вершин и множество дуг Графически Граф, представленный на рис., состоит из множества вершин и множество дуг

Перечислением Перечислением

Матрица инцидентности - это матрица вершин и инцидентных им дуг. Матрица инцидентности - это матрица вершин и инцидентных им дуг. Дуга инцидентна вершине, если эта дуга исходит или заходит в данную вершину. Вершина инцидентна дуге, если в эту вершину заходит или исходит данная дуга. В матрице инцидентности в первом столбце расположены вершины, в первой строке – дуги. Остальные ячейки матрицы инцидентности заполняются по следующему правилу: , если из i-той вершины исходит j-тая дуга: , если в i-той вершину заходит j-тая дуга; , если i-тая вершина не инцидента j-той дуге; , если из i-той вершины исходит j-тая дуга и в нее же заходит, т.е. в i-той вершине j-тая дуга образует петлю.

Для графа, представленного на рис. матрица инцидентности имеет вид: Для графа, представленного на рис. матрица инцидентности имеет вид:

На практике в матрице инцидентности иногда нули не проставляются для наглядности. На практике в матрице инцидентности иногда нули не проставляются для наглядности. Свойство матрицы инцидентности – сумма элементов по столбцам равна 0 или 2.

Пример: Построить матрицу инцидентности для графа, изображённого на рисунке Пример: Построить матрицу инцидентности для графа, изображённого на рисунке

Пример: Построить матрицу инцидентности для графа, изображённого на рисунке (ответ) Пример: Построить матрицу инцидентности для графа, изображённого на рисунке (ответ)

Матрица инцидентности для неориентированного графа составляется по правилу: Матрица инцидентности для неориентированного графа составляется по правилу: , если i-тая вершина инцидентна j-тому ребру; , если i-тая вершина не инцидента j-тому ребру; , если в i-той вершине j-тое ребро образует петлю.

Для графа, представленного на рис., матрица инцидентности имеет вид: Для графа, представленного на рис., матрица инцидентности имеет вид:

Пример: Построить матрицу инцидентности для графа, изображённого на рисунке Пример: Построить матрицу инцидентности для графа, изображённого на рисунке

Пример: Построить матрицу инцидентности для графа, изображённого на рисунке Пример: Построить матрицу инцидентности для графа, изображённого на рисунке

Пример: Построить матрицу инцидентности для графа, изображённого на рисунке (ответ) Пример: Построить матрицу инцидентности для графа, изображённого на рисунке (ответ)

Матрица смежности Sm - это квадратная матрица размером N x N (N - количество вершин в графе), заполненная по следующему правилу: Матрица смежности Sm - это квадратная матрица размером N x N (N - количество вершин в графе), заполненная по следующему правилу: Если в графе имеется ребро e, соединяющее вершины u и v, то Sm[u,v] = Ves(e), в противном случае Sm[u,v] = “-”.

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

Удобство матрицы смежности состоит в наглядности и прозрачности алгоритмов, основанных на ее использовании. А неудобство - в несколько завышенном требовании к памяти: если граф далек от полного, то в массиве, хранящем матрицу смежности, оказывается много "пустых мест" (нулей). Кроме того, для "общения" с пользователем этот способ представления графов не слишком удобен: его лучше применять только для внутреннего представления данных. Удобство матрицы смежности состоит в наглядности и прозрачности алгоритмов, основанных на ее использовании. А неудобство - в несколько завышенном требовании к памяти: если граф далек от полного, то в массиве, хранящем матрицу смежности, оказывается много "пустых мест" (нулей). Кроме того, для "общения" с пользователем этот способ представления графов не слишком удобен: его лучше применять только для внутреннего представления данных.

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

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

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

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

1. Выбрать исходную вершину и включить её в маршрут. 1. Выбрать исходную вершину и включить её в маршрут. 2. Выбрать вершину ближайшую к данной по весу, включить её в маршрут. 3. Выбрать не использованные вершины ближайшую к последней, включить её в маршрут. 4. Вернуться к шагу 2 если не использованы все вершины. 5. Включить в маршрут исходную вершину.