Задачи для самостоятельного решения. 1. Что из приведенного ниже является путем в графе на рис

1. Что из приведенного ниже является путем в графе на рис. 4.13? Какие из них являются простыми? Найти длину каждого из путей.

а) , б) , в) , г) .

2. Что из приведенного ниже является циклом в графе на рис. 4.14? Которые из них простые циклы? Для каждого n -цикла определить значение n.

а) , б) , в) , г) .

3. Найти вершины и ориентированные ребра для приведенных ниже орграфов. Для каждой вершины определить степень входа и степень выхода. Имеются ли здесь источники и стоки?

4. Какие из приведенных ниже графов (рис. 4.16) являются деревьями?

5. Для корневого ориентированного дерева (рис. 4.17) найти:

а) потомков вершины ,

б) предков вершины ,

в) родителя вершины ,

г) уровень вершины ,

д) сыновей вершины ,

е) высоту дерева,

ж) листья дерева. Определите, является ли дерево бинарным.

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

7. Найти матрицы инцидентности и смежности следующих графов (рис. 4.19).

8. Для заданной матрицы смежности найти граф.

9. Для графа на рис. 4.20:

а) найти матрицу смежности,

б) используя матрицу смежности, найти все пути длины 2 и 3.

Дата добавления: 2014-12-27