Условие задачи
3. Найдите вершины и ориентированные ребра для приведенного орграфа на рис. 2. Для каждой вершины определите степень входа и степень выхода. Имеются ли здесь источники и стоки?
4. Для графа на рис. 2 постройте восемь подграфов.
5. Определите есть ли простой ориентированный путь для графа на рис.2? Если есть, то сколько их и какие, ответ обоснуйте?
6. Определите есть ли ориентированный цикл для графа на рис.2. Если есть, то сколько их и какие, ответ обоснуйте?
рис.2
Ответ
3. Найдите вершины и ориентированные ребра для приведенного орграфа на рис. 2. Для каждой вершины определите степень входа и степень выхода. Имеются ли здесь источники и стоки?
V={a;b;c;d;f;e} вершины; E={ba, bd, cd, cf, df, fe, ea} рёбра;
d-(a)=0; d-(b)=2; d-(c)=1; d-(d)=2; d-(e)=1; d-(f)=2 степени выхода;
d+(a)=2; d+(b)=1; d+(c)=1; d+(d)=2; d+(e)=1; d+(f)=2 степени входа;
а сток; источников нет в графе, т.к. все степени входа не равны нулю;
4. Для графа на рис...
