База ответов ИНТУИТ

Основы дискретной математики

<<- Назад к вопросам

Пусть неориентированный граф G=(V,E) задан с помощью списков смежности:
La: d, c, b           Lb: a                   Lc: i, hLd: a, e, f           Le: d, g, f             Lf: d, e, gLg: e, f              Lh: c, i                Li: c, h
Постройте, начиная с вершины a, обход этого графа в глубину, в котором соседи каждой вершины рассматриваются в порядке, определенном ее списком смежности. Какая из следующих нумераций вершин ему соответствует?

(Отметьте один правильный вариант ответа.)

Варианты ответа
\begin{array}{ccccccccc}a&b&c&d&e&f&g&h&i\\  1&9&6&2&3&4&5&8&9\end{array}
\begin{array}{ccccccccc}a&b&c&d&e&f&g&h&i\\ 1&9&6&2&3&5&4&7&8\end{array}
\begin{array}{ccccccccc}a&b&c&d&e&f&g&h&i\\  1&9&6&2&3&5&4&8&7\end{array}
(Верный ответ)
\begin{array}{ccccccccc}a&b&c&d&e&f&g&h&i\\  1&6&7&2&3&5&4&9&8\end{array}
\begin{array}{ccccccccc}a&b&c&d&e&f&g&h&i\\ 1&5&2&6&7&9&8&4&3\end{array}
Похожие вопросы
Пусть неориентированный граф G=(V,E) задан с помощью списков смежности:
La: c, d, b           Lb: a, f, g             Lc: a, d, eLd: a, c, e           Le: c, d                Lf: bLg: b, i, h           Lh: g, i                Li: g, h
Постройте, начиная с вершины a, обход этого графа в глубину, в котором соседи каждой вершины рассматриваются в порядке, определенном ее списком смежности. Какая из следующих нумераций вершин ему соответствует?
Пусть неориентированный граф G=(V,E) задан с помощью списков смежности:
La: b, c, d, g           Lb: a, f, d             Lc: a, d, eLd: a, b, c, e           Le: c, d, f             Lf: b, eLg: a, i, h              Lh: g, i                Li: g, h
Постройте, начиная с вершины a, обход этого графа в глубину, в котором соседи каждой вершины рассматриваются в порядке, определенном ее списком смежности. Какая из следующих нумераций вершин ему соответствует?
Пусть задан ориентированный нагруженный граф G:
  • V= {a, b, c, d, e, f, g, h },
  • E= {(a,b; 21), (a, c; 5), (a, d; 4), (a, e; 16), (a, f; 13), (a, g; 10), (b, e; 10), (b, f; 8), ( b,g; 5), (b, h; 2), (c, e; 10), (c,f; 7), (d, b; 10), (d, g; 5), (d, h; 21), (g,b; 10), (g, h; 10) }
  • (здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ).Используя алгоритм Дейкстры, определите дерево кратчайших путей из вершины a в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?
    Пусть задан ориентированный нагруженный граф G:
  • V= {a, b, c, d, e, f, g, h },
  • E= { (a, b; 5), (a, c; 32), (a, d; 2), (a, e; 32), (a, f; 12), (a, g; 15), (b, f; 6), (b, e; 20), ( b, h; 4), (c, h; 5), (d, g; 8), (d, h; 21), (g, c; 10), (g; e; 12), (f, d; 5), (f, b; 17) }
  • (здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ).Используя алгоритм Дейкстры, определите дерево кратчайших путей из вершины a в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?
    Пусть задан ориентированный нагруженный граф G:
  • V= {a, b, c, d, e, f, g, h },
  • E= { (a, c; 24), (a, d; 8), (a, e; 12), (a, f; 2), (a, g; 15), (b, c; 5), ( b,g; 15), (c, h; 5), (d, b; 10), (d, e; 3), (d, g; 10), (d, h; 21), (e, g; 2), (f, d; 5), (f, b; 17) }
  • (здесь каждая скобка (u,v; D) задает ребро (u,v) из E и его "вес" c(u,v)=D ).Используя алгоритм Дейкстры, определите дерево кратчайших путей из вершины a в остальные вершины графа. Каков суммарный вес всех ребер этого дерева?
    Пусть задан неориентированный граф G=(V,E):V= {a, b, c, d, e, f, g, h , i}, E = {(a, b), (a, c), (b, d), (b, c), (b, f), (d, e), (f, e), (a, g), (g, i), (h, g), (i, h) }.Используя вариант поиска в глубину с подсчетом функции ВЕРХ, определите все мосты этого графа и укажите их число.
    Пусть задан неориентированный граф G=(V,E):V= {a, b, c, d, e, f, g, h , i}, E = {(a, b), (a, c), (b, d), (b, c), (d, e), (d, f), (f, g), (f, h), (f,i) }.Используя вариант поиска в глубину с подсчетом функции ВЕРХ, определите все мосты этого графа и укажите их число.
    Пусть задан неориентированный граф G=(V,E):V= {a, b, c, d, e, f, g, h , i}, E = {(a, b), (a, c), (b, d), (b, c), (b, e), (f, e), (f, g), (d, h), (f, i), (h, a) }.Используя вариант поиска в глубину с подсчетом функции ВЕРХ, определите все мосты этого графа и укажите их число.

    Пусть граф G=(V,E) задан своей матрицей смежности

    A_G=\begin{array}{ccccc}1 & 1 & 0 & 0 & 0\\0 & 0 & 0 & 1 & 1\\1 & 0 & 0 & 0 & 0\\0 & 0 & 0 & 1 & 1\\0 & 0 & 1 & 0 & 0\end{array}

    Постройте граф достижимости G*=(V,E*) для G и определите, сколько в нем новых ребер,т.е. чему равна разность |E*| - |E|.

    Пусть граф G=(V,E) задан своей матрицей смежности

    A_G=\begin{array}{ccccc}0& 1 &0 &0 &0\\0 &1& 0& 0& 0\\0 &0 &0 &1 &0\\0 &1 &0 &0 &1\\1 &0 &0 &0 &1\end{array}

    Постройте граф достижимости G*=(V,E*) для G и определите, сколько в нем новых ребер, т.е. чему равна разность |E*| - |E|.