Главная Случайная страница


Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Теория графов - раздел математики исследующий свойства конечного множества элементов с заданными связями и отношениями между ними с помощью математических и графических средств.

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

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

 

.

Геометрическое представление графов.

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

Граф - это множество вершин (точек) и множество ребер (связей), соединяющих некоторые пары вершин.

Или другими словами граф это система которая может рассматриваться как множество кружков и множество соединяющих их линий. ( см. Рисунки 8 и 9)

Пример графа - схема метрополитена, схема железных или автомобильных дорог: множество станций, населённых пунктов (вершины графа) и соединяющих их линий, железные и авто дороги (ребра графа).

 

 

Кружки называются вершинами графа, линии без стрелок – рёбрами, линии со стрелками – дугами.

Граф - математическая модель взаимодействующих систем, имеющая вид системы точек, часть из которых соединена отрезками.

Графом называетсяпара (V,E), где V - конечное множество вершин, а E - набор неупорядоченных и упорядоченных пар вершин.

Или другими словами, графом называется некоторое количество вершин (кружков)V, соединённых некоторым количеством рёбер или дуг E.

- Вершина V

 

Рёбра, бывают неориентированными и ориентированными.

- ребро E неориентированное

 

- дуга - ориентированное ребро Е.

 

Рисунок 7. Вершина, рёбро и дуга.

Обозначим граф буквой G=(V,E).

 

 

Рисунок 8. Граф Ga. Рисунок 9. Граф Gb

 

На рисунках 8 и 9 представлены графы Ga - у которого V - количество вершин равно 4,

а E – количество рёбер равно 3 b и граф Gb - у которого V - количество вершин равно 4,

а E – количество дуг равно 3 b.

 

 

Признаки видов графов неориентированного и орграфа.

Неориентированный граф - граф ребра которого не имеют направления (двусторонние).Граф Ga. – неориентированный граф так как содержит только ребра.

 

Ориентированный граф (орграф) -граф ребра которого имеют некоторое направление. Граф Gb - содержащий только дуги - ориентированный, или орграф.

Смежные вершины - если две вершины соединены ребром е, то говорят, что они смежны между собой, а ребро e принадлежит (инцидентно) каждой из них.

Степень вершины - количество ребер графа, принадлежащих (инцидентных) ей.

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

Вершины, имеющие степень 0 называют изолированными.

 

 

Рисунок 10.

Для орграфа на рис.10 входящие степени вершин 1,2,3,4,5 равны соответственно 0,1,1,1,0, исходящие - 2,0,0,1,0.

Степени вершин, получаемые сложением входящих и исходящих степеней равны 2,1,1,2,0. Таким образом, вершина 5 - изолированная.

Рисунок 11. Петля.

Петля- ребро принадлежащее (инцидентное) одной вершине (единственной). Рисунок 11.

Петля –ребро, дуга, соединяющее вершину саму с собой.

Петля- ребро оба конца которого принадлежат одной и той же вершине.

Может быть несколько петель

Псевдограф — граф, содержащий петли

 

Если одну пару вершин соединяют два или более ребер, то такие ребра называют кратными.

Граф называется простым, если он не содержит ни петель, ни кратных ребер, иначе граф называется мультиграфом. (В некоторых источниках граф с кратными ребрами называют мультиграфом, с петлями - псевдографом.)

Простой граф, любая пара вершин которого соединена ребром, называется полным. В полном графе n * (n-1)/2 ребер.

Граф называется полным если он содержит максимально возможное количество рёбер.

Граф называется разреженным, если общее количество ребер значительно меньше их возможного количества.

 

 

 

Рисунок 12. Полный граф. Рисунок 13. Разреженный граф.

 

 

Путь в орграфе

Путём называется такая последовательность вершин в ориентированном графе при которой конец входящей дуги является началом исходящей дуги.

 

 

 

Рисунок 14. Путь в орграфе.

Путь в орграфе — это последовательность вершин v1, v2, …, vn, для которой существуют дуги e1 -> e2, e2 -> e3, …, en-1 – vn> en.

Говорят, что этот путь начинается в вершине v1, проходит через вершины v2, v3, …, vn-1, и заканчивается в вершине vn.

На рисунке 14. путь это последовательность вершин 1,2,3,4,7,8,9.

Длина пути — это количество дуг, составляющих путь. На рисунке 14. длина пути равна 6.

Вершина 1- начало пути, вершина 9 - конец пути

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

Цикломназывается путь из некоторой вершины в эту же вершину, содержащий хотя бы одно ребро. На рисунке 14. Путь 1, 2, 5, 1. – цикл.

Цикл простой, если в нем нет повторяющихся вершин (за исключением начальной (конечной), которая является первой и последней вершиной пути).

Цепь – последовательность смежных вершин. Или множество рёбер (в неориентированном графе) которые можно расположить так, что конец одного ребра является началом другого.

 

Граф дерево

Граф без циклов называется деревом.

Важный класс графов составляют ориентированные деревья.

Во многих приложениях дерево удобно считать ориентированным графом. Как показывает пример на рисунке 15, «превратить» дерево в ориентированный граф несложно.

 

 

Рисунок 15. Граф дерево.

Дадим соответствующее определение.

 

Определение. Ориентированный граф G называется ориентированным деревом, если выполняются следующие условия:

1. существует в точности одна вершина (корень), степень захода которой равна нулю;

2. степень захода любой вершины, кроме корня, равна единице;

3. для любой вершины v, отличной от корня, существует путь из корня в эту вершину;

Граф называется двудольным, если множество его вершин V можно разбить на непересекающиеся подмножества V1 и V2 так, что никакие две вершины одного подмножества не смежны. Пример двудольного графа на рис. 16.

 

 

 

Рисунок 16. Двудольный граф.

Если левое подмножество представить как необходимые виды работ, а правое как сотрудников обладающих компетенциями для выполнения этих видов работ.

Связи - это компетенции, которыми обладают сотрудники.

Мы получаем граф, который наглядно представляет, кто какие виды работ может выполнять.

На основе этого графа можно определять заработную плату с учётом объёма и разнообразия компетенций сотрудников.

Этот граф наглядно показывает, что увеличение объёма и разнообразия компетенций сотрудников позволить обеспечить надёжность и устойчивость организации.

Так в Советский период на всех предприятиях было развёрнуто «движение смежников», стимулировалось овладение смежной специальностью. Это объяснялось непрерывным ростом производства и нехваткой рабочих рук.

В современный период аналогичный принцип внедрён в компании Toyota под названием «Бережливое производство».

В 2002 г. руководство Toyota обратилось к «ведущим специалистам по технологиям производства компании с просьбой подумать над недостатками системы "бережливого производства" — той самой системы, принципы которой сделали Toyota предметом поклонения менеджеров во всем мире.

"Бережливое производство" подразумевает в первую очередь способность к гибкости, когда, например, один рабочий может выполнять самые разные задания.

Эта система оказалась более эффективной, чем американские сборочные линии, где сотрудник десятки лет выполняет одну-единственную специфическую работу.

Последнее изменение этой страницы: 2016-08-28

lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда...