Основные определения и применения

Как говорилось в главе 1, граф G представляет собой обычный способ кодирования парных отношений в множестве объектов: он состоит из набора узлов V и набора ребер E, каждое из которых «соединяет» два узла.
Таким образом, ребро e E пред- ставляется двухэлементным подмножеством V: e ={и, v} для некоторых и, v V, при этом и и v называются концами ребра e.

Ребра в графе обозначают симметричные отношения между их концами. Часто требуется представить асимметричные отношения; в таких случаях используется понятие направленного графа. Направленный граф G' состоит из набора узлов V и набора направленных ребер E', также называемых дугами. Каждое ребро e' E представляется упорядоченной парой (u, v); иначе говоря, роли и и v не взаимоза- меняемы, узел и называется начальным, а узел v — конечным. Также говорят, что ребро e' выходит из узла и и входит в узел v.

Если требуется подчеркнуть, что рассматриваемый граф не является направ- ленным, его называют ненаправленным графом; тем не менее по умолчанию под термином «граф» понимается именно ненаправленный граф. Также стоит сделать пару замечаний по поводу нашего использования терминологии. Во-первых, хотя ребро e в ненаправленном графе должно обозначаться как множество узлов {и, v}, чаще (и даже в книгах) используется запись, принятая для упорядоченных пар: e = (u, v). Во-вторых, узлы графа часто называются вершинами; в данном контексте эти два термина имеют абсолютно одинаковый смысл.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Основные определения и применения:

  1. Основные направления применения метода.
  2. 4.1. Определение и область применения
  3. Основные направления применения метода.
  4. § 3. КОНКРЕТИЗАЦИЯ ОБЩИХ ОПРЕДЕЛЕНИЙ — УСЛОВИЕ ИХ ПРИМЕНЕНИЯ В ПРИКЛАДНЫХ ИССЛЕДОВАНИЯХ
  5. 2. Определение и основные признаки сделки
  6. Статья 77. Применение дополнительных наказаний в случае освобождения от отбывания основного наказания с испытанием
  7. 1. Определение ключевых понятий, основные проявления и анализ ядра характера
  8. 40. Основные теоретические подходы в определении классов. Немарксистские подходы
  9. Типология органов и основные типологические группы современной российской журналистики (качественные и массовые издания, каналы, программы; органы информации различной функционально-целевой, предметно-тематической, направленности; рассчитанные на определенные группы аудитории, разной периодичности).
  10. Статья 55. Лишение права занимать определенные должности или заниматься определенной деятельностью
  11. 2. Лишение права занимать определенные должности или заниматься определенной деятельностью
  12. § 85 Значение бесспорного владения. – Отличие бесспорного владения от давности владения. – Установление земской давности и применение оной к делам межевым. – Может ли давность применяться к совместному и к чересполосному владению по предметам вотчинного права. – Применение давности к делам специального размежевания
  13. 2. Вещи, определенные родовыми признаками, и индивидуально-определенные вещи
  14. § 33 Общее правило о переходе наследства к детям. – Отличие отделенных от неотделенных. – Право представления. – Право родительское. – Право боковых родственников. – Римская система определения прав по классам и степеням. – Германская система определения прав по линиям и коленам.
  15. ПРИМЕНЕНИЕ В ГОРОСКОПЕ
  16. ЗНАНИЕ: ПРИМЕНЕНИЕ