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

Некоторые дополнительные определения на графах

Читайте также:
  1. II ТЕРМИНЫ И ОПРЕДЕЛЕНИЯ
  2. II. Дополнительные шаблоны Модели М. Эриксона
  3. II. Основные определения
  4. III . Если дополнительные занятия не приносят результата
  5. IV. Дополнительные замечания
  6. NB! Некоторые липиды могут гидролизоваться щелочью
  7. VII. НЕКОТОРЫЕ ПОЯСНЕНИЯ К ПСИХОТЕРАПЕВТИЧЕСКОЙ ТЕХНИКЕ

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

Ребро ei и вершина vj называются инцидентными если вершина vj является одной из двух вершин, на которых базируется ребро ei.

Два ребра графа имеющие общую вершину называются смежными. Две вершины графа имеющие общее ребро называются смежными

Путем P(va,vb) ={ei | i=1,…n} между двумя вершинами va и vb графа G(V,E) называется непустое упорядоченное подмножество ребер графа “ведущее” от вершины va к v:. Интуитивно понятный термин “ведущее” означает что:

- e1 инцидентно va,
- en инцидентно vb,

- ei смежна ei-1 | i=2,…n.

Иногда “путь” называют “цепью”.

В приведенном ниже графе (Рисунок 2.1‑2) между вершинами v5 и v7 существует единственный путь состоящий из ребер e5 и e6:
P(v5,v7) = {e5,e6}.

На том же графе между вершинами v1 и v3 существует два пути:
P1(v1,v3) = {e2} и P2(v1,v3) = {e1,e3}.

А вот пути между вершинами v2 и v6 не существует (равно как и между v8 и v1 и многими другими парами).

Рисунок 2.1‑2. Пример трехкомпонентного графа

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

На приведенном выше примере (Рисунок 2.1‑2) граф имеет три компонента связности:
C1=<{v1,v2,v3,v4},{e1,e2,e3,e4}>; C2=<{v5,v6,v7},{e5,e6}>; C3=<{v8}>.


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


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

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