Приложения

Приложение 1.1

Базовые понятия теории графов

Теория графов — математический язык для формализованного определения понятий, связанных с анализом и синтезом структур систем и процессов.

• Граф ( GRAPH ) – вообще говоря, пара G= ( V, Е ), где V — непустое множество с вершинами, а Е — множество пар ei = ( vi 1, vi 2), vij, которые задают ребра. Обычно V называют множеством вершин, а Е — множеством ребер. Граф изображают на плоскости в виде точек (вершин) и соединяющих их линий (ребер).

• Дуга — ориентированное ребро.

• Две вершины называются смежными , если существует соединяющее их ребро.

• Ребра называются смежными , если они опираются на общую вершину.

• Вершина графа v и некоторое его ребро называются инцедентными , если е = ( v, w ) или е = ( w, v ), где w — некоторая вершина графа.

• Висячая вершина — вершина, которая инцедентна единственному ребру.

• Висячее ребро — ребро, инцедентное висячей вершине.

• Петля — ребро, инцедентное одной (единственной) вершине.

• Мультиребро — множество ребер, инцедентных одной и той же паре вершин ( u, v ).

• Мощность мультиребра — число ребер в мультиребре.

• Степень вершины — число инцедентных ей ребер. Обозначается deg ( v )).

• Вес вершины ( ребра ) – любое число (действительное, целое или рациональное), которое устанавливается в соответствие данной вершине (ребру) по каким-либо логическим соображениям.

• Эксцентриситет вершины ecc ( v ) – максимальное расстояние от v до других вершин.

• Диаметр графа diam ( G ) – максимальный эксцентриситет его вершин.

• Граф называют однородным , если степени всех его вершин одинаковы.

• Цепь в графе G = { V, Е } – последовательность вершин v 0, v 1, …vn — такая, что n > 0 и vi, vj соединены ребром. ( i = 0 ..n — 1; j = i + 1) n – длина цепи. Если вершины, входящие в цепь, различны, то цепь простая , иначе – составная.

• Цикл — замкнутая цепь.

• Обход графа — цикл, проходящий через все вершины графа по одному разу.

• Связный граф — граф, в котором из любой вершины можно найти цепь в любую другую вершину. Несвязный граф распадается на компоненты связности (максимальные связные подграфы).

• Мост — ребро графа, удаление которого увеличивает число его компонент связности.

• Корень (root) – специально выделенная по тем или иным причинам вершина.

Приложения 1.2

Обзор теорий, внесших вклад в исследования межфирменных сетей