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

1. Покажите, что для ориентированного графа G, имеющего не менее одной дуги, граф G не имеет контуров. 2. Покажите, что для ориентированного графа G, имеющего по крайней мере одну дугу, следующие утверждения равносильны: a. граф G– сильно связный 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 вершинами. Найдите цикломатическое число построенного графа.

< Предыдущая		Следующая >