В этом уроке мы переходим от теории к практике. Мы будем работать на примерах и рассмотрим графы со специфическими свойствами. Вы узнаете больше о простых графах, матрицах и других базовых понятиях теории графов.
Что такое простой граф
Простыми называются графы с такими свойствами:
-
В них нет параллельных ребер — между вершинами лежит только по одному ребру
-
В них нет петель — нет ребер, которые начинаются и заканчиваются в одной и той же вершине
Рассмотрим пример визуализации простого графа:
Такие визуальные представления графа содержат массу полезной информации, но пока она нам недоступна. Чтобы раскрыть эти данные в удобном виде, нужно научиться описывать граф.
Для начала обозначим этот граф, чтобы лучше понять открывающую формулу .
У наших вершин отсутствуют метки, поэтому присвоим любой случайной вершине метку . Затем пройдемся по графу, обозначая каждую вершину буквенно-цифровым символом. Пока ничего сложного — мы просто присвоили символы вершинам нашего графа:
Теперь построим числовую нотацию графа. Для этого мы создадим два набора обозначений:
-
Вершины графа. Здесь все достаточно просто — это набор символов
-
Ребра графа. Ребро — это то, что соединяет две вершины. Отсюда следует, что ребро можно представить через две вершины, которые оно соединяет. Другими словами, множество ребер содержит список координатно-подобных вершин. Например, первое ребро между вершинами и обозначается как
Запишем представление множества для остальной части графа:
Как показано на рисунке выше, стандартная нотация для графа может быть идеально описана двумя отдельными наборами обозначений: один для вершин, а другой — для ребер.
Теперь представим, что нам нужно передать граф на обработку компьютеру. Как передать ему обозначения? В текущем виде это было бы неудобно, поэтому воспользуемся другим методом — матричной нотацией.
Матричная нотация простых графов
Компьютеры лучше справляются с числами, чем с распознаванием изображений. Именно поэтому спецификации графа чаще всего передаются компьютеру в матричной форме.
В промышленности практикуются два основных типа:
-
Матрицы смежности
-
Матрицы инцидентности
Рассмотрим два этих метода и обозначим наш граф обоими способами.
Матрица смежности
Матрица смежности основана на вершинах, смежных друг с другом — еще их называют связанными или соседними. Другими словами, матрица смежности описывает, являются ли две вершины смежными ( ) или нет ( ). Каждый элемент в такой матрице — это просто булево число, описывающее связность.
Вернемся к примеру —графу с множеством вершин и множеством ребер . В матрице смежности этот граф преобразуется в матрицу размера . Строки и столбцы обозначены одним и тем же единственным набором вершин для любого графа . Внутри матрицы мы находим либо , либо . В этом случае единица означает две смежные вершины:
-
Первая обозначена в строке
-
Вторая обозначена в в столбце
Таким образом, матрица смежности — это граф в виде матрицы, в которой основное внимание уделяется смежным вершинам. Давайте расшифруем наш граф в виде матрицы смежности:
Матрица инцидентности
Второй распространенный синтаксис для преобразования графов в матрицы — это матрица инцидентности.
В ней граф с множеством вершин и множеством ребер преобразуется в матрицу размером на . Строки и столбцы обозначаются как вершины и ребра соответственно. Внутри матрицы мы снова видим, что все элементы обозначены либо как , либо как — больше булевых чисел. На этот раз единица означает связь между вершиной в строке и ребром в столбце.
Интересное свойство матриц инцидентности: при сложении всех элементов в столбце всегда получается два. Это закономерно, потому что любое ребро в простом графе имеет только две вершины, соединенные с ним.
Запишем наш пример графа в виде матрицы инцидентности:
Сравнивая обе матричные нотации, можно вывести несколько дифференциалов:
-
В большинстве случаев, ребер всегда больше, чем вершин, поэтому матрицы смежности имеют меньше столбцов, чем матрицы инцидентности
-
По той же причине матрицы смежности более разрежены — от до . Можно предположить, что они менее информативны на элемент матрицы
-
Матрицы смежности всегда имеют форму квадрата, а матрицы инцидентности — форму прямоугольника
Ключевое различие заключается в обозначениях:
-
В первой матрице вершины представлены и в строках, и в столбцах
-
Во второй матрице вершины представлены только в строках, а столбцы обозначают ребра
Выводы
В этом уроке мы изучили простые графы и матрицы смежности. С этими знаниями вы сможете перейти к изучению различных типов графов, разберетесь с более запутанными графами. В итоге эта тема поможет разобраться в одной интересных областей теории графов — теории сетей.
Остались вопросы? Задайте их в разделе «Обсуждение»
Вам ответят команда поддержки Хекслета или другие студенты
Для полного доступа к курсу нужен базовый план
Базовый план откроет полный доступ ко всем курсам, упражнениям и урокам Хекслета, проектам и пожизненный доступ к теории пройденных уроков. Подписку можно отменить в любой момент.
