No Image

Тест по теории графов с ответами

СОДЕРЖАНИЕ
216 просмотров
11 марта 2020

Тест проверяет знания по теме "Теория графов"

Скачать:

Вложение Размер
test_.docx 36.48 КБ

Предварительный просмотр:

Тема: Теория графов

1.1. На рисунке изображен :

а ) Полный граф; б) неполный граф; в) граф типа «дерево» г) нулевой;

1.2. Полный граф имеет 7 вершин, то количество ребер будет равно:

а) 14; б) 21; в) 7; г) 42.

1.3. Какие из указанных в графе на рисунке маршрутов являются путем?

а) АВГВД б) АВГ в) АВДАБ г) АБВАД

1.4. Какие из указанных циклов являются простыми ?

а) АВГА б) АБВГБА; в) ВБАГВ; г) ДВАГВД

1.5. Хроматическое число графа на рисунке равно:

а) 3; б) 6; в) 4; г) 2.

2.1. Сколько ребер нужно провести чтобы достроить граф, изображенный на рисунке до полного?

2.2. Назвать наибольшее число висячих вершин, дерева с 10-ю вершинами .

2.3. Укажите критерий эйлеровости графа.

3. 1 . Изобразите с помощью графа договорные отношения между предприятиями А, Б, В, Г, Д, Е, если к рассматриваемому моменту:
предприятие А установило договорные отношения со всеми другими предприятиями;
Б установило с Г и Д;
В установило со всеми предприятиями, кроме предприятия Е.
Сколько вершин и сколько ребер имеет полученный граф?

3.2. Представьте выражение 14+с*а помощью ориентированного упорядоченного дерева.

Тема: Теория графов

1.1. На рисунке изображен :

а ) Полный граф; б) неполный граф; в) граф типа «дерево» г) нулевой;

1.2. Полный граф имеет 9 вершин, то количество ребер будет равно:

а) 18; б) 72; в) 9; г) 36.

1.3. Какие из указанных в графе на рисунке маршрутов являются путем?

а) АВГВБ б) АВГВ в) АВДАГ г) АБВ

1.4. Какие из указанных циклов являются простыми ?

а) АВГДВА б) АБВГВА; в) ВБАГВ; г) ДВАГВД

1.5. Хроматическое число графа на рисунке равно:

а) 3; б) 6; в) 4; г) 2.

2.1. Сколько ребер нужно провести, чтобы достроить граф, изображенный на рисунке, до полного?

2.2. Назвать наименьшее число висячих вершин, дерева с 15-ю вершинами

2.3. Сформулируйте достаточные условия гамильтоновости графа.

3.1. Среди семи стран установлены экономические отношения, причем каждая страна имеет экономические договоры с каждой другой страной. Изобразите в виде графа результат установленных экономических отношений. Сколько вершин и ребер имеет полученный граф?

3.2. Представьте выражение 25: (а-в) с помощью ориентированного упорядоченного дерева.

Тест: Основы теории графов

пара двух бесконечных множеств: множество точек и множество линий, соединяющих некоторые пары точек;

множество линий, соединяющих некоторые пары точек;

пара двух конечных множеств: множество точек и множество линий.

инцидентны одной и той же вершине;

Какие из графов являются подграфами данного графа G:

В полуэйлеровом графе допускаются

3 вершины нечетной степени;

2 вершины нечетной степени;

1 вершина нечетной степени.

маршрут минимальной стоимости;

маршрут, где нет повторяющихся вершин;

маршрут, где нет повторяющихся ребер;

маршрут, где нет повторяющихся вершин и ребер.

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

Последовательность ребер, в которой каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза – это…

Для того, чтобы конечный связный граф был деревом, необходимо и

достаточно, чтобы число его ребер было:

Больше или равно числу его вершин

Равно числу его вершин

На единицу больше числа его вершин

На единицу меньше числа его вершин

Цикломатическое число дерева равно нулю.

Цикломатическое число леса равно нулю.

Цикломатическое число леса равно всегда положительно

Для остальных графов цикломатические числа — отрицательные.

Выберите верные утверждения.

В матрице инцидентности для неориентированного графа:

bij = 1, если вершина Vi инцидентна ребру Xj;

bij = 0, если вершина Vi инцидентна ребру Xj;

bij = -1, если вершина Vi не инцидентна ребру Xj;

bij = 0, если вершина Vi не инцидентна ребру Xj.

Выберите верные утверждения.

В матрице инцидентности для ориентированного графа:

bij = 1, если вершина Vi является началом дуги Xj;

bij = -1, если вершина Vi является концом дуги Хj;

bij = 0, если вершина Vi является концом дуги Хj;

bij = 0, если вершина Vi не инцидентна дуге Xj.

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?

Читайте также:  Почему некоторые видео на youtube без звука

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К ?

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Рыцарь, находясь в пункте А, узнал, что Прекрасной Даме, в пункте К, через 14 часов может грозить опасность. Взяв с собой карту, он немедленно выехал на помощь. Числа на рисунке обозначают время движения (в часах) от пункта до пункта. Успеет ли рыцарь спасти Прекрасную Даму? (Ответ запишите в форме: Нет АБЕК 17 или Да АБЕК 17)

