Ел-нт х наз-ся мін-м min в множині , якщо не існує (тобто від нього не існує менших), аналогічно у- макс-м max, якщо не існує .

Якщо у множині існує найменший елемент, то він єдиний і одночасно є min, але не навпаки, але не навпаки. Аналогічно, найбільший елемент є макс-й. Найменший і найбільший ел-ти мн-ни А познач-ся min A та max A.

Нехай А-підмножина ЧВМ (частково впорядкована множина).

Найбільша серед нижніх граней множини А (якщо вона існує) називається точною нижньою гранню і позначається inf A(інфімум). Аналогічно – найменше з верхніх граней називається точною гранню і позначається sup A(супремум)- точна верхня грань.

Між властивостями верхніх і нижніх граней є повна подібність. Це пояснюється тим, що з кожного часткового порядку можна утворити протилежний порядок , - поклавши, що , якщо . При цьому нижні грані стають верхніми, min-max і т.д.

ЧВМ, в якій для кожних 2-ох елементів a i b існує іх точна нижня грань inf {a,b}=a^b – найбільша серед елементів, що передує а і b називається нижньою напівграткою . Аналогічно верхня напівгратка - це ЧВМ, така, що а і b існує точна верхня грань: sup{a,b}=ab( -cупремум).

Кожна лінійно впорядкована множина є нижньою і верхньою напівграткою : В ЛВМ -.

В нижній напівгратці взяття точної нижньої грані є бінарною операцією з властивостями:

Т: Для кожної операції “ * ” : з властивостями

1) x*y=y*x; 2) x*(y*z)=(x*y)*z; 3) х*х=х.

Існує єдиний частковий порядокна х,для якого ху–це точно нижня грань- .

4 Основні поняття та твердження про графи та орграфи.

Графом наз-мо пару G=(V,E) з двох множин, для якої елементи V наз-ть вершинами графа, елементи Е- його ребрами і для кожного ребра еЄЕ вказано дві вершини v1,v2Є V, (можливо v1=v2), які називають кінцями ребра е. для довільного графа G множини його вершин і ребер інколи позначаємо V(G) і Е(G). Надалі розглядаємо тільки скінченні графи (зі скінченною кіл-тю вершин і ребер). Графи зручно зображати на площині:вершини–точками, а ребра – дугами між ними. Звичайно до графа висувають вимогу, що між кожними двома вершинами повинно бути не більш ніж одне ребро, і один кінець ребра не може збігатись з іншим (немає петель). Якщо у графі дозволено петлі, то його називають псевдо графом. Граф у якому між двома верш-ми можливі кілька ребер наз. мультографом. У звичайному графі кінці кожного ребра є рівноправними. Якщо ж вважаємо, що ребро спрямоване від однієї вершини до іншої, тобто перша з них є початком, а друга кінцем, то таке ребро називають орієнтованим і позначають стрілкою. Граф ребра якого орієнтовані наз. орієнтованим графом або орграфом.

Над графами виконують такі дії:

А) з довільного графа G можна вилучити будь-яку вершину v разом з всіма ребрами кінцем яких він є. Отриманий граф познач. G\{v}.

Б)В довільному графі можна ототожнити дві вершини, замінивши їх одною вершиною. При цьому для всіх ребер, кінцем для яких була v1 або v2 кінцем вважатиметься u. При цьому можуть з’явитися петлі і кратні ребра (ребра, які з’єднують ті ж вершини).

В) якщо для дов-го ребра е графа G ототожнити його кінці v1 і v2 то цю дію наз. стягуванням даного ребра. При цьому можливо доведеться вилучити отриману петлю,якщо граф не може бути псевдо графом.

Г) довільні графи G1 і G2 можна об’єднати отримавши новий граф G з V(G) = V(G1)UV(G2) Е(G) = Е(G1)UЕ(G2). Якщо Е(G1)?Е(G2) =ш, то це об’єднання наз. диз’юктивним.

Д) для довільних графів G1 і G2 розглядаємо їх добуток G1хG2. Вважаємо, що V(G1хG2) = =V(G1)хV(G2), тобто вершини нового графа – це пари (v1,v2), де v1ЄV(G1), а v2Є V(G2). Стрілки маємо 2-ох сортів: вигляду (е1, v2) та (v1,е2), де е1 – ребро G1, v2 – вершина G2, v1 – вершина G1, а е2 – ребро G2. якщо ребро е1 сполучає вершини z i t, то (е1, v2) сполучає (z,V2) з(t ,V2). Аналогічно з(t , v2). Якщо е2 сполучає а і b, то (v1,а) і (v1,b).

Графи в памяті комп’ютера зображаються такими способами: а) списком ребер. Всі вершини графа пронумеровані і кожне ребро зображається парою (m,n) – де m,n – номери кінців ребра.при цьому для орієнтованого графа порядок номерів в парі суттєвий, а для неорієнтованого ні.; б)якщо вершина v є кінцем ребра е, то кажемо, що v та е інцидентні. Відповідно граф G зображається матрицею інцидентності.

Якщо граф містить n вершин і m ребер, то його матриця інцидентості має n рідків та m стовпців.

Елемент іkl=1, якщо вершина vk є кіцем ребра еL ( vk і еL інцидентні) і іkl=0 в іншому випадку. Для орграфа вважаємо: іkl=-1, якщо vk –початок еL; і=1, якщо vk –кінець еL; іkl=0 в інших випадках.

Матрицю інцидентності графа G позначають І(G ).

Вершини v1 і v2 називають суміжними, якщо існує ребро з v1в v2. Відповідно для кожного графа G можна скласти матрицю суміжності S(G), у якій S kl=1, якщо існіє ребро з vk у vl.

Якщо граф містить n вершин, то матриця S(G) має розмір nх n, причому для неорієнтованого графа S(G) симетрична, оскільки кожне існіє ребро з vk у vl є одночасно ебром з vl у vk. Skl(G)=1 =>