ПОӘК 042-14. 01. 20. 205/03-2013 02. 09. 20013 №1 басылым

a0, b10, c011, d1011, e1111 

2. Построить оптимальное префиксное алфавитное кодирование для алфавита {a,b,c,d} со следующим распределением вероятностей появления букв:

p_a=1/2, p_b=1/4, p_c=1/8, p_d=1/8/

2. Составить матрицу инцидентности для мультиграфа, изображенного на рис. 4.51.

5. Для графов G₁ и G₂ из предыдущей задачи найти G₁ x G₂,G₁ [G ₂] и G₂ [G₁].

6. С помощью матрицы смежности графа (рис. 4.53) найти его матрицы достижимости, контрдостижимости и сильных компонент.

7. Найти матрицу расстояний, диаметр, радиус, центральные и периферийные вершины графа, изображенного на рис. 4.54.

8. Найти все кратчайшие маршруты из вершины 2 для взвешенного графа (рис. 4.55).

9. Доказать, что в любом конечном бесконтурном графе существуют вершины с нулевой степенью исхода и с нулевой степенью захода

10. Проверить на эйлеровость и найти минимальное множество покрывающих цепей:

а) графа К₅; б) графа, изображенного на рис. 4.56.

1. Докажите тождества, используя только определения операций над множествами.

4. Найдите область определения, область значений отношения Р. является ли отношение Р рефлексивным, симметричным, антисимметричным, транзитивным?