Винни-Пух вышел на прогулку, взяв с собой карту. Числа на рисунке обозначают время движения (в минутах) от пункта до пункта. Помогите Винни-Пуху найти кратчайший путь от своего дома в пункте А до дома Пятачка в пункте К. Перечислите пункты, через которые должен пройти Винни-Пух, и подсчитайте время, которое он затратит на весь путь. (Ответ запишите в форме: АВЖЗДК 80)

Атос поскакал в гости к Портосу, взяв с собой карту. Числа на рисунке обозначают время движения (в часах) от пункта до пункта. Помогите Атосу найти кратчайший путь от своего поместья в пункте Е до поместья Портоса в пункте Д. Перечислите пункты, через которые должен проехать Атос, и подсчитайте время, которое он затратит на весь путь. (Ответ запишите в форме: ЕКЗИГД 20)

Рыцарь, находясь в пункте А, узнал, что Прекрасной Даме, в пункте О, ровно через сутки может грозить опасность. Взяв с собой карту , он немедленно выехал на помощь. Числа на рисунке обозначают время движения (в часах) от пункта до пункта. Успеет ли рыцарь спасти Прекрасную Даму? Обоснуйте ответ, указав кратчайший маршрут и время, затраченное на весь путь. (Ответ запишите в форме: Нет АБВГО 38 или Да АБВГО 38)

Какое минимальное количество рёбер нужно убрать из полного графа с 15 вершинами, чтобы он перестал быть связным?

число связных компонент графа

число его ребер

Последовательность ребер не­ориентированного графа, в которой вторая вершина предыдуще­го ребра совпадает с первой вершиной следующего

Маршрут , в котором ребро встречается только один раз

ребер ориентированного графа, в которой конец предыдущего ребра совпадает с началом следующего и все ребра единственны

Путь, у которого совпадают начало и конец

Любые подграфы связного графа, содержащие все вершины графа G и являющиеся деревом

Графы, между любыми двумя вершинами которых есть маршрут

Графы, которые имеют изоморфные им графы, в изображении которых на плоскости ребра пересекаются только в вершинах

Графы, имеющие взаимно-однозначное соответствие между их ребрами и вершинами, причем со-ответствующие ребра соединяют соответствующие вершины

Граф со смежными вершинами

Граф со смежными ребрами

Строго бинарное дерево

Бинарное дерево, каждый узел уровня n которого является листом, а каждый узел уровня меньше, чем n, имеет непустое левое и правое поддеревья.

Полное бинарное дерево

подмножество множества деревьев, когда каждый узел либо является листом, либо образует два поддерева: левое и правое.

Читайте также:  Портативная колонка своими руками схема

дерево, в котором поддеревья каждого узла образуют упорядоченное подмножество.

такой граф, у которого каждый узел, не являющийся листом, содержит два и только два поддерева — левое и правое.

Укажите степени вершин графа

Укажите степени вершин графа

Укажите степени вершин графа

Укажите степени вершин графа

Найдите цикломатическое число графа G

Найдите цикломатическое число графа G

Найдите цикломатическое число графа G

Найдите цикломатическое число графа G

Найдите цикломатическое число графа G

100 тестовых заданий по теме "Основы теории графов"

Из базы заданий случайным образом выбираются 10 заданий.

В сборнике присутствуют задания в закрытой и открытой формах, задания на установление соответствия и т.д.

Предназначен для студентов 2 курса СПО специальности Прикладная информатика (по отраслям)

  • Лебедев Вадим СергеевичНаписать 2641 11.12.2017

Номер материала: ДБ-947515

    11.12.2017 1540
    10.12.2017 378
    10.12.2017 453
    10.12.2017 369
    10.12.2017 203
    10.12.2017 223
    10.12.2017 1882
    10.12.2017 187

Не нашли то что искали?

Вам будут интересны эти курсы:

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение редакции может не совпадать с точкой зрения авторов.

Ответственность за разрешение любых спорных моментов, касающихся самих материалов и их содержания, берут на себя пользователи, разместившие материал на сайте. Однако редакция сайта готова оказать всяческую поддержку в решении любых вопросов связанных с работой и содержанием сайта. Если Вы заметили, что на данном сайте незаконно используются материалы, сообщите об этом администрации сайта через форму обратной связи.

Список вопросов теста

Вопрос 1

На ри­сун­ке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж и К. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном на­прав­ле­нии, ука­зан­ном стрел­кой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город К?

Варианты ответов
  • 12
  • 13
  • 9
  • 5
Вопрос 2

Выберите один из 4 вариантов ответа:

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

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

Выберите несколько из 5 вариантов ответа:

Варианты ответов
  • символы.
  • графические изображения.
  • числа.
  • муззыка.
  • текст
Вопрос 4

Выберите один из 4 вариантов ответа:

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

Выберите один из 4 вариантов ответа:

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

Выберите один из 4 вариантов ответа:

