Главная / Алгоритмы и дискретные структуры / Графы и их применение / Тест 5

Графы и их применение - тест 5

Упражнение 1:

Номер 1

Что называется гамильтоновым путем в графе?

Ответ:

(1) путь, содержащий все ребра графа

(2) если граф можно нарисовать на плоскости так, чтобы никакие два его ребра не имели других общих точек, кроме их общей вершины, то это называют гамильтоновым путем в графе

(3) только ребра ориентированного графа

(4) замкнутая цепь, проходящая ровно один раз через каждую вершину графа

Номер 2

Что называется гамильтоновой цепью?

Ответ:

(1) замкнутая цепь, проходящая через каждое ребро графа

(2) замкнутая цепь, проходящая через каждую вершину графа

(3) разомкнутая цепь, проходящая через все вершины графа степени 1

(4) разомкнутая цепь, проходящая через каждое ребро графа

Номер 3

Какой граф называется гамильтоновым графом?

Ответ:

(1) связный граф G, если существует замкнутая цепь, проходящая через каждую вершину ровно один раз

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

(3) граф, содержащий его дополнение

(4) связный граф G, если существует замкнутая цепь, проходящая через каждую его четную вершину

Упражнение 2:

Номер 1

Какой граф является эйлеровым или гамильтоновым  графом?

Ответ:

(1) G₁ - эйлеров граф

(2) G₄ - гамильтонов граф

(3) G₂ - гамильтонов граф

(4) G₃ - эйлеров граф

Номер 2

Какой граф называется полугамильтоновым?

Ответ:

(1) если снять ограничение на замкнутость цепи, то граф называется полугамильтоновым, при этом каждый гамильтонов граф будет полугамильтоновым

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

(3) связный граф G называется полугамильтоновым, если существует замкнутая цепь, проходящая через каждое его ребро

(4) гамильтоновым графом G называется граф, ограниченный простым циклом и не содержащий внутри других циклов

Номер 3

Какой граф обладает гамильтоновым циклом?

Ответ:

(1) гамильтонов граф

(2) триангулированный граф

(3) если граф G связный и все его вершины четные, то он обладает гамильтоновым циклом

(4) если в графе существует замкнутая цепь, проходящая через каждое его ребро, то она называется гамильтоновым циклом

Упражнение 3:

Номер 1

Если в простом графе с n(≥3) вершинами ρ(v)≥n/2 для любой вершины v, то каким  является граф G?

Ответ:

(1) если в простом графе с n(≥3) вершинами ρ(v)≥n/2 для любой вершины v, то граф G является гамильтоновым

(2) граф, в котором нет петель, но есть кратные ребра

(3) граф, в котором все вершины имеют четную степень

(4) граф, в котором все вершины имеют нечетную степень

Номер 2

Каким является граф N₁?

Ответ:

(1) вырожденным гамильтоновым

(2) мультиграфом

(3) Эйлеровым

(4) полуэйлеровым

Номер 3

Каким  графом является плоское представление додекаэдра?

Ответ:

(1) гамильтоновым

(2) полуэйлеровым

(3) полугамильтоновым

(4) эйлеровым

Главная / Алгоритмы и дискретные структуры / Графы и их применение / Тест 5