Главная > Документ


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

[править]

Материал из Википедии — свободной энциклопедии

(Перенаправлено с Частичный порядок)

Текущая версия [показать стабильную версию] (сравнить)  

(+/-)

Данная версия страницы не проверялась участниками с соответствующими правами. Вы можете прочитать последнюю проверенную или т. н. стабильную версию от 19 января 2009, однако она может значительно отличаться от текущей версии. Проверки требуют 19 правок.

Перейти к: навигация, поиск

Подмножества {x, y, z}, упорядоченные отношением включения

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

В качестве абстрактного примера можно привести совокупность подмножеств множества из трех элементов {x,y,z}, упорядоченное по отношению включения.

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

Содержание

[убрать]

  • 1Определение и примеры

    • 1.1Терминология и обозначения

    • 1.2Строгий и нестрогий порядок

    • 1.3Примеры

  • 2Связанные определения

    • 2.1Несравнимые элементы

    • 2.2Минимальный/максимальный и наименьший/наибольший элементы

    • 2.3Верхние и нижние грани

  • 3Специальные типы частично упорядоченных множеств

    • 3.1Линейно упорядоченные множества

    • 3.2Вполне упорядоченные множества

  • 4Теоремы о частично упорядоченных множествах

  • 5Примечания

  • 6Литература

  • 7См. также

[править] Определение и примеры

Порядком, или частичным порядком, на множестве M называется бинарное отношениена M (определяемое некоторым множеством ), удовлетворяющее следующим условиям[1]:

  • Рефлексивность:

  • Транзитивность:

  • Антисимметричность:

Множество M, на котором задано отношение частичного порядка, называется частично упорядоченным (англ.partiallyorderedset, poset). Если быть совсем точным[2], то частично упорядоченным множеством называется пара , где M — множество, а  — отношение частичного порядка на M.

[править] Терминология и обозначения

Отношение частичного порядка обычно обозначают символом , по аналогии с отношением «меньше либо равно» на множестве действительных чисел. При этом, если , то говорят, что элемент aне превосходитb, или что aподчиненb.

Если и , то пишут a < b, и говорят, что aменьшеb, или что aстрого подчиненb.

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

[править] Строгий и нестрогий порядок

Отношение, удовлетворяющее условиям рефлексивности, транзитивности и антисимметричности, также называют нестрогим, или рефлексивным порядком. Если условие рефлексивности заменить на условие антирефлексивности:

то получим определение строгого, или антирефлексивного порядка.

Если  — нестрогий порядок на множестве M, то отношение < , определяемое как:

является строгим порядком на M. Обратно, если <  — строгий порядок, то отношение , определенное как

является нестрогим порядком.

Поэтому все равно — задать на множестве нестрогий порядок, или строгий порядок. В результате получится одна и та же структура. Разница только в терминологии и обозначениях.

[править] Примеры

Подмножества {x, y, z}, упорядоченные отношением включения

Как уже указывалось выше, множество действительных чиселчастично упорядочено по отношению «меньше либо равно» .

Пусть M — множество всех действительнозначных функций, определенных на отрезке [a,b], то есть функций вида

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

Пусть M — некоторое множество. Множество всех подмножеств M (так называемый булеан), частично упорядочено по включению .

Множество всех натуральных чиселчастично упорядочено по отношению делимости.

[править] Связанные определения

[править] Несравнимые элементы

Если a и b — действительные числа, то имет место одно и только из соотношений:

В случае, если a и b — элементы произвольного частично упорядоченного множества, то существует четвёртая логическая возможность: не выполнено ни одно из указанных трех соотношений. В этом случае элементы a и b называются несравнимыми. Например, если M — множество действительнозначных функций на отрезке [0,1], то элементы f(x) = x и g(x) = 1 − x будут несравнимы. Возможность существования несравнимых элементов объясняет смысл термина «частично упорядоченное множество».

[править] Минимальный/максимальный и наименьший/наибольший элементы

Основные статьи: Максимум (математика), Минимум (математика)

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

