Четверг, 28.03.2024, 14:10
Ш  К  О  Л  А     П  И  Ф  А  Г  О  Р  А
      Предмет математики настолько серьезен, что нужно
не упускать случая, сделать его немного занимательным".
                                                                              Блез Паскаль
Главная | Регистрация | Вход Приветствую Вас Гость | RSS
ПАМЯТКИ ПО МАТЕМАТИКЕ   ВЕЛИКИЕ МАТЕМАТИКИ   ТЕОРИЯ ЧИСЕЛ   МАТЕМАТИЧЕСКАЯ ЛОГИКА
УРОКИ МАТЕМАТИКИ В ШКОЛЕ
МАТЕМАТИЧЕСКАЯ КЛАДОВАЯ
В МИРЕ ЗАДАЧ
ЕГЭ ПО МАТЕМАТИКЕ
МАТЕМАТИКА В НАЧАЛЬНОЙ ШКОЛЕ
ВАРИ, КОТЕЛОК!
УДИВИТЕЛЬНАЯ МАТЕМАТИКА
ВЫСШАЯ МАТЕМАТИКА
В МИРЕ ИНТЕРЕСНОГО
Категории раздела
ПРОСТЫЕ ЧИСЛА. ДОЛГАЯ ДОРОГА К БЕСКОНЕЧНОСТИ [37]
КОГДА ПРЯМЫЕ ИСКРИВЛЯЮТСЯ. НЕЕВКЛИДОВЫ ГЕОМЕТРИИ [23]
МУЗЫКА СФЕР. АСТРОНОМИЯ И МАТЕМАТИКА [57]
МАГИЯ ЧИСЕЛ. МАТЕМАТИЧЕСКАЯ МЫСЛЬ ОТ ПИФАГОРА ДО НАШИХ ДНЕЙ [27]
ИНВЕРСИЯ [20]
ИСТИНА В ПРЕДЕЛЕ. АНАЛИЗ БЕСКОНЕЧНО МАЛЫХ [47]
БЕСКОНЕЧНОСТЬ В МАТЕМАТИКЕ [43]
МАТЕМАТИЧЕСКАЯ ЛОГИКА И ЕЕ ПАРАДОКСЫ [6]
ИЗМЕРЕНИЕ МИРА. КАЛЕНДАРИ, МЕРЫ ДЛИНЫ И МАТЕМАТИКА [33]
АБСОЛЮТНАЯ ТОЧНОСТЬ И ДРУГИЕ ИЛЛЮЗИИ. СЕКРЕТЫ СТАТИСТИКИ [31]
КОДИРОВАНИЕ И КРИПТОГРАФИЯ [47]
МАТЕМАТИКА В ЭКОНОМИКЕ [39]
ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ И МАТЕМАТИКА [35]
ЧЕТВЕРТОЕ ИЗМЕРЕНИЕ. ЯВЛЯЕТСЯ ЛИ НАШ МИР ТЕНЬЮ ДРУГОЙ ВСЕЛЕННОЙ? [9]
ТВОРЧЕСТВО В МАТЕМАТИКЕ [44]
ЗАГАДКА ФЕРМА. ТРЕХВЕКОВОЙ ВЫЗОВ МАТЕМАТИКЕ [30]
ТАЙНАЯ ЖИЗНЬ ЧИСЕЛ. ЛЮБОПЫТНЫЕ РАЗДЕЛЫ МАТЕМАТИКИ [95]
АЛГОРИТМЫ И ВЫЧИСЛЕНИЯ [17]
КАРТОГРАФИЯ И МАТЕМАТИКА [38]
ПОЭЗИЯ ЧИСЕЛ. ПРЕКРАСНОЕ И МАТЕМАТИКА [23]
ТЕОРИЯ ГРАФОВ [33]
НАУКА О ПЕРСПЕКТИВЕ [29]
ЧИСЛА - ОСНОВА ГАРМОНИИ. МУЗЫКА И МАТЕМАТИКА [15]
Главная » Файлы » МИР МАТЕМАТИКИ » ТЕОРИЯ ГРАФОВ

Графы, множества и отношения
20.01.2016, 13:06
Математика, подобно любому прочному зданию, твердо стоит на фундаменте. Логика играет главную роль при выполнении дедуктивных умозаключений, лежит в основе понятий истинности и ложности, различий между аксиомами (постулатами) и теоремами, допустимыми формами доказательств и так далее. Теория множеств — еще одна колонна, на которой стоит здание математики. С ее помощью можно формализовать самые основные составляющие математических структур: элементы, множества, отношения, функции.

