Контрольное задание №2.

1. Покажите, что для ориентированного графа G, имеющего не менее одной дуги, графGне имеет контуров.

2. Покажите, что для ориентированного графа G, имеющего по крайней мере одну дугу, следующие утверждения равносильны:

   1. граф G– сильно связный

   2. любая дуга графа Gлежит в контуре

3. Покажите, что число ориентированных эйлеровых цепей в орграфе, имеющем nвершин иm> 2nдуг, четно.

4. Пусть G– простой орграф сnвершинами иmдугами; покажите, что еслиGсвязен, но не сильно связен, то:n-1≤ m≤ (n-1)(n-2), а еслиGсильно связен, то:n≤ m≤ n(n-1)

5. Пусть А – матрица смежности орграфа с множеством вершин {v₁,…,v_n}. Докажите, что (i,j)-й элемент изA^kравен числу ориентированных маршрутов длиныkизv_iвv_j. Какой смысл можно придумать суммам строк и суммам столбцов матрицы А?

6. Постройте ориентированный ациклический граф с а) 6; б) 8; в) 10; г) 12 вершинами.

7. Произведите топологическую сортировку графа из предыдущего задания.

8. Постройте несколько деревьев а) 4; б) 5; в) 7; г) 8 порядка.

9. Постройте фундаментальную систему циклов для любого дерева из предыдущего задания.

10. Постройте произвольный ориентированный граф с циклами с а) 4; б) 5; в) 6; г) 8 вершинами. Найдите цикломатическое число построенного графа.