ВУЗ:
Составители:
Рубрика:
3
Часть II.
..
. Теория графов
(Способы уменьшения заполнения в методах Гаусса и Холецкого.
Прогнозирование заполнения для симметричных положительно
определённых матриц)
§1.
..
. Основные понятия
Все рассматриваемые ниже алгоритмы относятся к символическому этапу
обработки симметричных положительно определённых матриц. Основным
инструментом при разработке таких алгоритмов является теория графов.
Между разреженными матрицами и графами существует естественное взаимно-
однозначное соответствие.
Граф G задаётся совокупностью вершин V и совокупностью рёбер E:
G(V,E). Каждое ребро r ∈ E определяется парой вершин u, v из V: r = (u,v), где
u,v ∈V.
Опр.
Если мы не различаем рёбра (u,v) и (v,u), т.е. считаем, что (u,v) = (v,u), то
граф называется неориентированным, а если различаем, то ориентированным
(орграф).
Опр.
Граф называется помеченным (пронумерованным), если каждой его
вершине присвоен порядковый номер.
Между графами и матрицами существует взаимно однозначное
соответствие.
Пусть А = {a
ij
} – симметричная матрица (n×n). Каждой i-той строке матрицы
(i=1,..,n) поставим в соответствие вершину v
i
и каждому ненулевому элементу
a
ij
поставим в соответствие ребро (v
i
,v
j
). Таким образом, получим граф G(V,E).
Так как матрица симметрична, т.е. a
ij
= a
ji
, то граф является
неориентированным. Пара (v
i
,v
j
) будет являться ребром в том и только том
случае, когда a
ij
≠ 0. Если матрица А симметрична и положительно определена,
то все её диагональные элементы a
ii
≠ 0, поэтому диагональному элементу
a
ii
≠ 0 соответствует в этом случае петля (v
i
,v
i
) и предположение о том, что
a
ii
≠ 0 для ∀i, отвечает тому, что граф содержит все петли. Поэтому обычно нет
необходимости явно учитывать наличие петель в графе для этого случая и,
таким образом, по любому неориентированному помеченному графу можно
однозначно построить портрет симметричной положительно определённой
матрицы (СПОМ).
В дальнейшем будут рассматриваться только такие матрицы.
Опр.
Две вершины v
i
и v
j
графа G(V,E) называются смежными, если они
соединены ребром. Говорят, что ребро (v
i,
v
j
) инцидентно вершинам v
i
, v
j
.
Опр. Степенью вершины v
i
называется число инцидентных ей ребер.
3
Часть II.. Теория графов
(Способы уменьшения заполнения в методах Гаусса и Холецкого.
Прогнозирование заполнения для симметричных положительно
определённых матриц)
§1.. Основные понятия
Все рассматриваемые ниже алгоритмы относятся к символическому этапу
обработки симметричных положительно определённых матриц. Основным
инструментом при разработке таких алгоритмов является теория графов.
Между разреженными матрицами и графами существует естественное взаимно-
однозначное соответствие.
Граф G задаётся совокупностью вершин V и совокупностью рёбер E:
G(V,E). Каждое ребро r ∈ E определяется парой вершин u, v из V: r = (u,v), где
u,v ∈V.
Опр. Если мы не различаем рёбра (u,v) и (v,u), т.е. считаем, что (u,v) = (v,u), то
граф называется неориентированным, а если различаем, то ориентированным
(орграф).
Опр. Граф называется помеченным (пронумерованным), если каждой его
вершине присвоен порядковый номер.
Между графами и матрицами существует взаимно однозначное
соответствие.
Пусть А = {aij} симметричная матрица (n×n). Каждой i-той строке матрицы
(i=1,..,n) поставим в соответствие вершину vi и каждому ненулевому элементу
aij поставим в соответствие ребро (vi,vj). Таким образом, получим граф G(V,E).
Так как матрица симметрична, т.е. aij = aji, то граф является
неориентированным. Пара (vi,vj) будет являться ребром в том и только том
случае, когда aij ≠0. Если матрица А симметрична и положительно определена,
то все её диагональные элементы aii ≠0, поэтому диагональному элементу
aii ≠0 соответствует в этом случае петля (vi,vi) и предположение о том, что
aii ≠0 для ∀i, отвечает тому, что граф содержит все петли. Поэтому обычно нет
необходимости явно учитывать наличие петель в графе для этого случая и,
таким образом, по любому неориентированному помеченному графу можно
однозначно построить портрет симметричной положительно определённой
матрицы (СПОМ).
В дальнейшем будут рассматриваться только такие матрицы.
Опр. Две вершины vi и vj графа G(V,E) называются смежными, если они
соединены ребром. Говорят, что ребро (vi,vj) инцидентно вершинам vi, vj.
Опр. Степенью вершины vi называется число инцидентных ей ребер.
