Курсы повышения квалификации

К теме “Графы”

Все графы, фигурирующие в контрольной работе, обыкновенные, без петель и кратных ребер.

4.1. Существует ли граф с заданным набором степеней вершин? Если ответ да, то нарисовать подходящий граф, если нет — объяснить почему.

а) 1, 1, 2, 2, 2, 4;

б) 1, 2, 2, 3, 3, 4;

в) 2, 2, 3, 3, 4, 4.

4.2. На рис. 1 представлены 3 графа. Имеются ли среди них одинаковые? Если да, то перечислить буквы, которыми они обозначены; если нет, то для каждого графа, не имеющего пары, объяснить, почему данный граф не совпадает ни с каким из оставшихся.

Рис. 1

4.3. Сколько циклов длины 4 имеет граф, изображенный на рис. 1б?

4.4. Укажите мосты и точки сочленения для графа, представленного на рис. 2.

Рис. 2

4.5. Для графа, изображенного на рис. 3, построить: а) каркас наименьшего веса; б) каркас наибольшего веса.

Рис. 3

4.6. Некоторые графы из четырех, изображенных на рис. 4, описаны также некоторыми из таблиц 1–3. Укажите, какие именно. Ответ записать в виде: номер таблицы — буква рисунка (например, 3б), а на соответствующем рисунке расставить буквы от А до G, обозначающие вершины.

Рис. 4

К теме “Логические модели в информатике” 

При выполнении заданий 5.1 и 5.2 перечислите номера всех правильных ответов.

5.1. Высказывание равносильно высказыванию

5.2. Таблицу истинности, совпадающую с табл. 1, имеет формула F(X, Y),

Таблица 1

5.3. Известно, что высказывание ложно. Что можно сказать о значении истинности высказываний А, В и С?

5.4. Для последовательности высказываний An при n > 3 выполнено следующее рекуррентное соотношение: . Какое значение — истина или ложь — имеет высказывание A₂₀₀₇, если A₁ и A₃ истинны, а A₂ — ложно?

5.5. Известно, что высказывание F, зависящее от трех высказываний А, В и С, принимает значение истина в том и только том случае, когда ровно одно из высказываний А, В и С имеет значение ложь. Составьте для F логическую формулу.

5.6. Для цепи, изображенной на рис. 5, постройте эквивалентную ей более простую цепь (вы можете подготовить схему в электронном виде или нарисовать ее от руки и отсканировать).

Рис. 5

5.7. Для мостовой схемы, изображенной на рис. 6, постройте эквивалентную ей последовательно-параллельную схему.

Рис. 6