<<
>>

Достижимость и связность.

Определение. Вершина w графа D (или орграфа) называется достижимой из вершины v, если либо w=v, либо существует путь из v в w(маршрут, соединяющий v и w).

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

Определение. Псевдографом D(V, X), ассоциированным с ориентированным псевдографом, называется псевдограф G(V, X0) в котором Х0 получается из Х заменой всех упорядоченных пар (v, w) на неупорядоченные пары (v, w).

Определение. Орграф называется слабо связным, если связным является ассоциированный с ним псевдограф.

<< | >>
Источник: Архаров Евгений Валерьевич. Учебно–методический комплекс по дисциплине Математика Нижний Новгород, 2011. 2011

Еще по теме Достижимость и связность.:

  1. Гетерогенность, сбалансированность, роль государства
  2.   2.1.2. Онтологические проблемы физики  
  3.   4.8. Проблема истинности и рациональности в соЦиально-гуманитарных науках  
  4. § 6. Возможность и Правомочность логики в качестве наукоучения
  5. § 22. Законы мышления как предполагаемые естественные законы, которые в своем изолированном действии ЯВЛЯЮТСЯ причиной              15 разумного мышления
  6. Характер языков
  7. ЛАЦИЙ И ЭЛЛАДА[91]
  8. Философия «всеединства» B.C. Соловьева
  9. [ПОДСТРОЧНЫЕ ПРИМЕЧАНИЯ К ПЕРЕВОДУ МИЛЛЯ]
  10. Содержание дисциплины
  11. Достижимость и связность.
  12. Перечень вопросов к экзамену на первом курсе