Четверг, 24.09.2020, 09:05
Ш  К  О  Л  А     П  И  Ф  А  Г  О  Р  А
      Предмет математики настолько серьезен, что нужно
не упускать случая, сделать его немного занимательным".
                                                                           Блез Паскаль
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
ПАМЯТКИ ПО МАТЕМАТИКЕ   ВЕЛИКИЕ МАТЕМАТИКИ   ТЕОРИЯ ЧИСЕЛ   МАТЕМАТИЧЕСКАЯ ЛОГИКА
УРОКИ МАТЕМАТИКИ В ШКОЛЕ


МАТЕМАТИЧЕСКАЯ КЛАДОВАЯ


В МИРЕ ЗАДАЧ
ЕГЭ ПО МАТЕМАТИКЕ
МАТЕМАТИКА В НАЧАЛЬНОЙ ШКОЛЕ
ВАРИ, КОТЕЛОК!
УДИВИТЕЛЬНАЯ МАТЕМАТИКА
ВЫСШАЯ МАТЕМАТИКА
В МИРЕ ИНТЕРЕСНОГО
Категории раздела
ПРОСТЫЕ ЧИСЛА. ДОЛГАЯ ДОРОГА К БЕСКОНЕЧНОСТИ [37]
КОГДА ПРЯМЫЕ ИСКРИВЛЯЮТСЯ. НЕЕВКЛИДОВЫ ГЕОМЕТРИИ [23]
МУЗЫКА СФЕР. АСТРОНОМИЯ И МАТЕМАТИКА [57]
МАГИЯ ЧИСЕЛ. МАТЕМАТИЧЕСКАЯ МЫСЛЬ ОТ ПИФАГОРА ДО НАШИХ ДНЕЙ [27]
ИНВЕРСИЯ [20]
ИСТИНА В ПРЕДЕЛЕ. АНАЛИЗ БЕСКОНЕЧНО МАЛЫХ [47]
БЕСКОНЕЧНОСТЬ В МАТЕМАТИКЕ [43]
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ЕЕ ПАРАДОКСЫ [6]
ИЗМЕРЕНИЕ МИРА. КАЛЕНДАРИ, МЕРЫ ДЛИНЫ И МАТЕМАТИКА [33]
АБСОЛЮТНАЯ ТОЧНОСТЬ И ДРУГИЕ ИЛЛЮЗИИ. СЕКРЕТЫ СТАТИСТИКИ [31]
КОДИРОВАНИЕ И КРИПТОГРАФИЯ [47]
МАТЕМАТИКА В ЭКОНОМИКЕ [39]
ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ И МАТЕМАТИКА [35]
ЧЕТВЕРТОЕ ИЗМЕРЕНИЕ. ЯВЛЯЕТСЯ ЛИ НАШ МИР ТЕНЬЮ ДРУГОЙ ВСЕЛЕННОЙ? [9]
ТВОРЧЕСТВО В МАТЕМАТИКЕ [44]
ЗАГАДКА ФЕРМА. ТРЕХВЕКОВОЙ ВЫЗОВ МАТЕМАТИКЕ [30]
ТАЙНАЯ ЖИЗНЬ ЧИСЕЛ. ЛЮБОПЫТНЫЕ РАЗДЕЛЫ МАТЕМАТИКИ [95]
АЛГОРИТМЫ И ВЫЧИСЛЕНИЯ [17]
КАРТОГРАФИЯ И МАТЕМАТИКА [38]
ПОЭЗИЯ ЧИСЕЛ. ПРЕКРАСНОЕ И МАТЕМАТИКА [23]
ТЕОРИЯ ГРАФОВ [33]
НАУКА О ПЕРСПЕКТИВЕ [29]
ЧИСЛА - ОСНОВА ГАРМОНИИ. МУЗЫКА И МАТЕМАТИКА [15]
Статистика

Онлайн всего: 7
Гостей: 7
Пользователей: 0
Форма входа

Главная » Файлы » МИР МАТЕМАТИКИ » ТЕОРИЯ ГРАФОВ

Деревья, за которыми виден лес
20.01.2016, 20:11

Дерево — это очень простой граф, все вершины которого соединены так, что отсутствуют циклы, как, например, на следующем рисунке:



В дереве можно проложить маршрут между любыми двумя вершинами.

Далее приведены все возможные деревья с числом вершин от 1 до 8.



Последовательность чисел, обозначающих количество всех возможных деревьев для каждого числа вершин, выглядит так: 1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551, 1301, 3159…

Если дерево имеет р вершин, то в нем всегда будет р — 1 ребер, но для каждого значения р можно изобразить рр-2 разных деревьев (формула Кэли). Понятие дерева впервые ввел Кэли в 1857 году. Деревья образуют очень важный класс графов, так как в них все вершины соединены минимально возможным числом ребер. Благодаря этому деревья находят интересное применение в самых разных областях: при проектировании электрических цепей, телефонных сетей, при поиске маршрутов между населенными пунктами и так далее.

Следующая простая и красивая теорема дает характеристику деревьям, а также имеет крайне важное практическое значение:

«Граф G является деревом тогда и только тогда, когда между любыми двумя различными его вершинами и v существует единственный путь. Это равносильно следующему утверждению: С является связным графом, если он имеет р вершин и р — 1 ребро».

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

