Содержание
- Инцидентность и смежность в графах
- Матрицы смежности
- Матрицы инцидентности
- Списки инцидентности
- Преимущества и недостатки каждого способа
Инцидентность вершин и рёбер графа, смежность вершин графа
Инцидентность —
это когда вершина 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
Преимущества и недостатки каждого способа
Матрицы смежности и инцидентности целесообразнее использовать когда:
- число вершин графа невелико;
- число рёбер графа относительно большое;
- в алгоритме часто требуется проверять, соединены ли между собой две вершины;
- в алгоритме используются фундаментальные понятия теории графов, например, связность графа.
Из-за последнего обстоятельства матрицы чаще используются в теоретических исследованиях
графов.
Списки инцидентности целесообразнее использовать когда:
- число вершин графа велико;
- число рёбер графа относительно невелико;
- граф формируется по какой-либо модели;
- во время действия алгоритма часто требуется модифицировать граф;
- в алгоритме часто используются локальные свойства вершин, например, например, окрестности вершин.
На практике списки чаще используются в прикладных целях.
Загрузка...
