Элементы теории графов: Учебное пособие

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