Клауди Альсина - Том 11. Карты метро и нейронные сети. Теория графов

Тут можно читать онлайн Клауди Альсина - Том 11. Карты метро и нейронные сети. Теория графов - бесплатно полную версию книги (целиком) без сокращений. Жанр: Математика, издательство «Де Агостини», год 2014. Здесь Вы можете читать полную версию (весь текст) онлайн без регистрации и SMS на сайте лучшей интернет библиотеки ЛибКинг или прочесть краткое содержание (суть), предисловие и аннотацию. Так же сможете купить и скачать торрент в электронном формате fb2, найти и слушать аудиокнигу на русском языке или узнать сколько частей в серии и всего страниц в публикации. Читателям доступно смотреть обложку, картинки, описание и отзывы (комментарии) о произведении.
  • Название:
    Том 11. Карты метро и нейронные сети. Теория графов
  • Автор:
  • Жанр:
  • Издательство:
    «Де Агостини»
  • Год:
    2014
  • Город:
    Москва
  • ISBN:
    978-5-9774-0682-6
  • Рейтинг:
    3.8/5. Голосов: 101
  • Избранное:
    Добавить в избранное
  • Отзывы:
  • Ваша оценка:
    • 80
    • 1
    • 2
    • 3
    • 4
    • 5

Клауди Альсина - Том 11. Карты метро и нейронные сети. Теория графов краткое содержание

Том 11. Карты метро и нейронные сети. Теория графов - описание и краткое содержание, автор Клауди Альсина, читайте бесплатно онлайн на сайте электронной библиотеки LibKing.Ru

Наш мир полон не только букв и цифр, но и самых разных изображений. Это картины, фотографии, произведения искусства, многочисленные схемы… Вспомните схему вашей линии метро или автобусного маршрута — это всего лишь линия с точками, рядом с которыми подписаны названия остановок. Подобные схемы из точек и линий называются графами. Именно о них вы узнаете, прочитав эту книгу.

Том 11. Карты метро и нейронные сети. Теория графов - читать онлайн бесплатно полную версию (весь текст целиком)

Том 11. Карты метро и нейронные сети. Теория графов - читать книгу онлайн бесплатно, автор Клауди Альсина
Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать
Цепь на квадратной сетке На этой сетке размерами 7 x 7 клеток нужно провести - фото 108

Цепь на квадратной сетке

На этой сетке размерами 7 x 7 клеток нужно провести вдоль линий сетки пять непересекающихся линий так, чтобы соединить точки, обозначенные одинаковыми буквами.

Советуем читателю вооружиться терпением и как следует поразмыслить над тем как - фото 109

Советуем читателю вооружиться терпением и как следует поразмыслить над тем, как найти единственное решение этой задачи. Не торопитесь заглядывать в ответы в конце главы.

* * *

МАРТИН ГАРДНЕР (1914–2010)

Среди звездных авторов научно-популярной литературы особенно ярко блистает звезда Мартина Гарднера. Он родился в городе Талса, штат Оклахома, США, изучал философию, но после окончания университета занялся журналистикой. Много лет, с 1956 по 1986 год, он был автором ежемесячной рубрики «Математические игры» в журнале Scientific American. В этой рубрике и в своих многочисленных книгах он рассказывал о математике, играх, алгоритмах, парадоксах и головоломках.

Кроме этого, он писал о философии, научных исследованиях в различных областях, а также был автором комментариев ко многим книгам. Любопытно, что Гарднер не выступал на конференциях и не преподавал, уделяя все время написанию книг и статей.

Обложка одной из многочисленных книг Мартина Гарднера Маршрут коня на - фото 110

Обложка одной из многочисленных книг Мартина Гарднера.

* * *

Маршрут коня на шахматной доске

Шахматная доска используется во множестве математических задач. Классическими являются задачи о перемещении различных фигур (пешки, слона, ладьи, ферзя) по шахматной доске. Особый интерес представляет следующий вопрос: может ли шахматный конь пройти по всем 64 клеткам доски ровно один раз и вернуться в исходную клетку?

Эта задача имеет решение; более того, оно не является единственным. Эту головоломку, как и многие другие шахматные задачи, можно решить с помощью теории графов. Каждая клетка доски соответствует вершине графа, ход коня — ребру, соединяющему две вершины графа. Следовательно, задача сводится к нахождению гамильтонова цикла в этом графе.

Маршрут коня по шахматной доске.

Математики не стали ограничиваться стандартной доской размером 8 x 8 клеток и рассмотрели возможность обхода досок размерами 5 x 5, 6 x 6, 3 x 10 клеток и других. Эти задачи представляют собой задачи на поиск гамильтоновых цепей в графах, число вершин которых равняется n x m . Например, для доски 6 x 6 клеток задача имеет решение, для досок 5 x 5 или 2 x 8 — нет.

