Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. Дайте определение нагруженного графа. Приведите примеры объектов, моделями которых являются нагруженные и ненагруженные графы.
  2. Личностно ориентированные формы поведения жертв экстремальной ситуации
  3. Личностно ориентированные формы поведения спасателей в экстремальных ситуациях
  4. Медицинские томографы
  5. Нагруженные графы
  6. Основная надпись и дополнительные графы для чертежей и схем

Граф называется ориентированным если для любого его ребра про пару ее инцидентных вершин известно какая из вершин является началом ребра, а какая ее концом. На ребрах ориентированных графов таким образом появляется направление – от начальной вершины к конечной, которое принято в графических изображениях обозначать стрелкой (Рисунок 2.1‑3). Примером ориентированного графа может служить схема бассейна рек ибо (известно в каком направлении течет каждая из рек его составляющих) или схема электрического сигала (ток течет от источников к приемникам). Немного позднее будет показано, что и графы моделирующие управление проектом являются ориентированными.

Рисунок 2.1‑3. Пример ориентированного графа.

Для каждой вершины ориентированного графа все инцидентные ребра можно разделить на исходящие (началом которых является данная вершина) и на входящие (концом которых является данная вершина).

Для ориентированного графа принято различать корневые вершины и терминальные вершины. Корневой вершиной называется вершина графа, все инцидентные ребра которой являются исходящими. Терминальной вершиной называется вершина графа, все инцидентные ребра которой являются входящими. На приведенном выше графе вершины v1 и v6 являются корневыми, а v2 и v5 – терминальными.

Граф называется неориентированным если ни для одного его ребра направление не задано. Схема метрополитена – это пример неориентированного графа.

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


Дата добавления: 2015-07-20; просмотров: 112 | Нарушение авторских прав


Читайте в этой же книге: Управление проектом | Фазы и процессы проекта | Управление проектом и компьютерное моделирование | MS Project 2003 | Представление PERT | Gantt представление | Инвертирование представлений | Критический путь и продолжительность проекта. | Атрибуты событий | Атрибуты работ |
<== предыдущая страница | следующая страница ==>
Некоторые дополнительные определения на графах| Нагруженные графы

mybiblioteka.su - 2015-2024 год. (0.006 сек.)