Немного о графах

Задачи на теорию графов встречаются на школьных математических олимпиадах, начиная, по моим наблюдениям, где-то с регионального этапа. И решать такие задачи обычным школьникам, которые о графах никогда не слышали, тяжело. Приведу некоторые начальные сведения из теории графов и пару, как мне кажется, интересных задач, для решения которых понадобятся только приведенные здесь сведения.

Итак, что же такое граф?

Определение. Пусть задано некоторое непустое множество

    \[V\]

и множество

    \[E\]

пар различных элементов из

    \[V\]

. Элементы множества

    \[V\]

называются вершинами графа, элементы множества

    \[E\]

называются ребрами графа, а пара

    \[(V,E)\]

, т.е. множество вершин и множество ребер, называется графом.

Обычно в качестве множества

    \[V\]

берут множество первых

    \[n\]

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

    \[V=\{1,2,3,4,5,6,7,8\}\]

и ребрами

    \[E=\{ (1,2),(1,3),(2,3),(2,5),(2,8),(3,4),(4,6),(5,6),(5,7),(6,7),(7,8)\}.\]

Если две вершины графа соединены ребром, то они называются смежными, иначе — несмежными. Число ребер, выходящих из данной вершины, называется степенью этой вершины. Читать полностью ‘Немного о графах’ »

Математики хронически несчастливы и растеряны (и так и должно быть)

Джереми Кун

Бóльшая часть инженеров-программистов открывает для себя две вещи, имеющие отношение к математике: математика действительно трудна, и она открывает двери в мир новых идей. Таким образом, это очень похоже на обучение чтению. Как только вы немного освоите математику, вы сможете свободно читать книги, пользоваться ее идеями для решения задач и, возможно, даже самостоятельно написать что-то новое.

Многие люди, пытающиеся учиться математике самостоятельно, используют два подхода. В первом случае они изучают только то, что нужно для использования интересующих их вещей. В этом нет ничего плохого, но это сродни освоению достаточно простого словарного запаса, необходимого для заполнения налоговых документов. Часто это слишком специальные вещи, которые не могут дать представления о том, как применять ключевые идеи в других местах. Типичным примером является изучение конкретных вещей из линейной алгебры для понимания какого-то алгоритма машинного обучения. Это похвально и несомненно полезно, но, по моему опыту, этот путь заставляет начинать с нуля в каждом новом приложении. Читать полностью ‘Математики хронически несчастливы и растеряны (и так и должно быть)’ »

Кривые Гильберта

Кривые Гильберта названы в честь немецкого математика Давида Гильберта. Впервые они были описаны в 1891 году.

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

Самый простой способ понять, как строится кривая Гильберта, следующий. Представьте, что у вас есть длинный кусок веревки и вы хотите расположить веревку на плоской сетке с квадратными ячейками. Ваша цель состоит в том, чтобы веревка пересекала стороны каждого квадрата сетки ровно один раз. Читать полностью ‘Кривые Гильберта’ »

Боязнь математики и понимание информации о генетически модифицированных продуктах

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

“Боязнь математики, которая проявляется, когда люди обеспокоены использованием математики или статистики, приводит к уменьшению усилий, и уменьшается способность заниматься математикой’’, — сказала Роксана Пэррот, заслуженный профессор. — “Боязнь математики также, как было установлено, ухудшает работу памяти.’’

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

“Это первое известное нам исследование, в котором изучалась боязнь математики применительно к здоровью и оценке риска’’, — сказала Пэррот. — “Математика стала обычным элементом во многих сообщениях об исследованиях, связанных со здоровьем и рисками, обращающихся к математической компетенции и игнорирующих познавательные и эмоциональные компоненты.‘’ Читать полностью ‘Боязнь математики и понимание информации о генетически модифицированных продуктах’ »

Математик и джинн

Вот такой забавный комикс был найден здесь: http://www.smbc-comics.com.

Читать полностью ‘Математик и джинн’ »

Математическое доказательство размером с Википедию слишком большое, чтобы люди могли его проверить

Борис Конев и Алексей Лисица

Если ни один человек не может проверить доказательство теоремы, действительно ли это может считаться математикой? Этот интересный вопрос возник в связи с недавним доказательством, полученным с помощью компьютера. Оно столь же велико, как все содержание Википедии, поэтому маловероятно, что его когда-нибудь сможет проверить человек. Читать полностью ‘Математическое доказательство размером с Википедию слишком большое, чтобы люди могли его проверить’ »