Инцидентность и смежность в графах, матрицы смежности, матрицы инцидентности, списки инцидентности
Инцидентность вершин и рёбер графа, смежность вершин графа
Инцидентность - это когда вершина a является либо началом либо концом ребра e. Две вершины называются инцидентными, если у них есть общее ребро.
Для того, чтобы задать граф аналитически, множества V вершин графа и множества U рёбер графа, которые фигурировали в определении графа, будет недостаточно. Потребуется ещё и множество P троек вида (a, u, b), указывающих какую пару a, b элементов множества вершин V соединяет тот или иной элемент u множества рёбер U графа. Элементы множества P называются инциденциями графа. Вот мы и подошли к одному из первых понятий теории графов - инцидентности.
Понятие инцидентности - одно из главных при создании структур данных для представления графов в памяти ЭВМ, к которым мы перейдём после примера 1.
Пример 1. Задать аналитически граф, представленный на рисунке ниже. (рис. А)
Решение. Распространённые ошибки - не заметить вершины графа, которые не соединены ни с одной другой вершиной, в том числе с самой собой, и не включить их во множество вершин графа, а также указать не все рёбра графа, соединяющие две вершины. Поэтому вершину f данного графа обязательно включаем во множество вершин графа V, а, рёбра 6 и 7, хотя они соединяют одну и ту же вершину саму с собой и обе не имеют направления, включаем во множество рёбер U.
Итак, задаём граф следующими множествами:
множество вершин: V = {a, b, c, d, e, f}
множество рёбер: U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}
множество инциденций: P = {(b, 1, a), (b, 2, a), (a, 3, b), (b, 4, b), (b, 5, b), (c, 6, c), (c, 7, c), (b, 8, d), (d, 8, b), (b, 9, d), (b, 10, e), (b, 11, e), (e, 11, b)}
Смежность вершин графа - это когда две вершины графа соединены ребром.
Зададимся вопросом: можно ли поместить слона в компьютер? Ответ: можно, если слона смоделировать в виде графа, в котором вершинами являются части его тела, а рёбра соединяют те части тела, которые соединены в слоне как биологическом объекте. При этом получившийся граф должен быть представлен в памяти компьютера в понятном компьютеру виде.
В связи с широким применением графов в программировании и информационных технологиях вообще возникает вопрос о представлении графа в виде структуры данных. Различные способы представления графов в памяти компьютера отличаются объёмом занимаемой памяти и скоростью выполнения операций над графами.
Наиболее часто используются три такие структуры данных - матрица смежности, матрица инцидентности и список инцидентности.
Матрицы смежности
Матрица смежности, как и матрица инцидентности, позволяет установить множество вершин, соседних с заданной (то есть рассматриваемой в конкретной задаче), не прибегая к полному просмотру всей матрицы. Матрицы смежности обычно представляются двумерным массивом размера n x n, где n - число вершин графа.
Матрица смежности S - это квадратная матрица, в которой и число строк, и число столбцов равно n - числу вершин графа. В ячейки матрицы смежности записываются некоторые числа в зависимости от того, соединены соответствующие вершины рёбрами или нет, и от типа графа.
Матрица смежности для неориентированного графа
Элемент матрицы смежности sij неориентированного графа определяется следующим образом:
- равен единице, если вершины vi и vj смежны;
- равен нулю, если вершины vi и vj не смежны.
Если для элемента матрицы vij имеет место i = j, то есть элемент находится на диагонали, то этот элемент равен единице, если этот элемент имеет петлю, и нулю, если элемент не имеет петли.
Пример 2. Составить матрицу смежности для графа, представленного на рисунке ниже.
Ответ.
| V | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 1 | 1 | 0 | 0 |
| 2 | 1 | 0 | 0 | 1 | 1 |
| 3 | 1 | 0 | 0 | 0 | 1 |
| 4 | 0 | 1 | 0 | 0 | 0 |
| 5 | 0 | 1 | 1 | 0 | 0 |
Таким образом, матрица смежности неориентированного графа симметрична относительно главной диагонали.
Матрица смежности для ориентированного графа
Элемент матрицы смежности sij ориентированного графа определяется следующим образом:
- равен единице, если из вершины vi в вершину vj входит дуга;
- равен нулю, если из вершины vi в вершину vj дуга не входит.
Как и для неориентированных графов, так и для ориентированных, если для элемента матрицы vij имеет место i = j, то есть элемент находится на диагонали, то этот элемент равен единице, если этот элемент имеет петлю, и нулю, если элемент не имеет петли.
Пример 3. Составить матрицу смежности для графа, представленного на рисунке ниже.
Ответ.
| V | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 2 | 0 | 1 | 0 | 0 | 0 |
| 3 | 1 | 0 | 0 | 0 | 0 |
| 4 | 0 | 1 | 0 | 0 | 0 |
| 5 | 0 | 1 | 1 | 0 | 0 |
Таким образом, матрица смежности ориентированного графа не симметрична.
Матрица смежности для графа с кратными рёбрами
Если в графе есть вершины, соединённые между собой несколькими рёбрами, то элемент матрицы смежности sij равен числу рёбер, соединяющих вершины vi и vj. Из этого следует, что если вершины vi и vj не соединены рёбрами, то элемент матрицы смежности sij равен нулю.
Пример 4. Составить матрицу смежности для графа, представленного на рисунке ниже.
Ответ.
| V | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 3 | 2 | 0 | 0 |
| 2 | 3 | 0 | 0 | 1 | 1 |
| 3 | 2 | 0 | 0 | 0 | 1 |
| 4 | 0 | 1 | 0 | 0 | 0 |
| 5 | 0 | 1 | 1 | 0 | 0 |
Матрица смежности для взвешенного графа
В случае взвешенного графа элемент матрицы смежности sij равен числу w, если существует ребро между вершинами vi и vj с весом w. Элемент sij равен нулю, если рёбер между вершинами vi и vj не существует.
Пример 5. Составить матрицу смежности для графа, представленного на рисунке ниже.
Ответ.
| V | 1 | 2 | 3 | 4 | 5 |
| 1 | 0 | 11 | 9 | 0 | 0 |
| 2 | 11 | 0 | 0 | 5 | 8 |
| 3 | 9 | 0 | 0 | 0 | 2 |
| 4 | 0 | 5 | 0 | 0 | 0 |
| 5 | 0 | 8 | 2 | 0 | 0 |
Матрицы инцидентности
Матрица инцидентности H - это матрица размера n x m, где n - число вершин графа, m - число рёбер графа. Обычно в матрице инцидентности строки соответствуют вершинам графа, а столбцы - рёбрам графа.
Матрица инцидентности для неориентированного графа
Элемент матрицы инцидентности для неориентированного графа hij определяется следующим образом:
- равен единице, если вершина vi инцидентна ребру ej;
- равен нулю, если вершина vi не инцидентна ребру ej.
Пример 6. Составить матрицу инцидентности для графа, представленного на рисунке ниже.
Ответ.
| V | 1-2 | 1-3 | 2-4 | 2-5 | 3-5 |
| 1 | 1 | 1 | 0 | 0 | 0 |
| 2 | 1 | 0 | 1 | 1 | 0 |
| 3 | 0 | 1 | 0 | 0 | 1 |
| 4 | 0 | 0 | 1 | 0 | 0 |
| 5 | 0 | 0 | 0 | 1 | 1 |
Матрица инцидентности для ориентированного графа
Элемент матрицы инцидентности для ориентированного графа hij определяется следующим образом:
- равен минус единице, если вершина vi является началом ребра ej;
- равен единице, если вершина vi является концом ребра ej;
- равен нулю, если вершина vi не инцидентна ребру ej.
Пример 7. Составить матрицу инцидентности для графа, представленного на рисунке ниже.
Ответ.
| V | 1-2 | 1-3 | 2-4 | 2-5 | 3-5 |
| 1 | 1 | -1 | 0 | 0 | 0 |
| 2 | -1 | 0 | -1 | -1 | 0 |
| 3 | 0 | 1 | 0 | 0 | -1 |
| 4 | 0 | 0 | 1 | 0 | 0 |
| 5 | 0 | 0 | 0 | 1 | 1 |
На сайте есть пример реализации на языке программирования С++ алгоритма обхода в глубину графа, представленного матрицей инцидентности.
Списки инцидентности
Графы значительного объёма целесообразно хранить в памяти компьютера в форме списков инцидентности.
Список инцидентности одной вершины графа включает номера вершин, смежных с ней.
Ссылки на начало этих списков образуют одномерный массив, индексами которого служат номера вершин графа.
Пример 8. Составить списки инцидентности для графа, представленного на рисунке ниже.
Ответ.
1:2→3
2:1→4→5
3:1→5
4:2
5:2→3
Преимущества и недостатки каждого способа
Матрицы смежности и инцидентности целесообразнее использовать когда:
- число вершин графа невелико;
- число рёбер графа относительно большое;
- в алгоритме часто требуется проверять, соединены ли между собой две вершины;
- в алгоритме используются фундаментальные понятия теории графов, например, связность графа.
Из-за последнего обстоятельства матрицы чаще используются в теоретических исследованиях графов.
Списки инцидентности целесообразнее использовать когда:
- число вершин графа велико;
- число рёбер графа относительно невелико;
- граф формируется по какой-либо модели;
- во время действия алгоритма часто требуется модифицировать граф;
- в алгоритме часто используются локальные свойства вершин, например, например, окрестности вершин.
На практике списки чаще используются в прикладных целях.
| Назад<<< | Листать | Вперёд>>> |