Варианты ответов
  • совокупность объектов со связями между ними.
  • граф с циклом.
  • граф, в котором нет циклов, то есть в нём нельзя из некоторой вершины пройти по различным рёбрам и вернуться в ту же вершину.
  • информационная модель, имеющая вид графа, вершинам которого соответствуют определённые объекты, а рёбра задают отношения между ними.
Вопрос 7

Дайте определение понятию "Граф".

Выберите один из 3 вариантов ответа:

Варианты ответов
  • Граф – это условное графическое изображение предмета с точными соотношениями его размеров, получаемое методом моделирования.
  • Граф – это совокупность объектов со связями между ними.
  • Граф – это графическое отображение состава и структуры сложной системы.
Вопрос 8

Взвешенный граф – это.

Выберите один из 4 вариантов ответа:

Варианты ответов
  • граф, в котором нет циклов.
  • путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза.
  • граф, в котором вершины или рёбра характеризуются некоторой дополнительной информацией.
  • граф с циклом.
Читайте также:  Естественный заземлитель что это
Вопрос 9

Какой тип графа изображён на рисунке?

Выберите один из 4 вариантов ответа:

Варианты ответов
  • Цепь.
  • Взвешенный граф.
  • Семантическая сеть.
  • Цикл.
Вопрос 10

Семантическая сеть – это.

Выберите один из 4 вариантов ответа:

Варианты ответов
  • цепь, в которой начальная и конечная вершины совпадают.
  • совокупность объектов со связями между ними.
  • граф с циклом.
  • информационная модель, имеющая вид графа, вершинам которого соответствуют определённые объекты, а рёбра задают отношения между ними.
Вопрос 11

Выберите один из 4 вариантов ответа:

Варианты ответов
  • путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза.
  • граф, в котором вершины или рёбра характеризуются некоторой дополнительной информацией.
  • граф, в котором нет циклов
  • граф с циклом.
Вопрос 12

Какой тип графа изображён на рисунке, если при рисовании данного графа нельзя отрывать ручку от бумаги?

Выберите один из 4 вариантов ответа:

Варианты ответов
  • Цепь.
  • Взвешенный граф.
  • Семантическая сеть.
  • Цикл.
Вопрос 13

Выберите один из 4 вариантов ответа:

Варианты ответов
  • граф с циклом.
  • цепь, в которой начальная и конечная вершины совпадают.
  • граф, в котором вершины или рёбра характеризуются некоторой дополнительной информацией.
  • информационная модель, имеющая вид графа, вершинам которого соответствуют определённые объекты, а рёбра задают отношения между ними.
Вопрос 14

Выберите один из 4 вариантов ответа:

Варианты ответов
  • граф, в котором вершины или рёбра характеризуются некоторой дополнительной информацией.
  • цепь, в которой начальная и конечная вершины совпадают.
  • информационная модель, имеющая вид графа, вершинам которого соответствуют определённые объекты, а рёбра задают отношения между ними.
  • путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза.
Вопрос 15

На рисунке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж и К. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном направлении, ука­зан­ном стрелкой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город К?

Варианты ответов
  • 8
  • 10
  • 15
  • 12
Вопрос 16

На рисунке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж и К. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном направлении, ука­зан­ном стрелкой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город К?

Варианты ответов
  • 10
  • 20
  • 14
Вопрос 17

На рисунке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, Ж и К. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном направлении, ука­зан­ном стрелкой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город К?

Варианты ответов
  • 10
  • 15
  • 19
Вопрос 18

На рисунке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, К. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном направлении, ука­зан­ном стрелкой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город К?

Варианты ответов
  • 7
  • 12
  • 17
Вопрос 19

На рисунке — схема дорог, свя­зы­ва­ю­щих го­ро­да А, Б, В, Г, Д, Е, К. На ри­сун­ке изоб­ра­же­на схема соединений, свя­зы­ва­ю­щих пунк­ты А, В, С, D, Е, F, G, Н. По каж­до­му со­еди­не­нию можно дви­гать­ся толь­ко в одном направлении, ука­зан­ном стрелкой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из пунк­та А в пункт Н?

Варианты ответов
  • 9
  • 13
  • 17
Вопрос 20

На ри­сун­ке изоб­ра­же­на схема соединений, свя­зы­ва­ю­щих пунк­ты А, В, С, D, Е, F, G, Н. По каж­до­му со­еди­не­нию можно дви­гать­ся толь­ко в одном направлении, ука­зан­ном стрелкой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из пунк­та А в пункт Н?

Варианты ответов
  • 4
  • 7
  • 8
Вопрос 21

На рисунке — схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном направлении, ука­зан­ном стрелкой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да А в город G?

Варианты ответов
  • 12
  • 20
  • 8
Вопрос 22

На ри­сун­ке изоб­ра­же­на схема дорог, свя­зы­ва­ю­щих го­ро­да A, B, C, D, E, F, G. По каж­дой до­ро­ге можно дви­гать­ся толь­ко в одном направлении, ука­зан­ном стрелкой. Сколь­ко су­ще­ству­ет раз­лич­ных путей из го­ро­да A в город D?

Комментировать
216 просмотров
Комментариев нет, будьте первым кто его оставит

Это интересно
Adblock detector