Весовая матрица графа это

Матрицей инцидентности называется матрица B = [bij ], i =1, 2, . . . , n, j = 1,2, . . . , m (где n – число вершин, а m – число ребер графа), строки которой соответствуют вершинам, а столбцы – ребрам. Элемент матрицы в неориентированном графе равен:

В случае ориентированного графа с n вершинами и m дугами элемент матрицы инцидентности равен:

Строки матрицы также соответствуют вершинам, а столбцы – дугам.

Матрица инцидентности однозначно определяет структуру графа (см. рис. 1.1. ав, д-ж). В каждом столбце матрицы B ровно две единицы. Равных столбцов нет.

Недостаток данного представления состоит в том, что требуется n m единиц памяти, большинство из которых будет занято нулями. Не всегда удобен доступ к информации. Например, для ответа на вопросы “есть ли в графе дуга (x, y)?” или “к каким вершинам ведут ребра из вершины x?” может потребоваться перебор всех столбцов матрицы.

Простой взвешенный граф может быть представлен своей матрицей весов W =[wij], где wij – вес ребра, соединяющего вершины i, j = 1,2, . , m. Веса несуществующих ребер полагаются равными ? или 0 в зависимости от задачи. Матрица весов является простым обобщением матрицы смежности.

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

Для человека наиболее естественно использовать изображения графов (рисунки, схемы) для объяснения связей между элементами какой-то системы. Поскольку информатика занимается автоматической обработкой данных с помощью компьютеров, сразу возникает вопрос: “Как представить информацию о графе в памяти компьютера?” Хранить ее в виде рисунка (растрового или векторного) неэффективно, потому что рисунок предназначен для восприятия человеком, а не компьютером.

Компьютеру удобнее всего хранить информацию в виде таблиц (массив тоже можно считать простейшей таблицей). Для описания графа часто используют квадратную таблицу, которая описывает все возможные связи между узлами (без учета дублирования). Если, например, на пересечении строки Aи столбца Bзаписано число 1, это означает, что есть ребро, соединяющее вершины Aи B; число 0 в этой ячейке означает, что такого ребра нет. Такую таблицу называют матрицей смежности. На рисунке показанаи схема дорог, соответствующий ей

Читайте также:  Вай фай пишет требуется авторизация

граф и его матрица смежности:

Единица на главной диагонали (выделенной серым цветом) показывает, что в графе есть петля — ребро, которое начинается и заканчивается в одной и той же вершине.

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

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

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

Однако с точки зрения теории графов это будет тот же самый граф, поскольку весовая матрица не изменилась. По аналогии можно вспомнить, что в математике записи 0,5, 1/2, 3/6 и 5/10 обозначают одно и то же число.

Что можно выяснить с помощью весовой матрицы? Во-первых, определить, есть ли ребро между двумя заданными вершинами, и если есть, какова его длина (вес). Для этого достаточно посмотреть в соответствующую ячейку. Например, значение, выделенное кружком на рисунке, показывает, что между вершинами Bи Cесть ребро с весом 5:

Предполагая, что веса ребер обозначают расстояния между вершинами, можно определить длину пути, проходящего через заданные вершины, — сумму длин ребер, составляющих этот путь. В данном случае длина замкнутого пути ABCDAскладывается из длин ребер AB, BC, CDи DA, которые определяются по таблице. Получаем: 3 + 5 + 6 + 4 = 18.

Наконец, полезно научиться рисовать граф по заданной весовой матрице. Нужно только помнить, что это можно сделать разными способами.

Для последней приведенной матрицы рисунок может быть, например, таким:

Вопросы и задачи:

1) Как по весовой матрице графа определить количество ребер (количество петель)?

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

Читайте также:  Где плюс и минус у зарядника телефона

3) Для каждой приведенной ниже весовой матрицы:

· определите вес ребра между вершинами Bи D(если оно есть);

· предполагая, что веса ребер обозначают расстояния между вершинами, определите длину пути ABDCEA;

· укажите, какой из трех путей — ABDC, ADECили AEBC— самый короткий, а какой самый длинный:

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

Лучшие изречения: Для студентов недели бывают четные, нечетные и зачетные. 9465 – | 7448 – или читать все.

78.85.5.224 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

Матрица смежности — один из способов представления графа в виде матрицы.

Содержание

Определение [ править | править код ]

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента aij равно числу рёбер из i-й вершины графа в j-ю вершину.

