Приложения

Приложения

Приложение 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

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

Приложение 1.2 (продолжение)

Приложение 1.2 (окончание)

Источник : [Третьяк, Румянцева, 2003]. Приложение 1.3 Вопрос профессора В. Преображенского

Данный текст является ознакомительным фрагментом.