Реферати українською » Математика » Графи і частково впорядковані множини


Реферат Графи і частково впорядковані множини

Страница 1 из 2 | Следующая страница

>Графи і лише частково впорядковані безлічі

Обидві ці структури є приватними випадками бінарних відносин. Нехай поставлено безліч якихось об'єктів і з цих об'єктів за якимось певному принципу формуються пари. Наприклад, дано деяке безліч людей, а пари ньому вибираються за таким принципом: перший елемент пари - один діловий чоловік, а другий - з його батьків. У цьому і той ж то вона може бути присутнім на двох і більше парах, наприклад, коли той і хоча б людина має двох, трьох чи більше дітей. Наприклад, три пари такому випадку (Іван, Марія), (Дарія, Марія), (Гліб, Марія) означають, що Іван, Дарія і Гліб - діти Марії. Як математичного прикладу бінарного відносини можна навести пари, що складаються з деякого безлічі чисел, у своїй перше число у кожному парі менше другого. Це приклад бінарного відносини "менше". Інший приклад: задана деяка система множин, а бінарну ставлення до в цій системі формується з пар множин за принципом: перше безліч включено на друге безліч - це приклад бінарного відносини "включення множин".

Є багато типів бінарних стосунків із різними властивостями. Найбільш загальним з цих типів є граф. Це довільне бінарну ставлення, та його особливістю є незвична термінологія - елементи безлічі, з яких формуються пари, називаються вершинами, не бажаючи пари залежність від їх властивостей носять назви ребра чи дуги.Графи зазвичай зображуються над вигляді таблиці з цими двома колонками (кожна рядок такий таблиці представляє пару елементів - вершин), а вигляді схеми.

Розглянемо приклад. Нехай поставлено безліч вершин

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

з яких сформована деяке безліч пар

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

Безліч пар E, сформований із безлічі V вершин, є взірцем бінарного відносини.Преобразуем це бінарну ставлення до схему. І тому зобразимо листку папери усі його вершини довільним способом мислення й з'єднаємо ці вершини лініями зі стрілками те щоб кожна стрілка виходила з першого елемента пари входила на другий елемент пари (див. малюнок 1). У цьому, якщо подібне виявиться, що деяка пара вершин з'єднується стрілкою в у бік, ми замість ліній зі стрілками намалюємо лінію без стрілок (до нашого прикладу це пари (a, з) і (з, a)). З огляду на це дугами в графі є з'єднувальні лінії зі стрілками до однієї бік, а ребрами - сполуки без стрілок чи з стрілками, спрямованими у обидва боки. Можна вважати, що кожен ребро містять пару різноспрямованих дуг.

Мал.1

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

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

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

Якщо ми, використовуючи зображення довільного графа, рухатимемося від вершини на вершину відповідно до напрямом дуг (у своїй по ребру можна пересуватися у бік), то послідовність вершин, що відзначаються принаймні такого "обходу", називається шляхом у цьому графі. Наприклад для графа G малюнку 8 існують такі шляху: (a, b,d); (з, e); (a, з, a, b) тощо. Шляхи можна записувати, використовуючи стрілки, наприклад,a®b®d. У цьому можливі графи, які мають єсамопересекающиеся шляху, тобто. деякі вершини і дуги можуть у деяких шляхах повторюватися.

>Циклом в графі називається цей шлях, що його початкова й кінцева вершина збігаються.

