Зарегистрируйтесь, чтобы продолжить обучение

Нотации Теория графов

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

Что такое простой граф

Простыми называются графы с такими свойствами:

  • В них нет параллельных ребер — между вершинами лежит только по одному ребру

  • В них нет петель — нет ребер, которые начинаются и заканчиваются в одной и той же вершине

Рассмотрим пример визуализации простого графа:

eyJpZCI6Ijk1NGMwMjNiNTJhMWMxOWQwN2M1MDExZjAxZGVhNGYwLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=46bebdb2fa96d13202cf872f6c62040777c9d8f139087e67d5b2019eb9096db2

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

Для начала обозначим этот граф, чтобы лучше понять открывающую формулу .

У наших вершин отсутствуют метки, поэтому присвоим любой случайной вершине метку . Затем пройдемся по графу, обозначая каждую вершину буквенно-цифровым символом. Пока ничего сложного — мы просто присвоили символы вершинам нашего графа:

eyJpZCI6IjU3NWI4MTA0NmYyYjJmYTA1ZGViZDA4ZDg2N2MxNTMyLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=2e390e5e455077f0bab85c2e744d9023fec85878ae0d4b59cd7c6bcfbedafb56

Теперь построим числовую нотацию графа. Для этого мы создадим два набора обозначений:

  1. Вершины графа. Здесь все достаточно просто — это набор символов

  2. Ребра графа. Ребро — это то, что соединяет две вершины. Отсюда следует, что ребро можно представить через две вершины, которые оно соединяет. Другими словами, множество ребер содержит список координатно-подобных вершин. Например, первое ребро между вершинами и обозначается как

Запишем представление множества для остальной части графа:

eyJpZCI6ImRiN2Y0YWU1YTYyYjNmZDhiODViNTlmOTk1NDkyY2YzLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=93b2393ce3cca6778923bb7a0e090811b7d3d5ea12c2bb86cc0b6d3eeec362ea

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

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

Матричная нотация простых графов

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

В промышленности практикуются два основных типа:

  • Матрицы смежности

  • Матрицы инцидентности

Рассмотрим два этих метода и обозначим наш граф обоими способами.

Матрица смежности

Матрица смежности основана на вершинах, смежных друг с другом — еще их называют связанными или соседними. Другими словами, матрица смежности описывает, являются ли две вершины смежными ( ) или нет ( ). Каждый элемент в такой матрице — это просто булево число, описывающее связность.

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

  • Первая обозначена в строке

  • Вторая обозначена в в столбце

Таким образом, матрица смежности — это граф в виде матрицы, в которой основное внимание уделяется смежным вершинам. Давайте расшифруем наш граф в виде матрицы смежности:

eyJpZCI6ImJlYjI2YjU2MGU2NTcxZTE3ZmYxMDY4MWY2NTFlOTU1LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=0b7f4d784916fdbdbac22da9ddbf612d4bb8b4b6b49174a62ac28a84fda68902

Матрица инцидентности

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

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

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

Запишем наш пример графа в виде матрицы инцидентности:

eyJpZCI6ImU0M2JkOTJjNjE2ODJhNzJkODU0ZjljZDhiZTI4MWI4LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=2670dd5e5b222be70f805bfdab8cd4fe832023cc0bf6f926290ae5b654c74365

Сравнивая обе матричные нотации, можно вывести несколько дифференциалов:

  • В большинстве случаев, ребер всегда больше, чем вершин, поэтому матрицы смежности имеют меньше столбцов, чем матрицы инцидентности

  • По той же причине матрицы смежности более разрежены — от до . Можно предположить, что они менее информативны на элемент матрицы

  • Матрицы смежности всегда имеют форму квадрата, а матрицы инцидентности — форму прямоугольника

Ключевое различие заключается в обозначениях:

  • В первой матрице вершины представлены и в строках, и в столбцах

  • Во второй матрице вершины представлены только в строках, а столбцы обозначают ребра

Выводы

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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