Например в СУБД используются графы блокировок (и вообще графы ожиданий какого-либо ресурса).
Графы зависимостей объектов БД.
Можно сделать обзор моделей представления графов в реляционной БД. С анализом +/- и т.п.
Графы и алгоритмы на них используются в картографии. У Oracle, например, есть опция к СУБД Spatial, где много чего реализовано. Наверняка и у других вендоров есть подобное.
Вот что сходу пришло в голову. Пусть продолжит кто-нибудь еще.
