Теория графов

MathProblemsBank banner

MathProblemsBank banner

Math Problems and solutions

Список задач Бесплатные задачи

Внимание! Если выбран подраздел, то поиск будет произведен в нем!

условие: Найти остовное дерево минимального веса графа. Веса ребер приведены на графе.

6.4.16 Теория графов

100 ₽

условие: Найти основные характеристики графа (эксцентриситеты вершин, степени вершин, матрица смежности, числа вершинной и реберной связности, радиус, диаметр и диаметральную цепь, плотность и неплотность, хроматическое число), представленного рисунком. В случае несвязного графа характеристики следует найти для большей компоненты.

6.4.17 Теория графов

150 ₽

условие: Найти три неизоморфных остовных дерева графа. В случае несвязного графа остовные деревья следует найти для большей компоненты.

6.4.18 Теория графов

80 ₽

условие: Найти остовное дерево минимального веса графа. Веса ребер приведены на графе.

6.4.19 Теория графов

100 ₽

условие: Доказать, что любой \( k \)-связный граф \( G \), построенный на \( n \geq 2 \) вершинах, \( k \geq 2 \), содержит цикл \( C \), длина которого больше или равна \( 2 k \).

6.4.20 Теория графов

200 ₽

условие: Доказать, что граф \( G \) является реберно двусвязным тогда и только тогда, когда его можно представить в виде \( G=G_{0} \cup G_{1} \cup \ldots \cup \) \( G_{k} \), где \( G_{0}- \) произвольный цикл в графе \( G \), а \( G_{i}, i>0 \), представляет собой либо ручку, либо замкнутую ручку для подграфа \( G_{0} \cup G_{1} \cup \ldots \cup \) \( G_{i-1} \) графа \( G \).

6.4.21 Теория графов

250 ₽

Условие: Пусть \( G \) вершинно \( k \)-связен. Образуем из \( \mathrm{G} \) новый граф \( G^{\prime} \) путем добавления к \( G \) новой вершины \( y \) и не менее \( k \) ребер из \( y \) в \( k \) различных вершин графа \( G \). Доказать, что \( G^{\prime} \) так-же \( k- \) связен.

6.4.22 Теория графов

150 ₽

Условие: По заданной матрице весов \( \Omega \) графа \( G \) найти величину минимального пути и сам путь от вершины \( v_{1} \) до вершины \( v_{7} \) по алгоритму Беллмана-Мура. \[ \Omega=\left(\begin{array}{ccccccc} - & 6 & \infty & \infty & 12 & \infty & \infty \\ \infty & - & 4 & 10 & \infty & 15 & \infty \\ \infty & \infty & - & 4 & \infty & \infty & \infty \\ \infty & \infty & \infty & - & \infty & \infty & 6 \\ \infty & -8 & 7 & 11 & - & -6 & \infty \\ \infty & \infty & -8 & 7 & 8 & - & 5 \\ \infty & \infty & \infty & \infty & \infty & \infty & - \end{array}\right) \]

6.4.23 Теория графов

200 ₽

условие: Найти основные характеристики графа (эксцентриситеты вершин, степени вершин, матрица смежности, числа вершинной и реберной связности, радиус, диаметр и диаметральную цепь, плотность и неплотность, хроматическое число), представленного рисунком. В случае несвязного графа характеристики следует найти для большей компоненты.

6.4.24 Теория графов

150 ₽

условие: Взвешенный граф задан матрицей длин дуг. Нарисовать граф. Найти: a) остовное дерево минимального веса; б) кратчайшее расстояние от вершины \( v_{6} \) до остальных вершин графа, используя алгоритм Дейкстры. \[ \left[\begin{array}{cccccc} \infty & 2 & 3 & \infty & 1 & \infty \\ 2 & \infty & 1 & 1 & \infty & 4 \\ 3 & 1 & \infty & 5 & \infty & \infty \\ \infty & 1 & 5 & \infty & 4 & 2 \\ 1 & \infty & \infty & 4 & \infty & 3 \\ \infty & 4 & \infty & 2 & 3 & \infty \end{array}\right] \]

6.4.25 Теория графов

250 ₽

Условие: Орграф задан матрицей смежности. Необходимо: а) нарисовать граф; б) выделить компоненты сильной связности; в) заменить все дуги ребрами и в полученном неориентированном графе найти эйлерову цепь (или цикл). \[ \left(\begin{array}{llllll} 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 \end{array}\right) . \]

6.4.26 Теория графов

200 ₽

условие: Взвешенный граф задан матрицей длин дуг. Нарисовать граф. Найти: a) остовное дерево минимального веса; б) кратчайшее расстояние от вершины \( v_{4} \) до остальных вершин графа, используя алгоритм Дейкстры. \[ \left[\begin{array}{cccccc} \infty & \infty & \infty & 2 & 3 & 4 \\ \infty & \infty & 3 & \infty & 1 & 2 \\ \infty & 3 & \infty & 5 & \infty & 1 \\ 2 & \infty & 5 & \infty & 4 & 1 \\ 3 & 1 & \infty & 4 & \infty & \infty \\ 4 & 2 & 1 & 1 & \infty & \infty \end{array}\right] \]

6.4.27 Теория графов

250 ₽

\( \underline{\text { Условие: }} \) Орграф задан матрицей смежности. Необходимо: a) нарисовать граф; б) выделить компоненты сильной связности; в) заменить все дуги ребрами и в полученном неориентированном графе найти эйлерову цепь (или ЦиКЛ). \[ \left(\begin{array}{llllll} 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 1 \end{array}\right) \]

6.4.28 Теория графов

70 ₽

условие: Взвешенный граф задан матрицей длин дуг. Нарисовать граф. Найти: a) остовное дерево минимального веса; б) кратчайшее расстояние от вершины \( v_{4} \) до остальных вершин графа, используя алгоритм Дейкстры.

6.4.29 Теория графов

250 ₽

Условие: Найти число граней планарного графа с 10-ю вершинами, степени которых равны \( 2,2,2,3,3,3,4,4,4,5 \).

6.4.30 Теория графов

100 ₽

‹
1
2
3
›