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