Слайды и текст доклада
Pic.2
Графы: определения и примеры Графы: определения и примеры Путь в графе Решение логических задач Ориентированные графы Путь в орграфе Деревья Матрица смежности
Pic.3
Говоря простым языком, граф - это множество точек (для удобства изображения - на плоскости) и попарно соединяющих их линий (не обязательно прямых). В графе важен только факт наличия связи между двумя …
Pic.6
Граф – это графическое изображение состава и структуры системы. Граф – это графическое изображение состава и структуры системы. Граф состоит из вершин и линий связи. Граф, содержащий симметричные (не …
Pic.7
Любому ребру соответствует ровно две вершины, а вот вершине может соответствовать произвольное количество ребер, это количество и определяет степень вершины. Изолированная вершина вообще не имеет …
Pic.8
Теорема 1. В графе G(V,X) сумма степеней всех его вершин – число четное, равное удвоенному числу ребер графа. Теорема 1. В графе G(V,X) сумма степеней всех его вершин – число четное, равное …
Pic.9
Граф G называется полным, если любые две его различные вершины соединены одним и только одним ребром. Граф G называется полным, если любые две его различные вершины соединены одним и только одним …
Pic.10
Две вершины называются смежными, если они являются разными концами одного ребра. Две вершины называются смежными, если они являются разными концами одного ребра. Два ребра называются смежными, если …
Pic.11
Путь в графе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны. Например, в изображенном графе, есть два различных пути из вершины a в вершину с: adbc и …
Pic.12
Вершина v достижима из вершины u, если существует путь, начинающийся в u и заканчивающийся в v. Вершина v достижима из вершины u, если существует путь, начинающийся в u и заканчивающийся в v. Граф …
Pic.13
Длина пути - количество ребер, из которых этот путь состоит. Например, длина уже упомянутых путей adbc и abc - 3 и 2 соответственно. Длина пути - количество ребер, из которых этот путь состоит. …
Pic.28
Орграф - это граф, все ребра которого имеют направление. Такие направленные ребра называются дугами. На рисунках дуги изображаются стрелочками ( рис. 3)
Pic.29
В отличие от ребер, дуги соединяют две неравноправные вершины: одна из них называется началом дуги (дуга из нее исходит), вторая - концом дуги (дуга в нее входит). Можно сказать, что любое ребро - …
Pic.30
Путь в орграфе - это последовательность вершин (без повторений), в которой любые две соседние вершины смежны, причем каждая вершина является одновременно концом одной дуги и началом следующей дуги. …
Pic.32
А)Нарисуйте граф системы «Компьютер», содержащий следующие вершины: процессор, оперативная память, внешняя память, клавиатура, дисплей, принтер. Соедините их направленными линиями(стрелками), …
Pic.33
Взвешенный (другое название: размеченный) граф (или орграф) - это граф (орграф), некоторым элементам которого (вершинам, ребрам или дугам) сопоставлены числа. Наиболее часто встречаются графы с …
Pic.34
Длина пути во взвешенном (связном) графе - это сумма длин (весов) тех ребер, из которых состоит путь. Расстояние между вершинами - это, как и прежде, длина кратчайшего пути. Например, расстояние от …
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.49
Пример: Построить матрицу инцидентности для графа, изображённого на рисунке (ответ) Пример: Построить матрицу инцидентности для графа, изображённого на рисунке (ответ)
Pic.50
Матрица смежности Sm - это квадратная матрица размером N x N (N - количество вершин в графе), заполненная по следующему правилу: Матрица смежности Sm - это квадратная матрица размером N x N (N - …
Pic.52
Для неориентированного графа эта матрица определяется следующим образом. Для неориентированного графа эта матрица определяется следующим образом. Если вершины и являются смежными, то . В противном …
Pic.54
Удобство матрицы смежности состоит в наглядности и прозрачности алгоритмов, основанных на ее использовании. А неудобство - в несколько завышенном требовании к памяти: если граф далек от полного, то в …
Pic.55
Иерархическими называются системы, между элементами которых установлены отношения подчинения или вхождения друг в друга. Иерархическими называются системы, между элементами которых установлены …
Pic.58
Граф называется гамильтоновым, если для каждой вершины графа найдется маршрут начинающейся и заканчивающей в этой вершине и проходящий через все вершины только один раз. Такой маршрут называется …
Pic.59
Графическая модель задачи коммивояжера состоит из гамильтонова графа, вершины которого изображают города, а ребра — связывающие их дороги. Кроме того, каждое ребро оснащено весом, обозначающим …
Pic.60
К сожалению, эффективный алгоритм решения данной задачи пока не известен. Для сложных сетей число гамильтоновых циклов, которые необходимо просмотреть для выделения минимального, непомерно огромно. …
Pic.61
1. Выбрать исходную вершину и включить её в маршрут. 1. Выбрать исходную вершину и включить её в маршрут. 2. Выбрать вершину ближайшую к данной по весу, включить её в маршрут. 3. Выбрать не …
Скачать презентацию
Если вам понравился сайт и размещенные на нем материалы, пожалуйста, не забывайте поделиться этой страничкой в социальных сетях и с друзьями! Спасибо!