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

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

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

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

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

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

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

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

eyJpZCI6IjU2NDhjYWVkODE3YTZiNzc4N2I1YTNjYTVjNWJhZDI5LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=a53127c41ed1135f1b9a0f23a182fa5d45b078818b5753885c3c2b9146b6adf9

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

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

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

eyJpZCI6IjIzYWI1ZjA2NDIxMTgyMDgxNjZmYzg1YThlYzM3MzNjLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=d665aec190d3c1e864d0d7424d40688f7c41ffee2e34ce2c0c733ce5d8730c91

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

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

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

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

eyJpZCI6IjdhNjBmZmFmYjdhZTE1ZmFjYmU3MDZkMGUwNzFiZjYzLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=c49fd6bad9b9b94396fc7d5c1e053ac000f9767091524fcef7866947b2495988

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

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

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

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

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

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

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

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

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

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

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

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

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

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

eyJpZCI6ImMwYmYwOWNjNTUzYjFkNzljODhlYjRmOWUyNmM2MWRhLnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=026d01c7f2bbb1f1c8c504449788d88797812e6ff01df311873f0c3dddaa5d82

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

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

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

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

eyJpZCI6ImYwMDM3NWExMjUyYzdiMWIxODA3MTg0MzEwZDcwMWE2LnBuZyIsInN0b3JhZ2UiOiJjYWNoZSJ9?signature=191bb51022d30ed5ae1da4ba70ab276f37845cbc2c772a84488c918684b8ac56

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

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

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

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

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

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

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

Выводы

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


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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Изображение Тото

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