Говорить о том, что ребро g и каждая из вершин u и y инцидентна g, стоит лишь в том случае, если g соединяет u и y. Уяснив это, перейдем к рассмотрению данного метода. Матрица инцидентности строиться по похожему, но не по тому же принципу, что и матрица смежности. Так если последняя имеет размер n×n, где n – число вершин, то матрица инцидентности – n×m, здесь n – число вершин графа, m – число ребер. То есть теперь чтобы задать значение какой-либо ячейки, нужно сопоставить не вершину с вершиной, а вершину с ребром.
В каждой ячейки матрицы инцидентности неориентированного графа стоит 0 или 1, а в случае ориентированного графа, вносятся 1, 0 или -1.
То же самое, но наиболее структурировано:
1. Неориентированный граф:
· 1 – вершина инцидентна ребру;
· 0 – вершина не инцидентна ребру.
2. Ориентированный граф:
· 1 – вершина инцидентна ребру, и является его началом;
· 0 – вершина не инцидентна ребру;
· -1 – вершина инцидентна ребру, и является его концом.
Построим матрицу инцидентности сначала для неориентированного графа (рис. 3.10), а затем для орграфа (рис. 3.11). Ребра обозначим буквами от a до e, вершины – цифрами. Все ребра графа не направленны, поэтому матрица инцидентности заполнена положительными значениями.
Рисунок 3.10 – Неориентированный граф и его матрица инцидентности
Для орграфа матрица имеет немного другой вид. В каждую из ее ячеек внесено одно из трех значений. Обратите внимание, что нули в двух этих матрицах занимают одинаковые позиции, ведь в обоих случаях структура графа одна. Но некоторые положительные единицы сменились на отрицательные, например, в неориентированном графе ячейка (1, b) содержит 1, а в орграфе -1. Дело в том, что в первом случае ребро b не направленное, а во втором – направленное, и, причем вершиной входа для него является вершина «1».
Рисунок 3.11 – Ориентированный граф и его матрица инцидентности
Каждый столбец отвечает за какое-либо одно ребро, поэтому граф, описанный при помощи матрицы инцидентности, всегда будет иметь следующий признак: любой из столбцов матрицы инцидентности содержит две единицы, либо 1 и -1 когда это ориентированное ребро, все остальное в нем – нули.
В программе матрица инцидентности задается, также как и матрица смежности, а именно при помощи двумерного массива. Его элементы могут быть инициализированы при объявлении, либо по мере выполнения программы.
Не нашли то, что искали? Воспользуйтесь поиском:
Лучшие изречения: Только сон приблежает студента к концу лекции. А чужой храп его отдаляет. 8831 — | 7545 — или читать все.
78.85.5.224 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.
Отключите adBlock!
и обновите страницу (F5)
очень нужно
Инцидентность вершин и рёбер графа, смежность вершин графа
Инцидентность — это когда вершина a является либо началом либо концом ребра e. Две вершины называются инцидентными, если у них есть общее ребро.
Для того, чтобы задать граф аналитически, множества V вершин графа и множества U рёбер графа, которые фигурировали в определении графа, будет недостаточно. Потребуется ещё и множество P троек вида (a, u, b) , указывающих какую пару a, b элементов множества вершин V соединяет тот или иной элемент u множества рёбер U графа. Элементы множества P называются инциденциями графа. Вот мы и подошли к одному из первых понятий теории графов — инцидентности.
Понятие инцидентности — одно из главных при создании структур данных для представления графов в памяти ЭВМ, к которым мы перейдём после примера 1.
Пример 1. Задать аналитически граф, представленный на рисунке ниже. (рис. А)
Решение. Распространённые ошибки — не заметить вершины графа, которые не соединены ни с одной другой вершиной, в том числе с самой собой, и не включить их во множество вершин графа, а также указать не все рёбра графа, соединяющие две вершины. Поэтому вершину f данного графа обязательно включаем во множество вершин графа V , а, рёбра 6 и 7, хотя они соединяют одну и ту же вершину саму с собой и обе не имеют направления, включаем во множество рёбер U .
Итак, задаём граф следующими множествами:
множество рёбер: U =
Смежность вершин графа — это когда две вершины графа соединены ребром.
Зададимся вопросом: можно ли поместить слона в компьютер? Ответ: можно, если слона смоделировать в виде графа, в котором вершинами являются части его тела, а рёбра соединяют те части тела, которые соединены в слоне как биологическом объекте. При этом получившийся граф должен быть представлен в памяти компьютера в понятном компьютеру виде.
В связи с широким применением графов в программировании и информационных технологиях вообще возникает вопрос о представлении графа в виде структуры данных. Различные способы представления графов в памяти компьютера отличаются объёмом занимаемой памяти и скоростью выполнения операций над графами.
Наиболее часто используются три такие структуры данных — матрица смежности, матрица инцидентности и список инцидентности.
Матрицы смежности
Матрица смежности, как и матрица инцидентности, позволяет установить множество вершин, соседних с заданной (то есть рассматриваемой в конкретной задаче), не прибегая к полному просмотру всей матрицы. Матрицы смежности обычно представляются двумерным массивом размера n x n , где n — число вершин графа.
Матрица смежности S — это квадратная матрица, в которой и число строк, и число столбцов равно n — числу вершин графа. В ячейки матрицы смежности записываются некоторые числа в зависимости от того, соединены соответствующие вершины рёбрами или нет, и от типа графа.
Матрица смежности для неориентированного графа
Элемент матрицы смежности s ij неориентированного графа определяется следующим образом:
— равен единице, если вершины v i и v j смежны;
— равен нулю, если вершины v i и v j не смежны.
Если для элемента матрицы v ij имеет место 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 |
Таким образом, матрица смежности неориентированного графа симметрична относительно главной диагонали.
Матрица смежности для ориентированного графа
Элемент матрицы смежности s ij ориентированного графа определяется следующим образом:
— равен единице, если из вершины v i в вершину v j входит дуга;
— равен нулю, если из вершины v i в вершину v j дуга не входит.
Как и для неориентированных графов, так и для ориентированных, если для элемента матрицы v ij имеет место 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 |
Таким образом, матрица смежности ориентированного графа не симметрична.
Матрица смежности для графа с кратными рёбрами
Если в графе есть вершины, соединённые между собой несколькими рёбрами, то элемент матрицы смежности s ij равен числу рёбер, соединяющих вершины v i и v j . Из этого следует, что если вершины v i и v j не соединены рёбрами, то элемент матрицы смежности s ij равен нулю.
Пример 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 |
Матрица смежности для взвешенного графа
В случае взвешенного графа элемент матрицы смежности s ij равен числу w, если существует ребро между вершинами v i и v j с весом w. Элемент s ij равен нулю, если рёбер между вершинами v i и v j не существует.
Пример 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 — число рёбер графа. Обычно в матрице инцидентности строки соответствуют вершинам графа, а столбцы — рёбрам графа.
Матрица инцидентности для неориентированного графа
Элемент матрицы инцидентности для неориентированного графа h ij определяется следующим образом:
— равен единице, если вершина v i инцидентна ребру e j ;
— равен нулю, если вершина v i не инцидентна ребру e j .
Пример 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 |
Матрица инцидентности для ориентированного графа
Элемент матрицы инцидентности для ориентированного графа h ij определяется следующим образом:
— равен минус единице, если вершина v i является началом ребра e j ;
— равен единице, если вершина v i является концом ребра e j ;
— равен нулю, если вершина v i не инцидентна ребру e j .
Пример 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. Составить списки инцидентности для графа, представленного на рисунке ниже.
Преимущества и недостатки каждого способа
Матрицы смежности и инцидентности целесообразнее использовать когда:
- число вершин графа невелико;
- число рёбер графа относительно большое;
- в алгоритме часто требуется проверять, соединены ли между собой две вершины;
- в алгоритме используются фундаментальные понятия теории графов, например, связность графа.
Из-за последнего обстоятельства матрицы чаще используются в теоретических исследованиях графов.
Списки инцидентности целесообразнее использовать когда:
- число вершин графа велико;
- число рёбер графа относительно невелико;
- граф формируется по какой-либо модели;
- во время действия алгоритма часто требуется модифицировать граф;
- в алгоритме часто используются локальные свойства вершин, например, например, окрестности вершин.
На практике списки чаще используются в прикладных целях.
На данной странице вы можете задать матрицу инцидентности и построить по ней граф
© Граф Online — создание и визуализация графа в два клика или по матрице смежности и поиск кратчайшего пути, поиск компоненты связности, поиск Эйлеровго цикла. Поделиться: Twitter, Facebook, В Контакте. 2015 — 2019