Дискретная математика

Контрольная работа № 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) Является ли полной система функций? Образует ли она базис?