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

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

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

Номер 1

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

Ответ:

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

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

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

(4) только граф, степени вершин которого равны 1

Номер 2

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

Ответ:

(1) граф, изоморфный плоскому графу

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

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

(4) если у него любые две вершины смежны

Номер 3

Что называют гранью в плоском представлении графа?

Ответ:

(1) обхват графа

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

(3) его дополнение

(4) его радиус

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

Номер 1

Что называется перегородками в графе?

Ответ:

(1) ребра, соединяющие циклы

(2) мосты, соединяющие циклы

(3) бесконечная грань

(4) диаметр графа

Номер 2

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

Ответ:

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

(2) два графа гомеоморфны, если они планарны

(3) два графа гомеоморфны, если они плоские

(4) два графа гомеоморфны, если они простые и плоские

Номер 3

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

Ответ:

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

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

(3) если он имеет только висячие вершины

(4) если он не имеет петель

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

Номер 1

Какое выражение является формулой Эйлера (здесь V - число вершин в графе, E - число ребер, а R - число граней)?

Ответ:

(1) V-E+R=2

(2) V-E+R=2+2E

(3) 3R≤2E

(4) 2E=20

Номер 2

Какие грани в графе называются соседними?

Ответ:

(1) две грани в графе, если они имеют одну общую вершину

(2) две грани, если они ограничены неориентированными ребрами

(3) две грани, если число их вершин строго равно числу ребер

(4) две грани, если их границы имеют хотя бы одно общее ребро

Номер 3

Сколько бесконечных граней имеет всякое плоское представление графа?

Ответ:

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

(2) бесконечное множество

(3) столько, сколько у него ребер

(4) столько, сколько у него вершин

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