Что значит соседние вершины
соседние вершины
Смотреть что такое «соседние вершины» в других словарях:
Полигональная сетка — Пример полигональной сетки, изображающей дельфина. Полигональная сетка (англ. polygon mesh) или неструктурированная сетка это совок … Википедия
Приполярный Урал — География Приполярный Урал наиболее высокая часть горной системы Урала. Именно здесь расположена высшая точка Уральских гор Народа (Народная), 1894,5 м. Выделяются еще несколько относительно высоких вершин, отличающихся альпийским рельефом:… … Энциклопедия туриста
Многоугольник — У этого термина существуют и другие значения, см. Многоугольник (значения). Примеры многоугольников Многоугольник это геометрическая фигура, обычно оп … Википедия
Гарц — У этого термина существуют и другие значения, см. Гарц (значения). Гарц … Википедия
Мишабель — нем. Mischabel … Википедия
Многоугольник — В элементарной геометрии М. называется фигура, ограниченная прямыми линиями, называемыми сторонами. Точки, в которых стороны пересекаются, называются вершинами. Число вершин равняется числу сторон. Смотря по этому числу, М. называются:… … Энциклопедический словарь Ф.А. Брокгауза и И.А. Ефрона
Многоугольник — Многоугольник. В элементарной геометрии М. называется фигура,ограниченная прямыми линиями, называемыми сторонами. Точки, в которыхстороны пересекаются, называются вершинами. Число вершин равняется числусторон. Смотря по этому числу, М. называются … Энциклопедия Брокгауза и Ефрона
Диоскуры — Питер Пауль Рубенс Похищение дочерей Левкиппа. 1617 18. Старая пинакотека. Мюнхен Диоскуры (др. греч … Википедия
Выпуклый многоугольник — Пентаграмма вписанная в правильный выпуклый пятиугольник: все диагонали лежат внутри Выпуклым многоугольником называется многоугольник, обладающий тем свойством, что все его точки лежат по одну сторону от любой прямой, проходящей через две его… … Википедия
Сторона — Сторона: Сторона многоугольника отрезок, соединяющий две его соседние вершины. Сторона обязательства Сторона международного договора Воюющие стороны Стороны света Стороны монеты: аверс и реверс Стороны кассеты: «А» и «Б» Используется в названиях… … Википедия
Значение слова «вершина»
1. Верхняя, самая высокая часть чего-л. Горные вершины Спят во тьме ночной. Лермонтов, Из Гете. Шумел ветер в голых тополях, уходящих вершинами в сумрак. А. Н. Толстой, Хмурое утро.
2. чего. Высшая степень чего-л. — Уважай сомнения и вопросы: они — переполненный избыток, роскошь жизни и являются больше на вершинах счастья, когда нет грубых желаний. И. Гончаров, Обломов. [Островский], на вершине своей славы, незадолго до смерти, был привлечен к управлению Малым театром. Немирович-Данченко, Из прошлого.
Источник (печатная версия): Словарь русского языка: В 4-х т. / РАН, Ин-т лингвистич. исследований; Под ред. А. П. Евгеньевой. — 4-е изд., стер. — М.: Рус. яз.; Полиграфресурсы, 1999; (электронная версия): Фундаментальная электронная библиотека
Вершина местности (горы, горного хребта).
Вершина синтаксической группы
ВЕРШИ’НА, ы, ж. (книжн.). 1. Самая высокая часть чего-н. В. горы. 2. перен. Высшая степень достижения. В. творчества. ◊
Источник: «Толковый словарь русского языка» под редакцией Д. Н. Ушакова (1935-1940); (электронная версия): Фундаментальная электронная библиотека
верши́на
1. самая верхняя часть объекта, обычно — вытянутого по вертикали ◆ Вершина горы. ◆ Вершина небоскрёба. ◆ На вершине этого холма лежит усадьба, состоящая из одного необитаемого господского домика и сада. Тургенев, «Три встречи», 1852 г. ◆ Утро было прекрасное, солнце освещало вершины лип, пожелтевших уже под свежим дыханием осени. Пушкин, «Капитанская дочка», 1836 г.
2. геометр. точка пересечения сторон угла, смежных сторон многоугольника, смежных рёбер многогранника или образующих линий конуса ◆ Вершина угла. ◆ Вершина треугольника. ◆ Вершина пирамиды.
3. матем. то же, что узел ◆ Вершина графа, не связанная ребром ни с одной вершиной, называется изолированной.
4. перен. наивысшее достижение ◆ Эта книга стала вершиной его творчества.
Обход графа: поиск в глубину и поиск в ширину простыми словами на примере JavaScript
Доброго времени суток.
Что такое обход графа?
Простыми словами, обход графа — это переход от одной его вершины к другой в поисках свойств связей этих вершин. Связи (линии, соединяющие вершины) называются направлениями, путями, гранями или ребрами графа. Вершины графа также именуются узлами.
Двумя основными алгоритмами обхода графа являются поиск в глубину (Depth-First Search, DFS) и поиск в ширину (Breadth-First Search, BFS).
Несмотря на то, что оба алгоритма используются для обхода графа, они имеют некоторые отличия. Начнем с DFS.
Поиск в глубину
DFS следует концепции «погружайся глубже, головой вперед» («go deep, head first»). Идея заключается в том, что мы двигаемся от начальной вершины (точки, места) в определенном направлении (по определенному пути) до тех пор, пока не достигнем конца пути или пункта назначения (искомой вершины). Если мы достигли конца пути, но он не является пунктом назначения, то мы возвращаемся назад (к точке разветвления или расхождения путей) и идем по другому маршруту.
Давайте рассмотрим пример. Предположим, что у нас есть ориентированный граф, который выглядит так:
Мы находимся в точке «s» и нам нужно найти вершину «t». Применяя DFS, мы исследуем один из возможных путей, двигаемся по нему до конца и, если не обнаружили t, возвращаемся и исследуем другой путь. Вот как выглядит процесс:
Здесь мы двигаемся по пути (p1) к ближайшей вершине и видим, что это не конец пути. Поэтому мы переходим к следующей вершине.
Мы достигли конца p1, но не нашли t, поэтому возвращаемся в s и двигаемся по второму пути.
Достигнув ближайшей к точке «s» вершины пути «p2» мы видим три возможных направления для дальнейшего движения. Поскольку вершину, венчающую первое направление, мы уже посещали, то двигаемся по второму.
Мы вновь достигли конца пути, но не нашли t, поэтому возвращаемся назад. Следуем по третьему пути и, наконец, достигаем искомой вершины «t».
Так работает DFS. Двигаемся по определенному пути до конца. Если конец пути — это искомая вершина, мы закончили. Если нет, возвращаемся назад и двигаемся по другому пути до тех пор, пока не исследуем все варианты.
Мы следуем этому алгоритму применительно к каждой посещенной вершине.
Необходимость многократного повторения процедуры указывает на необходимость использования рекурсии для реализации алгоритма.
Заметка: этот специальный DFS-алгоритм позволяет проверить, возможно ли добраться из одного места в другое. DFS может использоваться в разных целях. От этих целей зависит то, как будет выглядеть сам алгоритм. Тем не менее, общая концепция выглядит именно так.
Анализ DFS
Давайте проанализируем этот алгоритм. Поскольку мы обходим каждого «соседа» каждого узла, игнорируя тех, которых посещали ранее, мы имеем время выполнения, равное O(V + E).
Краткое объяснение того, что означает V+E:
V — общее количество вершин. E — общее количество граней (ребер).
Может показаться, что правильнее использовать V*E, однако давайте подумаем, что означает V*E.
V*E означает, что применительно к каждой вершине, мы должны исследовать все грани графа безотносительно принадлежности этих граней конкретной вершине.
С другой стороны, V+E означает, что для каждой вершины мы оцениваем лишь примыкающие к ней грани. Возвращаясь к примеру, каждая вершина имеет определенное количество граней и, в худшем случае, мы обойдем все вершины (O(V)) и исследуем все грани (O(E)). Мы имеем V вершин и E граней, поэтому получаем V+E.
Далее, поскольку мы используем рекурсию для обхода каждой вершины, это означает, что используется стек (бесконечная рекурсия приводит к ошибке переполнения стека). Поэтому пространственная сложность составляет O(V).
Теперь рассмотрим BFS.
Поиск в ширину
BFS следует концепции «расширяйся, поднимаясь на высоту птичьего полета» («go wide, bird’s eye-view»). Вместо того, чтобы двигаться по определенному пути до конца, BFS предполагает движение вперед по одному соседу за раз. Это означает следующее:
Вместо следования по пути, BFS подразумевает посещение ближайших к s соседей за одно действие (шаг), затем посещение соседей соседей и так до тех пор, пока не будет обнаружено t.
Чем DFS отличается от BFS? Мне нравится думать, что DFS идет напролом, а BFS не торопится, а изучает все в пределах одного шага.
Далее возникает вопрос: как узнать, каких соседей следует посетить первыми?
Для этого мы можем воспользоваться концепцией «первым вошел, первым вышел» (first-in-first-out, FIFO) из очереди (queue). Мы помещаем в очередь сначала ближайшую к нам вершину, затем ее непосещенных соседей, и продолжаем этот процесс, пока очередь не опустеет или пока мы не найдем искомую вершину.
Анализ BFS
Может показаться, что BFS работает медленнее. Однако если внимательно присмотреться к визуализациям, можно увидеть, что они имеют одинаковое время выполнения.
Очередь предполагает обработку каждой вершины перед достижением пункта назначения. Это означает, что, в худшем случае, BFS исследует все вершины и грани.
Несмотря на то, что BFS может казаться медленнее, на самом деле он быстрее, поскольку при работе с большими графами обнаруживается, что DFS тратит много времени на следование по путям, которые в конечном счете оказываются ложными. BFS часто используется для нахождения кратчайшего пути между двумя вершинами.
Таким образом, время выполнения BFS также составляет O(V + E), а поскольку мы используем очередь, вмещающую все вершины, его пространственная сложность составляет O(V).
Аналогии из реальной жизни
Если приводить аналогии из реальной жизни, то вот как я представляю себе работу DFS и BFS.
Когда я думаю о DFS, то представляю себе мышь в лабиринте в поисках еды. Для того, чтобы попасть к цели мышь вынуждена много раз упираться в тупик, возвращаться и двигаться по другому пути, и так до тех пор, пока она не найдет выход из лабиринта или еду.
Упрощенная версия выглядит так:
В свою очередь, когда я думаю о BFS, то представляю себе круги на воде. Падение камня в воду приводит к распространению возмущения (кругов) во всех направлениях от центра.
Упрощенная версия выглядит так:
Выводы
Общие понятия теории графов
Графом называется набор точек (эти точки называются вершинами), некоторые из которых объявляются смежными (или соседними). Считается, что смежные вершины соединены между собой ребрами (или дугами).
Таким образом, ребро определяется парой вершин. Два ребра, у которых есть общая вершина, также называются смежными (или соседними).
Граф называется ориентированным (или орграфом), если некоторые ребра имеют направление. Это означает, что в орграфе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет. Геометрически граф часто изображают точками плоскости, причем соседние вершины соединены дугами (для орграфа некоторые дуги имеют направление, что обычно отмечают стрелкой).
Помимо этого, в теории графов рассматриваются также мультиграфы – это такие графы, в которых могут быть петли (т. е. некоторая вершина соединена сама с собой ребром) или некоторые пары вершины могут быть соединены между собой несколькими ребрами.
Маршрут в графе – это последовательность соседних (смежных) вершин. Ясно, что можно определить маршрут и как последовательность смежных ребер (в этом случае ребра приобретают направление). Заметим, что в маршруте могут повторяться вершины, но не ребра. Маршрут называется циклом, если в нем первая вершина совпадает с последней.
Путь в графе (иногда говорят простой путь) – это маршрут без повторения вершин (а значит, и ребер).
Контур – это цикл без повторения вершин, за исключением первой вершины, совпадающей с последней.
Последовательности вершин (рис. 1): 1–2–3–4–2–5 не простой путь, а маршрут; последовательности 1–2–3–4–7–5 и 1–2–5 – простые пути; 1–2–3–4–2–5–6–1 –это цикл (но не контур); 1–2–5–6–1 – это контур.
Если имеется некоторый маршрут из вершины t в вершину s, заданный в виде последовательности ребер, которые в этом случае приобрели направление, и если в этот маршрут входит ребро, соединяющее вершины (i, j), то это ребро по отношению к вершине i называют иногда прямой дугой, а по отношению к вершине j – обратной дугой (или обратным ребром).
Граф называется связным, если любые две его вершины можно соединить маршрутом (или путем). На рис. 1 изображен связный граф.
Ребро, при удалении которого граф перестает быть связным, иногда называют мостом или перешейком.
Следующее определение имеет смысл только для графов или мультиграфов без петель (но не для орграфов).
Степень вершины – это число ребер, входящих в эту вершину. Вершина называется висячей, если ее степень равна единице.
Лемма 1. Если степень всех вершин в графе больше или равна двум, то граф обязательно содержит контур.
Именно с задач, поставленных и решенных Леонардом Эйлером, началась теория графов. Философ Иммануил Кант, гуляя по городу Кенигсбергу (сейчас этот город называется Калининград), поставил задачу (1736), известную в математике как задача о семи кенигсбергских мостах: можно ли пройти по всем этим мостам и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти только один раз. Наш петербургский знаменитый математик швейцарского происхождения Леонард Эйлер блестяще решил эту задачу. На рис. 2 изображена схема семи мостов Кенигсберга (заметим, что сейчас осталось только два из них), а также мультиграф, соответствующий этой схеме (при построении графа считалось, что каждый берег реки и острова – это вершины графа, а мосты – его ребра; видно, что в данном случае у нас получился мультиграф без петель).
В соответствии с поставленной Кантом (и решенной Эйлером) задачей можно дать следующие определения:
Граф (или мультиграф без петель) называется эйлеровым, если существует цикл без повторения ребер (такой цикл называют эйлеровым), обходящий все вершины графа. Граф называется полуэйлеровым, если существует маршрут без повторения ребер (эйлеров путь), обходящий все ребра графа ровно один раз. На рис. 3 изображены: а – эйлеров граф, б – полуэйлеров граф и в – граф, не являющийся ни эйлеровым, ни полуэйлеровым (люди старшего поколения знают, что в школах раньше было много загадок типа “можно ли нарисовать данную фигуру не отрывая ручку от бумаги”, что и соответствует эйлерову или полуэйлерову графу).
Теорема (Эйлер). Для того чтобы данный связный граф (не орграф, но, возможно, мультиграф без петель) был эйлеровым, необходимо и достаточно, чтобы степени всех вершин были четными.Данный связный граф будет полуэйлеровым тогда и только тогда, когда степени двух вершин будут нечетными, а степени остальных вершин – четными.
Матрицы в графах
Трудно переоценить роль матриц в теории графов (в частности, матрицы полезны, чтобы данный граф более “легко” воспринимался компьютером). Перечислим наиболее известные матрицы.
1. Матрица смежности. Это квадратная матрица порядка п (п – число вершин), в которой нули стоят по главной диагонали (если в графе нет петель, а если петли есть в вершине k (и число этих петель равно р), то на главной диагонали в строчке с номером k стоит число р). Если вершина i связана с вершиной j одним ребром, то элемент матрицы смежности aij равен 1, если эти вершины связаны s ребрами, то аij= s. Аналогичным образом строятся матрицы смежности для орграфов и для мультиграфов.
Легко видеть, что матрица В =А 2 = АА составлена из целых чисел bij, которые равны числу путей длины 2, соединяющих вершины i и j. Понятно, что А 3 составлена из чисел, равных числу путей длины 3 (т. е. путей из 3-х ребер) из вершины i в вершину j и т. д.
2. Матрица инциденций – это матрица размера n m, где n – число вершин, а m – число ребер графа, при этом ее элементы kij равны 1, если вершина с номером i является для ребра с номером j начальной или конечной (если ребро неориентировано) и начальной для ориентированных ребер. Заметим, что матрица инциденций сравнительно редко используется, так как в современных условиях (где число ребер часто очень велико) она имеет слишком большое число столбцов.
3. Структурная матрица. Именно эта матрица имеет особое значение в теории сетей связи. Структурная матрица – это символьная матрица порядка п. Она составляется следующим образом: на главной диагонали стоит 1, т. е. aii = 1, остальные элементы – это символьные обозначения ребер (если вершины i и j не соединены ребром, то aii = 0). При этом, если при i j – это отрицание а, которое обычно отмечается чертой сверху. Если связи вершины i c вершиной j нет, то соответствующий элемент равен 0, структурная матрица может составляться и для орграфа и для мультиграфа без петель (здесь если два ребра а и b соединяют две вершины, то соответствующий элемент при i j этот элемент равен 
Отметим, что в учебных целях, когда действия с матрицами осуществляются студентами “вручную” (число вершин в графе невелико), можно обозначать ребра латинскими буквами без индексов a, b, c и т. д., но при использовании компьютера гораздо удобнее обозначать ребра а(i,j), если это ребро соединяет вершины i и j при i j.
Теорема. Для того чтобы найти все пути (простые) из вершины i в вершину j достаточно раскрыть минор M(j,i) структурной матрицы методами булевой алгебры. При этом раскрытие минора производится обычными действиями с определителями, но при этом сложение заменяется дизъюнкцией, умножение – конъюнкцией, знаки умножения на числа не используются.
Подробно доказывать эту теорему не будем, но отметим, что определитель равен сумме (в данном случае дизъюнкции) элементов, взятых по одному из каждой строчки и каждого столбца с определенным знаком. В нашем случае знаки не присутствуют, а значит, любой член раскрытия определителя всей структурной матрицы S соответствует циклу в графе. Если же брать минор M(j,i), то его раскрытие соответствует тем членам определителя, в которых имелся элемент s(j,i), но без самого этого элемента (таким образом, индексы i и j встречаются вместо двух только один раз). Это и означает, что получаем маршрут от вершины с номером i к вершине с номером j.
Понятно, что раскрытие минора методами булевой алгебры предусматривает, что верны следующие соотношения: 1 a = 1, 
(это свойство нужно, для того чтобы не проходить по одному ребру дважды в противоположных направлениях), а также используется правило простого поглощения (х ху = х). Видно, что если не использовать правило поглощения, то получим все маршруты (без повторения ребер), связывающие вершины i и j.
Примечание. 1. Если граф не ориентирован, то миноры M(j,i) и M(i,j) совпадают.
2. После получения ответа, черточки над обозначениями ребер (т. е. отрицания) можно убрать (на самом деле “черта” над ребром означает, что ребро проходится от вершины с большим номером к вершине с меньшим номером). Затем рекомендуется записать каждый путь по порядку прохождения ребер (в этом случае удобны обозначения ребер с индексами вершин).
Сечением (разрезом) между вершинами i и j называется неизбыточный набор ребер, при удалении которых из графа теряется связь между данными вершинами (не существует пути из вершины i в вершину j). Заметим, что сечений между данными вершинами может быть много, и они могут содержать разное количество ребер.
Слово “неизбыточный” означает, что если любое ребро из сечения снова возвратить в граф, то связь восстановится.
Естественно, что если известны все пути из вершины i в вершину j, причем эти пути заданы в виде ДНФ, т. е. дизъюнктивной нормальной формы (а именно такой вид получается после раскрытия соответствующего минора структурной матрицы), то все сечения между этими вершинами можно получить отрицанием этих путей (по правилу де Моргана конъюнкцию заменить на дизъюнкцию и наоборот), затем полученное выражение снова привести к ДНФ, используя раскрытие скобок по обычным правилам, при этом правило поглощения обеспечит неизбыточность набора ребер в каждом сечении. Ясно, что знаки отрицания (черточки над символами ребер) можно опустить. Пример на эту тему приведен в разд. 15 (примеры решения типовых задач).
Дата добавления: 2016-06-22 ; просмотров: 2770 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