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

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

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

a.

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

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

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

5. Пусть А – матрица смежности орграфа с множеством вершин {v1,…,vn}. Докажите, что (i, j)-й элемент из Akравен числу ориентированных маршрутов длины kиз viв vj. Какой смысл можно придумать суммам строк и суммам столбцов матрицы А?

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

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

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

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

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