No Image

Что такое матрица инцидентности графа

СОДЕРЖАНИЕ
0 просмотров
22 января 2020

На рис. 1,2 изображено множество точек и множество линий , соединяющих эти точки, которые все вместе образуют граф .Если линии имеют стрелки, то граф называется ориентированным или орграфом (рис. 2).

Рис. 1. Граф . Рис. 2. Орграф .

Графы и можно представить в аналитической форме либо матрицей смежности ,либо матрицей инцидентности .

Для нашего конкретного неориентированного графа матрицы и выглядят следующим образом:

Матрица смежности для неориентированного графа всегда симметрична.

Фигурирующая в ней 2 может быть в некоторых случаях заменена на 1.

В матрице инцидентности сумма единиц по столбцам указывает на степень вершины vi. Нередко расположение вершин и ребер в этой матрице меняют местами (транспонируют). Так, для нашего конкретного орграфа матрицы и выглядят существенно иначе:

В общем случае матрица смежности для ориентированного графа уже не будет симметричной. В матрице инцидентности ставится 1, если дуга исходит из вершины, и —1, если дуга заходит в нее.

Матрица смежности и матрица инцидентности

Есть два стандартных способа представить граф G = (V,E)

– как набор списков смежных вершин

как матрицу смежности.

Первый обычно предпочтительнее, ибо дает более компактное представление разреженных графов– тех, у которых |E| много меньше |V| 2 .

Большинство стандартных алгоритмов используют именно это представление. Но в некоторых ситуациях удобнее пользоваться матрицей смежности – например, для плотных графов, у которых |EG| сравнимо с |VG| 2 .

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

Определение Матрицей смежностиграфа G = (V, E) называется квадратная булева матрицаAпорядкаn,элементы которой определяются следующим образом:

А – симметрическая матрица

На главной диагонали матрицы смежности всегда стоят 0.

Число единиц в строке равно степени соответствующей вершины.

Матрицей инцидентностиграфаGназывается булева матрица размера |V|´|G| вида

В каждом столбце матрицы ровно две единицы

Равных столбцов нет.

Например, на следующем рисунке граф задан графически, списком смежных вершин, матрицей смежности и матрицей инцидентности.

Инцидентность вершин и рёбер графа, смежность вершин графа

Инцидентность — это когда вершина 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 1 1
2 1 1 1
3 1 1
4 1
5 1 1

Таким образом, матрица смежности неориентированного графа симметрична относительно главной диагонали.

Читайте также:  Что делать если ошибка 0xc0000022

Матрица смежности для ориентированного графа

Элемент матрицы смежности s ij ориентированного графа определяется следующим образом:

— равен единице, если из вершины v i в вершину v j входит дуга;

— равен нулю, если из вершины v i в вершину v j дуга не входит.

Как и для неориентированных графов, так и для ориентированных, если для элемента матрицы v ij имеет место i = j , то есть элемент находится на диагонали, то этот элемент равен единице, если этот элемент имеет петлю, и нулю, если элемент не имеет петли.

Пример 3. Составить матрицу смежности для графа, представленного на рисунке ниже.

V 1 2 3 4 5
1 1
2 1
3 1
4 1
5 1 1

Таким образом, матрица смежности ориентированного графа не симметрична.

Матрица смежности для графа с кратными рёбрами

Если в графе есть вершины, соединённые между собой несколькими рёбрами, то элемент матрицы смежности s ij равен числу рёбер, соединяющих вершины v i и v j . Из этого следует, что если вершины v i и v j не соединены рёбрами, то элемент матрицы смежности s ij равен нулю.

Пример 4. Составить матрицу смежности для графа, представленного на рисунке ниже.

V 1 2 3 4 5
1 3 2
2 3 1 1
3 2 1
4 1
5 1 1

Матрица смежности для взвешенного графа

В случае взвешенного графа элемент матрицы смежности s ij равен числу w, если существует ребро между вершинами v i и v j с весом w. Элемент s ij равен нулю, если рёбер между вершинами v i и v j не существует.

Пример 5. Составить матрицу смежности для графа, представленного на рисунке ниже.

V 1 2 3 4 5
1 11 9
2 11 5 8
3 9 2
4 5
5 8 2

Матрицы инцидентности

Матрица инцидентности 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
2 1 1 1
3 1 1
4 1
5 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
2 -1 -1 -1
3 1 -1
4 1
5 1 1

Списки инцидентности

Графы значительного объёма целесообразно хранить в памяти компьютера в форме списков инцидентности.

Список инцидентности одной вершины графа включает номера вершин, смежных с ней.

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

Пример 8. Составить списки инцидентности для графа, представленного на рисунке ниже.

Читайте также:  Стоит ли покупать тестовый автомобиль

Преимущества и недостатки каждого способа

Матрицы смежности и инцидентности целесообразнее использовать когда:

  • число вершин графа невелико;
  • число рёбер графа относительно большое;
  • в алгоритме часто требуется проверять, соединены ли между собой две вершины;
  • в алгоритме используются фундаментальные понятия теории графов, например, связность графа.

Из-за последнего обстоятельства матрицы чаще используются в теоретических исследованиях графов.

Списки инцидентности целесообразнее использовать когда:

  • число вершин графа велико;
  • число рёбер графа относительно невелико;
  • граф формируется по какой-либо модели;
  • во время действия алгоритма часто требуется модифицировать граф;
  • в алгоритме часто используются локальные свойства вершин, например, например, окрестности вершин.

На практике списки чаще используются в прикладных целях.

Что такое матрица инцидентности?

Матрица инцидентности имеет вид представления графа в виде матрицы, в которой каждый столбец задаёт отдельную дугу. Строки матрицы при этом задают вершины. Положительное число в столбце задаёт вершину, из которой выходит дуга, а отрицательное — в которую входит. Если оба числа положительные, то дуга неориентированная.

Примеры матриц инцидентности

Граф из 3 соединённых вершин Граф с ориентированными дугами Граф из 4 вершин и одной дугой
Ссылка на граф Ссылка на граф Ссылка на граф

Использование Матрицы инцидентности в сервисе Граф Онлайн

Сервис Граф Онлайн предоставляет вам возможность создать Создать граф по матрице инцидентности.

Также вы можете редактировать существующую матрицу инцидентности. Для этого вам необходимо выбрать меню Граф -> Матрица инцидентности.

Для того чтобы использовать матрицу инцидентности, вам необходимо ввести её в правильном формате.

Формат ввода матрицы инцидентности

Вводя матрицу инцидентности, вам необходимо руководствоваться следующими правилами:

  1. Матрица должна содержать число строк равное количеству вершин и столбцов равное количеству ребер.
  2. Чтобы задать неориентированную дугу необходимо в строки, соответствующие начальной и конечной вершинам, поставить их вес.
  3. Чтобы задать ориентированную дугу необходимо в строки, соответствующие начальной вершине, поставить её вес, а в соответствующие конечной вершине, её вес со знаком минус.

А теперь рассмотрим основные ошибки ввода матриц инцидентности.

Основные ошибки ввода матриц инцидентности

© Граф Online — создание и визуализация графа в два клика или по матрице смежности и поиск кратчайшего пути, поиск компоненты связности, поиск Эйлеровго цикла. Поделиться: Twitter, Facebook, В Контакте. 2016. (Edit — History — Print — Recent Changes — Search)

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

Это интересно
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
No Image Компьютеры
0 комментариев
Adblock detector