лекции по дм. лекции. Основные понятия теории множеств. Способы задания множеств 4 Диаграммы Венна. 4
 Скачать 1.51 Mb.
|
Раскраска графов. Хроматическое число. Планарность. Укладка графов. Алгоритмы раскрашивания.Раскраска графов – приписывание цветов (например, чисел) его вершинам так, что никакие две смежные вершины не получают одинаковый цвет. Наименьшее возможное число цветов раскраски – хроматическое число. Обозначение: x(G). Очевидно, что существует m-раскраска графа G для любого m в диапазоне x(G) m p. Множество вершин одного цвета - одноцветный класс. Одноцветные классы образуют независимые множества вершин, т. е. никакие две вершины в одноцветном классе не смежны. Теорема 1. Хроматическое число графа G не превышает максимальной степени вершин графа, увеличенной на 1. x(G) 1 + G. Граф укладывается на некоторой поверхности, если его можно нарисовать на этой поверхности так, чтобы ребра графа при этом не пересекались. Граф – планарный, если его можно уложить на плоскость. Плоский граф – граф, уложенный на плоскости. Область, ограниченная ребрами в плоскости графа и не содержащая внутри себя вершин и ребер, – грань. Число граней плоского графа G обозначается r(G).   Планарный граф и его укладка на плоскости. Внешняя часть плоскости также образует грань. Для графов, уложенных на некоторой поверхности, справедливо определенное соотношение между числом вершин, ребер и граней, это соотношение – Эйлерова характеристика поверхности. Теорема 1(формула Эйлера). В связном планарном графе справедливо следующее: p - q + r = 2. Теорема 2(о 5 красках). Всякий планарный граф можно раскрасить пятью красками. Алгоритм раскрашивания: для раскрашивания графа применяют следующую схему рекурсивной процедуры p: 1) Выбрать в графе G некоторое максимальное множество вершин S; 2) Покрасить вершины множества S в очередной цвет; 3) Применить процедуру p к графу G – S. Тема 18. Переключательные функции. Основные понятия и определения. Способы задания переключательных функций. Таблица истинности. Переключательные функции одного и двух аргументов. Специальные разложения ПФ. Переключательные функции. Существенные и несущественные переменные. Булевы функции одной переменной. Булевы функции двух переменных.Функции вида f: E2n E2, где E2 = {0;1} – функции алгебры логики или булевы функции. Множество булевых функций от n переменных обозначим pn и pn := { f| f : E2n E2}. Булеву функцию от n переменных можно задать таблицей истинности.
Если число переменных n, то в таблице истинности имеется 2n строк, соответствующих всем различным комбинациям значений переменных, которым можно сопоставить 22^n различных столбцов, соответствующих различным функциям. Т.о. число булевых функций от n переменных |pn| = 22^n. Булева функция f pn существенно зависит от переменной xi, если существует такой набор значений a1, a2,…, ai–1, ai+1,…, an–1, an, что выполняется условие f(a1, a2,…, ai–1, ai+1,…, an–1, an) f(a1, a2,…, ai–1, 1, ai+1,…, an–1, an). В этом случае xi – существенная переменная, в обратном случае xi – несуществующая (фиктивная) переменная. Пример. Пусть булевы функции f1(x1, x2); f2(x1, x2) заданы следующей таблицей истинности:
Для этих функций переменная x1 – существенная, а x2 – несущественная. По определению булевы функции равны, если одна из другой получается введением (или удалением) несущественных переменных. Функции называются эквивалентными, если их таблицы совпадают с точностью до переменных. Для исключения фиктивной переменной удаляется столбец с этой переменной, дублирующие строки удаляются. Булевы функции одной переменной представим в виде таблицы.
|