Rivalry2

HTML Diff

1 added 1 removed

Original 2026-01-01

Modified 2026-02-26

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

2 <h2>Что такое простой граф</h2>

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

4 <ul><li>В них нет параллельных ребер - между вершинами лежит только по одному ребру</li>

5 <li>В них нет петель - нет ребер, которые начинаются и заканчиваются в одной и той же вершине</li>

6 </ul>Рассмотрим пример визуализации простого графа:

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

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

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

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

11 <ol><li>Вершины графа. Здесь все достаточно просто - это набор символов A, B, C, D, E, F</li>

12 <li>Ребра графа. Ребро - это то, что соединяет две вершины. Отсюда следует, что ребро можно представить через две вершины, которые оно соединяет. Другими словами, множество ребер содержит список координатно-подобных вершин. Например, первое ребро между вершинами A и B обозначается как AB</li>

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

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

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

16 <h2>Матричная нотация простых графов</h2>

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

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

19 <ul><li>Матрицы смежности</li>

20 <li>Матрицы инцидентности</li>

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

22 <h3>Матрица смежности</h3>

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

24 Вернемся к примеру -графу G с множеством вершин V и множеством ребер E. В матрице смежности этот граф преобразуется в матрицу размера V^2. Строки и столбцы обозначены одним и тем же единственным набором вершин для любого графа G. Внутри матрицы мы находим либо 0, либо 1. В этом случае единица означает две смежные вершины:

25 <ul><li>Первая обозначена в строке</li>

26 <li>Вторая обозначена в в столбце</li>

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

28 <h3>Матрица инцидентности</h3>

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

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

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

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

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

33 + Сравнивая обе матричные нотации, можно вывести несколько различий:

34 <ul><li>В большинстве случаев, ребер всегда больше, чем вершин, поэтому матрицы смежности имеют меньше столбцов, чем матрицы инцидентности</li>

35 <li>По той же причине матрицы смежности более разрежены - от 0 до 1. Можно предположить, что они менее информативны на элемент матрицы</li>

36 <li>Матрицы смежности всегда имеют форму квадрата, а матрицы инцидентности - форму прямоугольника</li>

37 </ul>Ключевое различие заключается в обозначениях:

38 <ul><li>В первой матрице вершины представлены и в строках, и в столбцах</li>

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

40 </ul><h2>Выводы</h2>

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