Дискретный анализ - тест 15

Укажите множество, с которым у множества деревьев с  вершинами имеется взаимнооднозначное соответствие:

 (1) множество слов длины в алфавите из символов 

 (2) множество слов длины в алфавите из символов 

 (3) множество слов длины в алфавите из символов 

 (4) множество слов длины в алфавите из символов 

Какой способ наиболее эффективен при подсчете количества деревьев:

Количество слов длины  в алфавите из  символов равно:

 (1)  

 (2)  

 (3)  

 (4)  

Количество слов длины  в алфавите из  символов, причем каждый символ входит в это слово, равно:

 (1)  

 (2)  

 (3)  

 (4)  

Множество деревьев на  вершинах с  концевыми вершинами имеет взаимнооднозначное соответствие с этим множеством:

 (1) множество слов длины в алфавите из символов 

 (2) множество слов длины в алфавите из символов, причем каждый символ в это слово входит 

 (3) множество слов длины в алфавите из символов, причем каждый символ в это слово входит 

 (4) множество слов длины в алфавите из символов 

Какие из методов доказательства применяются при подсчете количества деревьев на  вершинах с  концевыми вершинами:

Сколько существует деревьев на 3 вершинах с 2 концевыми вершинами:

Сколько существует деревьев на 4 вершинах с 2 концевыми вершинами:

Сколько существует деревьев на 6 вершинах с 4 концевыми вершинами:

Какова первоначальная формулировка задачи о кенигсбергских мостах:

В формулировке задачи о кенигсбергских мостах в терминах теории графов:

Формулировка задачи о кенигсбергских мостах в терминах теории графов выглядит так:

По определению, эйлеров путь для конечного неориентированного графа -это:

В каких задачах встречаются эйлеровы пути

Конечный граф - это граф, у которого:

В конечном неориентированном графе эйлеров путь существует тогда и только тогда, когда:

Началом и концом эйлерова пути могут быть вершины:

Эйлеров путь может существовать в графе, количество вершин нечетной степени в котором:

Как соотносятся между собой эйлеровы пути и эйлеровы циклы в графе:

Конечный неориентрованный граф имеет эйлеров цикл тогда и тольо тогда, когда:

Оцените сложность алгоритма построения эйлерова цикла в графе с количеством вершин  и количеством ребер :

Чем замечательны эйлеровы пути и эйлеровы циклы на практике:

Гамильтонов путь на простом неориентрованном графе - это:

Путь имеет тип цикла, если:

Некоторый простой путь называется полным, если: 

Полный простой путь длины  имеет тип цикла, если выполняется условие:

Полным максимальным путем называют:

Максимальный полный путь в связном графе имеет тип цикла тогда и только тогда, когда:

Продолжите утверждение: "В связном графе либо имеется гамильтонов цикл, либо:

Каким свойством обладает длина максимальных путей в графе без гамильтоновых циклов:

Укажите достаточное условие существования гамильтонова пути в графе с  вершинами:

 (1) для любой пары вершин сумма степеней этих вершин не менее чем  

 (2) для любой пары вершин сумма степеней этих вершин более чем  

 (3) для любой пары вершин сумма степеней этих вершин не менее чем  

Укажите достаточное условие существования гамильтонова цикла в графе с  вершинами:

 (2) для любой пары вершин сумма степеней этих вершин не менее чем  

 (3) для любой пары вершин сумма степеней этих вершин более чем  

Какова максимальная длина простого пути в графе с  вершинами:

 (1)  

 (2)  

 (3)  

 (4)  

Если степень каждой из вершин графа строго больше половины количества вершин графа, то:

Степенной последовательностью графа называют:

Простой граф, имещий две вершины степени 3, соединенные тремя непересекающимися путями длины не менее 2, называется:

Укажите верные утверждения:

Для какого графа наименьшее количество вершин, удаление которых приводит к несвязному или одновершинному графу, равно двум:

Граф называется гамильтоновым, если он:

Граф называется негамильтоновым, если он:

Двухсвязный негамильтонов граф:

Для какого графа наименьшее количество вершин, удаление которых приводит к несвязному или одновершинному графу, равно трем:

Какой граф называют плоским:

Любой четырехсвязный планарный граф:

Любой планарный граф:

Вес ребра - это:

Длина пути в ориентированном графе с весами ребер - это:

Кратчайший путь - это:

Расстояние от одной вершины графа до другой - это:

В каких задачах применяются ориентированные графы с весами ребер:

Определите сложность решения задачи поиска кратчайших путей в орграфе без циклов отрицательной длины,  - количество вершин графа

 (1)  

 (2)  

 (3)  

Определите сложность решения задачи поиска кратчайших путей в графе с неотрицательными весами ребер  - количество вершин графа:

 (1)  

 (2)  

 (3)  

Определите сложность решения задачи поиска кратчайших путей в графе без циклов,  - количество вершин графа:

 (1)  

 (2)  

 (3)  

Процедура перенумерации вершин графа так, чтобы номер вершины, куда ведет ребро, был больше, чем номер вершины-предшественника, называется: