§ 18. Графы. Вершины и рёбра

Родословное дерево семьи, схема молекулы, карта метро, схема радиоприёмника — вещи совершенно разные. Но все четыре чертежа отвечают на один и тот же вопрос: что с чем связано. В родословной линия ведёт от отца к сыну, на карте метро — от станции к соседней станции, на схеме прибора — от детали к детали, спаянной с ней проводом. Математика заметила это сходство и придумала общий чертёж для любых связей — граф. С дворянским титулом это слово не связано: оно идёт от латинского grafica — «черчение», «рисование».

Вершины и рёбра

Граф — это изображение объектов и связей между ними с помощью точек и линий. Точки называются вершинами графа, а линии, соединяющие вершины, — рёбрами.

В летнем лагере идёт турнир по настольному теннису. Играют шестеро: Аня, Боря, Вера, Гриша, Даша и Егор. К среде сыграно шесть партий: Аня — Боря, Аня — Вера, Боря — Вера, Боря — Гриша, Вера — Даша, Гриша — Даша. В таком списке разобраться трудно. Нарисуем граф: каждого участника обозначим точкой с подписью, а если двое уже встречались за столом — соединим их точки линией (рис. 1).

Получилось шесть вершин и шесть рёбер. У каждого ребра два конца, и оба конца — вершины; говорят, что ребро исходит из вершины или входит в неё. Из вершины «Боря» исходят три ребра, из вершины «Аня» — два. Теперь видно то, чего в списке было не разглядеть: Боря сыграл больше всех, а Аня, Боря и Вера сыграли между собой все партии, какие могли.

Заметь и то, чего на этом графе нет. Не видно, кто выиграл: ребро говорит лишь о том, что партия состоялась.