Например, a ≡ b означает "A равно B"
жүктеу/скачать 83,07 Kb.
|
Дискретт3 математика жауап
Алгоритм Флойда-Уоршелла это алгоритм, который позволяет найти кратчайшие пути между всеми парами вершин во взвешенном ориентированном графе. Алгоритм работает за время �(�3)O(n3), где �n - число вершин в графе. Алгоритм Флойда-Уоршелла основан на динамическом программировании и использует матрицу расстояний �d, в которой хранятся длины кратчайших путей между вершинами. Изначально матрица �d заполняется весами ребер графа, если ребро существует, и бесконечностью, если ребра нет. Затем алгоритм выполняет �n итераций, на каждой из которых пытается улучшить значения в матрице �d, используя вершину с номером �k в качестве промежуточной. Для этого алгоритм перебирает все пары вершин �i и �j и проверяет, можно ли уменьшить расстояние между ними, если пройти через вершину �k. Если да, то алгоритм обновляет значение �[�][�]d[i][j] по формуле �[�][�]=min(�[�][�],�[�][�]+�[�][�])d[i][j]=min(d[i][j],d[i][k]+d[k][j]). После выполнения всех итераций матрица �d содержит длины кратчайших путей между всеми парами вершин. Если в графе есть циклы отрицательного веса, то алгоритм обнаружит это, если в матрице �d появятся отрицательные значения на диагонали, то есть �[�][�]<0d[i][i]<0 для некоторого �i. В этом случае кратчайшие пути не определены, так как можно уменьшать длину пути, проходя по циклу отрицательного веса. Для более подробного описания алгоритма Флойда-Уоршелла см1. Цикл Гамильтона это цикл в графе, который проходит через каждую вершину графа ровно один раз. Граф, содержащий цикл Гамильтона, называется гамильтоновым графом. Например, в следующем графе существует цикл Гамильтона, проходящий через вершины �,�,�,�,�,�,�,�,�A,B,C,D,E,F,G,H,A: graph G { A -- B; A -- C; A -- D; B -- C; B -- E; C -- D; C -- F; D -- E; D -- G; E -- F; E -- H; F -- G; G -- H; } Свойства графа с циклом Гамильтона зависят от типа графа (ориентированный или неориентированный, простой или не простой, планарный или не планарный и т.д.). Однако существуют некоторые общие критерии, которые необходимы или достаточны для существования цикла Гамильтона в графе. Например, если граф является полным, то он обязательно содержит цикл Гамильтона. Если граф является двудольным, то он содержит цикл Гамильтона тогда и только тогда, когда каждая доля содержит одинаковое число вершин и граф является полным двудольным графом. Если граф является простым и неориентированным, то он содержит цикл Гамильтона тогда и только тогда, когда для любого подмножества вершин �S графа выполняется неравенство �(�−�)≤∣�∣c(G−S)≤∣S∣, где �(�−�)c(G−S) - число компонент связности в графе �−�G−S, полученном из �G удалением вершин из �S. Это неравенство называется условием Оре. Для более подробной информации о циклах Гамильтона и свойствах графов с ними см2. Граф это математическая модель, состоящая из множества вершин и множества ребер, соединяющих некоторые пары вершин. Графы широко используются в реальной жизни для представления различных объектов и их взаимосвязей. Например, графы могут быть использованы для моделирования: Сетей связи, таких как Интернет, телефонные сети, социальные сети и т.д. Вершины графа соответствуют узлам сети, а ребра - каналам связи между ними. С помощью графов можно анализировать свойства сетей, такие как пропускная способность, задержка, надежность, степень централизации и т.д. Транспортных систем, таких как дорожные сети, железные дороги, авиалинии и т.д. Вершины графа соответствуют пунктам отправления и прибытия, а ребра - маршрутам перемещения между ними. С помощью графов можно определять оптимальные пути, расписания, тарифы, потоки пассажиров и грузов и т.д. Структур данных, таких как списки, стеки, очереди, дерев жүктеу/скачать 83,07 Kb. Достарыңызбен бөлісу:
|