Некоторые задачи на рисование графов, которые встречаются в математике и информатике:

В математике:

• Задача о домиках и колодцах. 1 В деревне есть три колодца, трое жителей решили протопать тропинки от своих домов к каждому из трёх колодцев так, чтобы они не пересекались. 1
• Задача о пяти хуторах. 1 Пять хуторов расположены в вершинах правильного пятиугольника. 1 Нужно проложить дороги от каждого из них к остальным так, чтобы не было перекрёстков. 1
• Задача о четырёх красках. 1 На политической карте мира нарисовано несколько государств. 1 Карту нужно раскрасить так, чтобы две страны, имеющие общую границу, были покрашены в разные цвета. 1
• Задача о Кенигсбергских мостах. 5 На острове, окружённом рекой, через которую перекинуто семь мостов, нужно определить, может ли кто-нибудь непрерывно обойти их, проходя только однажды через каждый мост. 5

В информатике:

• Задача о дорожной системе. 3 В таблице приведены расстояния между четырьмя посёлками. 3 Нужно изобразить схематически приведённую дорожную систему и с помощью графа определить кратчайший путь из посёлка А в D. 3
• Задача о трёхзначных числах. 3 Нужно найти количество трёхзначных чисел, составленных из цифр 5, 6, 7, при условии, что каждая цифра используется только один раз. 3