Специальность 230100.62 Контрольная работа по дискретной математике (стр. 9 )

Задача 9. Дан нагруженный граф.

А) Будем считать граф ненагруженным.

Определите степени всех вершин графа. Запишите матрицу смежности вершин. Укажите мосты и точки сочленения, если они есть. Проверьте, является ли граф эйлеровым, гамильтоновым, двудольным. Запишите соответствующие определения и критерии. Запишите какой-нибудь маршрут от до . Укажите какой-нибудь простой цикл. Постройте дерево, покрывающее граф.

Б) Будем считать граф нагруженным.

Постройте минимальное соединение графа и найдите его длину (вес). Используя алгоритм Дейкстры, найдите кратчайший путь от до .

Контрольная работа по дискретной математике  Специальность 230100.62

Вариант 2

Задача 1. Докажите, что при любом натуральном имеет место равенство

.

Задача 2. Сколько существует различных способов выбора команды из трех юношей и трех девушек из группы студентов, в которую входят 6 юношей и 5 девушек?

Задача 3. Найдите коэффициент при в разложении .

Задача 4. Даны числовые множества и . Найдите , , , , , и . Изобразите .

а) ,

б) , где — множество цифр .

Задача 5. Каждый из 45 туристов, прибывших в Мон-Сен-Мишель, свое свободное время посвятил посещению старого бенедиктинского аббатства, покупке сувениров и поеданию устриц в местном ресторанчике. Аббатство посетило 28 человек, сувениры приобрели 18, а устрицами успели полакомиться 14 человек; из посетивших аббатство лакомились устрицами 6, попробовали устриц и купили сувениры 7,посетили аббатство и купили сувениры — 4. Сколько человек успели осмотреть исторические достопримечательности, попробовать местные деликатесы и купить сувениры на память, а сколько успели только посетить аббатство?

Задача 6. Проверьте, являются ли отношение на множестве рефлексивным, антирефлексивным, симметричным, антисимметричным, транзитивным, эквивалентным, отношением порядка (строгого или нестрогого).

.

Укажите матрицу отношения и постройте граф.

Задача 7. Операция на множестве задана таблицей Кэли. Проверьте, является ли эта операция коммутативной, ассоциативной, существуют ли единичный и обратный элементы?

Вычислите .

Задача 8. Дана переключательная функция

А) .

Постройте таблицу истинности. Найдите СДНФ и СКНФ. Постройте полином Жегалкина. Проверьте, является ли функция монотонной. Проверьте, является ли функция линейной. Проверьте, является ли функция самодвойственной. Проверьте, является ли функция сохраняющей 0. Проверьте, является ли функция сохраняющей 1. Выясните, образует ли функционально полную систему. Если нет, то можно ли добавлением к функции получить функционально полную систему. Минимизируйте ДНФ и КНФ для с помощью карты Карно. Постройте соответствующие контактные схемы.

Б) . Минимизируйте ДНФ и КНФ для с помощью карты Карно.

Задача 9. Дан нагруженный граф.

А) Будем считать граф ненагруженным.

Определите степени всех вершин графа. Запишите матрицу смежности вершин. Укажите мосты и точки сочленения, если они есть. Проверьте, является ли граф эйлеровым, гамильтоновым, двудольным. Запишите соответствующие определения и критерии. Запишите какой-нибудь маршрут от до . Укажите какой-нибудь простой цикл. Постройте дерево, покрывающее граф.

Б) Будем считать граф нагруженным.

Постройте минимальное соединение графа и найдите его длину (вес). Используя алгоритм Дейкстры, найдите кратчайший путь от до .

Контрольная работа по дискретной математике  Специальность 230100.62