Зарегистрируйтесь для доступа к 15+ бесплатным курсам по программированию с тренажером

Диграфы Теория графов

В этом уроке мы познакомимся с направленным графом — диграфом. Также расскажем, чем он отличается от обычного графа и как его можно построить и представить.

Что такое диграф

В теории графов существует понятие направленного графа или диграфа, когда к ребрам добавляют направление:

eyJpZCI6IjkzMWQ0OGQyZDY4YzI0NDgwN2FiZTQyYjUxZjZmZjI5LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=5cdfd14f39c027987de089b5467212beb7518a42997bfe2f590c0fca862b570c

Диграфы применяют для моделирования дорожных сетей. Неориентированный граф может моделировать только двусторонние дороги, но направленный граф дает возможность построить дорогу и с односторонним движением.

Если дорожная сеть состоит из дорог с односторонним и двусторонним движением, мы можем использовать пары направленных ребер. Например, по одному в каждом направлении для дорог с двусторонним движением.

В качестве другого примера можно привести графы, которые часто используются для моделирования состояний в игре. Состояния — это вершины, а ребра между вершинами указывают на возможность перехода из одного состояния в другое в игре.

Во многих играх ходы работают только в одну сторону, как в шашках или шахматах. Поэтому для моделирования состояний многих игр больше подходит направленный граф, чем неориентированный.

Если ребра графа — это двухэлементные подмножества вершин, то в направленном графе вместо подмножеств мы используем упорядоченные пары для ребер.

Направленные пути и циклы в диграфе — это пути и циклы, которые учитывают ориентацию ребер. Например, ниже показаны направленный путь и направленный цикл :

eyJpZCI6IjM0YzNiMWM2NmVjYzc3ZmEzOTk1M2EwODE1NzVmZjVjLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=cdfe642715e20b91c2095593cffe6c883c40451210f1f86042c9f95e349e0133

В обоих случаях все ребра идут в одном направлении, когда вы прослеживаете путь и цикл. Граф, который лежит в основе диграфа, получен из диграфа удалением всех направлений из ребер.

Один из способов построения диграфа — взять обычный граф и добавить направления к его ребрам. Это называется ориентацией графа.

Диграф — это пара , где:

  • — множество объектов (вершины)

  • — коллекция упорядоченных пар элементов (направленные ребра)

Направленное ребро из в мы обычно записываем как . Вершина называется головной, а - хвостовой. Мы также можем создавать мультиграфы, в которых разрешены циклы и множественные ребра.

Понятие степени вершины теперь разделяется на два понятия: indegree и outdegree. Indegree (полустепень захода вершины) вершины — это общее количество ребер, направленных из других вершин в , а outdegree (полустепень исхода вершины) — общее количество ребер, направленных из в другие вершины.

Чтобы лучше разобраться с диграфами, рассмотрим несколько теорем.

Теоремы о диграфах

Одной из первых теорем, которую мы рассмотрели, была формула Degree sum — сумма степеней вершин в графе в два раза больше числа ребер. У нее есть аналог для диграфов.

Теорема для формулы суммы степеней для диграфов. В любом диграфе сумма полустепеней захода вершины всех вершин равна количеству ребер в диграфе. Аналогично — сумма отступов всех вершин равна количеству ребер в диграфе.

Докажем данную теорему. У каждого ребра есть голова и хвост. Голова вносит в сумму отступов, а хвост — в сумму заступов.

Теорема о четных степенях для эйлеровых графов также имеет хороший аналог для диграфов. Напомним, что у графа есть эйлеровая схема, когда каждая вершина имеет четную степень.

Есть версия и для сильно связанных диграфов — то есть для диграфов, в которых существует путь из любой вершины в любую другую, или граф содержит ровно одну сильно связную компоненту. Рассмотрим ее:

У сильно связного диграфа есть эйлерова схема, когда полустепени захода вершины каждой вершины совпадают с ее полустепенями исхода вершины

Теперь разберем, как можно представить диграфы.

Представление диграфов

Ранее мы представляли граф в виде списка смежности. Вот вариант для диграфа:

class Digraph(dict):
def add(self, v):
if v not in self:
self[v] = []
def add_edge(self, u, v):
self[u].append(v)

Если вы посмотрите на оригинал, то увидите, что этот класс digraph точно такой же, только в нем нет строки self[v]` и append(u) в методе add_edge. Это то, что делает ребра двусторонними в обычном графе. Если ее не добавить, мы получим одностороннее ребро.

Выводы

В этом уроке мы познакомились с направленным графом — диграфом. Чтобы его построить, нужно взять обычный граф и добавить направления к его ребрам. Этим он и будет отличаться от обычного графа. Диграфы помогают моделировать дорожные сети не только с двусторонним движением, но и с односторонним.


Аватары экспертов Хекслета

Остались вопросы? Задайте их в разделе «Обсуждение»

Вам ответят команда поддержки Хекслета или другие студенты

Об обучении на Хекслете

Для полного доступа к курсу нужен базовый план

Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.

Получить доступ
1000
упражнений
2000+
часов теории
3200
тестов

Открыть доступ

Курсы программирования для новичков и опытных разработчиков. Начните обучение бесплатно

  • 130 курсов, 2000+ часов теории
  • 1000 практических заданий в браузере
  • 360 000 студентов
Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»

Наши выпускники работают в компаниях:

Логотип компании Альфа Банк
Логотип компании Aviasales
Логотип компании Yandex
Логотип компании Tinkoff

Используйте Хекслет по-максимуму!

  • Задавайте вопросы по уроку
  • Проверяйте знания в квизах
  • Проходите практику прямо в браузере
  • Отслеживайте свой прогресс

Зарегистрируйтесь или войдите в свой аккаунт

Отправляя форму, вы принимаете «Соглашение об обработке персональных данных» и условия «Оферты», а также соглашаетесь с «Условиями использования»
Изображение Тото

Задавайте вопросы, если хотите обсудить теорию или упражнения. Команда поддержки Хекслета и опытные участники сообщества помогут найти ответы и решить задачу