В наглядных объяснениях теории множеств используются как символы, так и графические обозначения. N = (1, 2, 3, …} обозначает множество натуральных чисел. На рисунке ниже изображено это же множество в виде точек на прямой.



* * *

ГЕОРГ КАНТОР (1845–1918) И ТЕОРИЯ МНОЖЕСТВ

Этот гениальный немецкий математик создал теорию множеств, чтобы дать более строгие определения многим математическим понятиям, в частности понятию бесконечности. Важный вклад в теорию множеств также внесли Фридрих Фреге и Юлиус Дедекинд. Благодаря Кантору стало возможным говорить, что «конечное множество — это множество, которое не является бесконечным» и что множество А является бесконечным, если между этим множеством и его подмножеством можно установить взаимно однозначное соответствие, то есть один к одному. Кантор прояснил вопрос, касающийся счетных бесконечных множеств, например множеств натуральных, целых или дробных чисел. Ему же принадлежит определение различных категорий бесконечностей (трансфинитные кардинальные и ординальные числа). Его идеи породили ожесточенные споры с другими математиками того времени (его основным противником стал Леопольд Кронекер), появились некоторые парадоксы, которые требовалось разрешить. Однако благодаря ему родилась красивая и фундаментальная теория множеств.

* * *

Для конечных множеств А = {a, b, с, d}, В = {а, Ь, е, f} обычно используются диаграммы Венна. На этих диаграммах элементы множеств представлены в виде отдельных точек и замкнутых кривых, ограничивающих группы точек.



Для множеств А, В их декартово произведение А x В определяется так:


то есть как множество упорядоченных пар (а, Ь). Это обозначение связано с традицией, начатой Рене Декартом, обозначать точки на плоскости (х, у) или в пространстве (х, у, z) упорядоченными парами или тройками чисел — координатами. Заметим, что слова по сути тоже представляют собой упорядоченные множества букв.



Декартовы координаты на плоскости и в пространстве.


На основе декартовых произведений вида А x A, то есть произведений множества на само себя, можно определить базовое понятие отношения R как подмножества А х А. Иными словами, отношение указывает элементы А, связанные между собой.

Если (а, Ь) принадлежит R, то между а и Ь имеется отношение. Если (а, с) не принадлежит R, то между а и с отсутствует отношение. Так, для данного отношения R для каждого элемента а имеет смысл рассматривать класс всех элементов, для которых установлено отношение с а. Если (а, Ь) принадлежит R, то это отношение также записывается в форме «а R Ь».

Рассмотрим в качестве примера множество А = {2, 3, 4, 5, 6, 7, 8, 9, 10} и отношение R на множестве A: a R Ь, если а кратно Ь. Упорядоченные пары для этого отношения можно представить в декартовых координатах.



Представление отношения в декартовых координатах.


Также можно использовать ориентированный граф, как показано ниже:



Направленный граф, представляющий отношение.


Отношения эквивалентности

Применительно к классификациям на множестве особый интерес представляют так называемые отношения эквивалентности R на множестве А. Они обладают тремя свойствами.

1. Рефлексивностью: a R а.

2. Симметричностью: если a R Ь, то b R а.

3. Транзитивностью: если a R b и b R с, то a R с.

Иными словами, отношение существует между любым элементом и им самим, это отношение обладает симметричностью и транзитивностью для троек элементов.

Если отношение R удовлетворяет всем этим свойствам, то множество А разделено на классы. Подобные отношения на конечных множествах можно представить с помощью графов: элементы множеств будут представлены в виде точек, соединенных линиями со стрелками, которые будут обозначать отношения.



Представление свойств отношения эквивалентности в виде графов.


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



Классификация, связанная с отношением эквивалентности.


Если А — множество людей, a R — отношение «иметь одинаковый возраст», то при классификации элементов множества на основе этого отношения сформируются группы по возрасту. Если А — множество целых чисел, a R — такое отношение, что a R Ь, если а — Ь без остатка делится на два, то при классификации получатся группы четных и нечетных чисел.


Отношение порядка

Еще один тип отношений, неотъемлемых в математике, да и в жизни, — это отношения порядка, которые обладают следующими свойствами.

1. Рефлексивностью: a R а.

2. Антисимметричностью: если a R Ь и Ь R а, то должно выполняться а = Ь.

3. Транзитивностью: если a R b и b R с, то a R с.

Вместо «а R b», как правило, используется обозначение «а =< Ь», которое нам прекрасно знакомо применительно к числам (0 =< 1 =< 2 =< …). Следовательно, для каждого элемента имеет смысл рассматривать множество {Ь/а =< Ь} всех элементов, больших а, или множество {Ь/Ь =< а} всех элементов, меньших а. И снова с помощью графов можно представить элементы множества в виде вершин, соединить ребрами упорядоченные элементы и ввести критерий вертикальности («элемент, расположенный ниже, является меньшим»), горизонтальности («элемент, расположенный правее, является бóльшим») или использовать для указания упорядоченности ориентированные графы.



