![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Матрица смежности — один из способов представления графа в виде матрицы.
Матрица смежности графа 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; Прочитано: 2450 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!