Графи і частково впорядковані множини
Обидві ці структури є окремими випадками бінарних відносин. Нехай задано безліч якихось об'єктів і з цих об'єктів за якимось певним принципом формуються пари. Наприклад, дано деякий безліч людей, а пари в ньому вибираються за таким принципом: перший елемент пари - якась людина, а другий - один з її батьків. При цьому один і той ж людина може бути присутнім в двох і більше парах, наприклад, коли один і той ж людина має двох, трьох чи більше дітей. Наприклад, три пари в цьому відношенні (Іван, Марія), (Дарина, Марія), (Гліб, Марія) означають, що Іван, Дарина і Гліб - діти Марії. Як математичного прикладу бінарного відносини можна привести пари, складені з деякого безлічі чисел, при цьому перше число в кожній парі менше другого. Це приклад бінарного відношення "менше". Інший приклад: задана деяка система множин, а бінарне відношення в цій системі формується з пар множин за принципом: перше безліч включено в друге безліч - це приклад бінарного відношення "включення множин".
Існує багато типів бінарних відносин з різними властивостями. Найбільш загальним з цих типів є граф. Це довільне бінарне відношення, але його особливістю є незвична термінологія - елементи множини, з якого формуються пари, називаються вершинами, а самі пари в залежності від їх властивостей носять назви ребра або дуги. Графи зазвичай зображаються не в вигляді таблиці з двома колонками (кожний рядок такої таблиці представляє пару елементів - вершин), а у вигляді схеми.
Розглянемо приклад. Нехай задано безліч вершин
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) і т.д. Шляхи можна записувати, використовуючи стрілки, наприклад, a ® b ® d. При цьому можливі графи, у яких є самопересекающиеся шляху, тобто деякі вершини і дуги можуть у деяких шляхах повторюватися.
Циклом в графі називається такий шлях, коли його початкова та кінцева вершина збігаються.
Наприклад, у графі на малюнку 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 бінарне відношення з наступними властивостями:
рефлексивності: a £ a для будь-якого a Î X;
транзитивності: якщо a £ b і b £ c, то a £ c;
антисиметричність: з a £ b і b £ a слід a = b,
де a, b і c - довільні елементи частково упорядкованої множини X.
Серед всіх відносин часткового порядку найбільш простим у структурному відношенні є лінійний порядок, коли для будь-якої пари різних елементів (a, b) множини визначити або a £ b, або b £ a. Прикладами лінійного порядку є безлічі чисел, впорядкованих за величиною, і безлічі слів, розташованих в лексикографічному порядку. Їх можна по заданому порядку сформувати у вигляді однієї безперервної послідовності. Наприклад, 2 <5 <12 <19. При лінійному порядку всі елементи частково упорядкованої множини можна вибудувати в один ланцюжок по заданому відношенню.
У той же час існує чимало множин з відношенням часткового порядку, серед яких є пари елементів, не пов'язані цим ставленням. До таких множинам, зокрема, відносяться системи множин, порівнюваних по включенню. Наприклад, якщо задано три безлічі
P = {a, b, c}; Q = {b, d}; R = {a, b, c, d},
то для них лінійний порядок встановити неможливо, так як множини P і Q непорівнянні - жодне з них не включено в інше. У той же час, якщо безліч Q в цій сукупності замінити на безліч Q 1 = {b, c}, то ми отримаємо лінійний порядок
Q 1 Ì P Ì R або {b, c} Ì {a, b, c} Ì {a, b, c, d}.
Ще одним широко відомим ставленням часткового порядку є порядок по подільності. Припустимо, задано деяке безліч позитивних цілих чисел (наприклад, D = {1, 2, 3.4, 6, 12}. Тоді будемо вважати, що для двох чисел x і y вірно x £ y, якщо і тільки якщо число y ділиться без залишку на число x.
Для заданої множини D порядок по подільності вірний для пар (1,2); (2,4); (3,6) і т.д., Але для деяких пар (наприклад, (4,6)) такий порядок не дотримується , так як число 6 не ділиться без залишку на число 4. Неважко переконатися, що відношення порядку по подільності повністю відповідає властивостям частково впорядкованих множин (рефлексивності, транзитивності і антисиметричність).
У математиці відомо чимало структур, що відповідають часткового порядку. Розглянемо деякі загальні властивості відносин часткового порядку. Далі з метою скорочення будемо використовувати замість терміна "частково упорядкований безліч" термін у-безліч - своєрідна калька з еквівалентного англійського терміна poset.
Будь у-множину можна представити як орієнтований граф, в якому дуга a ® b між парою елементів означає a £ b. Однак не будь-який орієнтований граф є представленням у безлічі. Щоб суто орієнтований граф представляв правильне у безліч, необхідно і достатньо щоб у ньому не було циклів.
В математичній літературі у-безлічі зазвичай зображаються у вигляді неорієнтованих графів (рис.2), при цьому мається на увазі, що попередні елементи розташовані нижче наступних. Тому, якщо в цих схемах правильно замінити ребра на дуги, то все дуги виявляться спрямованими знизу вгору.
Рис.2
На цих малюнках показані не всі зв'язки між елементами - ті, які слідують з властивості транзитивності (наприклад, зв'язок p ® s на кожному з цих малюнків), в них відсутні. Таке скорочене уявлення у множин без транзитивних зв'язків називається діаграмою Хассе.
Надалі ми будемо зображати частково впорядковані множини не так як це прийнято в математичних роботах з алгебри (див. малюнок 2), а у вигляді орієнтованих графів. Визначимо найменший і найбільший елементи у-множин.
Найменшим елементом у-множини M (якщо він існує) називається елемент y такий, що y £ a для будь-якого елемента a Î M.
Найбільшим елементом у-множини M (якщо він існує) називається елемент y такий, що a £ y для будь-якого елемента a Î M
Наприклад, в у-множині, зображеному на рис.2, b, немає ні найбільшого, ні найменшого елементів, найменший елемент (p) є в у множинах, зображених на рис.2, a, c, d, а найбільший елемент є тільки в у множинах, зображених на малюнку 2, a, c.
Якщо як відносини часткового порядку ми виберемо ставлення включення, то в цьому відношенні найменшим елементом є порожня множина (Æ) (воно включено в будь безліч), а найбільшим є універсум (до нього включено будь безліч системи).
Розглянемо два дуже важливих поняття теорії у-множин, які дозволяють істотно полегшити вирішення деяких завдань аналізу міркувань. Це верхні і нижні конуси. Нехай A - довільна підмножина у безлічі M (тобто A Í M). Визначимо для безлічі A верхній і нижній конуси.
Нижнім конусом безлічі A називається безліч всіх таких елементів x, що належать безлічі M, кожен з яких буде менше або дорівнює (£) щодо будь-якого елемента a, що належить безлічі A.
Верхнім конусом безлічі A називається безліч всіх таких елементів x, що належать безлічі M, для кожного з яких будь-який елемент з множини A буде менше або дорівнює (£) йому.
Нижній і верхній конуси можна визначати не тільки для підмножин, а й для елементів у безлічі M. Якщо у-безліч зображено у вигляді орієнтованого графа, то верхній і нижній конус для будь-якого елементу X можна "вирахувати", використовуючи властивість досяжності:
верхній конус елемента X - це безліч елементів, у це безліч входить сам елемент X і всі елементи, досяжні з X;
нижній конус елемента X - це безліч елементів, у це безліч входить сам елемент X і всі елементи, з яких X досяжно.
Наприклад, на безлічі чисел M = {2, 4, 5, 7}, що згруповані у величині, нижнім конусом числа 4 є безліч {2, 4}, а верхнім - {4, 5, 7}. Якщо розглянути у безліч, показане на малюнку 9, b, то
= {P, q, r} і
= {R, s, t, u}.
Далі ми розглянемо дві теореми, пов'язані з конусами. C допомогою першої теореми можна обчислити верхні і нижні конуси не для окремих елементів, а для деяких їх сукупностей. За змістом верхні конуси для деякого безлічі M елементів повинні містити такі елементи, які одночасно досяжні з кожного елемента множини M. Аналогічно, якщо обчислюється нижній конус для безлічі M, то він повинен містити такі елементи, кожен з яких передують будь-якого елементу з множини M. Тоді верхній і нижній конуси для цієї множини обчислюються у відповідності з наступною теоремою.
Теорема. Нехай у довільному у-безлічі вибрано деяку підмножину M = {Q 1, q 2, ... q n} його елементів. Тоді
(I) M D = Ç
Ç ... Ç
;
(Ii) M Ñ = Ç
Ç ... Ç
.
Доказ. Нехай m i - довільний елемента множини M D. Щоб для кожного q k (q k Î M) дотримувалася умова q k £ m i, необхідно і достатньо, щоб елемент m i містився у верхньому конусі кожного з елементів множини M. А це означає, що елемент m i міститься в перетині Ç
Ç ... Ç
верхніх конусів всіх цих елементів. Аналогічно, якщо m i - довільний елемента множини M Ñ, то для кожного q k (q k Î M) дотримується умова m i £ q k, а це означає, що елемент m i міститься в нижньому конусі кожного з елементів множини M. Отже, всі елементи множини M Ñ повинні знаходитися в перетині
Ç
Ç ... Ç
нижніх конусів. Кінець докази.
Для кращого розуміння співвідношень, пов'язаних з конусами, розглянемо граф, який зображає діаграму Хассе деякого у-безлічі (малюнок 3).
Рис.3
За цим малюнком можна, використовуючи властивість досяжності, легко обчислити верхні і нижні конуси будь-яких елементів. Наприклад,
R D = {R, G, F, Q}
(Елемент R міститься у верхньому конусі за визначенням, а інші елементи введені як досяжні з R);
M D = {M, N, G, F, Q}; D D = {D}; C D = {C, D}; D Ñ = {D, C, A}
(Елемент D міститься в нижньому конусі за визначенням, а елементи C і A введені в нижній конус, оскільки з них досяжний елемент D);
R Ñ = {R, A}; M Ñ = {M}; C Ñ = {C, A}, G Ñ = {G, M, R, A}.
Знаючи верхні або нижні конуси елементів, можна по теоремі легко обчислити відповідно верхні і нижні конуси для множин, що складаються з цих елементів. Наприклад,
{R, M} D = R D Ç M D = {R, G, F, Q} Ç {M, N, G, F, Q} = {G, F, Q};
{R, C} D = R D Ç C D = {R, G, F, Q} Ç {C, D} = Æ
(Подивившись на малюнок 10, можна переконатися, що в графі немає жодної вершини, яка досяжна як з R, так і з C);
{R, M} Ñ = R Ñ Ç M Ñ = {R, A} Ç {M} = Æ;
{R, C} Ñ = R Ñ Ç C Ñ = {R, A} Ç {C, A} = {A}.
Розглянемо ще одне співвідношення, пов'язане з конусами.
Теорема 2. Нехай r і q - різні елементи у-множини, при цьому r £ q. Тоді для верхніх і нижніх конусів цих елементів дотримуються співвідношення Í
і
Í
.
Доказ. Дані співвідношення випливають з визначень верхніх і нижніх конусів. Якщо r £ q, то це означає, що q міститься в і, отже, всі елементи з
також міститься в
. У той же час в нижніх конусах навпаки: якщо r £ q, то це означає, що r міститься в
і, отже, всі елементи з
також міститься в
. Кінець докази.
Наприклад, для у-множини, зображеного на малюнку 3, елементи A і G - порівняти, тобто A £ G (елемент A передує елементу G). Побудуємо верхні і нижні конуси цих елементів:
A D = {A, C, D, R, G, F, Q}; G D = {G, F, Q}; A Ñ = {A}; G Ñ = {G, R, A, M}.
Порівнюючи ці конуси з включення, ми побачимо, що відповідно до теореми 2 дотримуються наступні співвідношення: G D Í A D і A Ñ Í G Ñ. Якщо ж вибрати для аналізу пару елементів, для яких відношення £ не має місця (наприклад, елементи Q і N на малюнку 3), то ми побачимо, що для них, співвідношення, сформульовані в теоремі 2, не вірні.
Для аналізу E-структур дуже важливими є ще два поняття - мінімальні і максимальні елементи. Суть в тому, що вони істотно відрізняються від найменшого та найбільшого елементів. Почнемо з мінімальних елементів. Як ми вже знаємо, якщо в структурі існує найменший елемент, то він менше будь-якого іншого елемента цього у безлічі. Але існують елементи (в алгебрі їх іноді називають атомами), які більше найменшого, але при цьому мають одним дивовижну властивість. Припустимо, що елемент A - атом, а X i довільний елемент цього у-множини, крім найменшого. Тоді при порівнянні атома A з будь-яким елементом X i можливі тільки два варіанти:
1) A £ X i або 2) елементи A і X i непорівнянні. Атоми на відміну від найменших елементів називаються мінімальними елементами.
Щоб краще зрозуміти це розглянемо малюнок 10. Видно, що в цьому у-безлічі найменшого елемента не існує, оскільки жоден елемент у ньому не володіє тим властивістю що він передує будь-якого елементу. Наприклад, елементу A не передує жоден елемент, але при цьому він сам не передує таким елементам як M та N (тобто пари (A, N) і (A, M) не можна порівняти, оскільки невідомо, який з елементів в кожній з цих пар є попередником іншого). Тому елемент A можна вважати мінімальним (але не найменшим!) Елементом. Неважко бачити, що в цій же структурі є ще один мінімальний елемент - M, який має ті ж властивості, що й елемент A. Т. е. в цій структурі існують два мінімальних елемента (хоча найменшого в ній немає). Якщо в структурі є найменший елемент, то в цьому випадку мінімальними елементами є інші елементи, які більше найменшого, але при цьому безпосередньо примикають до нього.
Максимальні елементи в у-множинах визначаються аналогічно. Максимальні елементи (в алгебрі вони іноді називаються коатомамі) - це елементи, що володіють такими властивостями:
1) якщо найбільший елемент існує, то максимальні елементи безпосередньо передують найбільшому елементу;
2) будь-який елемент у безлічі (крім найбільшого) або передує максимальному елементу, або не порівняти з ним.
Подивившись на у-безліч на малюнку 10, можна з урахуванням цих властивостей легко визначити його максимальні елементи: це D, F і Q.