Наглядное представление упорядоченности.


На следующем рисунке стрелками, обозначающими «включен в», указана упорядоченность частей множества из трех элементов {а, Ь, с}.



Граф включения множеств.


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


Отображения

Еще одним базовым обозначением теории множеств является отображение f: А —> В, где элементам а множества А присваивается единственный элемент bf (а) множества В. График функции f определяется как


Это множество можно представить на множестве А x В.



График функции f(x) = х2 (парабола).



График функции целой части числа для положительных вещественных чисел.



Температура тела человека.

* * *

ЖОРЖ ПЕРЕК И ЕГО «ДУМАТЬ/КЛАССИФИЦИРОВАТЬ»

Блестящий интеллектуал Жорж Перек в период с 1976 по 1982 год опубликовал множество сюрреалистических статей критического содержания. Две наиболее выдающихся среди этих статей носили названия «Думать/классифицировать» и «Краткие заметки об искусстве и способе расставлять книги». В них Перек показывает, как сложно классифицировать людей или вещи, расставить по порядку книги и так далее. Например, он демонстрирует чрезвычайную сложность составления «упорядоченной» библиотеки, так как книги можно расставить в алфавитном порядке по фамилиям их авторов, по цвету обложек, переплету, дате покупки, дате публикации, формату, жанру, языку… Сложные ситуации всегда возникают и в теории, и на практике.

* * *

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

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

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

Отображения, связывающие элементы двух конечных множеств А и В, обычно представляют сочетанием графов и диаграмм Венна.



Графическое представление отображения f, связывающего множества {a, b, с, d} и {1, 2, 3, 4}.


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



Инъективное отображение.



Сюръективное отображение.



Биективное отображение.


Чтобы найти все возможные отображения конечного множества А на множество В, будет полезно использовать графы, которые являются деревьями.



Дерево возможных отображений множества A = {a, b} на множество B = {1, 2, 3, 4}.


Если даны два отображения — отображение f множества А на множество В и отображение g множества В на множество С, то имеет смысл говорить о композиции отображений и g множества А на множество С, то есть о присвоении каждому элементу а множества А элемента g (f(а)) множества С. Композиции отображений g и обозначается как g о f. Ее можно представить в виде графов следующего вида.



Граф композиции отображений q и f.


Нечеткие множества и графы

В последние десятилетия в целях моделирования сложных ситуаций реальной жизни все шире применяется теория нечетких множеств, созданная инженером Калифорнийского университета в Беркли Лотфи Заде. В классической трактовке элемент а либо принадлежит множеству А, либо нет. Следовательно, множество определяется характеристической функцией: она принимает значение 1 для элементов, принадлежащих A, и 0 для элементов, не принадлежащих A.

Идея Заде состояла в том, чтобы расширить характеристические функции и создать нечеткие множества, то есть определить функции, которые ставят в соответствие элементам x универсального множества X значения f(х) в интервале от 0 до 1. В такой трактовке f(х) определяет степень принадлежности х к А.



Нечеткие множества, соответствующие утверждению «результат примерно равен 1».

* * *

ЖУРНАЛЫ О ДИСКРЕТНОЙ МАТЕМАТИКЕ, КОМБИНАТОРИКЕ И ГРАФАХ

Ниже перечислены ведущие современные журналы по этим темам.

· Ars Combinatorica.

· European Journal of Combinatorics.

· Combinatorica.

· Geombinatorics.

· Combinatorics, Probability and Computing.

· Journal of Algebraic Combinatorics.

· Designs, Codes and Cryptology.

· Journal of Combinatorial Theory. Series A.

· Discrete and Computational Geometry.

· Journal of Combinatorial Theory. Series B.

· Discrete Applied Mathematics.

· Journal of Geometry.

· Discrete Mathematics.

· Journal of Graph Theory.

· Electronic Journal of Combinatorics.

* * *

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

В рамках теории нечетких множеств также рассматриваются нечеткие классификации и упорядоченность; можно говорить о степенях отношений. Эта теория основана на теории множеств и может быть подтверждена примерами из теории вероятностей (вероятность является оценкой какого-либо события и лежит в интервале от 0 до 1), но особенно интересна в эмпирических моделях и при решении задач, на которые нельзя дать четкого и однозначного ответа в рамках классической математики.

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


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

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

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


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

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


    Copyright MyCorp © 2024
    Яндекс.Метрика Top.Mail.Ru