Графы и алгоритмы

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

Какие из следующих графов изоморфны графу $\overline {C_5 }$ ?

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

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

$\overline {C_5 }$ (Верный ответ)

$\overline {C_3 + K_2 }$

$2K_1 \circ 3K_1$

$\overline {P_5 }$

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

Сколько различных абстрактных двудольных графов можно получить, добавляя одно ребро к графу $C_{12}$ ?

Пусть

- ребра с наименьшими весами в некотором взвешенном графе, причем $w(e_1 ) \le w(e_2 )$ . Какие из следующих утверждений верны для любого графа и любой весовой функции?

Для двудольного графа построено BFS-дерево с корнем

. Ребро графа (x,y)

дереву не принадлежит. Какие из следующих соотношений могут выполняться (

обозначает расстояние между вершинами в графе)?

Для некоторого графа построено BFS-дерево с корнем

. Ребро графа (x,y)

дереву не принадлежит. Какие из следующих соотношений могут выполняться (

обозначает расстояние между вершинами в графе)?

В графе с весовой функцией

строится каркас с помощью алгоритма Крускала. Пусть $e_1 ,e_2 , \ldots ,e_k$ - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого $i = 2,3, \ldots k$ ?

В графе с весовой функцией

строится каркас с помощью алгоритма Прима. Пусть $e_1 ,e_2 , \ldots ,e_k$ - список всех ребер каркаса в том порядке, в каком они добавлялись при построении. Какие из следующих утверждений верны для любого графа, любой весовой функции и любого $i = 2,3, \ldots k$ ?

Дан граф

с множеством ребер

. Для каких из перечисленных ниже семейств $\Phi$ подмножеств множества

пара $(E,\Phi )$ является матроидом для любого графа

Какие из следующих утверждений верны для любого графа

и любого его подграфа

Пусть каждая из функций f_1

является потоком в некоторой сети. Какие из следующих функций обязательно будут потоками в той же сети?

Дан граф

с множеством вершин

, $\Phi$ - семейство всех независимых множеств вершин этого графа (пустое множество тоже считается независимым). В каких из перечисленных ниже случаев пара $(V,\Phi )$ является матроидом,?

Графы и алгоритмы

Какие из следующих графов изоморфны графу?

Какие из следующих графов изоморфны графу $\overline {C_5 }$ ?