WikiDer > Диаграмма Хассе

Hasse diagram
Не путать с Диаграмма Гесса.
В набор мощности двухэлементного набора, упорядоченного включение

В теория порядка, а Диаграмма Хассе (/ˈчасæsə/; Немецкий: [ˈHasə]) является разновидностью математическая диаграмма используется для представления конечного частично заказанный набор, в виде Рисование своего переходная редукция. Конкретно для частично упорядоченного множества (S, ≤) один представляет каждый элемент S как вершина в плоскости и рисует отрезок или кривая, которая идет вверх из Икс к у в любое время у охватывает Икс (то есть всякий раз, когда Икс < у и нет z такой, что Икс < z < уЭти кривые могут пересекать друг друга, но не должны касаться каких-либо вершин, кроме своих конечных точек. Такая диаграмма с помеченными вершинами однозначно определяет ее частичный порядок.

Диаграммы названы в честь Хельмут Хассе (1898–1979); в соответствии с Гаррет Биркофф (1948), они названы так из-за того, что Хассе эффективно использовал их. Однако Хассе не был первым, кто использовал эти диаграммы. Один пример, предшествующий Хассе, можно найти у Анри Густава Фогта (1895). Хотя диаграммы Хассе изначально были разработаны как метод создания чертежей частично упорядоченных наборов вручную, в последнее время они были созданы автоматически с использованием рисунок графика техники.[1]

Фраза «диаграмма Хассе» может также относиться к транзитивной редукции как к абстрактной ориентированный ациклический граф, независимо от любого рисунка этого графика, но это использование здесь избегается.[2][3][4]

"Хорошая" диаграмма Хассе

Хотя диаграммы Хассе являются простыми и интуитивно понятными инструментами для работы с конечными позы, «хорошие» диаграммы рисовать оказывается довольно сложно. Причина в том, что в целом будет много возможных способов нарисовать диаграмму Хассе для данного позета. Простая техника - начать с минимальные элементы порядка, а затем постепенное рисование больших элементов часто дает довольно плохие результаты: легко теряются симметрии и внутренняя структура порядка.

Следующий пример демонстрирует проблему. Рассмотрим набор мощности 4-элементного множества, упорядоченного включением . Ниже представлены четыре различных диаграммы Хассе для этого частичного порядка. Каждое подмножество имеет узел, помеченный двоичной кодировкой, которая показывает, входит ли определенный элемент в подмножество (1) или нет (0):

Hypercubeorder binary.svg   Гиперкубики binary.svg   Hypercubestar binary.svg   Hypercubematrix binary.svg

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

Восходящая планарность

Основная статья: Плоский рисунок вверх
Эта диаграмма Хассе решетка подгрупп из группа диэдра Dih4 не имеет пересекающихся краев.

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

  • Если отрисовываемый частичный порядок решетка, то его можно нарисовать без пересечений тогда и только тогда, когда в нем размер заказа максимум два.[5] В этом случае непересекающийся чертеж может быть найден путем получения декартовых координат для элементов из их положений в двух линейных порядках, реализующих размер порядка, а затем поворота чертежа против часовой стрелки на угол 45 градусов.
  • Если частичный заказ имеет не более одного минимальный элемент, или не более одного максимальный элемент, то его можно протестировать в линейное время есть ли у него непересекающаяся диаграмма Хассе.[6]
  • это НП-полный чтобы определить, можно ли нарисовать частичный порядок с несколькими источниками и стоками как диаграмму Хассе без перекрестков.[7] Однако найти диаграмму Хассе без перекрестков управляемый с фиксированными параметрами при параметризации количеством точки сочленения и трехкомпонентные компоненты транзитивной редукции частичного порядка.[8]
  • Если у-координаты элементов частичного порядка задаются, тогда диаграмма Хассе без перекрестков, учитывающая эти назначения координат, может быть найдена за линейное время, если такая диаграмма существует.[9] В частности, если входной poset является градуированный посет, за линейное время можно определить, существует ли диаграмма Хассе без перекрестков, в которой высота каждой вершины пропорциональна ее рангу.

Нотация UML

Выражение примера с помощью стандартных соединителей наследования UML. Каждый набор представляет собой отдельный объект (стандартные блоки UML имеют прямоугольную форму).

Стандартная диаграмма цепочки включений - это UML класс, связывая множества отношением наследования. На рисунке показан вложенная коллекция наборов, C:

B = {♠, ♥, ♦, ♣};     B1 = {♠, ♥};   B2 = {♦, ♣};   B3 = {♣};
C = {B, B1, B2, B3}.

Примечания

  1. ^ Например, см. Ди Баттиста и Тамассия (1988) и Фриз (2004).
  2. ^ Христофидес, Никос (1975), Теория графов: алгоритмический подход, Academic Press, стр. 170–174..
  3. ^ Thulasiraman, K .; Свами, М. Н. С. (1992), "5.7 Ациклические ориентированные графы", Графики: теория и алгоритмы, Джон Вили и сын, стр. 118, ISBN 978-0-471-51356-8.
  4. ^ Банг-Дженсен, Йорген (2008), «2.1 Ациклические диграфы», Орграфы: теория, алгоритмы и приложения, Springer Monographs in Mathematics (2-е изд.), Springer-Verlag, стр. 32–34, ISBN 978-1-84800-997-4.
  5. ^ Гарг и Тамассия (1995a), Теорема 9, с. 118; Бейкер, Фишберн и Робертс (1971), теорема 4.1, стр.18.
  6. ^ Гарг и Тамассия (1995a), Теорема 15, с. 125; Бертолацци и др. (1993).
  7. ^ Гарг и Тамассия (1995a), Следствие 1, с. 132; Гарг и Тамассия (1995b).
  8. ^ Чан (2004).
  9. ^ Юнгер и Лейперт (1999).

Рекомендации

внешняя ссылка