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