Діаграма Хассе - вид діаграм. використовуваний для подання кінцевого частково впорядкованої множини у вигляді малюнка його транзитивного скорочення. Конкретно, для частково впорядкованої множини (S. ≤) діаграма представляє кожен елемент S як вершини на площині і відрізки або криві, що йдуть вгору від елемента x до елементу y. якщо x ≤ y і не існує елемента z. для якого x ≤ z ≤ y. Ці криві можуть перетинатися, але не повинні проходити через вершини, якщо тільки вони не є кінцями лінії. Така діаграма з позначеними вершинами однозначно визначають частковий порядок.
Вперше систематично такого роду візуалізація описана Біркгофом в 1948 році [1]. їм же дано назву в честь використав подібні діаграми Хельмута Хассе. проте такого роду малюнки зустрічаються і в більш ранніх працях, наприклад, в підручнику французького математика Анрі Фохта (нім. Henri Vogt) 1895 року видання [2].
Хоча діаграми Хассе є простим і інтуїтивно зрозумілим засобом для роботи з кінцевим частково впорядкованим безліччю. вельми складно намалювати «хорошу», зручну для візуального сприйняття діаграму для досить нетривіального безлічі через великої кількості можливих варіантів відображення. Проста техніка, що припускає почати з мінімальних елементів і малювати вищележачі елементи послідовно часто дає погані результати - симетрії і внутрішні структури легко втратити.
Наприклад, булеан безлічі з чотирьох елементів, упорядкованого операцією включення ⊆ може бути представлений будь-який з чотирьох наведених нижче діаграм (кожна підмножина забезпечено міткою з бінарної кодуванням, яка б показала, міститься відповідний елемент в підмножині - 1, чи ні - 0):
Перша діаграма демонструє структуру рівнів. Другий діаграма має ту ж структуру рівнів, але на ній деякі ребра подовжені, щоб підкреслити, що чотиривимірний куб є об'єднанням двох тривимірних. Третя діаграма показує деяку внутрішню симетрію. У четвертій діаграмі вершини впорядковані подібно матриці 4 × 4.
Діаграма Хассе подгрупповой решітки діедріческой групи D i h 4 _> не має пересічних ребер.
Деякі властивості часткових порядків щодо планарності їх діаграми Хассе (тобто можливості намалювати її без перетину ребер):
- Якщо частковий порядок є гратами. то його можна намалювати без перетинів тоді і тільки тоді, коли розмірність порядку не менше двох [3] [4].
- Якщо частковий порядок має щонайменше один мінімальний або максимальний елемент, то можна за лінійний час перевірити, чи існує діаграма без перетинів [5].
- Визначити, чи можна частковий порядок уявити планарной діаграмою Хассе, в загальному випадку NP-повна задача [6].
- Якщо задані y -коордінати елементів часткового порядку, то за лінійний час може бути знайдена його діаграма Хассе, яка зберігає задані координати, якщо тільки така діаграма існує [7]. Зокрема, якщо приватний порядок має рівні, можна за лінійний час визначити, чи є діаграма Хассе без перетинів, у якій висота кожної вершини пропорційна її рангу.