Дерева, їх характеризації

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

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

Дерево не має кратних ребер і петель.

Будь-яке дерево з n вершинами містить n - 1 ребро. Більш того, кінцевий зв'язний граф є деревом тоді і тільки тоді, коли B - P = 1, де B - число вершин, P - число ребер графа.

Граф є деревом тоді і тільки тоді, коли будь-які дві різні його вершини можна з'єднати єдиним елементарним шляхом.

Будь-яке дерево однозначно визначається відстанями (довжиною найменшою ланцюга) між його кінцевими (ступеня 1) вершинами.

Будь-яке дерево є дводольним графом. Будь-яке дерево, що містить рахункове кількість вершин, є планарним графом.

Для будь-яких трьох вершин дерева, шляхи між парами цих вершин мають рівно одну загальну вершину.

Кістяк (остов) - це підграф даного графа, що містить всі його вершини і є деревом. Ребра графа, що не входять в остов, називаються хордами графа щодо остова.

Булева алгебра, булева решітка - частково впорядкована множина спеціального виду; дистрибутивная решітка, що має найбільший елемент 1 - одиницю булевої алгебри, найменший елемент 0 - нуль булевої алгебри, і містить одна відповідність кожного свого елемента x - елемент (НЕ x)

Повні графи. Доповнення графа. Повні підграфи. Теорема Рамсея.

Повний граф - простий граф, в якому кожна пара різних вершин суміжна. Повний граф з n вершинами має n (n - 1) / 2

В теорії графів доповненням або зворотним до графу G називається такий граф H, який має той же безліч вершин, що і G, але в якому дві незбіжні вершини суміжні тоді і тільки тоді, коли вони не суміжні в G. Щоб знайти зворотний граф, доповніть даний граф до повного і видаліть всі ребра, які вже були до цього.

Кліка (повний підграф) - підмножина вершин, кожні дві з яких з'єднані ребром графа.

Нехай дано числа a1, a2. an. Тоді існує таке число R, що, як би ми не пофарбували ребра повного графа на R вершинах в n кольорів, знайдеться або повний підграф 1-го кольору на a1 вершинах, або повний підграф 2-го кольору на a2 вершинах, ... або повний підграф n-го кольору на an вершинах.

Булевим кільцем називають кільце, в якому всі елементи ідемпотентна (коммутативность, наявність одиниці або подільників нуля не потрібно). Цікавою особливістю булевих кілець є те, що

зокрема, при

тобто булево кільце завжди коммутативно.

Дводольні графи, необхідна і достатня умова існування.

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

Граф є дводольним тоді і тільки тоді, коли він не містить циклу непарної довжини. Тому двочастковий граф не може містити кліку розміром більше 2.

Граф є дводольним тоді і тільки тоді, коли він 2-розфарбовуємо (тобто його хроматичної число дорівнює двом)

Граф розбивається на пари різнокольорових вершин тоді і тільки тоді, коли будь-які k елементів однієї з часткою пов'язані принаймні з k елементами інший (Теорема Холла).

Двочастковий граф, у якого в кожній частині більше 2 вершин, є непланарним.

Грати. Групи. Унарні алгебри.