Задать вопрос юристу

§2.1. Основные определения

Пусть V – произвольное множество, V2 – множество всех его двухэлементных подмножеств, т.е. множество неупорядоченных пар {а, b}, где а, b Î V. Пара (V, E), где Е – произвольное подмножество V2, называется графом (неориентированным графом).

При этом элементы множества V называются вершинами графа, элементы множества E – ребрами. Множества вершин и ребер графа G обозначаются символами V(G) и E(G) соответственно. Вершины и ребра графа называются его элементами.

В дальнейшем рассматриваются только конечные графы, т.е. множество E предполагается конечным. Число | V(G) | вершин называется его порядком и обозначается через |G|. Если |G| = п, |E(G)| = т, то G называют (п, т)-графом.

Говорят, что две вершины u и v смежны, если множество {u, v} является ребром, и не смежны в противном случае. Если е = {u, v} – ребро, то вершины u и v называют его концами. В этом случае также говорят, что ребро е соединяет вершины u и v. Такое ребро обозначается символом uv .

Два ребра называются смежными, если они имеют общий конец.

Вершина е и ребро v называются инцидентными, если v является концом ребра е, и не инцидентными в противном случае.


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

Это (5, 6)-граф, V(G) = {1, 2, 3, 4, 5}, E(G) = {{1, 2}, {1, 5}, {2,3}, {2, 4}, {2, 5}, {4, 5}}. Вершины 1и 2 смежны, а 1 и 3 не смежны. Вершина 1 и ребро {1, 2} инцидентны.

Иногда в графах допускается наличие петель, т.е. ребер {а, а} (рис. 2.2), и кратных ребер, т.е. ребро {а, b} учитывается несколько раз (рис. 2.3). Мы будем рассматривать графы без петель и кратных ребер.

Ориентированный граф – это пара (V, А), где V – множество вершин, А – множество ориентированных ребер (или дуг), т.е. упорядоченных пар (u, v), где u, v Î V. При этом и называется началом дуги, v – концом. На рисунке дуги отмечаются стрелками, указывающими направление от начала к концу (рис. 2.4).

<< | >>
Источник: Дискретная математика. Лекции. 2016

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

  1. Слово как основная единица лексико-семантического уровня языка. Другие ед-цы этого уровня. Об определении слова. Различные подходы к определению слова. Проблемы отдельности. Дифференциальные признаки.
  2. 5.1 Основные определение.
  3. 3.1 Основные определения
  4. 2.1 Основные определения
  5. 2.1. Основные определения
  6. § 1 Основные определения.
  7. 2.1. Основные понятия и определения
  8. Основные определения
  9. Ряды. Основные определения.
  10. Основные определения
  11. 3.1. Основные определения
  12. 1.1. Определения, основные положения