Введение - Определение кратчайшего пути в графе
Начало теории графов как математической дисциплины было положено Эйлером в его знаменитом рассуждение о Кенигсбергских мостах. Однако эта статья Эйлера 1736 года была единственной в течение почти ста лет. Интерес к проблемам теории графов возродился около середины прошлого столетия и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. Естественные науки оказали свое влияние на это благодаря исследованиям электрических цепей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок подавалось формулировкам непосредственно в терминах графов, и это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за рамки конкретного вопроса. Наиболее знаменитая среди этих задач-проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 года. Никакая проблема не вызывала столь многочисленных и остроумных работ в области теории графов. Благодаря своей простой формулировке и раздражающей неуловимости она до сих пор остается мощным стимулом исследований различных свойств графов.
Настоящее столетие было свидетелем неуклонного развития теории графов, которая за последние десять - двадцать лет вступила в новый период интенсивных разработок. В этом процессе явно заметно влияние запросов новых областей: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных цепей, а также проблем психологии и биологии.
Вследствие этого развития предмет теории графов является уже обширным, что все его основные направления невозможно изложить в одном томе. В настоящем первом томе предлагаемого двухтомного труда сделан акцепт на основные понятия и на результаты, вызывающие особый систематический интерес.
По теории графов имеется очень мало книг; основной была книга Д. Кенига (1936), которая для своего времени давала превосходнейшее введение в предмет. Довольно странно, что таких книг на английском языке до сих пор не было, несмотря на то, что многие важнейшие результаты были получены американскими и английскими авторами.
Похожие статьи
-
Введение - Визуализация графа цитирования
В данной работе рассматриваются методы автоматической и полуавтоматической визуализации графов цитирования на плоскости. Визуализация графов на плоскости...
-
Библиотека GridMD поддерживает три механизма определения действий, связываемых с узлами графа [8]. Узел графа может соответствовать исполнению стороннего...
-
Основные определения, термины и понятия - Визуализация графа цитирования
1. Граф - совокупность множества вершин и наборов пар вершин, называемых ребрами. 2. Ориентированный граф - граф в котором пары вершин в ребрах...
-
Введение в искусственный интеллект - Искусственный интеллект
Понятие "интеллект" впервые возникло в психологии. Психологи считают, что интеллект - это "свойство личности, выражающееся в способности глубоко и точно...
-
Методической целью расчетно-графической работы (РГР) по курсу "Автоматизированный электропривод" является приобретение и закрепление студентами...
-
Введение - Разработка программы для реализации редактора временных графов синхронизации
Математическое моделирование дискретно-событийных динамических систем является относительно молодым направлением науки теории управления. Разработка...
-
Введение - Школьная социальная сеть
Актуальность темы исследования. Одним из важнейших вопросов управления образовательным учреждением в условиях реализации ФГОС является вопрос...
-
ВВЕДЕНИЕ - Разработка системы управления знаниями в проектной консалтинговой организации
Исследование посвящено разработке системы управления знаниями в проектной консалтинговой организации. Проекты существовали всегда на протяжении истории...
-
Введение - Интеллектуальные информационные системы
Чаще всего искусственным интеллектом, или ИИ (Artificial Intelligence - AI), называют процесс создания машин, которые способны действовать таким образом,...
-
Введение в экспертные системы. Определение и структура - Разработка интеллектуальных подсистем САПР
В качестве рабочего определения экспертной системы примем следующее. Экспертные Системы это сложные программные комплексы, аккумулирующие знания...
-
В вычислительной технике понятие безопасности является весьма широким. Оно подразумевает и надежность работы компьютера, и сохранность ценных данных, и...
-
Введение - База данных "Определение факультативов для студентов"
Система баз данных -- это, по сути, не что иное, как компьютеризированная система хранения однотипных записей. Саму же базу данных можно рассматривать...
-
Предметная область IoT (Интернет вещей) - это сеть физических объектов - устройств, транспортных средств, зданий и других вещей со встроенной...
-
Заключение - Разработка программы для реализации редактора временных графов синхронизации
Результатом выполнения задания является реализованный редактор временных графов синхронизации (класс временных сетей Петри), соответствующий задачам,...
-
Введение - Проектирование автоматизированной информационной системы
Информационный интерфейс программа С развитием информационных технологий компьютеры, с их расширенными функциональными возможностями, активно применяются...
-
В курсовой работе в соответствии с заданием на проектирование решается задача разработки программы вычисления определенных интегралов численными...
-
Изучение возможностей экспертных систем Цель работы Целью является проектирование и разработка фрагмента экспертной системы. Теоретическое введение...
-
Введение - Пользовательский контент
Мы живем в информационную эру -- эпоху, когда информация и знания представляют высшую ценность в обществе, а также, которая отличается практически...
-
Использование муравьиных алгоритмов для решения задачи поиска оптимального маршрута в графе Цель работы Изучить метод муравьиных колоний. Научиться...
-
Данная дипломная работа посвящена теме информационная система учета службы горючих и смазочных материалов войсковой части. Объектом разработки является...
-
Введение, Роль и значение информационных революций. - Проблемы компьютеризации общества
Трудно назвать другую сферу человеческой деятельности, которая развивалась бы столь стремительно и порождала бы такое разнообразие проблем и мнений, как...
-
Введение - Разработка модуля маршрутизации с использованием Graph Hopper
Тенденция к разработке автоматизированной системы построения оптимального маршрута между объектами сегодня заметна как никогда. Решение вопроса...
-
Поиск кратчайшего пути в лабиринте на языке Си
Лабораторная работа № 3 Поиск кратчайшего пути в лабиринте на языке Си Формулировка задания Найти кратчайший путь в лабиринте от текущего положения до...
-
Введение - Некоммерческие организации и проблемы их развития
В настоящее время в России актуальной является проблема становления гражданского общества. Институтами гражданского общества считают органы местного...
-
Введение - Поиск, накопление и обработка информации
Умственный труд в любой его форме всегда связан с поиском информации. Тот факт, что этот поиск становится сейчас все сложнее и сложнее, в доказательствах...
-
20. Пользователь через UI инициирует создание определения 21. Приложение получает данные описывающие определение и изменяет свое состояние 22. Приложение...
-
Введение - Объектно-ориентированный подход и диаграммы классов в UML
Психологи уже давно показали, что средний человек может одновременно воспринимать адекватно в пределах десятка единиц информации. Таким образом, при...
-
Программа реализует алгоритм четырех махов. Входным параметром является имя файла. На выходе печать: является ли граф единичным интервальным,...
-
ВВЕДЕНИЕ - Понятие о системах автоматизированного проектирования
Все большее количество промышленных предприятий внедряют на производстве системы автоматизированного проектирования технологических процессов....
-
Введение - Система автоматизированного разделения кода прикладных программ
Множество современных приложений используют базы данных для накопления самых разных видов информации, которые могут включать пользовательскую статистику,...
-
Автоматическое расположение вершин на плоскости - Визуализация графа цитирования
Первая проблема, о которой стоит поговорить - это проблема автоматического расположения вершин на плоскости. Для начала поставим базовую задачу, как она...
-
Постановка задачи - Визуализация графа цитирования
В качестве результата выпускной квалификационной работы требуется создать программу, позволяющую визуализировать граф цитирования публикаций, которые...
-
Введение - Различные виды программ для Multi-Touch столов
Мобильные телефоны, планшеты, платежные терминалы, стенды с интерактивными картами торговых центров, Multi-Touch стенды на выставках - все это яркие...
-
Введение - Философские основы кибернетики и методология ее применения в военном деле
Процесс научно-технической революции является причиной для пересмотра многих положений военной науки, так как коренные изменения в вооружении и...
-
Введение - Роль ключевых предложений в построении текста
Постоянное увеличение объемов существующей в мире информации является вполне естественным процессом. В его основе лежат как стремительно развивающийся...
-
Введение - Программирование на языке C++
Производственная практика является важным этапом подготовки квалифицированных специалистов. Она является видом учебно-вспомогательного процесса, в ходе...
-
Введение - Применение нейрокомпьтерных технологий в методах управления сложными объектами
Данная статья посвящена аналитическому обзору возможностей управления сложными объектами с помощью нейрокомпьютеров. Рассмотрено несколько областей, в...
-
Схема презентации. Титульный слайд Презентация начинается со слайда, содержащего название работы (доклада) и имена авторов. Эти элементы обычно...
-
Введение - Исследование алгоритмов
С недавнего времени такая область кибернетики, как создание искусственных систем распознавания образов, стала представлять особый интерес. Потребность в...
-
Введение, Этапы разработки программы - Разработка программы "Будильник"
Внедрение электронно-вычислительных машин, современных средств переработки и передачи информации послужило началом нового процесса, называемым...
Введение - Определение кратчайшего пути в графе