Летние международные олимпиады для 1-11 классов Участвовать→
Конкурс разработок «Пять с плюсом» июнь 2021
Добавляйте свои материалы в библиотеку и получайте ценные подарки
Конкурс проводится с 1 июня по 30 июня

Конспект лекции по теме "Матрицы инцидентности и смежности"

Данная разработка представляет собой конспект лекции на тему "Матрицы инцидентности и смежности по дисциплине "Элементы математической логики" и раскрывает данную тему. Данный материал может использоваться преподавателями среднеспециальных и высших учебных заведений при изучении данной дисциплины
Просмотр
содержимого документа

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

 

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

Если вершины и ребра (дуги) графа (орграфа) занумерованы, соответствующие множества имеют вид: V = {v1, v2, ...,vn}; Е = {e1, е2, ...,еm},то отношение инцидентности можно определить матрицей, имеющей m строк и п столбцов. Столбцы соответствуют вершинам (узлам) графа, строки - ребрам (дугам).

Матрицей инцидентности графа G сn вершинами и т ребрами называется матрица B(G)={bij}размерности т x n, элементы которой определяются по формулам:

1, если i е реброинцидентно j йвершине; bij    

0, впротивномслучае

Матрицей инцидентности орграфа D cn вершинами и т дугами называется матрица B(D)={bij}размерности т х п, элементы которой определяются по формулам:

1, еслиi е реброисходитиз j йвершины bij 0, еслиi е ребронеинцидентно j йвершине

1, еслиi е ребро заходитв j йвершину

Если ориентированный граф содержит петлю, то в соответствующее место матрицы D ставится произвольное число отличное от -1, 0 или 1.

Пример 1

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

image 

Граф G, изображенный на рисунке - неориентированный. В составляемой матрице столбцы

соответствуют вершинам графа, строки – ребрам графа. Так как количество ребер графа равно 4, а число вершин равно 4, то матрица инцидентности B(G) будет иметь размерность 4*4. Эта матрица состоит из 0 и 1. Запись в матрице ведется построчно. В i -ой строке ставим единицу в тех столбцах, в которых соответствующие вершины инцидентны ребру ei, в остальных столбцах ставим нули.

Таким образом, матрица инцидентности данного графа будет иметь вид:

imageimage1 0 0 1

1 1 0 0

B(G)  

0 1 0 1

0 1 1 0

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

V

imageimageе111 V02 V03 V41

                                                                                                             е21     1    0    0

B(G)

                                                                                                              е30     1    0    1

                                                                                                             е40     1    1    0

Пример 2

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

image 

Граф Д изображенный на рисунке - ориентированный, В составляемой матрице столбцы со-

ответствуют узлам графа, строки – дугам графа. Запись в матрице ведется построчно. Таким образом, матрица инцидентности данного графа будет иметь вид:

imageimage                                                                                                             1         0 0          0

                                                                                                               1            0 0 1

B(D) 1 1 0             0 0 1 0 1 0 1 1 0

 

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

Другим матричным способом задания графа (орграфа) является задание его матрицы смежности.

Две вершины в графе (орграфе) называются смежными, если они инцидентны одному и тому же ребру (дуге).

Матрицей смежности графа G = (V, Е), где V={v1, v2, ..., vn},называется квадратная матрица A(G) = {аij} порядка n, элементы которой определяются по формулам:

aij k,гдеk 0,1,2,...числорёбер инцидентныхпареvi,vj

Матрицей смежности орграфа D = (V, Е), где V={v1, v2, ..., vn}, называется квадратная матрица A(D) = {аij} порядка п, элементы которой определяются по формулам:

aij k,гдеk 0,1,2,...числодугсначаломвvi иконцомвvj

Пример 3

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

image 

Граф G, изображенный на рисунке - неориентированный. В составляемой матрице столбцы и

строки соответствуют вершинам графа. Так как количество вершин графа равно 4, то матрица инцидентности - это квадратная матрица порядка 4. Матрица может состоять из любых значений. Данные значения определяются количеством рѐбер, связывающих рассматриваемые вершины. Запись в матрице ведется построчно. Таким образом, матрица смежности данного графа будет иметь вид:

0         imageimage1 0 1

1         0 1 1

A(G)

0         1 0 0

1         1 0 0

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

V

V 1 V2 V3 V4

imageimage                                                                                                               10     1    0    1

V

                                                                                             A(G) 21     0    1    1

V

                                                                                                               30     1    0    0

V

                                                                                                               41     1    0    0

Пример 4

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

image 

Граф Д изображенный на рисунке - ориентированный, В составляемой матрице столбцы и

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

0        imageimage0     0       1

1        0     1       0

A(D)

0        0     0       0

1        1     0       0

 

 

Информация о публикации
Загружено: 26 марта
Просмотров: 131
Скачиваний: 0
Фоминых Ирина Владимировна
Прочее, СУЗ, Уроки

Проверьте знания своих учеников интересными заданиями

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

Скачать материал