<<
>>

Ориентированные графы

Если ребра из множества U ориентированы, что обычно показывается стрелкой, то они называются дугами, и сам граф называется ориентированным графом или орграфом (рис. 6).

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

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


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

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

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

направленностью дуг в графе.

Циклы и контуры

Путь ui, u2, ..., Ui называется замкнутым, если в нем начальная вершина дуги u1 совпадает с конечной вершиной дуги Ui.


Так,              например,              в графе представленном на рис. 7

последовательности дуг:

u3, u6, u11, - являются ориентированным циклом, ориентированным контуром;

un, u3, u4, u7, ui, U12, u9 - являются ориентированным циклом;

u3, u4, u7, u1o, u9, u11 - являются ориентированным циклом, ориентированным контуром, гамельтонов цикл.

Замкнутый путь, в котором нет одинаковых дуг, но, могут повторяться внутренние вершины пути (а не только первая и последняя вершины), называется ориентированным циклом.

Если в замкнутом пути нет ни одинаковых дуг, ни одинаковых вершин (кроме первой и последней), то такой путь называется ориентированным контуром.

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

Степени вершин.

Число дуг, для которых вершина Xi является начальной вершиной, называется полустепенью исхода вершины xi. Обозначается d0(xi).

Число дуг, для которых вершина xi является конечной вершиной, называется полустепенью захода вершины xi. Обозначается dt(xi).

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

где n - число вершин и m - число дуг графа.

Подграфы.

Часть графа Gi называется подграфом G если множество вершин Xi является подмножеством вершин X, а множество Ui является подмножеством дуг U исходного графа, образованного ребрами соединяющими между собой только вершины графа из Xi.

Пусть дан граф G(X,U). Остовным подграфом Gp графа G называется граф (X, Up), для которого множество дуг Up является подмножеством множества дуг U исходного графа.

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

Порожденный подграф состоит из подмножества вершин Xs множества вершин исходного графа и всех таких дуг графа G, у которых начальные и конечные вершины принадлежат подмножеству Xs.

Рис. 8. а) исходный граф; б) остовный подграф; в) порожденный подграф; г) подграф исходного графа.

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

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

Ориентированный граф называется сильно связным или сильным, если для любых двух различных вершин Xi и xj существует по крайней мере один путь, соединяющий xi с Xj. Это определение означает, что любые две вершины такого графа взаимно достижимы.

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

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


Рис. 9. а) сильно связный граф; б) и в) слабо связные графы.

<< | >>
Источник: Арапов А.А.. Теория организации и системный анализ. 2003

Еще по теме Ориентированные графы:

  1. ОРИЕНТИРОВАННАЯ НА РЫНОК ОРГАНИЗАЦИЯ
  2. Глава 8 Как ориентировать детей
  3. ГЛАВА 2 Менеджер, ориентированный на стоимость
  4. Ценности, ориентированные на среду
  5. Методы ценообразования, ориентированные на спрос
  6. Цели, ориентированные на конкуренцию
  7. Организации, ориентированные на рынок
  8. Расширенная событийно-ориентированная модель
  9. Ценности, ориентированные на себя
  10. Ламбен Жан-Жак. Менеджмент, ориентированный на рынок, 2007
  11. Ценности, ориентированные на другого
  12. Ценообразование, ориентированное на конкурентов
  13. ОРГАНИЗАЦИЯ, ОРИЕНТИРОВАННАЯ НА СТОИМОСТЬ
  14. Прикладная концепция мотивации в корпоративно ориентированных организациях
- Антикризисное управление - Деловая коммуникация - Документоведение и делопроизводство - Инвестиционный менеджмент - Инновационный менеджмент - Информационный менеджмент - Исследование систем управления - История менеджмента - Корпоративное управление - Лидерство - Маркетинг в отраслях - Маркетинг, реклама, PR - Маркетинговые исследования - Менеджмент организаций - Менеджмент персонала - Менеджмент-консалтинг - Моделирование бизнес-процессов - Моделирование бизнес-процессов - Организационное поведение - Основы менеджмента - Поведение потребителей - Производственный менеджмент - Риск-менеджмент - Самосовершенствование - Сбалансированная система показателей - Сравнительный менеджмент - Стратегический маркетинг - Стратегическое управление - Тайм-менеджмент - Теория организации - Теория управления - Управление качеством - Управление конкурентоспособностью - Управление продажами - Управление проектами - Управленческие решения - Финансовый менеджмент - ЭКОНОМИКА ДЛЯ МЕНЕДЖЕРОВ -