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