Постройте графы соответствующие каждой из весовых матриц

Постройте графы соответствующие каждой из весовых матриц

1. Постройте матрицы смежности и весовые матрицы для каждого графа:

2. Постройте графы, соответствующие каждой из матриц смежности:

3. Постройте графы, соответствующие каждой из весовых матриц:

4. Постройте орграф, соответствующий каждой из весовых матриц.

Матрица смежности графа — это квадратная матрица, в которой каждый элемент принимает одно из двух значений: 0 или 1. Прежде чем отобразить граф через матрицу смежности, рассмотрим простой пример такой матрицы (рис. 1).

Это двоичная квадратная матрица, т. к. число строк в ней равно числу столбцов, и любой из ее элементов имеет значение либо 1, либо 0. Первая строка и первый столбец (не входят в состав матрицы, а показаны здесь для легкости ее восприятия) содержат номера, на пересечении которых находится каждый из элементов, и они определяют индексное значение последних. Имея в наличии лишь матрицу такого типа, несложно построить соответствующий ей граф.

Слева на рисунке изображена все та же матрица смежности, имеющая размерность 4×4. Числа, выделенные синим, можно рассматривать как вершины смешанного графа, расположенного справа – того, представлением которого является матрица.

Для графического отображения графа необходимо уметь вычислять по матрице смежности количество его вершин, а также обладать знанием следующего правила. Когда из одной вершины в другую проход свободен (имеется ребро), тогда в ячейку заноситься 1, иначе – 0. Немного формализовав только что сказанное, получим: если из i в j существует ребро, то A[i][j]:=1, в противном случае A[i][j]:=0. Как видно, все элементы на главной диагонали равны нулю, это следствие отсутствия у графа петель. Но ни что не мешает, чтобы некоторые или все элементы главной диагонали были единицами.

В программе матрица смежности задается при помощи обычного двумерного массива, имеющего размерность n×n, где n – число вершин графа.

Читайте также:  Где искать настройки браузера яндекс

На языке C++, описать ее можно, например, так:

Для обработки на ЭВМ графы удобно представлять в виде матриц смежности и инциденций.

Матрица смежности – это квадратная матрица размерностью n x n, (где n – число вершин графа), однозначно представляющая его структуру.

A = ij>, i, j = 1, 2, . n, а каждый элемент матрицы определяется следующим образом:

Матрица инциденций представляет собой прямоугольную матрицу размером n x m, где n – количество вершин графа, а m – количество дуг графа. Обозначается матрица инциденций B = = ij>, i = 1, 2, . n, j = 1, 2, . m.

Каждый элемент матрицы определяется следующим образом:

bij = 1, если хi является начальной вершиной дуги aj,

bij = –1, если хi является конечной вершиной дуги aj,

bij = 0, если хi не является концевой вершиной дуги aj или если aj является петлей.

Рис.2. Орграф и его матричное представление: а – орграф; б – матрица смежности; в – матрица инциденций

На рис.2, а,б приведен граф и его матрица смежности, по которой можно найти характеристики вершин. Так сумма элементов i-ой строки матрицы дает полустепень исхода вершины хi, а сумма элементов i-го столбца дает полустепень захода вершины хi. По матрице смежности можно найти прямые и обратные отображения. Рассмотрим i-ю строку матрицы. Если элемент aij=1, то элемент графа хj входит в отображение Г(хi). Например, в 2-й строке матрицы А (рис.2,б) единицы стоят в 2-м и 5-м столбцах, следовательно, Г(х2) = < х2, х5>.

Для графа на рис.2,а матрица инциденций приведена на рис.4,в. Поскольку каждая дуга инцидентна двум различным вершинам, за исключением того случая, когда дуга образует петлю, то каждый столбец либо содержит один элемент равный 1 и один – равный – 1, либо все элементы столбца равны 0.

Читайте также:  Как полностью удалить игру в стим

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

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: На стипендию можно купить что-нибудь, но не больше. 9511 — | 7532 — или читать все.

Ссылка на основную публикацию
Подключить телефон к телевизору самсунг через usb
Обмен данными между различными устройствами стал гораздо проще: раньше чтобы посмотреть на телевизоре фотографии снятые на телефон, необходимо было закачать...
Пин код разблокировки сети на самсунге
Прежде всего, необходимо иметь в виду, что чаще всего, код разблокировки будет принят телефоном Samsung находящимся только в оригинальном заводском...
Пинг до серверов варфейс
В CryProxy появилась новая функция — улучшение пинга. В этой статье рассказываем, как она работает и как попробовать уменьшить пинг...
Подложка под текст картинки
Depositphotos приготовил несколько приёмов для того, чтобы вы усилили с помощью фотографии ваши визуальные истории. Презентации? Рекламные баннеры? Представление большого...
Adblock detector