В последнее время теория графов привлекает все более пристальное внимание специалистов различных областей знания. Наряду с традиционными применениями ее в таких науках, как физика, электротехника, химия, она проникла и в науки, считавшиеся раньше далекими от нее - экономику, социологию, лингвистику и др. Давно известны тесные контакты теории графов с топологией. теорией групп и теорией вероятностей. Особенно важная взаимосвязь существует между теорией графов и теоретической кибернетикой. Широко используется теория графов при решении различных задач на вычислительных машинах.