Что такое граф в контексте дискретной математики?

В контексте дискретной математики граф — это структура, состоящая из набора объектов, где некоторые пары объектов в некотором смысле «связаны» 2.

Объекты представлены абстракциями, называемыми вершинами (также называемыми узлами или точками), а каждая из связанных пар вершин называется ребром (также называемым связующим звеном или линией) 2.

Графы могут быть ориентированными или неориентированными, в зависимости от того, имеют ли рёбра направление 1.

С математической точки зрения граф — это совокупность двух множеств: одно из них — множество вершин, другое — множество рёбер 4. Каждый элемент из множества рёбер представляет собой пару элементов из множества вершин 4.

Графы используются для моделирования различных ситуаций, включая социальные сети, транспортные системы и многие другие 1.