Одна и та же математическая формулировка возникает в разных практических задачах. Пусть, например, мы хотим назначить даты экзаменов так, чтобы никому не надо было сдавать два экзамена в один день, и при этом хотим занять поменьше дней. Заведём вершину для каждого экзамена и соединим две вершины ребром, если хотя бы один студент сдаёт оба экзамена. Раскрасив граф в минимальное число цветов, получим оптимальное расписание (экзамены одного цвета назначаются на один день).
Граф задаётся множеством вершин V и множеством рёбер E, соединяющих пары вершин. (Английская терминология: вершина называется vertex или node, а ребро — edge.)
В примере с картой V = {1, 2, 3, ..., 13}, а рёбра из E соединяют страны, граничащие друг с другом (в частности, E содержит рёбра {1, 2}, {9, 11} и {7, 13}). Отношение «быть соседом» симметрично, так что ребро из x в y возникает одновременно с ребром из y в x. Поэтому мы записываем ребро, соединяющее x с y, как множество: {x, y}. Такие рёбра называются неориентированными (undirected), а соответствующий граф — неориентированным графом (undirected graph).
Бывают и несимметричные отношения, и их изображают ориентированными рёбрами (directed edges). В ориентированном графе наличие ребра из x в y не гарантирует наличие ребра из y в x. Ориентированное ребро из x в y будем обозначать (x, y). Можно считать «всемирную паутину» (World Wide Web) ориентированным графом: из вершины u идёт ориентированное ребро в вершину v, если на странице u есть ссылка на страницу v. В этом графе миллиарды вершин и рёбер, так что алгоритмы, с ним работающие, должны быть быстрыми (к счастью, такие алгоритмы есть — многое можно сделать за линейное время).