27. Теорема Эйлера и теория графов
Теория графов возникла в 18 веке с интересной историей.
Кенигсберг был городом в исторической Пруссии (современная Россия) с 7 мостами, которые пересекали реку Прегель.
Было задано:
Можно ли обойти Кёнигсберг по каждому мосту ровно по одному разу?
Обратите внимание, что не имело значения, что мы закончили именно там, где начали.
Мы вернемся к этому после изучения некоторых терминов.
График
Граф — это математическая структура, состоящая из:
- вершины (также называемые узлами или точками) (V), которые соединены
- ребра (также называемые ссылками или линиями) (E)
Он представлен как:
G = (V, E)
Степень
Количество ребер конкретной вершины называется ее степенью.
Графы обычно используются в компьютерных науках для описания отношений между различными объектами.
Например, Facebook в виде графика представляет разных людей (вершины) и их отношения (ребра).
Точно так же редакторы Википедии (edges), вносящие вклад в различные языковые версии Wikipedia (vertices) в течение одного летнего месяца, можно представить в виде графика, как показано ниже.
Используя приведенный выше пример Кенигсберга, город с рекой и ее мостами можно схематически описать следующим образом.
Эйлер впервые представил приведенную выше диаграмму с помощью графика, как показано ниже.
Он описал каждый массив суши с помощью вершины или узла, а каждый мост — с помощью ребра.
Эйлер вывел теорему, которая утверждает, что:
Мосты в городе можно пересечь ровно один раз, если, кроме двух, все точки имеют «четную степень».
Глядя на граф, представляющий Кенигсберг, видно, что каждая вершина имеет нечетную степень, и, следовательно, невозможно пройти по городу, пересекая каждый мост ровно один раз.
Эта теорема породила современную теорию графов, т. е. изучение графов.
28. Графики и типы
Направленный граф/орграф
gграфик, в котором ребра имеют ориентацию.
Это означает, что ребро можно пересечь только в одном направлении.
Например, график, представляющий информационный бюллетень Medium и его подписчиков.
Неориентированный граф
gграфик, в котором ребра не имеют ориентации.
Это означает, что ребро может проходить в обоих направлениях.
Например, график, представляющий отношения между друзьями на Facebook.
Цикл
Цикл — это граф, некоторые вершины которого (не менее 3) соединены в замкнутую цепь.
Циклический график
Это граф с хотя бы одним циклом.
Ациклический график
Это граф без циклов.
Подключенный график
Это граф с ребром из любой вершины в другую.
Может быть:
- Сильное соединение: если между всеми вершинами есть двунаправленные реберные соединения.
- Слабое соединение: если нет двунаправленных соединений между всеми вершинами.
Отключенный график
Граф без связанных вершин называется несвязным.
29. Трансверсальные алгоритмы графов
Поиск в глубину
Поиск в глубину (DFS) — это алгоритм поиска структур данных графа.
Алгоритм начинается с корневого узла и исследует как можно дальше каждую ветвь, прежде чем вернуться к началу.
Поиск в глубину можно определить в Python, как показано ниже.
Здесь мы определяем класс Node, где его конструктор определяет его children (соединенные вершины) и name.
Метод addChild добавляет к узлу новых потомков.
Метод depthFirstSeach рекурсивно реализует алгоритм поиска в глубину.
class Node:
def __init__(self, name):
self.children = []
self.name = name
def addChild(self, name):
self.children.append(Node(name))
return self
def depthFirstSearch(self, array):
array.append(self.name)
for child in self.children:
child.depthFirstSearch(array)
return array
Поиск в ширину
Поиск в ширину (BFS) — это еще один алгоритм поиска в структуре данных графа.
Он начинается с корневого узла и исследует все узлы в текущей ветви, прежде чем перейти к узлам в других ветвях.
Алгоритм можно определить ниже, используя метод breadthFirstSearch класса Node.
class Node:
def __init__(self, name):
self.children = []
self.name = name
def addChild(self, name):
self.children.append(Node(name))
return self
def breadthFirstSearch(self, array):
# Write your code here.
queue = [self]
while len(queue)> 0:
current = queue.pop(0)
array.append(current.name)
for child in current.children:
queue.append(child)
return array
Ознакомьтесь с другими частями этой серии ниже:
Спасибо, что прочитали эту статью!
Если вы новичок в Python или программировании в целом, ознакомьтесь с моей новой книгой под названиемThe No Bulls**t Guide To Learning Pythonниже:
