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

Матричный.

3.1. Большинство задач автоматизации конструирования схем удобно решать при использовании матричного способа представления графов. Квадратная таблица R=//r_i,j // _n*n называется матрица смежности, если ее элементы образуются по правилу:

r_i,j = 1, если вершина x_i соединена с x_j ребром, т.е. x_i смежна x_j;

r_i,j = 0, в противном случае.

Заметим, что для мультиграфа и смешанного графа задают:

r_i,j = p, если вершина x_i соединена с вершиной x_j p числом ребер;

r_i,j = 0 в противном случае.

Очевидно, что для задания неорграфов можно использовать треугольную матрицу R, так как r_i,j = r_j,i. Так для графа на рисунке1 матрица смежности R представлена таблицей на рисунке 2.

Рисунок 1.

Рисунок 2.

а, треугольная матрица R^* для этого же графа запишется:

Строки и столбцы матрицы смежности R cоответствуют вершинам графа. На пересечении i-й строки и j-го столбца ставится элемент r_i,j, соответствующий числу ребер, соединяющих вершины x_i и x_j. Строки и столбцы матрицы R можно нумеровать числами натурального ряда, соответствующими индексам помеченных вершин. Петлям в графе соответствуют элементы r_i,i главной диагонали матрицы R. Преимущесво использования матриц смежности - это простота выполнения преобразований и операций над графами, как для конструктора, так и для ЭВМ.

Граф можно задавать также матрицей ИНЦИДЕНЦИЙ B, строки которой соответствуют вершинам графа, столбцы - рёбрам. Элементы b_i,j матрицы B могут принимать значения (0 или 1):

b_i,j = 1, если ребро u_k инцидентно вершине x_i;

b_i,j = 0, если ребро u_k не инцидентно вершине x_i.

Рисунок 3.

Для графа, представленного на рисунке 3, матрица инциденций B имеет вид:

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