Приложение 1.1 Базовые понятия теории графов Теория графов — математический язык для формализованного определения понятий, связанных с анализом и синтезом структур систем и процессов.
• Граф (GRAPH) – вообще говоря, пара G= (V, Е), где V — непустое множество с вершинами, а Е — множество пар ei = (vi1, vi2), vij, которые задают ребра. Обычно V называют множеством вершин, а Е — множеством ребер. Граф изображают на плоскости в виде точек (вершин) и соединяющих их линий (ребер).
• Дуга — ориентированное ребро.
• Две вершины называются смежными, если существует соединяющее их ребро.
• Ребра называются смежными, если они опираются на общую вершину.
• Вершина графа v и некоторое его ребро называются инцедентными, если е = (v, w) или е = (w, v), где w — некоторая вершина графа.
• Висячая вершина — вершина, которая инцедентна единственному ребру.
• Висячее ребро — ребро, инцедентное висячей вершине.
• Петля — ребро, инцедентное одной (единственной) вершине.
• Мультиребро — множество ребер, инцедентных одной и той же паре вершин (u, v).
• Мощность мультиребра — число ребер в мультиребре.
• Степень вершины — число инцедентных ей ребер. Обозначается deg(v)).
• Вес вершины (ребра) – любое число (действительное, целое или рациональное), которое устанавливается в соответствие данной вершине (ребру) по каким-либо логическим соображениям.
• Эксцентриситет вершины ecc(v) – максимальное расстояние от v до других вершин.
• Диаметр графа diam (G) – максимальный эксцентриситет его вершин.
• Граф называют однородным, если степени всех его вершин одинаковы.
• Цепь в графе G = {V, Е} – последовательность вершин v0, v1, ...vn — такая, что n > 0 и vi, vj соединены ребром. (i = 0..n — 1; j = i + 1) n – длина цепи. Если вершины, входящие в цепь, различны, то цепь простая, иначе – составная.
• Цикл — замкнутая цепь.
• Обход графа — цикл, проходящий через все вершины графа по одному разу.
• Связный граф — граф, в котором из любой вершины можно найти цепь в любую другую вершину. Несвязный граф распадается на компоненты связности (максимальные связные подграфы).
• Мост — ребро графа, удаление которого увеличивает число его компонент связности.
• Корень (root) – специально выделенная по тем или иным причинам вершина.
Приложения 1.2 Обзор теорий, внесших вклад в исследования межфирменных сетей Приложение 1.2 (продолжение)
Приложение 1.2 (окончание)
Источник: [Третьяк, Румянцева, 2003].
Приложение 1.3 Вопрос профессора В. Преображенского «Сегодняшняя классическая модель корпорации (а я говорю и о корпорации, с помощью которой люди управляют обществами, в том числе – государственной корпорации) исторически выросла из средневековых армий. Предтеча пирамид, с которыми мы сегодня сталкиваемся, – это модернизированная