- •Универсальное множество: Универсальное множество (универсум) — множество, содержащее все мыслимые объекты. Упорядоченное множество — множество, на котором задано отношение порядка.
- •Множество. Способы задания множеств (перечислением или списком, порождающей процедурой, описанием характеристического свойства). Привести примеры.
- •Объединение более чем двух множеств. Пусть дано семейство множеств Тогда его объединением называется множество, состоящее из всех элементов всех множеств семейства:
- •Алгебра множеств. Законы алгебры множеств. Доказать один из законов алгебры множеств.
- •Множество. Мощность множества. Нахождение мощности объединения множеств (для двух множеств, для трех множеств, для n-множеств). Привести пример.
- •Векторы. Прямое произведение множеств. Мощности прямого произведения множеств.
- •Отношения. Основные понятия отношений (отношения; унарные, бинарные, n-местные отношения)
- •Отношения. Бинарные отношения. Основные понятия (определение, обозначения, область определения, область значений, способы задания бинарных отношений). Привести примеры.
- •Способы задания бинарных отношений
- •Отношения. Свойства бинарных отношений (рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность). Привести примеры.
- •Переключательные (булевы) функции. Происхождение булевых функций.
- •Булевы функции от одного аргумента. (Определение. Все булевы функции от одного аргумента).
- •Булевы функции от двух аргументов (Определение булевой функции двух аргументов, тождественный ноль, тождественная единица, конъюнкция, штрих Шеффера, дизъюнкция, стрелка Пирса (функция Вебба)).
- •Свойства дизъюнкции, конъюнкции и отрицания (теорема 4.3).
- •Свойства эквиваленции, импликации и отрицания (теорема 4.4).
- •Выражение одних булевых функций через другие (теорема 4.5).
- •Булевы функции от n аргументов (определение, равенство булевых функций, суперпозиция булевых функций). Булевы функции от n переменных
- •Булевы функции и формулы алгебры высказываний.
- •Нормальные формы булевых функций.
- •Применение булевых функций к релейно-контактной схеме. Две основные задачи теории релейно-контактных схем.
- •Релейно-контактные схемы в эвм. Двоичный полусумматор. Одноразрядный двоичный сумматор.
- •Графы. Основные понятия и определения (вершины, ребра, петли, кратность ребра, псевдограф, мультиграф, граф, орграф, неориентированный граф). Привести примеры.
- •Графы. Матричное задание графов. Матрица смежности, матрица инцидентности. Привести примеры.
- •Графы. Свойства матрицы смежности и инцидентности. Утверждение о числе всех путей (маршрутов) длины k из одной вершины в другую. Утверждение о наличие хотя бы одного контура.
- •Графы. Связность. Компоненты связности. (Достижимость вершины, связный (сильно связный орграф) граф, слабо связанный, несвязанный, компонента связности (сильной связности)). Привести примеры.
- •Графы. Матрицы связности. Утверждение о матрицах связности, матрицы достижимости, матрицы сильной связности.
- •Графы. Поиск путей (маршрутов) с минимальным числом дуг (ребер). Алгоритм фронта волны.
- •Графы. Минимальные пути (маршруты) в нагруженных орграфах (графах). Алгоритм Форда-Беллмана.
Графы. Свойства матрицы смежности и инцидентности. Утверждение о числе всех путей (маршрутов) длины k из одной вершины в другую. Утверждение о наличие хотя бы одного контура.
Свойства матриц смежности и инцидентности.
Для ориентированного мультиграфа D=(V,X), V={v1,...,vn}, X={x1,...,xm}
- сумма строк матрицы B(D) является нулевой строкой (дуга один раз входит и один раз выходит);
- любая строка матрицы B(D) является линейной комбинацией остальных строк (вследствие предыдущего);
- ранг матрицы B(D) не превосходит n(D)-1 (также вследствие предыдущего);
- для любого контура в D сумма столбцов матрицы B(D), соответствующих дугам, входящим в этот контур, равна нулевому столбцу.
Для неориентированного мультиграфа G=(V,X), V={v1,...,vn}, X={x1,...,xm}
- сумма строк матрицы B(G) по модулю 2 является нулевой строкой (дуга один раз входит и один раз выходит, а вместе четно);
- любая строка матрицы B(G) является суммой по модулю 2 остальных строк (вследствие предыдущего);
- для любого цикла в G сумма по модулю 2 столбцов матрицы B(G), соответствующих ребрам, входящим в этот цикл, равна нулевому столбцу.
Графы. Связность. Компоненты связности. (Достижимость вершины, связный (сильно связный орграф) граф, слабо связанный, несвязанный, компонента связности (сильной связности)). Привести примеры.
Определение. Вершина w орграфа D (графа G) достижима из вершины v, если либо v=w, либо существует путь изv в w(маршрут, соединяющий v, w).
Дадим более удобное определение связных графов.
Определение. Граф называется связным, если для любых двух его вершин v, w существует простая цепь из v в w.
Определение. Граф (орграф) называется связным (сильно связным), если для любых двух его вершин v, w существует маршрут (путь), соединяющий v, w (из v и w).
Определение. Орграф называется односторонне связным, если для любых его двух вершин, по крайней мере, одна достижима из другой.
Определение. Если граф не является связным, то он называется несвязным.
Определение. Компонентой связности графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа.
В дальнейшем количество компонент связности графа будем обозначать k.
П ример 79.
Данный граф не является связным: k = 3.
Данный граф является связным: k = 0.
Т еорема. Пусть G – простой граф с n вершинами и k компонентами. Тогда число m его ребер удовлетворяет неравенствам
Следствие. Любой простой граф с n вершинами и более чем (т-1)(т-2)/2 ребрами связен.
При исследовании графов возникает вопрос: насколько сильно связен связный граф? Этот вопрос можно сформулировать и так: сколько ребер нужно удалить из графа, чтобы он перестал быть связным? Под операцией удаления вершин из графа будем понимать операцию, заключающуюся в удалении некоторой вершины вместе с инцидентными ей ребрами.
Определение. Вершина графа, удаление которой увеличивает число компонент связности, называется разделяющейся.
Определение. Разделяющим множеством связного графа G называется такое множество его ребер, удаление которого приводит к несвязному графу.
Определение. Разрезом называется такое разделяющее множество, никакое собственное подмножество которого не является разделяющим.
О пределение. Разрез, состоящий из одного ребра, называется мостом (перешейком).
Пример 80.
Для графа, изображенного на рис.33, каждое из множеств {e1, e2, e5}и {e3, e6, e7, e8} является разделяющим.
Разрезом является множество ребер {e1, e2}.
В графе возможно выделить несколько разделяющих множеств и разрезов.