Интересной читателю будет и задача о поиске маршрута шахматной ладьи из одного угла доски в диагонально противоположный, проходящего через все клетки. Можно рассмотреть доску размерами 7 x 7 клеток или общий случай — n x n клеток.

Простая игра в шахматы может подарить вам огромное множество интересных задач.

Льюис Кэрролл и эйлеровы графы

Чарльз Лютвидж Доджсон(1832–1898), известный под псевдонимом Льюис Кэрролл, был не только автором «Алисы в стране чудес», но и любителем занимательных математических задач. Он любил придумывать остроумные головоломки, которые мог решить даже ребенок. Некоторые из его задач сегодня изучаются в теории графов, хотя в его эпоху к теории графов относили лишь задачи, где нужно было нарисовать заданную фигуру, не отрывая карандаша от бумаги. Самой известной из подобных задач Кэрролла является задача о трех квадратах, показанных на рисунке. Сможете ли вы обойти этот граф, не отрывая карандаша от бумаги и не проводя ни одну линию дважды?

Томас ОБейрн придумал удивительный метод решения подобных задач который - фото 111

Томас О’Бейрн придумал удивительный метод решения подобных задач, который заключается в том, что нужно раскрасить смежные области чередующимися цветами (см. рисунок) и тем самым «разделить» области, чтобы найти искомый путь. Маршрут обхода становится очевидным, и можно легко провести карандашом нужный путь на исходном графе.

Задача о четырех окружностях Спустя много лет после Кэрролла ОБейрн придумал - фото 112

Задача о четырех окружностях

Спустя много лет после Кэрролла О’Бейрн придумал похожую задачу, заменив три квадрата четырьмя пересекающимися окружностями, которые образуют красивую симметричную фигуру.

Читателю предлагается найти способ обхода всех дуг четырех окружностей пройдя - фото 113

Читателю предлагается найти способ обхода всех дуг четырех окружностей, пройдя по каждой ровно один раз. Очевидно, что раскраска окружностей по описанному выше алгоритму поможет вам решить эту задачу. Если вам не удалось найти решение, загляните в конец этой главы, где приводится ответ к задаче (стр. 122).

Магические звезды

Магические звезды — удивительная игра из области занимательной комбинаторики, в которой смешались графы и числа.

На рисунке изображена пятиугольная звезда символ школы пифагорейцев Десять - фото 114

На рисунке изображена пятиугольная звезда — символ школы пифагорейцев. Десять ее вершин обозначены кругами. Можно ли расположить в вершинах звезды числа от 1 до 10 так, чтобы сумма чисел во всех рядах из четырех вершин была одинаковой? Эта сумма чисел называется магической константой. Попробуйте решить задачу, прежде чем продолжить чтение. Чему равна магическая константа для пятиугольной звезды?

Не получается? Не беспокойтесь. Вам не удается найти решение, потому что его не существует. Обратите внимание, что сумма чисел от 1 до 10 равна 55. Так как каждое число находится в двух линиях звезды, общая сумма чисел на всех линиях будет в два раза больше, чем 55, то есть 110. Следовательно, магическая константа должна равняться 110/5, то есть 22. Остается распределить числа так, чтобы их сумма в каждом ряду равнялась 22.

Иан Ричардс заметил: каждая из линий, в одной из вершин которой находится число 1, должна содержать, помимо единицы, еще три числа, которые в сумме дают 21. Следовательно, сумма чисел на двух этих линиях равна 42, поэтому 10 должно находиться в одном ряду с 1 (шесть чисел, среди которых нет 10, в сумме могут давать максимум 4 + 5 + 6 + 7 + 8 + 9 = 39). Пусть А — линия, на которой находятся 1 и 10, В — другая линия с вершиной 1, С — другая линия с вершиной 10. Тогда числа на линии А можно расположить четырьмя возможными способами. Если на одной из линий будут располагаться 1, 10, 4, 7, то поместить числа на В и С будет невозможно. Следовательно, остаются три случая:

Читать дальше
Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать


Клауди Альсина читать все книги автора по порядку

Клауди Альсина - все книги автора в одном месте читать по порядку полные версии на сайте онлайн библиотеки LibKing.




Том 11. Карты метро и нейронные сети. Теория графов отзывы


Отзывы читателей о книге Том 11. Карты метро и нейронные сети. Теория графов, автор: Клауди Альсина. Читайте комментарии и мнения людей о произведении.


Понравилась книга? Поделитесь впечатлениями - оставьте Ваш отзыв или расскажите друзьям

Напишите свой комментарий
x