Применение древовидных графов

1. Древовидная файловая система, или дерево директорий.

2. Дерево поиска, при котором все потомки с левой стороны всегда меньше родителя, а в правом не меньше.

3. Дерево для вычисления математических формул – например, префиксной и постфиксной формы записи.

Задачи по теме «Деревья»

1. Какое максимальное количество листьев может быть у дерева из n вершин? А минимальное?

2. Могут ли в дереве две вершины соединяться двумя различными путями?

3. Существует ли дерево, у которого одна вершина является и листом, и корнем?

4. Докажите, что в ориентированном дереве у каждой вершины не более одного родителя.

Связные графы

Определение

Если из каждой вершины можно попасть в каждую, то граф отношения называют связным.

Подмножество графа, в котором из каждой вершины можно попасть в каждую, называют компонентой связности.

Из определения можно увидеть, что если граф состоит из одной компоненты связности, он называется связным. Если из более чем одной компоненты связности, он называется несвязным.

Двудольные графы

Определение

Наглядное представление: двудольный граф — это граф, множество вершин которого можно разбить на две части таким образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.

Определение: неориентированный граф G = (W, E) называется двудольным, если множество его вершин можно разбить на две части , | U | > 0, | V | > 0, так, что ни одна вершина в U не соединена с вершинами в U и ни одна вершина в V не соединена с вершинами в V.

Пример: решётка, вершины которой раскрашены в 2 цвета в шахматном порядке.

Двудольный граф называется полным, если для каждой пары вершин существует ребро . Для | U | = i, | V | = j такой граф называется K_{i , j}

Упражнение 1. Приведите пример двудольного графа с 6 вершинами.

Упражнение 2. Докажите признаки двудольных графов:

1) Граф является двудольным тогда и только тогда, когда он не содержит цикла нечётной длины.

2) Граф является двудольным тогда и только тогда, когда он 2-раскрашиваем (то есть его хроматическое число равняется двум). Хроматическое число – минимальное количество цветов, требуемое для раскраски вершин графа, при которой любые вершины, соединенные ребром, раскрашены в разные цвета.

Двудольные графы применяются, когда изучаемые объекты разделяются на две группы так, что внутри групп интересующие нас взаимодействия отсутствуют. Например, в экономике — производители и потребители.

На рисунках вершины двудольного графа часто располагают на параллельных прямых.

С двудольными графами связана задача о назначениях. Пусть — множество претендентов на рабочие места, — множество рабочих мест. Необходимо каждого из претендентов обеспечить работой в соответствии с его профессиональной подготовкой.

Булевы функции

Определение. Функцию от одной или нескольких переменных, аргументы и значение которой могут принимать только значения 0 или 1, называют булевой функцией (в честь английского математика Джорджа Буля (1815 - 1864), одного из основателей математической логики).

Примеры.

Конъюнкция: = 1 тогда и только тогда, когда x и y оба равны 1.

Дизъюнкция: = 1 тогда и только тогда, когда x и y оба равны 1.

Для того, чтобы каждый раз не описывать значения словами, булеву функцию обычно задают таблицей истинности, то есть таблицей, в которой указаны значения для всех наборов переменных.

При этом значения наборов переменных располагают в лексикографическом порядке. Сначала набор из одних нулей, затем правый ноль заменяют 1, и так далее, до набора из одних единиц. Например:

x	y

x	y

Эквивалентность: (Значение выражения равно 1, если значения x и y совпадают)

x	y

Симметрическая разность: (Значение выражения равно 1, если значения x и y не совпадают)

x	y

Импликация: (Мнемоническое правило: из нуля следует что угодно – и ноль, и единица)

x	y

Отрицание:

x