Теория графов и её применение, Берж К.
Теория графов и её применение, Берж К.
Книга К.Бержа - первая по теории графов на русском языке. Между тем в последние годы интерес к теории резко усилился как со стороны математиков, так и представителей самых различных дисциплин. Это объясняется тем, что методы теории графов успешно решают многочисленные задачи теории электрических цепей, теории транспортных цепей, теории информации, кибернетики и др.
В книге Бержа теория графов излагается последовательно, начиная с самых основ. Предполагается, что читатель обладает весьма скромными математическими познаниями, хотя и имеет некоторую математическую культуру. В текст включены многочисленные, зачастую забавные, примеры. Книга может быть использована для первоначального изучения теории графов. Математики-профессионалы также найдут в ней много интересного.
Алгорифм для непосредственного выявления эйлерова цикла.
[Флёрн (Fleury)]. Рассмотрим связный мультиграф G, все вершины которого имеют четную степень, и постараемся нарисовать его одним росчерком, не прибегая в процессе построения к исправлениям уже начерченной части траектории. Достаточно придерживаться следующего правила:
1 Выходим из произвольной вершины а; каждое пройденное ребро зачеркиваем.
2 Никогда не идем по такому ребру и, которое в рассматриваемый момент является перешейком (т.е. при удалении которого граф, образованный незачеркнутыми ребрами, распадается на две компоненты связности, имеющие хотя бы по одному ребру),
Соблюдая это правило, мы всегда будем находиться в благоприятном положении, потому что когда мы находимся в х = а, граф (из незачеркнутых ребер) имеет две вершины нечетной степени: х и а; если отбросить изолированные вершины, то останется связный граф, который в силу теоремы 1 имеет эйлерову цепь, начинающуюся в х.
Содержание
Введение
Глава 1. Основные определения
Множества и многозначные отображения
Граф. Пути и контуры
Цепи и циклы
Глава 2. Предварительное изучение квазиупорядоченности
Квазипорядок, определяемый графом
Индуктивный граф и базы
Глава 3. Порядковая функция и функция
Гранди для бесконечного графа
Общие соображения относительно бесконечных графов
Порядковая функция
Функции Гранди
Операции над графами
Глава 4. Основные числа теории графов
Цикломатическое число
Хроматическое число
Число внутренней устойчивости
Число внешней устойчивости
Глава 5. Ядра графа
Теоремы существования и единственности
Приложение к функциям Гранди
Глава 6. Игры на графе
Игра Ним
Общее определение игры (с полной информацией)
Стратегии
Глава 7. Задача о кратчайшем пути
Процессы по этапам Некоторые обобщения
Глава 8. Транспортные сети
Задача о наибольшем потоке Задача о наименьшем потоке
Задача о потоке, совместимом с множеством значений
Бесконечные транспортные сети
Глава 9. Теорема о полустепенях
Полу степени исхода и захода
Глава 10. Паросочетание простого графа
Задача о наибольшем паросочетании
Дефицит простого графа
Венгерский алгорифм
Обобщение на бесконечный случай
Приложение к теории матриц
Глава 11. Факторы
Гамильтоновы пути и гамильтоновы контуры
Нахождение фактора
Нахождение частичного графа с заданными полустепенями
Глава 12. Центры графа
Центры
Радиус
Глава 13. Диаметр сильно связного графа
Общие свойства сильно связных графов без петель
Диаметр
Глава 14. Матрица смежности графа
Применение обычных матричных операций
Задачи на подсчет
Задача о лидере
Применение булевых операций
Глава 15. Матрицы инциденций
Вполне унимодулярные матрицы
Вполне унимодулярные системы
Цикломатические матрицы
Глава 16. Деревья и прадеревья
Деревья
Аналитическое исследование
Прадеревья
Глава 17. Задача Эйлера
Эйлеровы циклы Эйлеровы контуры
Глава 18. Паросочетание произвольного графа
Теория чередующихся цепей
Нахождение частичного графа с заданными степенями вершин
Совершенное паросочетание
Приложение к числу внутренней устойчивости
Глава 19. Фактороиды
Гамильтоновы циклы и фактороиды
Необходимое и достаточное условие существования фактороида
Глава 20. Связность графа
Точки сочленения
Графы без сочленений
h-связные графы
Глава 21. Плоские графы
Основные свойства
Обобщение
Добавления
I. Off общей теории, игр
II. О транспортных задачах
III. Об использовании, понятия потенциала в транспортных сетях
IV. Нерешенные задачи, и недоказанные предположения
V. О некоторых основных принципах подсчета (Ж. Риге)
VI. Дополнения к русскому переводу (А.А. Зыков и Г.И. Кожухин)
Литература
Теория графов и книга К. Бержа (послесловие к русскому переводу)
Указатель символов
Именной указатель
Предметный указатель.
| Рейтинг: | 4.8 баллов / 2537 оценок |
| Формат: | Книга |
| Уже скачали: | 12836 раз |
Похожие Книги
Нам показалось, что Книги ниже Вас заинтересуют не меньше. Эти издания Вы так же можете скачивать и читать совершенно бесплатно на сайте!
-
Елизавета I, королева Англии rtf 1,73Мб
Автор:Борис ГрибановНазвание: Елизавета I, королева АнглииИздательство: Терра-Книжный клубГод: 2003Формат: rtf Размер: 1.73 мбСерия: ВенценосцыНовый роман Бориса Грибанова посвящен судьбе величайшей . . .
-
Уютная квартира №5 (май 2011) pdf 42,1Мб
Название: Уютная квартираСтраниц: 82Формат: PDFКачество: ХорошееЯзык: РусскийРазмер: 42.1 МбСкачать Уютная квартира №5 (май 2011):VIP-File - на высокой скорости:http://vip-file.com/download/1519.1fb13 . . .
-
Мессия очищает диск (аудиокнига)
Название: Мессия очищает дискАвтор: Генри Лайон ОлдиИздательство: Аудиокнига своими рукамиГод выпуска: 2012Жанр: фантастикаАудио кодек: MP3Битрейт аудио: 128 kbpsИсполнитель: bleicherПродолжительно . . .
-
Мебель.Интерьер (март 2010) pdf 10,16Мб
название : Мебель.Интерьергод: март/ 2010номер: 2(42)издатель : ДиМаркформат: pdfстраниц: 132размер : 10,16 мбМебель.Интерьер - журнал города Омска о мебели и предметах интерьера.На границе стилейПода . . .
-
Dwell - 100 Houses We Love pdf 71,6Мб
Название: Dwell - 100 Houses We LoveГод / месяц: 2010/?Номер: ?Язык: английскийСтраниц: 197Формат: PDFРазмер: 71.6 MbDwell - американский журнал по архитектуре и дизайнуifolder.ruuploadbox.comdepositf . . .
-
Видеоурок "Монтаж подвесных потолков" 82,93Мб
Подвесной потолок становится полноценным элементом интерьера помещения только после того, как закончен его монтаж. Как правило, монтаж подвесных систем весьма прост, однако необходимо иметь представле . . .
-
Трапезундская принцесса (радиоспектакль)
Автор: Жак ОффенбахНазвание: Трапезундская принцесса Исполнители: Ростислав Плятт, Владимир Володин, Елена Савицкая, Капитолина Кузьмина, Татьяна Карпова, Серафим Аникеев, Григорий Ярон, Николай Рубан . . .
-
MAXI tuning #05 май 2007 pdf 57,9Мб
Название: MAXI tuningГод / месяц: 2007/05Номер: #05Формат: PDFРазмер: 57.9 MbMaxi Tuning — специализированное автомобильное издание, целиком посвященное тюнингу автомобилей.depositfiles.com . . .
-
MAXI tuning #10 октябрь 2007 pdf 59,1Мб
Название: MAXI tuningГод / месяц: 2007/10Номер: #10Формат: PDFРазмер: 59.1 MbMaxi Tuning — специализированное автомобильное издание, целиком посвященное тюнингу автомобилей.depositfiles.com . . .
-
MAXI tuning #06 июнь 2007 pdf 39,2Мб
Название: MAXI tuningГод / месяц: 2007/06Номер: #06Формат: PDFРазмер: 39.2 MbMaxi Tuning — специализированное автомобильное издание, целиком посвященное тюнингу автомобилей.depositfiles.com . . .
Вы не зарегистрированы!
Если вы хотите скачивать книги, журналы и аудиокниги бесплатно, без рекламы и без смс, оставлять комментарии и отзывы, учавствовать в различных интересных мероприятиях, получать скидки в книжных магазинах и многое другое, то Вам необходимо зарегистрироваться в нашей Электронной Библиотеке.
Отзывы читателей
Ой!
К сожалению, в нашей Бесплатной Библиотеке пока нет отзывов о Книге Теория графов и её применение, Берж К.. Помогите нам и другим читателям окунуться в сюжет Книги и узнать Ваше мнение. Оставьте свой отзыв или обзор сейчас, это займет у Вас всего-лишь несколько минут.