АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Матрица смежности

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

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

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

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

Граф	Матрица смежности

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

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

Недостатком являются требования к памяти, прямо пропорциональные квадрату количества вершин.

• Двумерный массив;
• Матрица с пропусками;
• Неявное задание (при помощи функции).

Дата добавления: 2015-09-27 | Просмотры: 495 | Нарушение авторских прав