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

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


Контрольная Типы бинарных отношений. Изображение графов в виде схемы. Цикл в графе, совпадение его начальной и конечной вершины. Понятие достижимости в теории графов, их математические свойства. Частично упорядоченное множество как один из типов бинарного отношения.

Информация:

Тип работы: Контрольная. Предмет: Математика. Добавлен: 04.09.2010. Сдан: 2010. Уникальность по antiplagiat.ru: --.

Описание (план):


12

Графы и частично упорядоченные множества

Обе эти структуры являются частными случаями бинарных отношений. Пусть задано множество каких-то объектов и из этих объектов по какому-то определенному принципу формируются пары. Например, дано некоторое множество людей, а пары в нем выбираются по такому принципу: первый элемент пары - некий человек, а второй - один из его родителей. При этом один и тот же человек может присутствовать в двух и более парах, например, когда один и тот же человек имеет двоих, троих или более детей. Например, три пары в этом отношении (Иван, Мария), (Дарья, Мария), (Глеб, Мария) означают, что Иван, Дарья и Глеб - дети Марии. В качестве математического примера бинарного отношения можно привести пары, составленные из некоторого множества чисел, при этом первое число в каждой паре меньше второго. Это пример бинарного отношения "меньше". Другой пример: задана некоторая система множеств, а бинарное отношение в этой системе формируется из пар множеств по принципу: первое множество включено во второе множество - это пример бинарного отношения "включение множеств".

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

Рассмотрим пример. Пусть задано множество вершин

V = {a, b, c, d, e},

из которого сформировано некоторое множество пар

E = { (a, b), (a, c), (b, d), (c, a), (c, e) }.

Множество пар E, сформированное из множества V вершин, является примером бинарного отношения. Преобразуем это бинарное отношение в схему. Для этого изобразим на листе бумаги все его вершины произвольным образом и соединим эти вершины линиями со стрелками так, чтобы каждая стрелка выходила из первого элемента пары и входила во второй элемент пары (см. рисунок 1). При этом, если окажется, что некоторая пара вершин соединяется стрелкой в одну и в другую сторону, то мы вместо линий со стрелками нарисуем линию без стрелок (для нашего примера это пары (a, c) и (c, a)). С учетом этого дугами в графе являются соединительные линии со стрелками в одну сторону, а ребрами - соединения без стрелок или со стрелками, направленными в обе стороны. Можно считать, что каждое ребро содержат пару разнонаправленных дуг.

Рис.1

Каждая дуга графа представлена начальной и конечной вершинами. Граф, у которого все связи представлены только ребрами, называется неориентированным графом (или просто графом). Граф, у которого отсутствуют ребра (т.е. все связи имеют только одно направление), называется ориентированным графом, а граф, у которого имеются и ребра, и дуги - смешанным.

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

G (a) = {b, c}; G (b) = {d}; G (c) = {a, e}; G (d) = G (e) = .

Если мы, используя изображение произвольного графа, будем двигаться от вершины к вершине в соответствии с направлением дуг (при этом по ребру можно передвигаться в любую сторону), то последовательность вершин, отмечаемых по мере такого "обхода", называется путем в данном графе. Например для графа G на рисунке 8 существуют следующие пути: (a, b, d); (c, e); (a, c, a, b) и т.д. Пути можно записывать, используя стрелки, например, abd. При этом возможны графы, у которых имеются самопересекающиеся пути, т.е. некоторые вершины и дуги могут в некоторых путях повторяться.

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

Например, в графе на рисунке 8 имеется один цикл, обусловленный тем, что в нем имеется ребро (a, c). Поэтому цикл можно представить в виде пути (a, c, a). Если в этот граф добавить еще одну дугу (d, a), то в этом случае появится еще одни цикл (d, a, b, d). По сути цикл - это путь без начала и конца, поскольку, "путешествуя" по циклу, мы можем крутиться в нем бесконечное число раз.

Одним из основных в теории графов является понятие достижимости. Вершина y графа G называется достижимой из вершины x, если в G существует путь из вершины x в вершину y. Часто бывает необходимо определить для каждой вершины графа G множество всех достижимых из нее вершин. Например, для вершины a в графе на рисунке 1 достижимыми являются все вершины этого графа (в том числе и сама вершина a), в то время как из вершины b достижима только одна вершина - d, а для вершины e в данном графе нет вообще достижимых вершин.

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

Частично упорядоченное множество - один из типов бинарного отношения. Отношение частичного порядка является одним из фундаментальных общематематических понятий и широко используется в теоретической математике, в системах логического вывода и во многих других приложениях. Оно является обобщением таких широко известных бинарных отношений как "меньше или равно" () для чисел и "включено или равно" () для множеств. Обозначение "" часто используется не только для обозначения отношения "меньше или равно" на множестве чисел, упорядоченных по величине, но и для обозначения произвольного отношения частичного порядка. Формально отношение частичного порядка определяется как заданное на множестве X бинарное отношение со следующими свойствами:

рефлексивности: aa для любого aX;

транзитивности: если ab и bc, то ac;

антисимметричности: из ab и ba следует a=b,

где a, b и c - произвольные элементы частично упорядоченного множества X.

Среди всех отношений частичного порядка наиболее простым в структурном отношении является линейный порядок, когда для любой пары разных элементов (a, b) множества определено либо ab, либо ba. Примерами линейного порядка являются множества чисел, упорядоченных по величине, и множества слов, расположенных в лексикографическом порядке. Их можно по заданному порядку сформировать в виде одной непрерывной последовательности. Например, 2<5<12<19. При линейном порядке все элементы частично упорядоченного множества можно выстроить в одну цепочку по заданному отношению.

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

P = {a, b, c}; Q = {b, d}; R = {a, b, c, d},

то для них линейный порядок установить невозможно, так как множества P и Q несравнимы - ни одно из них не включено в другое. В то же время, если множество Q в этой совокупности заменить на множество Q1 = {b, c}, то мы получим линейный порядок

Q1 P R или {b, c}{a, b, c}{a, b, c, d}.

Еще одним широко известным отношением частичного порядка является порядок по делимости. Предположим, задано некоторое множество положительных целых чисел (например, D = {1, 2, 3.4, 6, 12}. Тогда будем считать, что для двух чисел x и y верно xy, если и только если число y делится без остатка на число x.

Для заданного множества D порядок по делимости верен для пар (1,2); (2,4); (3,6) и т.д., Но для некоторых пар (например, (4,6)) такой порядок не соблюдается, так как число 6 не делится без остатка на число 4. Нетрудно убедиться, что отношение порядка по делимости полностью соответствует свойствам частично упорядоченных множеств (рефлексивности, транзитивности и антисимметричности).

В математике известно немало структур, соответствующих частичному порядку. Рассмотрим некоторые общие свойства отношений частичного порядка. Далее в целях сокращения будем использовать вместо термина "частично упорядоченное множество" термин у-множество - своеобразная калька с эквивалентного английского термина poset.

Любое у-множество можно представить как ориентированный граф, в котором дуга ab между парой элементов означает ab. Однако не любой ориентированный граф является представлением у_множества. Чтобы сугубо ориентированный граф представлял правильное у_множество, необходимо и достаточно чтобы в нем не было циклов.

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

Рис.2

На этих рисунках показаны не все связи между элементами - те, которые следуют из свойства транзитивности (например, связь ps на каждом из этих рисунков), в них отсутствуют. Такое сокращенное представление у_множеств без транзитивных связей называется диаграммой Хассе.

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


Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.