Причина этому такова. Пусть G — дерево. Даны две вершины G, u и v. Так как граф является связным, то существует по меньшей мере один путь между u и v. Если бы между этими вершинами существовало два пути, С1 и С2, то в графе G образовался бы цикл, что невозможно. Разумеется, если между двумя произвольными вершинами графа существует единственный путь, граф является связным и не содержит циклов.

* * *

ДЕРЕВЬЯ И ВЕРОЯТНОСТИ

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



Для расчета вероятностей нужно четко представлять все возможные исходы.

* * *

У. УИНГФИЛД И А. А. МАРКОВ: ТЕННИС И ТЕОРИЯ ГРАФОВ

Уолтер Уингфилд (1833–1912) запатентовал игру под названием теннис в феврале 1874 года. Андрей Андреевич Марков (1856–1922) занимался изучением последовательностей случайных событий, которые позднее стали называться цепями Маркова. Цепь Маркова представляет собой ориентированный граф, вершинам которого соответствуют состояния, а дугам — переходы из одного состояния в другое в зависимости от вероятности исходного события, но не всей последовательности предшествующих событий. Уингфилда и Маркова объединяет работа А. Л. Садовского и Л. Е. Садовского «Математика и спорт», в которой цепи Маркова используются для анализа теннисных партий. Так, на рисунке вероятности возможных исходов для каждого события соответственно равны 0,6 и 0,4.


* * *

Рассмотрим задачу, которую можно решить с помощью деревьев. Даны городов A1, А2Аn. Зная затраты на установление сообщения между каждой парой городов (стоимость строительства дорог, прокладки водо- и газопровода, линий электропередачи, телефонных линий), определите, как можно соединить города самым дешевым способом. Очевидно, что сеть «экономических связей» будет деревом, так как все города должны быть связаны друг с другом и не должно существовать циклов. Если бы в этой сети существовал цикл, можно было бы удалить одно из его ребер и все города по-прежнему были бы соединены между собой, но уже при меньших затратах.

Следовательно, дерево связей между городами будет иметь n — 1 ребро. Соединим два города, для которых стоимость прокладки всех коммуникаций будет наименьшей. Затем соединим один из них с третьим городом, для которого стоимость коммуникаций будет минимальной, и так далее. Как называется множество различных графов, которые являются деревьями?

Наверное, вы уже догадались: такое множество называется лесом. Вопреки известной пословице, в теории графов за деревьями лес виден.

* * *

ГРАФЫ И ГЕНЕАЛОГИЧЕСКИЕ ДЕРЕВЬЯ

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

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



Современное генеалогическое древо царской семьи Романовых, составленное на компьютере, и генеалогическое древо семейства Ругон-Маккаров из произведений писателя Эмиля Золя, составленное в 1878 году.



ГРАФ МАТЕМАТИЧЕСКИХ СВЯЗЕЙ

По адресу http://genealogy.math.ndsu.nodak.edu находится страница математического генеалогического проекта (Mathematics Genealogy Project), на которой собраны данные о математиках и их «потомках» — тех ученых, которые защитили докторскую диссертацию под их руководством. Проект непрерывно пополняется данными о все новых и новых диссертациях, и постепенно формируется дерево взаимосвязей между всеми математиками. По состоянию на апрель 2010 года были собраны данные о 140 982 математиках.



Главная страница проекта Mathematics Genealogy Project

Категория: ТЕОРИЯ ГРАФОВ | Добавил: admin | Теги: ИТК и мате, Мир Математики, искусственный интеллект, машинное обучение, популярная математик, математика и информатик, дидактический материал по матем
Просмотров: 1013 | Загрузок: 0 | Рейтинг: 0.0/0
УЧИТЕЛЮ ИНФОРМАТИКИ
КОНСПЕКТЫ УРОКОВ
ВНЕКЛАССНЫЕ МЕРОПРИЯТИЯ ПО ИНФОРМАТИКЕ
ПОСОБИЯ И МЕТОДИЧКИ ДЛЯ УЧИТЕЛЯ ИНФОРМАТИКИ
ИЗ ОПЫТА РАБОТЫ УЧИТЕЛЯ ИНФОРМАТИКИ
ЗАДАНИЯ ШКОЛЬНОЙ ОЛИМПИАДЫ ПО ИНФОРМАТИКЕ


ИНФОРМАТИКА В ШКОЛЕ


ИНФОРМАТИКА В НАЧАЛЬНЫХ КЛАССАХ
ИНФОРМАТИКА В 3 КЛАССЕ
ИНФОРМАТИКА В 4 КЛАССЕ
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 3 КЛАСС
КОНТРОЛЬНЫЕ РАБОТЫ ПО ИНФОРМАТИКЕ. 4 КЛАСС
ПРОГРАММИРОВАНИЕ ДЛЯ ДЕТЕЙ
СКАЗКА "ПРИКЛЮЧЕНИЯ ЭЛЕКТРОШИ"
ИГРОВЫЕ ТЕХНОЛОГИИ НА УРОКАХ ИНФОРМАТИКИ
ВИКТОРИНЫ ПО ИНФОРМАТИКЕ
КОМПЬЮТЕРНЫЕ ЧАСТУШКИ
ОБРАТНАЯ СВЯЗЬ
Поиск


Друзья сайта
  • Создать сайт
  • Все для веб-мастера
  • Программы для всех
  • Мир развлечений
  • Лучшие сайты Рунета
  • Кулинарные рецепты

  • Copyright MyCorp © 2020
    Яндекс.Метрика Рейтинг@Mail.ru