Дискретная математика
Контрольная работа № 1.
1) Для неориентированного графа выполнить следующие операции:
а) построить диаграмму графа;
б) определить является ли граф мульти-графом или псевдо-графом;
в) построить матрицу инцидентности;
г) построить матрицу смежности;
д) определить максимальную и минимальную степени вершин;
е) определить диаметр и радиус графа;
ж) найти множество центральных вершин;
з) определить число компонент связности графа;
и) определить наличие точек сочленения и мостов в графе;
к) определить вершинную и реберную связность графа;
л) найти цикломатическое число;
м) построить базисную цикломатическую матрицу;
н) построить цикломатическую матрицу (15-20 циклов);
о) определить толщину графа;
п) выделить планарные подграфы;
р) раскрасить вершины и ребра графа.
2) Для ориентированного графа выполнить следующие операции:
а) построить диаграмму графа;
б) построить матрицу инцидентности;
в) построить матрицу смежности;
г) определить максимальную и минимальную полу-степени вершин;
д) определить является ли граф сильно-, односторонне- или слабо- связным;
е) найти компоненты сильной связности графа;
ж) построить конденсацию графа.
Контрольная работа № 2.
1) Составьте таблицы истинности формул.
2) Проверьте двумя способами, будут ли эквивалентны следующие формулы:
а) составлением таблиц истинности;
б) приведением формул к СДНФ или СКНФ с помощью эквивалентных преобразований.
3) С помощью эквивалентных преобразований приведите формулу к ДНФ, КНФ, СДНФ, СКНФ. Постройте полином Жегалкина.
4) Найдите сокращенную, все тупиковые и минимальные ДНФ булевой функции f(x,y,z) тремя способами:
а) методом Квайна;
б) с помощью карт Карно;
в) методом Квайна-МакКлоски.
Каким классам Поста принадлежит эта функция?
5) С помощью карт Карно найдите сокращенную, все тупиковые и минимальные ДНФ или КНФ булевой функции f(x_1,x_2,x_3,x_4 ), заданной вектором своих значений.
6) Является ли полной система функций? Образует ли она базис?