Указания к решению контрольных

63

Указания к решению контрольной работы

Задача № 1. § 2.1: изоморфизм графов, матрица смежности вершин орграфа, пример 2.1.2, теорема 2.1.3, матрица инцидентности орграфа, пример 2.1.4; § 2.2: объединение графов, теорема 2.2.2 и следствие из неё, пример 2.2.2, пересечение графов, теорема 2.2.3 и следствие из неё, пример 2.2.3, композиция графов, теорема 2.2.4, пример 2.2.4.

Задача № 2. § 2.1: матрица смежности вершин неориентированного графа, пример 2.1.1, матрица инцидентности неориентированного графа, пример 2.1.3; § 2.2: декартово произведение графов, теорема 2.2.5 и замечание к ней, пример 2.2.5, прямое произведение графов, теорема 2.2.6 и замечание к ней, пример 2.2.6.

Задача № 3. § 2.4: теорема 2.4.5, пример 2.4.1.

Задача № 4. § 2.4: каркас в неориентированном графе, теорема 2.4.6, нагруженный граф, вес ребра, вес каркаса, минимальный каркас, алгоритм Краскала построения минимального остовного дерева, пример 2.4.2.

Задача № 5. § 2.5: внутренне устойчивое (независимое) множество вершин, максимальное независимое множество, наибольшее независимое множество, число внутренней устойчивости графа, ДНФ, КНФ, переход от КНФ к ДНФ, импликанта логической функции, сокращённая ДНФ, минимальная ДНФ и методы её нахождения, метод испытания импликант для минимизации ДНФ, метод К. Магу нахождения максимальных внутренне устойчивых множеств вершин графа, теорема 2.5.3, пример 2.5.2, внешне устойчивое (доминирующее) множество вершин, база, наименьшее доминирующее множество, число внешней устойчивости графа, метод К. Магу нахождения минимальных внешне устойчивых множеств вершин графа, теорема 2.5.4, пример 2.5.3.

Задача № 6. § 2.6: сеть, пропускная способность дуги, транспортная сеть, поток в транспортной сети, величина потока, разрез в транспортной сети, пропускная способность разреза, (s, t)-путь, прямые и обратные дуги (s, t)-пути, (s, t)-путь, насыщающий поток, алгоритм Форда-Фалкерсона построения максимального потока и разреза с минимальной пропускной способностью в транспортной сети, пример 2.6.2.

Задача № 7. § 1.1: операции над множествами и их свойства, тождества булевой алгебры множеств и методы их доказательства, пример 1.1.6.

Задача № 8. § 1.2: взаимно-однозначное соответствие между двумя множествами, равномощные множества, счётное множество, доказательства счётности любого бесконечного подмножества множества N, множеств Z и Q, пример 1.2.3, несчётное множество, мощность континуум, континуальные множества, доказательства (0,1)[0,1), (0,1)[0,1], (0,1)(a,b), (0,1)R, примеры 1.2.4, 1.2.5.

Задача № 9. § 1.3: функция, сюръективная, инъективная, биективная функция, область определения и область значений функции, вещественная функция, композиция функций, аналитический способ задания функций, сужение функции на множество, обратная функция, теорема 1.3.1, свойства функций и их композиций, пример 1.3.4.

Задача № 10. § 1.3: бинарное отношение, матрица и граф бинарного отношения, операции над отношениями, обратное отношение, шесть основных свойств отношений, примеры 1.3.5, 1.3.6.