>>

1. Основные понятия теории графов

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

Теория графов может рассматриваться как раздел дискретной математики (точнее - теории множеств), и формальное определение графа таково: задано конечное множество X, состоящее из n

элементов (X = {1, 2, ..., n}), называемых вершинами графа, и подмножество V декартова произведения X XX, то есть V сX2, называемое множеством дуг, тогда ориентированным графом G называется совокупность (X, V) (неориентированным графом называется совокупность множества X и множества неупорядоченных пар элементов, каждый из которых принадлежит множеству X). Дугу между вершинами i и j, i, j е X, будем обозначать (i, j). Число дуг графа будем обозначать m (V = (v1, v2, ..., vm)).

Язык графов оказывается удобным для описания многих физических, технических, экономических, биологических, социальных и других систем.

Язык графов оказывается удобным для описания многих физических, технических, экономических, биологических, социальных и других систем.

| >>
Источник: В.Н. Бурков, Д.А. Новиков. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ. 2001

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

  1. В.Н. Бурков, Д.А. Новиков. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ, 2001
  2. 1. Основные понятия теории графов
  3. ряд примеров приложений теории графов.
  4. «Пневматический» континуум и понятие «система»
  5. Творцы новых теорий
  6. ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ
  7. Источники, аспекты, основные результаты и перспективы когнитивного осмысления истории изучения глаголов речи
  8. ОРФОГРАФИЧЕСКАЯ ТЕОРИЯ ТРЕДИАКОВСКОГО*
  9. §2. Понятие «непреодолимой силы» в советской правовой литературе
  10. "Теория" государства и бесправия
  11. § 3. Понятие «закон» в концепции митрополита Илариона.
  12. § 6. Итоговые теории «широкого права» в Московской Руси. Концепция преп. Максима Грека
  13. Эволюционное и революционное развитие технической теории
  14. § 4. СТРУКТУРА И ФУНКЦИИ НАУЧНОЙ ТЕОРИИ. ЗАКОН КАК КЛЮЧЕВОЙ ЕЕ ЭЛЕМЕНТ
  15. 3.1. Элементы теории графов
  16. 3. Тождество диалектики, логики и теории познания.
  17. Основные определения.