21. Основные понятия теории графов.

Тео́рия гра́фов — раздел дискретной математики, изучающий свойства графов.

Граф – это множество вершин (узлов), соединенных ребрами. В строгом определении графом называется такая пара множеств G = (V,E), где V – подмножество любого счетного множества, а Е – подмножество V x V

Вершина – точка, где могут сходиться/выходить рёбра и/или дуги. Множество вершин графа G обозначается V(G).

Ребро – линия, соединяющая две вершины графа.

Дуга – это ориентированное ребро.

Путь – любая последовательность работ, в которой конечное событие каждой работы совпадает с начальным событием следующей работы.

Критический путь – (1 определение) наиболее продолжительный путь в сетевых графиках. (2 определение) работы этого пути определяют общую продолжительность работы над проектом.

Сеть – это граф, в котором существует лишь одна вешина, обознающая источник и одна вершина, обозначающая сток.

Источник – вершина, с которой начинается граф.

Сток – конечная вершина графа.

22. Модели структурного баланса.

1. Неориентированный граф G = (V,E)

2. Знак цепи в графе – произведение знаков ребер, образующих цепь.

3. Модель структурного баланса – знаковый граф G = (V,E)

4. Положительный знак ребра – симпатия между группами a и b

5. Отрицательный знак ребра – антипатия между группами a и b

Типы отношений в группах из 3-х человек:

Теорема Харари.

Для знакового графа следующие утверждения эквивалентны:

1. Граф G сбалансирован.

2. Любые две цели между вершинами u и v имеют одинаковый знак.

3. Множество V можно разбить на 2 непересекающихся множества А и В так, что каждое положительное ребро соединяет вершины из одного множества и каждое отрицательное ребро из различных множеств.

23. Статусные конфликты.

Математическая модель – связный бесконтурный орграф D=(V,A) (данная математическая модель наилучшим образом определяет субординацию)

Наличие дуги из u к v означает, что элемент u является непосредственным начальником v.

Если из вершины u в вершину v, причем длина данного пути больше 1, то это означает, что u вышестоящий начальник над v.

Длина кратчайшего пути от u до v – уровень v относительно u

Мера статуса:

Свойства:

1. Если вершина u не имеет выходных дуг,

2. - получается из орграфа D добавлением в граф (часть инфы отсутствует…) вершины непосредственно доставленной из вершины u, это означает, что если сотрудник получает что-то, то его статус повышается

Введем функцию:

, где число вершин на k уровне, которые располагаются ниже вершин(ы) u.

24. Конфликты альтернатив.

Конфликт альтернатив возникает, когда необходимо выбрать наилучшую альтернативу из множества. Либо может возникнуть, когда необходимо нашу альтернативу упорядочить.

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

Математическая модель:

Орграф T = (V,A) называют турнирным, если для любой пары вершин существует ровно одна дуга , либо

Победитель турнира: максимальное число дуг.

Утверждение.

В турнире существует полный простой путь

– число выходных дуг для вершины u

Примеры: