Некоторые задачи из реальной жизни, которые решаются с помощью теории графов и понятия степени вершин:

• Организация автомобильного движения в городе. 2 Схему организации автотранспорта представляет ориентированный граф, где вершинами считаются перекрёстки дорог, а рёбрами — дороги, соединяющие перекрёстки. 2
• Планирование доставок товаров. 2 Например, компания OZON планирует тысячи доставок товаров по пунктам выдачи и по адресам покупателей. 2 Для решения этой задачи используется теория графов и алгоритм для нахождения кратчайшего пути. 2
• Оптимальное размещение пунктов массового обслуживания. 2 Например, больниц, школ, банков, пожарных частей, почтамтов. 2 Важно минимизировать наибольшее расстояние от любой точки населённого пункта до ближайшего пункта обслуживания. 2
• Составление развлекательных маршрутов. 2 Например, по городу, чтобы обойти все достопримечательности по одному разу или определить, сколько существует доступных маршрутов. 2
• Проектирование вычислительных машин. 1 Компьютер состоит из нескольких модулей и их контактов. 1 Физическое положение модулей определено, и контакты нужно соединить проводами. 1
• Планирование расписания занятий. 1 Например, в университете нужно рассчитать минимальное количество академических часов в расписании занятий, необходимых для планирования всех курсов, чтобы одновременно не преподавались два раздела одного и того же курса. 1