Пояснения к выполнению контрольной по Дискретной математике
ЗАДАНИЕ А. Упростить формулы.
Пояснение - воспользоваться таблицей формул упрощения логических выражений, например, здесь
ЗАДАНИЕ B.
Комментарий - все просто, читаем строку (как читать) и рисуем в таблице нолики и единички.
ЗАДАНИЕ С.
Здесь не так все просто, но можно разобраться...
Задание С1.
Построение матрицы расстояний по матрице смежности, можно использовать алгоритм Дейкстры, а также Флойда-Уоршелла:
Эксцентритет вершины есть расстояние до наиболее удаленной вершины от нее.
Диаметр графа есть максимальное из расстояний между его вершинами.
Радиусом называется величина наименьшего эксцентриситета.
Центром соответственно называют вершину с наименьшим эксцентриситетом.
Примеры расчета можно найти здесь
Задание С2. Алгоритм нахождения компонент связности графа, используя метод поиска в ширину.
Распаковка 'Кода Прюфера'
Алгоритм восстановления дерева по коду Прюфера следующий:
- Пусть A - код Прюфера [a1, a2,...,], а N = [1,...,n] - полный перечень вершин
- Цикл:
- --- если v есть вершина с минимальным номером в N и ее нет в списке А, а u = a1, то соединяем u и v ребром
- --- вычеркиваем v из N, а также u из A
- --- повторяем цикл, пока код А не становится пустым, после этого оставшийся список в N содержит два числа (n-1, n). Соединяем их между собой на дереве
- дерево восстановлено
Немного про Прюфера и работу поисковой системы >>
Пример исходного кода кода Прюфера >>
|