Понятие «граф» связано с понятиями «графический», «графика». Действительно, графовые модели имеют простую и понятную графическую интерпретацию, позволяющую с их помощью образно представить самые разные объекты, в то же время оставаясь в рамках строгих математических моделей. Первой работой теории графов как математической дисциплины считают статью Эйлера (1736г.), в которой рассматривалась задача о Кёнигсбергских мостах. Эйлер показал, что нельзя обойти семь городских мостов и вернуться в исходную точку, пройдя по каждому мосту ровно один раз. Следующий импульс теория графов получила спустя почти 100 лет с развитием исследований по электрическим сетям, кристаллографии, органической химии и другим наукам. С графами, сами того не замечая, мы сталкиваемся постоянно. Например, графом является схема линий метрополитена. Точками на ней представлены станции, а линиями – пути движения поездов. Исследуя свою родословную и возводя ее к далекому предку, мы стоим так называемое генеалогическое древо. И это древо – граф. Методы теории графов широко применяются в дискретной математике. Без них невозможно обойтись при анализе и синтезе различных дискретных преобразователей: функциональных блоков компьютеров, комплексов программ и т.д. В настоящее время теория графов охватывает большой материал и активно развивается.