Книга является учебным пособием и состоит из пяти разделов. В первом даны основные понятия и определения теории графов, рассмотрены виды графов и способы их описания. Второй раздел посвящен вопросу о связности ориентированных графов. Важнейший вид графов - деревья рассмотрен в третьем разделе. Разобраны задачи описания и пересчета деревьев, а также задача о кратчайшем остове. Четвертый раздел посвящен вопросам пересчета и перечисления путей в графах. Здесь же приведены различные варианты задачи о кратчайшем пути и алгоритмы ее решения. В пятом разделе рассматриваются фундаментальные, эйлеровы и гамильтоновы циклы. Разбираются условия существования и алгоритмы поиска таких циклов в графе.
Пособие подготовлено по материалам курса лекций по теории графов, читаемого автором для студентов специальности "Прикладная математика" Пензенского государственного университета. Может быть использовано студентами других специальностей при изучении соответствующих разделов дискретной математики.