24. Графы

граф (ориентированный) – пара множеств <ND, A>, где:

• ND — вершины
• A — (ориентированные) дуги (рёбра) (A Í ND 2), определяемые как упорядоченные пары (ndb, nde) вершин, где ndb — начало, а nde— конец дуги

инцидентность — отношение между дугой и её концевыми вершинами, т.е. дуга a = (ndb, nde) инцидентна вершинам ndb и nde, а вершины ndb и nde инцидентны дуге a = (ndb, nde); вершины ndb и nde в этом случае являются смежными, то есть связаны отношением смежности (отношением непосредственного следования, непосредственного подчинения), для выражения которого служат матрицы смежности.

путь — такая последовательность вершин и дуг S = (v0, a1, v1 .. aN, vN), что ai = (vi-1, vi) для i=1..N; данный путь называется путем из v0 в vN длины N с начальной вершиной v0, конечной вершиной vN и внутренними ( промежуточными) вершинами v1 .. vN-1; вершины на этом пути связаны отношением следования, подчинения, достижимости, для выражения которого служат матрицы смежности.

суммарный граф для набора графов - граф, содержащий объединение их вершин и объединение их дуг.

дерево (ориентированное) – это (ориентированный) граф T = такой, что:

1. существует единственная вершина, в которую не входит ни одна дуга (эта вершина называется корнем),
2. в каждую из оставшихся вершин входит ровно одна дуга,
3. существует единственный путь из корня в любую другую вершину

также означающее, что корень соединен дугами с непосредственно подчинёнными ему вершинами, представляющими корни каждого из поддеревьев этого дерева.

узел — вершина, из которой выходит хотя бы одна дуга

лист — вершина, из которой не выходит ни одной дуги

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

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

Литература

• Берж К. Теория графов и ее применения. — М.: Изд-во иностр. лит., 1962.
• Материалы сайта transform.iis.nsk.su/WikiGrapp
• Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.
• Зыков А.А. Теория конечных графов. — Новосибирск: Наука. Сиб. отд-ние, 1969.
• Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
• Харари Ф. Теория графов. — М.: Мир, 1973.

Назад Вперёд