Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Матричные способы задания графов



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

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

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

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

· aij — число рёбер, связывающих вершины и , причем в некоторых приложениях при каждая петля (ребро при некотором ) учитывается дважды.

· Матрица смежности пустого графа, не содержащего ни одного ребра, состоит из одних нулей.

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

В случае ориентированного графа каждому ребру <x,y> ставится в соответствие "-1" на позиции (x,y) и "1" на позиции (y,x); если связи между вершинами нет, то ставится в соответствие "0".

Особенности:

· Не используется для графов с петлями, так как у петель одна вершина является и началом, и концом.

· В каждом столбце должны стоять две единицы, а все остальные символы - нули.

Вопрос





Дата публикования: 2014-12-08; Прочитано: 2454 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2025 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.006 с)...