Главная / Алгоритмы и дискретные структуры /
Графы и их применение / Тест 4
Номер 3
Ответ:
Графы и их применение - тест 4
Упражнение 1:
Номер 1
Ответ:
Номер 1
Что называется эйлеровым путем в графе?
Ответ:
(1) путь, содержащий все ребра графа
(2) путь, который можно нарисовать на плоскости так, чтобы никакие два его ребра не имели других общих точек, кроме общей вершины
(3) только ребра ориентированного графа
(4) путь, содержащий все ребра графа, степени смежных вершин которых равны 1
Номер 2
Ответ:
Что называется эйлеровой цепью?
Ответ:
(1) цепь, проходящая через каждое ребро графа
(2) цепь, проходящая через каждую вершину графа
(3) разомкнутая цепь, проходящая через все вершины графа степени 1
(4) разомкнутая цепь, проходящая через каждое ребро графа
Какой граф называется эйлеровым графом?
Ответ:
(1) связный граф
G, если существует замкнутая цепь, проходящая через каждое его ребро
(2) граф, ограниченный простым циклом и не содержащий других циклов
(3) граф
G, содержащий его дополнение
(4) связный граф
G, если существует замкнутая цепь, проходящая через каждую его вершину
Упражнение 2:
Номер 2
Ответ:
Номер 2
Какой граф называется полуэйлеровым?
Ответ:
(1) если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым, при этом каждый эйлеров граф будет полуэйлеровым
(2) связный граф
G будет полуэйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро
(3) связный граф
G называется полуэйлеровым, если существует замкнутая цепь, проходящая через каждую его вершину
(4) эйлеровым графом
G называется граф, ограниченный простым циклом и не содержащий других циклов
Номер 3
Ответ:
Какой граф обладает эйлеровым циклом?
Ответ:
(1) эйлеров граф
(2) триангулированный граф
(3) если граф
G связный и все его вершины четные, то он обладает эйлеровым циклом
(4) если в графе существует замкнутая цепь, проходящая через каждое его ребро, он называется эйлеровым циклом
Упражнение 3:
Номер 1
Ответ:
Номер 1
Какой граф называется мультиграфом?
Ответ:
(1) граф, в котором не допускаются петли, но пары вершин могут соединяться более чем одним ребром. Эти ребра называются кратными, а граф – мультиграфом
(2) граф, в котором нет петель, но есть кратные ребра
(3) граф, в котором все вершины имеют четную степень
(4) граф, в котором все вершины имеют нечетную степень
Номер 2
Ответ:
Может ли связный граф обладать эйлеровым путем, еслиvaиvb- единственные нечетные его вершины?
Ответ:
(1) если граф
G связный и va и vb единственные нечетные вершины его, то граф G обладает эйлеровым путем с концами va и vb
(2) граф обладает эйлеровым путем, если его грани ограничены неориентированными ребрами
(3) граф обладает эйлеровым путем, если у него число вершин строго равно числу ребер
(4) граф обладает эйлеровым путем, если он имеет бесконечную грань
Номер 3
Ответ:
Решение каждого ли лабиринта может быть найдено?
Ответ:
(1) безвыходных лабиринтов нет
(2) существует бесконечное множество решений
(3) да
(4) нет