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

Смотреть слайды в полном размере
Презентация «Графы. Сети. Деревья»

Вы можете ознакомиться с презентацией онлайн, просмотреть текст и слайды к ней, а также, в случае, если она вам подходит - скачать файл для редактирования или печати. Документ содержит 62 слайда и доступен в формате ppt. Размер файла: 1.33 MB

Просмотреть и скачать

Pic.1
«Графы. Сети. Деревья», слайд 1
Pic.2
Графы: определения и примеры Графы: определения и примеры Путь в графе Решение логических задач Орие
Графы: определения и примеры Графы: определения и примеры Путь в графе Решение логических задач Ориентированные графы Путь в орграфе Деревья Матрица смежности
Pic.3
Говоря простым языком, граф - это множество точек (для удобства изображения - на плоскости) и попарн
Говоря простым языком, граф - это множество точек (для удобства изображения - на плоскости) и попарно соединяющих их линий (не обязательно прямых). В графе важен только факт наличия связи между двумя …
Pic.4
«Графы. Сети. Деревья», слайд 4
Pic.5
«Графы. Сети. Деревья», слайд 5
Pic.6
Граф – это графическое изображение состава и структуры системы. Граф – это графическое изображение с
Граф – это графическое изображение состава и структуры системы. Граф – это графическое изображение состава и структуры системы. Граф состоит из вершин и линий связи. Граф, содержащий симметричные (не …
Pic.7
Любому ребру соответствует ровно две вершины, а вот вершине может соответствовать произвольное колич
Любому ребру соответствует ровно две вершины, а вот вершине может соответствовать произвольное количество ребер, это количество и определяет степень вершины. Изолированная вершина вообще не имеет …
Pic.8
Теорема 1. В графе G(V,X) сумма степеней всех его вершин – число четное, равное удвоенному числу реб
Теорема 1. В графе G(V,X) сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа. Теорема 1. В графе G(V,X) сумма степеней всех его вершин – число четное, равное …
Pic.9
Граф G называется полным, если любые две его различные вершины соединены одним и только одним ребром
Граф G называется полным, если любые две его различные вершины соединены одним и только одним ребром. Граф G называется полным, если любые две его различные вершины соединены одним и только одним …
Pic.10
Две вершины называются смежными, если они являются разными концами одного ребра. Две вершины называю
Две вершины называются смежными, если они являются разными концами одного ребра. Две вершины называются смежными, если они являются разными концами одного ребра. Два ребра называются смежными, если …
Pic.11
Путь в графе - это последовательность вершин (без повторений), в которой любые две соседние вершины
Путь в графе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны. Например, в изображенном графе, есть два различных пути из вершины a в вершину с: adbc и …
Pic.12
Вершина v достижима из вершины u, если существует путь, начинающийся в u и заканчивающийся в v. Верш
Вершина v достижима из вершины u, если существует путь, начинающийся в u и заканчивающийся в v. Вершина v достижима из вершины u, если существует путь, начинающийся в u и заканчивающийся в v. Граф …
Pic.13
Длина пути - количество ребер, из которых этот путь состоит. Например, длина уже упомянутых путей ad
Длина пути - количество ребер, из которых этот путь состоит. Например, длина уже упомянутых путей adbc и abc - 3 и 2 соответственно. Длина пути - количество ребер, из которых этот путь состоит. …
Pic.14
«Графы. Сети. Деревья», слайд 14
Pic.15
«Графы. Сети. Деревья», слайд 15
Pic.16
«Графы. Сети. Деревья», слайд 16
Pic.17
«Графы. Сети. Деревья», слайд 17
Pic.18
«Графы. Сети. Деревья», слайд 18
Pic.19
«Графы. Сети. Деревья», слайд 19
Pic.20
«Графы. Сети. Деревья», слайд 20
Pic.21
«Графы. Сети. Деревья», слайд 21
Pic.22
«Графы. Сети. Деревья», слайд 22
Pic.23
«Графы. Сети. Деревья», слайд 23
Pic.24
«Графы. Сети. Деревья», слайд 24
Pic.25
«Графы. Сети. Деревья», слайд 25
Pic.26
«Графы. Сети. Деревья», слайд 26
Pic.27
«Графы. Сети. Деревья», слайд 27
Pic.28
Орграф - это граф, все ребра которого имеют направление. Такие направленные ребра называются дугами.
Орграф - это граф, все ребра которого имеют направление. Такие направленные ребра называются дугами. На рисунках дуги изображаются стрелочками ( рис. 3)
Pic.29
В отличие от ребер, дуги соединяют две неравноправные вершины: одна из них называется началом дуги (
В отличие от ребер, дуги соединяют две неравноправные вершины: одна из них называется началом дуги (дуга из нее исходит), вторая - концом дуги (дуга в нее входит). Можно сказать, что любое ребро - …
Pic.30
Путь в орграфе - это последовательность вершин (без повторений), в которой любые две соседние вершин
Путь в орграфе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны, причем каждая вершина является одновременно концом одной дуги и началом следующей дуги. …
Pic.31
«Графы. Сети. Деревья», слайд 31
Pic.32
А)Нарисуйте граф системы «Компьютер», содержащий следующие вершины: процессор, оперативная память, в
А)Нарисуйте граф системы «Компьютер», содержащий следующие вершины: процессор, оперативная память, внешняя память, клавиатура, дисплей, принтер. Соедините их направленными линиями(стрелками), …
Pic.33
Взвешенный (другое название: размеченный) граф (или орграф) - это граф (орграф), некоторым элементам
Взвешенный (другое название: размеченный) граф (или орграф) - это граф (орграф), некоторым элементам которого (вершинам, ребрам или дугам) сопоставлены числа. Наиболее часто встречаются графы с …
Pic.34
Длина пути во взвешенном (связном) графе - это сумма длин (весов) тех ребер, из которых состоит путь
Длина пути во взвешенном (связном) графе - это сумма длин (весов) тех ребер, из которых состоит путь. Расстояние между вершинами - это, как и прежде, длина кратчайшего пути. Например, расстояние от …
Pic.35
«Графы. Сети. Деревья», слайд 35
Pic.36
Существует довольно большое число разнообразных способов представления графов. Однако мы изложим зде
Существует довольно большое число разнообразных способов представления графов. Однако мы изложим здесь только самые полезные с точки зрения программирования. Существует довольно большое число …
Pic.37
Графически Граф, представленный на рис. , состоит из множества вершин и множество дуг Графически Гра
Графически Граф, представленный на рис. , состоит из множества вершин и множество дуг Графически Граф, представленный на рис. , состоит из множества вершин и множество дуг
Pic.38
Перечислением Перечислением
Перечислением Перечислением
Pic.39
Матрица инцидентности - это матрица вершин и инцидентных им дуг. Матрица инцидентности - это матрица
Матрица инцидентности - это матрица вершин и инцидентных им дуг. Матрица инцидентности - это матрица вершин и инцидентных им дуг. Дуга инцидентна вершине, если эта дуга исходит или заходит в данную …
Pic.40
Для графа, представленного на рис. матрица инцидентности имеет вид: Для графа, представленного на ри
Для графа, представленного на рис. матрица инцидентности имеет вид: Для графа, представленного на рис. матрица инцидентности имеет вид:
Pic.41
На практике в матрице инцидентности иногда нули не проставляются для наглядности. На практике в матр
На практике в матрице инцидентности иногда нули не проставляются для наглядности. На практике в матрице инцидентности иногда нули не проставляются для наглядности. Свойство матрицы инцидентности – …
Pic.42
Пример: Построить матрицу инцидентности для графа, изображённого на рисунке Пример: Построить матриц
Пример: Построить матрицу инцидентности для графа, изображённого на рисунке Пример: Построить матрицу инцидентности для графа, изображённого на рисунке
Pic.43
Пример: Построить матрицу инцидентности для графа, изображённого на рисунке (ответ) Пример: Построит
Пример: Построить матрицу инцидентности для графа, изображённого на рисунке (ответ) Пример: Построить матрицу инцидентности для графа, изображённого на рисунке (ответ)
Pic.44
Матрица инцидентности для неориентированного графа составляется по правилу: Матрица инцидентности дл
Матрица инцидентности для неориентированного графа составляется по правилу: Матрица инцидентности для неориентированного графа составляется по правилу: , если i-тая вершина инцидентна j-тому ребру; , …
Pic.45
Для графа, представленного на рис. , матрица инцидентности имеет вид: Для графа, представленного на
Для графа, представленного на рис. , матрица инцидентности имеет вид: Для графа, представленного на рис. , матрица инцидентности имеет вид:
Pic.46
Пример: Построить матрицу инцидентности для графа, изображённого на рисунке Пример: Построить матриц
Пример: Построить матрицу инцидентности для графа, изображённого на рисунке Пример: Построить матрицу инцидентности для графа, изображённого на рисунке
Pic.47
Пример: Построить матрицу инцидентности для графа, изображённого на рисунке Пример: Построить матриц
Пример: Построить матрицу инцидентности для графа, изображённого на рисунке Пример: Построить матрицу инцидентности для графа, изображённого на рисунке
Pic.48
«Графы. Сети. Деревья», слайд 48
Pic.49
Пример: Построить матрицу инцидентности для графа, изображённого на рисунке (ответ) Пример: Построит
Пример: Построить матрицу инцидентности для графа, изображённого на рисунке (ответ) Пример: Построить матрицу инцидентности для графа, изображённого на рисунке (ответ)
Pic.50
Матрица смежности Sm - это квадратная матрица размером N x N (N - количество вершин в графе), заполн
Матрица смежности Sm - это квадратная матрица размером N x N (N - количество вершин в графе), заполненная по следующему правилу: Матрица смежности Sm - это квадратная матрица размером N x N (N - …
Pic.51
«Графы. Сети. Деревья», слайд 51
Pic.52
Для неориентированного графа эта матрица определяется следующим образом. Для неориентированного граф
Для неориентированного графа эта матрица определяется следующим образом. Для неориентированного графа эта матрица определяется следующим образом. Если вершины и являются смежными, то . В противном …
Pic.53
«Графы. Сети. Деревья», слайд 53
Pic.54
Удобство матрицы смежности состоит в наглядности и прозрачности алгоритмов, основанных на ее использ
Удобство матрицы смежности состоит в наглядности и прозрачности алгоритмов, основанных на ее использовании. А неудобство - в несколько завышенном требовании к памяти: если граф далек от полного, то в …
Pic.55
Иерархическими называются системы, между элементами которых установлены отношения подчинения или вхо
Иерархическими называются системы, между элементами которых установлены отношения подчинения или вхождения друг в друга. Иерархическими называются системы, между элементами которых установлены …
Pic.56
«Графы. Сети. Деревья», слайд 56
Pic.57
«Графы. Сети. Деревья», слайд 57
Pic.58
Граф называется гамильтоновым, если для каждой вершины графа найдется маршрут начинающейся и заканчи
Граф называется гамильтоновым, если для каждой вершины графа найдется маршрут начинающейся и заканчивающей в этой вершине и проходящий через все вершины только один раз. Такой маршрут называется …
Pic.59
Графическая модель задачи коммивояжера состоит из гамильтонова графа, вершины которого изображают го
Графическая модель задачи коммивояжера состоит из гамильтонова графа, вершины которого изображают города, а ребра — связывающие их дороги. Кроме того, каждое ребро оснащено весом, обозначающим …
Pic.60
К сожалению, эффективный алгоритм решения данной задачи пока не известен. Для сложных сетей число га
К сожалению, эффективный алгоритм решения данной задачи пока не известен. Для сложных сетей число гамильтоновых циклов, которые необходимо просмотреть для выделения минимального, непомерно огромно. …
Pic.61
1. Выбрать исходную вершину и включить её в маршрут. 1. Выбрать исходную вершину и включить её в мар
1. Выбрать исходную вершину и включить её в маршрут. 1. Выбрать исходную вершину и включить её в маршрут. 2. Выбрать вершину ближайшую к данной по весу, включить её в маршрут. 3. Выбрать не …
Pic.62
«Графы. Сети. Деревья», слайд 62


Скачать презентацию

Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!