Элемент называется минимальным (англ.minimalelement), если не существует элемента b < a. Другими словами, a — минимальный элемент, если для любого элемента либо b > a, либо b = a, либо b и a несравнимы. Элемент a называется наименьшим (англ.leastelement, lowerbound (opp. upperbound)), если для любого элемента имеет место неравенство . Очевидно, всякий наименьший элемент является также минимальным, но обратное в общем случае неверно: минимальный элемент a может и не быть наименьшим, если существуют элементы b, не сравнимые с a.

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

Аналогично вводятся понятия максимального (англ.maximalelement) и наибольшего (англ.greatestelement) элементов.

[править] Верхние и нижние грани

Пусть A — подмножество частично упорядоченного множества . Элемент называется верхней гранью (англ.upperbound) A, если любой элемент не превосходит u. Аналогично вводится понятие нижней грани (англ.lowerbound) множества A.

Любой элемент, больший, чем некоторая верхняя грань A, также будет верхней гранью A. А любой элемент, меньший, чем некоторая нижняя грань A, также будет нижней гранью A. Эти соображения ведут к введению понятий наименьшей верхней грани (англ.least upper bound) и наибольшейнижнейграни (англ.greatest lower bound).

[править] Специальные типы частично упорядоченных множеств

[править] Линейно упорядоченные множества

Основная статья: Линейно упорядоченное множество

Пусть  — частично упорядоченное множество. Если в M любые два элемента сравнимы, то множество M называется линейно упорядоченным (англ.linearlyorderedset). Линейно упорядоченное множество также называют совершенно упорядоченным (англ.totallyorderedset), или просто, упорядоченным множеством[3]. Таким образом, в линейно упорядоченном множество для любых двух элементов a и b имеет место одно и только одно из соотношений: либо a < b, либо a = b, либо b < a.

Также всякое линейно упорядоченное подмножество частично упорядоченного множества называют цепью (англ.chain), то есть цепь в частично упорядоченном множестве  — такое его подмножество, в котором любые два элемента сравнимы.

Из приведенных выше примеров частично упорядоченных множеств только множество действительных чисел является линейно упорядоченным. Множество действительнозначных функций на отрезке [a,b] (при условии a < b), булеан (при ), натуральные числа с отношением делимости — не являются линейно упорядоченными.

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

[править] Вполне упорядоченные множества

Основная статья: Вполне упорядоченное множество

Линейно упорядоченное множество называется вполне упорядоченным (англ.well-ordered), если каждое его непустое подмножество имеет наименьший элемент[4]. Соответственно, порядок на множестве называется полным порядком (англ.well-order).

Классический пример вполне упорядоченного множества — множество натуральных чисел. Утверждение о том, что любое непустое подмножество содержит наименьший элемент, равносильно принципу математической индукции. В качестве примера линейно упорядоченного, но не вполне упорядоченного множества можно привести множество неотрицательных чисел . Действительно, его подмножество {x:x > 1} не имеет наименьшего элемента.

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

[править] Теоремы о частично упорядоченных множествах

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

[править] Примечания

  1. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 7-е изд. — М.: «ФИЗМАТЛИТ», 2004. — С. 36. — 572 с. — ISBN 5-9221-0266-4

  2. Александров П. С. Введение в теорию множеств и общую топологию. — М.: «НАУКА», 1977. — С. 78. — 368 с.

  3. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 7-е изд. — М.: «ФИЗМАТЛИТ», 2004. — С. 38. — 572 с. — ISBN 5-9221-0266-4

  4. Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 7-е изд. — М.: «ФИЗМАТЛИТ», 2004. — С. 40. — 572 с. — ISBN 5-9221-0266-4

[править] Литература

  • Александров П. С. Введение в теорию множеств и общую топологию. — М.: «НАУКА», 1977. — 368 с.

  • Колмогоров А. Н., Фомин С. В. Элементы теории функций и функционального анализа. — 7-е изд. — М.: «ФИЗМАТЛИТ», 2004. — 572 с. — ISBN 5-9221-0266-4

  • Хаусдорф Ф. Теория множеств. — 4-е изд. — М.: УРСС, 2007. — 304 с. — ISBN 978-5-382-00127-2

Топологическая сортировка

[править]

