Алгоритмы: построение и анализ

Пусть двудольный граф задан следующей матрицей $\begin{pmatrix}1 & 1 & 1 & 1 & 1\\0 & 0 & 1 & 0 & 0\\0 & 0 & 1 & 0 & 1\\0 & 0 & 0 & 0 & 1\\0 & 1 & 0 & 0 & 1\\0 & 0 & 1 & 0 & 1\\\end{pmatrix}$ Чему равен размер максимального паросочетания?

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

Варианты ответа

4(Верный ответ)

Похожие вопросы

Пусть двудольный граф задан следующей матрицей $\begin{pmatrix}1 & 1 & 1 & 1 & 1\\0 & 1 & 1 & 0 & 0\\0 & 0 & 1 & 0 & 1\\0 & 0 & 0 & 0 & 1\\\end{pmatrix}$ Чему равен размер максимального паросочетания?

Пусть двудольный граф задан следующей матрицей $\begin{pmatrix}1 & 1 & 1 & 1 & 1\\0 & 0 & 1 & 0 & 0\\0 & 0 & 1 & 0 & 1\\0 & 0 & 0 & 0 & 1\\\end{pmatrix}$ Чему равен размер максимального паросочетания?

Пусть веса ребер полного графа заданы матрицей $A= \begin{pmatrix}- & 2 & 4 & 5 \\2 & - & 1 & 1 \\4 & 1 & - & 3 \\5 & 1 & 3 & - \\\end{pmatrix}$ . В каком порядке жадный алгоритм будет выбирать ребра максимального покрывающего поддерева?

Пусть веса ребер полного графа заданы матрицей $A= \begin{pmatrix}- & 6 & 4 & 3 \\6 & - & 3 & 5 \\4 & 3 & - & 1 \\3 & 5 & 1 & - \\\end{pmatrix}$ . В каком порядке жадный алгоритм будет выбирать ребра максимального покрывающего поддерева?

Пусть веса ребер полного графа заданы матрицей $A= \begin{pmatrix}- & 100 & -4 & -5 \\100 & - & -2 & -1 \\-4 & -2 & - & -3 \\-5 & -1 & -3 & - \\\end{pmatrix}$ . В каком порядке жадный алгоритм будет выбирать ребра максимального покрывающего поддерева?

Какие утверждения верны для следующей матрицы $A= \begin{pmatrix}1 & 1 & 0 & 0 & 1 \\0 & 0 & 0 & 1 & 0\\0 & 0 & 1 & 0 & 1\\0 & 0 & 1 & 1 & 0\\1 & 1 & 0 & 0 & 0\\\end{pmatrix}$ ?

Какие утверждения верны для следующей матрицы $A= \begin{pmatrix}0 & 1 & 0 & 0 & 1 \\1 & 0 & 0 & 1 & 0\\0 & 0 & 1 & 0 & 1\\1 & 1 & 1 & 1 & 0\\\end{pmatrix}$ ?

Какие утверждения верны для следующей матрицы $A= \begin{pmatrix}0 & 1 & 1 & 1 & 0 \\1 & 0 & 0 & 1 & 0\\0 & 0 & 1 & 0 & 1\\1 & 1 & 1 & 1 & 0\\\end{pmatrix}$ ?

Пусть на начало пятого шага венгерского алгоритма мы работали со следующими строками $\begin{pmatrix}3 & 0 & 1 & 0 & 4\\3 & 1 & 0 & 2 & 3\\ 3 & 0 & 2 & 2 & 3\\ 0 & 1 & 2 & 2 & 3\\ 3 & 1 & 2 & 2 & 3\\ \end{pmatrix}$ . Как будут выглядеть эти строки к концу пятого шага?

Пусть на начало пятого шага венгерского алгоритма мы работали со следующим двумя строками $\begin{pmatrix}3 & 0 & 1 & 0 & 4\\3 & 1 & 0 & 2 & 3\\ 3 & 0 & 2 & 2 & 3\\ 0 & 1 & 2 & 2 & 3\\ 3 & 2 & 2 & 1 & 2\\ \end{pmatrix}$ как будут выглядеть эти строки к концу пятого шага?

Алгоритмы: построение и анализ

Пусть двудольный граф задан следующей матрицей Чему равен размер максимального паросочетания?