Матричные способы задания графов. Упорядочение элементов орграфа
Читайте также:
|
.
.
.
На рисунке 12 изображен смешанный граф с вершинами v1, v2,¼, v6, ребрами e1, e2, e3, e5 и дугой e4. Смежные вершины v1, v2, инциденты ребру e1. Вершины v1, v3, инциденты параллельным ребрам e2 и e3. Вершине v4 инциденты петля e5 и дуга e4, причем v4 является началом дуги e4, а v5 – концом этой дуги. Степень вершины v1 равна 3, вершины v2 – 1, вершины v3 – 2, вершины v4 – 3, вершины v5 – 1, вершины v6 – 0. Таким образом, вершины v2 и v5 – висячие, а вершина v6 – изолированная. В случае дуги e4 точнее было бы говорить о полустепенях исхода и захода вершин v4 и v5, а именно: полустепень исхода вершины v4 равна 3, вершины v5 – 0, полустепень захода вершины v4 равна 2, вершины v5 – 1.
| e1 | e2 | e3 | e4 | e5 |
| v1 | ||||
| v2 | ||||
| I= | v3 | |||
| v4 | ||||
| v5 | -1 | |||
| v6 |
По этой матрице легко судить о наличии в графе параллельных ребер (два одинаковых столбца), петли (одна единица в столбце), дуги (значения разных знаков в столбце), изолированной вершины (нулевая строка), висячих вершин (одно ненулевое значение в строке).
б) Матрица смежности вершин – это квадратная матрица, размер которой определяется числом вершин в графе. Элементы этой матрицы определяются так: 
. Если в графе имеются параллельные ребра, то соответствующий элемент матрицы смежности полагают равным числу этих ребер. Так матрица смежности для графа на рисунке 12 такова:
| v1 | v2 | v3 | v4 | v5 | v6 |
| v1 | |||||
| v2 | |||||
| S= | v3 | ||||
| v4 | |||||
| v5 | |||||
| v6 |
По виду этой матрицы также несложно судить о наличии в графе кратных ребер, дуг, петель, висячих и изолированных вершин.
Дата добавления: 2015-10-19 ; просмотров: 17479 ; ЗАКАЗАТЬ НАПИСАНИЕ РАБОТЫ
Источник
Лабораторная работа №8
МАТРИЧНЫЕ СПОСОБЫ ПРЕДСТАВЛЕНИЯ ГРАФОВ
Целью работы является изучение матричных способов представления графов.
2 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
В последнее время теория графов стала простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем. Это проблемы проектирования интегральных схем и схем управления, исследования автоматов, логических цепей, блок-схем программ, экономики и статистики, химии и биологии, теории расписаний и дискретной оптимизации.
2.1 ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ
Граф G задается множеством точек или вершин x1,x2. xn (которое обозначается через X) и множеством линий или ребер a1,a2,…,an (которое обозначается символом А), соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается (и обозначается) парой (X, А).
Если ребра из множества А ориентированы, что обычно показывается стрелкой, то они называются дугами, и граф с такими ребрами называется ориентированным графом (орграф) (рисунок 1(а)). Если ребра не имеют ориентации, то граф называется неориентированным (неорграф) (рисунок 1(б)). В случае когда G=(X, А) является ориентированным графом и мы хотим пренебречь направленностью дуг из множества А, то неориентированный граф, соответствующий G, будем обозначать как G=(X, А).
Если дуга обозначается упорядоченной парой, состоящей из начальной и конечной вершин (т. е. двумя концевыми вершинами дуги), ее направление предполагается заданным от первой вершины ко второй. Так, например, на рисунке 1(а) обозначение (x1,x2) относится к дуге a1, а (x2,x1) — к дуге a2.
Другое, употребляемое чаще описание ориентированного графа G состоит в задании множества вершин Х и соответствия Г, которое показывает, как между собой связаны вершины. Соответствие Г называется отображением множества Х в Х, а граф в этом случае обозначается парой G=(X,Г).
В случае неориентированного графа или графа, содержащего и дуги, и неориентированные ребра (см., например, графы, изображенные на рисунках 1(б) и 1(в)), предполагается, что соответствие Г задает такой эквивалентный ориентированный граф, который получается из исходного графа заменой каждого неориентированного ребра двумя противоположно направленными дугами, соединяющими те же самые вершины. Так, например, для графа, приведенного на рисунке 1(б), имеем Г(x5)=<x1,x3,x4>, Г(x1)=<x5> и др.
Поскольку прямое соответствие или образ вершины Г(xi) представляет собой множество таких вершин xjX, для которых в графе G существует дуга (xi,xj), то через Г -1 (xi) естественно обозначить множество вершин xk, для которых в G существует дуга (xk,xi). Такое отношение принято называть обратным соответствием или прообразом вершины. Для графа, изображенного на рисунке 1(а), имеем
Отображение Г(Г(xi)) записывается как Г 2 (xi). Аналогично «тройное» отображение Г(Г(Г(xi))) записывается как Г 3 (xi) и т. д. Для графа, показанного на рисунке 1(а), имеем:
Д
угиa=(xi,xj), xixj, имеющие общие концевые вершины, называются смежными. Две вершины xi и xj называются смежными, если какая-нибудь из двух дуг (xi,xj) и (xj,xi) или обе одновременно присутствуют в графе. Так, например, на рисунке 2 дуги a1, a10, a3 и a6 как и вершины x5 и x3, являются смежными, в то время как дуги a1 и a5 или вершины x1 и x4 не являются смежными.
исло дуг, которые имеют вершинуxi своей начальной вершиной, называется полустепенью исхода вершины xi, и, аналогично, число дуг, которые имеют xi своей конечной вершиной, называется полустепенью захода вершины xi.
Очевидно, что сумма полустепеней захода всех вершин графа, а также сумма полустепеней исхода всех вершин равны общему числу дуг графа G, т. е.
, (1)
где n — число вершин и m — число дуг графа G.
Петлей называется дуга, начальная и конечная вершины которой совпадают. На рисунке 3, например, дуги a3 и a10 являются петлями.
Тут вы можете оставить комментарий к выбранному абзацу или сообщить об ошибке.
Источник