Материал из Википедии — свободной энциклопедии

Текущая версия (не проверялась)

Перейти к: навигация, поиск

Топологическая сортировка — упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин.

Содержание

[убрать]

  • 1Пример

  • 2Алгоритм

    • 2.1Пример работы алгоритма

  • 3Применение

  • 4Ссылки

  • 5Литература

[править] Пример

Для графа

Бесконтурный ориентированный граф

существует несколько согласованных последовательностей его вершин, которые могут быть получены при помощи топологической сортировки, например:

  • 7,5,11,3,8,2,9,10

  • 3,7,5,8,11,10,9,2

Видно, что в последовательности могут быть переставлены любые две стоящие рядом вершины, которые не входят в отношение частичного порядкаE.

[править] Алгоритм

Пусть дан бесконтурный ориентированный простой граф G = (V,E). Через обозначим множество вершин таких, что . То есть, A(v) — множество всех вершин, из которых есть ребро в вершину v. Пусть P — искомая последовательность вершин.

пока | P | < | V |

выбрать любую вершину v такую, что и

удалить v из всех

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

[править] Пример работы алгоритма

Пусть задан граф . В таком случае алгоритм выполнится следующим образом:

шаг

v

A(a)

A(b)

A(c)

A(d)

A(e)

P

0

-

a

a

a,b,c

a,c,d

1

a

b,c

c,d

a

2

c

b

d

a,c

3

b

d

a,c,b

4

d

a,c,b,d

5

e

a,c,b,d,e

На втором шаге вместо c может быть выбрана вершина b, поскольку порядок между b и c не задан.

[править] Применение

При помощи топологической сортировки строится корректная последовательность выполнения действий, всякое из которых может зависеть от другого: последовательность прохождения учебных курсов студентами, установки программ при помощи пакетного менеджера, сборки исходных текстов программ при помощи Makefile'ов.

[править] Ссылки

  • Пример алгоритма топологической сортировки на Python, C++, Pascal

  • Топологическая сортировка при помощи поиска в глубину — реализация на C++

[править] Литература

  • Ананий В. ЛевитинГлава 5. Метод уменьшения размера задачи: Топологическая сортировка // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс», 2006. — С. 220-224. — ISBN 5-8459-0987-2

  • Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К.Глава 22.4. Топологическая сортировка // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова. — 2-е изд. — М.: Вильямс, 2005. — С. 632-635. — ISBN 5-8459-0857-4



Скачать документ

Похожие документы:

  1. Мебиус-функция  ( x y ) частично упорядоченного множества ( P

    Документ
    ... частичноупорядоченныхмножеств. а) (2S,) (булеан)– множество всех подмножеств S, упорядоченное по включению; b) (D(n), | )– множество ... x. 2. Пусть дзета-функция (x,y) частичноупорядоченногомножества (P, ) определяется по правилу Доказать, ...
  2. Теория множеств Множества

    Лекция
    ... некоторая частичнаяупорядоченность, называются частичноупорядоченным. Примеры частичноупорядоченныхмножеств. 6) Всякое множество можно тривиальным образом рассматривать как частичноупорядоченное, если ...
  3. Роберт столл множества логика аксиоматические теории

    Документ
    ... Частичноупорядоченноемножество называют (прямым) произведением данных частичноупорядоченныхмножеств. 6. Двойственным к частичноупорядоченномумножеству называют частичноупорядоченноемножество (см. упражнение 1). Пусть — частичноупорядоченное ...
  4. Роберт столл множества логика аксиоматические теории

    Документ
    ... Частичноупорядоченноемножество называют (прямым) произведением данных частичноупорядоченныхмножеств. 6. Двойственным к частичноупорядоченномумножеству называют частичноупорядоченноемножество (см. упражнение 1). Пусть — частичноупорядоченное ...
  5. Бинарное отношение R на множестве А называется

    Документ
    ... частичным (линейным) порядком  называется частично (линейно) упорядоченным. Частичноупорядоченноемножество обозначается (А,  ). Диаграмма частичноупорядоченногомножества А (диаграмма Хассе) – ориентированный граф, множество ...

Другие похожие документы..