Большое количество прикладных задач может решаться с помощи теории графов. Расчёт при помощи ПЭВМ значительно облегчает эту задачу. С помощью графов могут быть решены следующие задачи:

1. Нахождение кратчайшего пути из пункта А в пункт Б. Без помощи ПЭВМ эта задача тоже решаема, но если большое количество вершин и рёбер, эта задача становится трудно разрешимой. Стоит отметить, что к нахождению кратчайшего пути могут сводиться другие задачи. 2. Имеется N городов, между каждым городом можно построить дорогу, стоимость строительства дороги известна, необходимо затратить минимум денег и соединить все города. Задача сводится к поиску минимального оставного дерева. Та же задача может быть интерпретирована, как прокладка компьютерной сети, но необходимо затратить минимум кабелей.

3. Предположим, необходимо нанять людей, которые выполняют определенную работу. Каждый человек может работать в разные часы, и брать за это разное количество денег. Нам необходимо нанять работников так, чтобы от момента А до момента Б хотя бы один из работников выполнял эту работу, и потратить на это минимум денег. Задача на кратчайший путь. Строим граф. Вершины - это моменты А и Б и время, в которое работник может заступить на работу и уйти с неё. Необходимо отыскать минимальный путь из А в Б. Причём, граф нагруженный и ориентированный.

4. Задача о занятости работников. Пусть имеется n работников и m видов работ. Каждый работник может выполнять какую - то работу, и каждую работу могут выполнять разные люди. Необходимо распределить рабочих так, чтобы максимальное количество было занято, причём одну работу может выполнять один рабочий. Строим граф, где определенного рабочего соединяем с работами, которые он может выполнять, также создаём псевдоисток, и соединяем его со всеми работниками. Все работы соединяем с псевдостоком. Вес дуг, соединяющих работника и работу равны 1. И тогда максимальное количество занятых человек равно пропускной способности графа.

5. В чистом виде пропускная способность может использоваться в транспортных или компьютерных сетях. Для расчёта пропускной способности дороги или канала связи.