Иногда, особенно в случае неориентированного графа, петля (ребро из i-й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента aii в этом случае равно удвоенному числу петель вокруг i-й вершины.

Матрица смежности простого графа (не содержащего петель и кратных рёбер) является бинарной матрицей и содержит нули на главной диагонали.

Матрица смежности двудольного графа [ править | править код ]

Матрица смежности A двудольного графа, доли которого имеют r и s вершин, может быть записана в следующем виде

A = ( 0 r , r B B T 0 s , s ) , <displaystyle A=<egin0_&B\B^&0_end>,>

где B является r × s <displaystyle r imes s> матрицей, а 0 r , r <displaystyle 0_> и 0 s , s <displaystyle 0_> представляют r × r <displaystyle r imes r> и s × s <displaystyle s imes s> нулевые матрицы. В этом случае меньшая матрица B единственным образом представляет граф, а оставшиеся части матрицы A можно отбросить. B иногда называется матрицей бисмежности.

Формально, пусть G = ( U , V , E ) <displaystyle G=(U,V,E)> будет двудольным графом с долями U = < u 1 , … , u r ><displaystyle U=<1>,dots ,u_>> и V = < v 1 , … , v s ><displaystyle V=<1>,dots ,v_>> . Бисопряжённая матрица является r × s <displaystyle r imes s> 0–1 матрицей B, в которой b i , j = 1 <displaystyle b_=1> тогда и только тогда, когда ( u i , v j ) ∈ E <displaystyle (u_,v_)in E> .

Если G является двудольным мультиграфом или взвешенным графом, то элементами b i , j <displaystyle b_> будет число рёбер между вершинами или веса рёбер ( u i , v j ) <displaystyle (u_,v_)> соответственно.

Примеры [ править | править код ]

  • Ниже приведён пример неориентированного графа и соответствующей ему матрицы смежности A. Этот граф содержит петлю вокруг вершины 1, при этом в зависимости от конкретных приложений элемент a 11 <displaystyle a_<11>>может считаться равным либо одному (как показано ниже), либо двум.
Читайте также:  В каком устройстве компьютера происходит обработка информации
Граф Матрица смежности
( 1 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 0 1 0 0 ) <displaystyle <egin1&1&0&0&1&0\1&0&1&0&1&0\0&1&0&1&0&0\0&0&1&0&1&1\1&1&0&1&0&0\0&0&0&1&0&0end>>
  • aij — число рёбер, связывающих вершины v i <displaystyle v_>и v j <displaystyle v_>, причём в некоторых приложениях каждая петля (ребро < v i , v i ><displaystyle ,v_>>при некотором i <displaystyle i>) учитывается дважды.
  • Матрица смежности пустого графа, не содержащего ни одного ребра, состоит из одних нулей.

Свойства [ править | править код ]

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

Два графа G1 и G2 с матрицами смежности A1 и A2 являются изоморфными тогда и только тогда, когда существует перестановочная матрица P, такая что

Из этого следует, что матрицы A1 и A2 подобны, а значит имеют равные наборы собственных значений, определители и характеристические многочлены. Однако обратное утверждение не всегда верно — два графа с подобными матрицами смежности могут быть неизоморфны (это бывает в случае, если матрица P не является перестановочной, например, матрицы ( 0 1 0 0 ) <displaystyle <egin0&1\0&0end>> и ( 0 2 0 0 ) <displaystyle <egin0&2\0&0end>> являются подобными, но соответствующие им графы не изоморфны).

Степени матрицы [ править | править код ]

Если A — матрица смежности графа G, то матрица A m обладает следующим свойством: элемент в i-й строке, j-м столбце равен числу путей из i-й вершины в j-ю, состоящих из ровно m ребер.

Структура данных [ править | править код ]

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

Использование матрицы смежности предпочтительно только в случае неразреженных графов, с большим числом рёбер, так как она требует хранения по одному биту данных для каждого элемента. Если граф разрежён, то большая часть памяти напрасно будет тратиться на хранение нулей, зато в случае неразреженных графов матрица смежности достаточно компактно представляет граф в памяти, используя примерно n 2 <displaystyle n^<2>> бит памяти, что может быть на порядок лучше списков смежности.

В алгоритмах, работающих со взвешенными графами (например, в алгоритме Флойда-Уоршелла), элементы матрицы смежности вместо чисел 0 и 1, указывающих на присутствие или отсутствие ребра, часто содержат веса самих рёбер. При этом на место отсутствующих рёбер ставят некоторое специальное граничное значение (англ. sentinel ), зависящее от решаемой задачи, обычно 0 или ∞ <displaystyle infty > .

Ссылка на основную публикацию
Adblock detector