Практическая работа по теме: «Графы. Способы задания графов. Степени вершин»

1 вариант

2 вариант

Часть А

1

Точки графа называются...

а) рёбрами графа;

б) пунктами графа;

в) вершинами графа

г) узлами графа.

Граф - это...

а) множество точек, две из которых обязательно соединяются линиями;

б) множество точек, которые никогда не соединяются линиями;

в) только две точки, которые соединяются линиями;

г) множество точек, которые могут соединяться линиями.

2

Линии, которые связывают вершины, называются...

а) сторонами графа; б) вершинами графа;

в) рёбрами графа; г) отрезками.

Какого элемента нет в графах?

а) ребра; б) вершины; в) высоты;
г) все элементы присутствуют.

3

Как называется направленная линия (со стрелкой)?

А) дуга Б) ребро В) вершина

Как называется направленная линия (со стрелкой)?

А) дуга Б) ребро В) вершина

Как называется направленная линия (со стрелкой)?

А) дуга Б) ребро В) вершина

Как называется направленная линия (со стрелкой)?

А) дуга Б) ребро В) вершина

Как называется направленная линия (со стрелкой)?

А) дуга Б) ребро В) вершина

Как называется направленная линия (со стрелкой)?

А) дуга Б) ребро В) вершина

Как называется направленная линия (со стрелкой)?

А) дуга Б) ребро В) вершина

Как называется направленная линия (со стрелкой)?

А) дуга Б) ребро В) вершина

Как называется направленная линия (со стрелкой)?

а) дуга; б) ребро; в) вершина.

ак называется направленная линия (со стрелкой)?

А) дуга Б) ребро В) вершина

Как называется ненаправленная линия (без стрелки)Что является наглядным средством представления и

структуры системы?

Как называется ненаправленная линия (без стрелки)?

а) дуга; б) ребро; в) вершина.

4

Изобразите графически полный ориентированный граф на 6 вершинах.

Изобразите графически полный ориентированный граф на 4 вершинах.

5

Изобразите графически неполный ориентированный граф на 4 вершинах.

Изобразите графически неполный ориентированный граф на 6 вершинах.

6

Сколько рёбер имеет полный граф с пятью вершинами?

Сколько рёбер имеет полный граф с шестью вершинами?

7

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

1) предприятие А установило договорные отношения со всеми другими предприятиями;

2) Б установило с Г и Д;

3) В установило со всеми предприятиями, кроме предприятия Е.

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

Изобразите с помощью графа договорные отношения между

предприятиями А, Б, В, Г, Д, Е, если к рассматриваемому моменту:

1) предприятие В установило договорные отношения со всеми другими предприятиями;

2) А установило с Г и Д;

3) Б установило со всеми предприятиями, кроме предприятия Д.

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

а) 5 вершин ,10 рёбер ; б) 6 вершин ,11 рёбер ; в) 6 вершин , 10 рёбер ; г) 5 вершин ,12 рёбер.

8

В соревнованиях по футболу участвуют 6 команд. Каждую из команд обозначили A,B, C, D, E, F.Определите по графу, какие из команд уже сыграли друг с другом. Сколько матчей сыграла каждая команда?

9

Определите вид графа:

а) неограф ; б) мультиграф ; в) псевдограф ; г) орграф .

10

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

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

11

Вершина графа нулевой степени называется:

Вершина графа первой степени называется:

а) висячей ;б) доминирующей ;в) изолированной.

12

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

Б

В

А

Д Г

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

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

13

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

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

14

Дан граф:

Степень вершины 1 равна: а) 3; б) 4; в) 5; г) 6;

15

По матрицам смежности определить какие из неографов являются полными:

а) 1,2 ;б) 3 ;в) 3 ,4 ; г) 4.

16

В таблицах приведена стоимость перевозки грузов между соседними станциями. Если пересечение строки и столбца пусто, то соответствующие станции не являются соседними. Укажите номер таблицы, для которой выполняется условие «Максимальная стоимость перевозки грузов от пункта В до пункта D не больше 6»

1 2 3 4

В таблице приведена стоимость перевозки пассажиров между соседними населенными пунктами. Укажите схему, соответствующую таблице.

а) 3;б) 1,3;в) 1,2,4; г) 2.

а) 1;б) 1,3;в) 1,2,4; г) 4.

17

Путешественник оказался в аэропорту ОСТРОВ в полночь (0:00).

Определите самое раннее время, когда он может попасть в аэропорт СИНЕЕ.

В одной сказочной стране всего 5 городов, которые соединены между собой непересекающимися магистралями. Расход топлива для каждого отрезка и цены на топливо приведены в таблице:

Проезд по магистралям возможен в обоих направлениях, однако в стране действует закон: выезжая из города А, путешественник обязан на весь ближайший отрезок до города Б закупить топливо по ценам, установленным в городе А. Определите самый дешевый маршрут из АИСТОВО в ЕНОТОВО.

а) 11:35;б) 16:10 ;в) 16:20; г) 9:50.

а) АИСТОВО - ЦАПЛИНО - БЫКОВО – ЕНОТОВО; б) АИСТОВО - ДРОНТОВО – ЕНОТОВО;

в)АИСТОВО - ЦАПЛИНО - ДРОНТОВО – ЕНОТОВО; г)АИСТОВО - БЫКОВО – ЕНОТОВО.

Часть Б

18

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

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

19

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

20

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет).

Определите длину кратчайшего маршрута из А в F.

Определите длину кратчайшего маршрута из А в B.

21

На рисунке приведена весовая матрица графа. Определите, сколько рёбер имеет такой граф.

22

На рисунке приведена весовая матрица графа, в которой веса обозначают расстояния между соседними пунктами.

Определите длину маршрута C-A-E-D-B.

Определите длину маршрута E-D-C-A.

23

Найти кратчайший путь от вершины 1 к вершине 5 графа, представленного на рисунке:

В графе G, показанном на рис. удалить дугу (х₃,х₂).

Результат представлен в матричном виде :

24

Изобразите графически: орграф G(V,E) V={1,2,3,4,5}, E={(1,2),(4,3),(3,5),(5,1),(4,1)}.

Изобразите графически: орграф G(V,E) V={1,2,3,4,5}, E={(1,3),(2,3),(1,5),(2,4),(1,2)}.

25

Изобразите графически: неограф G(V,E) V = {1; 2; 3; 4; 5; 6} E = {(1; 2); (1; 5); (2; 3); (3; 1); (3; 4); (4; 2); (4; 5); (4; 6); (5; 3) }.

Изобразите графически: неограф V = {1; 2; 3; 4; 5; 6} E = {(1; 2); (1; 3); (2; 3); (3; 1); (3; 6); (4; 2); (4; 5); (4; 6); (5; 1)}.

26

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

V = {1; 2; 3; 4; 5; 6};

E = {a; b; c; d; e}

E = {(1; 3); (1; 4); (1; 6); (2; 3);(4; 5)}

V = {1; 2; 3; 4; 5; 6};

E = {a; b; c; d; e}

E = {(1; 5); (2; 4); (2; 5); (3; 4);(5; 6)}

27

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