Читайте также: |
|
Многообразие задач моделируемых графами порождает большое количество дополнительных определений и классификаций используемых в теории графов. Познакомимся лишь с небольшой их частью, необходимой нам в моделировании управления проектами.
Ребро 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 | Нарушение авторских прав
<== предыдущая страница | | | следующая страница ==> |
MS Project 2003 | | | Ориентированные графы |