Граф задан диаграммой

А) Составьте маршруты длины 5 из вершиныV2 в вершину V5. Составьте простую цепь, соединяющую эти вершины.

В) Постройте простой цикл, содержащий вершину V4.

С) Определите вид заданного графа

7.
V1
V2
V3
V4
V5
V6
V7

10.
V1
V2
V3
V4
V5
V6
V7

8.

V7
V1
V2
V3
V4
V5
V6

V1
V2
V3
V4
V5
V6
V1
V2
V3
V4
V5
V6
V7

11.

V1
V2
V3
V4
V5
V6
V7

9.   12.  

Задание: Выполните задание по теме: Понятие дерева в теории графов:

13. Сколько различных способов обедов можно выбрать в вагоне-ресторане, если бы на каждый обед выбирать одно холодное блюдо, одно первое, одно второе, одно третье? В меню на этот раз были выставлены студень, красная икра, свежепосоленная рыба; на первое – уха из стерляди, щи с грибами; на второе – осетрина жаренная, теленок жареный на вертеле; на третье – арбузы, груши.   16. Перечислите все возможные сочетания деловой одежды, если у вас в гардеробе брючный костюм черного цвета, белая и голубая блузки, синяя юбка и серый джемпер.  
14. Изобразите дерево возможных исходов при троекратном бросании монеты. 17. Волейбольная сетка имеет вид прямоугольника размером 5×10 клеток. Какое наибольшее число верёвочек можно перерезать так, чтобы сетка не распалась на куски?
15. Нарисуйте граф с семью вершинами, в котором для любых двух вершин существует только один связывающий их путь.   18. Рассади участников «Большой восьмерки» за круглым столом всеми возможными способами.  

Задание: Графы и логические задачи:

19. В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что: · Вода и молоко не в бутылке. · Сосуд с лимонадом стоит между кувшином и сосудом с квасом. · В банке не лимонад и не вода. · Стакан стоит между банкой и сосудом с молоком. В каком сосуде находится, какая из жидкостей?   22. Какое наименьшее число переливаний необходимо для того, чтобы с помощью 7-и 11-литровых сосудов и крана с водой отмерить 2 литра?    
20. На улице, встав в кружок, беседуют Аня, Валя, Галя и Надя. · Девочка в зеленом платье – не Аня и не Валя – стоит между девочкой в голубом платье и Надей. · Девочка в белом платье стоит между девочкой в розовом и Валей. Какого цвета платье у каждой из девочек?   23. В семье четверо детей. Им 5, 8, 13 и 15 лет. Зовут их Аня, Боря, Вера и Галя. Сколько лет каждому ребенку, если одна девочка ходит в детский сад, Аня старше Бори, а сумма лет Ани и Веры делится на три?  
21. В Артеке за круглым столом оказалось пятеро ребят из Москвы, Санкт-Петербурга, Новгорода, Перми и Томска: Юра, Толя, Алеша, Коля и Витя. Москвич сидел между Томичем и Витей, санкт-петербуржец – между Юрой и Толей, а напротив него сидел пермяк и Алеша. Коля никогда не был в Санкт-Петербурге, Юра не бывал в Москве и Томске, а Томич с Толей регулярно переписываются. Определите, кто в каком городе живет.   24. Беседуют трое друзей – Белокуров, Рыжов и Чернов. Брюнет сказал Белокурову: «Любопытно, что один из нас – блондин, другой – брюнет, третий – рыжий, но ни у кого цвет волос не соответствует фамилии». Какой цвет волос у каждого из друзей?  

Задание: Выполните задание по теме: Сетевые графы: В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Числа, стоящие на пересечениях строк и столбцов означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите схему, соответствующую таблице.



25.
  A B C D E F
A          
B    
C        
D        
E    
F          
28.
  A B C D E F
A          
B    
C        
D        
E    
F          
26.
  А В С D
А    
В  
С      
D    
29.
  A B C D E F
A          
B    
C        
D        
E    
F          
27.
  А В С D Е
А    
В      
С      
D        
E      
30.
  А В С D Е
А      
В      
С    
D        
E        

Пояснения к работе:

Необходимые формулы:

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

Если ребра ориентированны, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом.

Если ребра не имеют ориентации, граф называется неориентированным.

граф задан диаграммой - student2.ru

Петля- это дуга, начальная и конечная вершина которой совпадают.

Простой граф- граф без кратных ребер и петель.

Степень вершины- это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер.

Пустым называется граф без ребер.

Полным называется граф, в котором каждые две вершины смежные.

Путь в ориентированном графе — это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.

Маршрут в графе путь, ориентацией дуг которого можно пренебречь.

Цепь- маршрут, в котором все ребра попарно различны.

Цикл- замкнутый маршрут, являющийся цепью.

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

Дерево— это связный граф без циклов.

Содержание отчета

1. Титульный лист в соответствии с СТП1.2-2005.

2. Цель работы

3. Задание

4. Выполненная практическая работа в соответствии с заданием

5. Ответы на контрольные вопросы

6. Вывод

Контрольные вопросы:

1. Дайте определение графа.

2. Сформулируйте понятие смежных ребер.

3. Дайте определение правильного графа.

4. Запишите формулу суммы степеней графа.

5. Дайте определение изолированной вершины графа.

Наши рекомендации