Дискретная математика: графы и автоматы. Альпин Ю.А - 4 стр.

                                       Глава 1
                   Неориентированные графы

                 § 1. Первые понятия теории графов

    Графом называется пара (V, E), где V — непустое множество, E
— некоторое множество двухэлементных подмножеств V . Элементы
V называют вершинами, а элементы E — рёбрами графа.1) Мы будем
рассматривать только конечные графы, то есть, графы с конечными
множествами вершин. Графы удобно изображать в виде рисунков,
состоящих из точек и линий, соединяющих некоторые пары точек.
Точки соответствуют вершинам графа, а линии — рёбрам. Напри-
мер, рисунок




                                           Рис. 1


изображает граф с множеством вершин V = {1, 2, 3, 4, 5, 6} и множе-
ством рёбер E = {{1, 2}, {1, 4}, {2, 4}, {2, 5}, {4, 5}, {5, 6}}.
    Если e = {u, v} — ребро графа, то вершины u и v называются
концами ребра e. Говорят, что ребро e = {u, v} соединяет вершины
u и v. Вершины, соединенные ребром, называются смежными. Ещё
говорят, что вершины u и v инцидентны ребру e = {u, v}. Отме-
тим крайние случаи: граф называется полным, если любые его две
вершины смежны, и пустым, если множество рёбер пусто.
    Маршрутом в графе называется всякая чередующаяся последо-
вательность вершин и рёбер
                             v1 , e1 , v2 , , . . . , ek , vk+1 ,                 (1)
в которой ребро ei соединяет вершины vi и vi+1 при i = 1, 2, . . . , k.
Обычно маршрут записывается короче, как последовательность
                                  v1 , v2 , . . . , vk+1 ,
  1)
     Точнее говоря, приведённое определение относится к неориентированным графам, но в
первой главе это прилагательное опускается.