Наприклад, в графі малюнку 8 є один цикл, обумовлений тим, що він є ребро (a, з). Тому цикл можна як шляху (a, з, 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 і з - довільні елементи частково упорядкованого безлічі X.

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

У той самий час є чимало множин зі ставленням часткового порядку, серед які є пари елементів, які пов'язані цим ставленням. До таких безлічам, зокрема, ставляться системи множин, порівнюваних з включення. Наприклад, якщо задано три безлічі

>P = {a, b, з};Q = {b,d}; R = {a, b, з,d},

то тут для них лінійний порядок встановити неможливо, оскільки безлічіP іQ непорівнянні - жоден з них включено до іншого. У той самий час, якщо безлічQ у цій сукупності замінити силою-силенноюQ1 = {b, з}, ми одержимо лінійний порядок

>Q1>P R чи {b,c}{a, b,c}{a, b, з,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.

Будь-якеу-множество можна подати як орієнтований граф, у якому дугаa®b пари елементів означаєab. Проте чи будь-який орієнтований граф є поданнямумножества. Щоб суто орієнтований граф представляв правильнеумножество, необхідне й досить щоб у ній був циклів.

У математичної літературіу-множества зазвичай зображуються якнеориентированних графів (мал.2), у своїй мається на увазі, що попередні елементи розташовані нижче наступних. Тому, тоді як цих схемах правильно замінити ребра на дуги, то ми все дуги виявляться спрямованими знизу вгору.

Рис.2

Цими малюнках показані в повному обсязі зв'язок між елементами - ті, що випливають із властивості транзитивності (наприклад, зв'язокp®s кожному з цих малюнків), у яких відсутні. Таке скорочена уявленняумножеств без транзитивних зв'язків називається діаграмоюХассе.

Надалі ми зображати частково впорядковані безлічі негаразд як це заведено в математичних працях з алгебрі (див. малюнок 2), а вигляді орієнтованих графів.Определим найменший і найбільший елементиу-множеств.

>Наименьшим елементому-множества M (коли він існує) називається елемент y такий, щоya нічого для будь-якого елементаaM.

Найбільшим елементому-множества M (коли він існує) називається елемент y такий, щоay нічого для будь-якого елементаaM

Наприклад, ву-множестве, зображеному на мал.2, b, немає найбільшого, ні найменшого елементів, найменший елемент (>p) є уумножествах, зображених на мал.2, a, з,d, а найбільший елемент є лише уумножествах, зображених малюнку 2, a, з.

Якщо ролі відносини часткового порядку ми виберемо ставлення включення, то такому випадку найменшим елементом є порожній безліч (>) (воно включено у будь-яку довільну безліч), а найбільшим є універсум (до нього включено будь-яке безліч системи).

Розглянемо два дуже важливих поняття теоріїу-множеств, що дозволяють істотно полегшити рішення деяких завдань аналізу міркувань. Це верхні і нижні конуси. Нехай 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}.

Далі ми розглянемо дві теореми, пов'язані з конусами. З допомогою першої теореми можна визначити верхні і нижні конуси задля окремих елементів, а окремих їх сукупностей. За змістом верхні конуси для деякого безлічі M елементів повинні містити такі елементи, що водночас реальні з кожного елемента безлічі M. Аналогічно, якщо обчислюється нижній конус для безлічі M, він мусить мати такі елементи, кожен із яких передують кожному елементу з багатьох M. Тоді верхній і нижній конуси при цьому безлічі обчислюються відповідно до наступній теоремою.

Теорему. нехай у довільномуу-множестве вибрано деяке підмножина M = {>q1,q2,...qn} його елементів. Тоді

(і) MD =...;

(>ii) M>=>....

Доказ. Нехайmі - довільний елемента безлічі MD. Щоб кожному заq>k (>q>k> M) дотримувалося умоваq>kmі, необхідне й досить, щоб елементmі утримувався у верхньому конусі кожного з елементів безлічі M. І це означає, що елементmі міститься у перетині... верхніх конусів всіх таких елементів. Аналогічно, якщоmі - довільний елемента безлічі M>, то тут для кожногоq>k (>q>k> M) дотримується умоваmіq>k, що СРСР розвалився, що елементmі міститься у нижньому конусі кожного з елементів безлічі M. Отже, все елементи безлічі M> має перебувати в перетині... нижніх конусів. Кінець докази.

Для кращого розуміння співвідношень, що з конусами, розглянемо граф, який зображає діаграмуХассе деякогоу-множества (малюнок 3).

>Рис.3

У цій малюнку можна, використовуючи властивість досяжності, легко обчислити верхні і нижні конуси будь-яких елементів. Наприклад,

RD = {R, G, F,Q}

(елемент R міститься у верхньому конусі з визначення, інші ж елементи запроваджені як досяжні з R);

MD = {M, N, G, F,Q}; DD = {D}; ЗD = {З, D}; D> = {D, З, A}

(елемент D міститься у нижньому конусі з визначення, а елементи З і A уведено підрозділи до нижній конус, оскільки їх можна досягти елемент D);

R> = {R, A}; M> = {M}; З> = {З, A}, G> = {G, M, R, A}.

Знаючи верхні чи нижні конуси елементів, можна за теоремі легко обчислити відповідно верхні і нижні конуси для множин, які перебувають із цих елементів. Наприклад,

{R, M}D = RD > MD = {R, G, F,Q}{M, N, G, F,Q}={G, F,Q};

{R, З}D = RD > ЗD = {R, G, F,Q}{C, D}=

(подивившись на малюнок 10, можна переконатися, що у графі немає жодної вершини, яка досяжним що з R, що з З);

{R, M}> = R> > M> = {R,A}{M}=;

{R, З}> = R>

Страница 1 из 2 | Следующая страница

Схожі реферати:

Навігація