А) Составьте маршруты длины 5 из вершиныV2 в вершину V5. Составьте простую цепь, соединяющую эти вершины.
В) Постройте простой цикл, содержащий вершину V4.
С) Определите вид заданного графа
Задание: Выполните задание по теме: Понятие дерева в теории графов:
| 13. | Сколько различных способов обедов можно выбрать в вагоне-ресторане, если бы на каждый обед выбирать одно холодное блюдо, одно первое, одно второе, одно третье? В меню на этот раз были выставлены студень, красная икра, свежепосоленная рыба; на первое – уха из стерляди, щи с грибами; на второе – осетрина жаренная, теленок жареный на вертеле; на третье – арбузы, груши. | 16. | Перечислите все возможные сочетания деловой одежды, если у вас в гардеробе брючный костюм черного цвета, белая и голубая блузки, синяя юбка и серый джемпер. |
| 14. | Изобразите дерево возможных исходов при троекратном бросании монеты. | 17. | Волейбольная сетка имеет вид прямоугольника размером 5×10 клеток. Какое наибольшее число верёвочек можно перерезать так, чтобы сетка не распалась на куски? |
| 15. | Нарисуйте граф с семью вершинами, в котором для любых двух вершин существует только один связывающий их путь. | 18. | Рассади участников «Большой восьмерки» за круглым столом всеми возможными способами. |
Задание: Графы и логические задачи:
| 19. | В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что: · Вода и молоко не в бутылке. · Сосуд с лимонадом стоит между кувшином и сосудом с квасом. · В банке не лимонад и не вода. · Стакан стоит между банкой и сосудом с молоком. В каком сосуде находится, какая из жидкостей? | 22. | Какое наименьшее число переливаний необходимо для того, чтобы с помощью 7-и 11-литровых сосудов и крана с водой отмерить 2 литра? |
| 20. | На улице, встав в кружок, беседуют Аня, Валя, Галя и Надя. · Девочка в зеленом платье – не Аня и не Валя – стоит между девочкой в голубом платье и Надей. · Девочка в белом платье стоит между девочкой в розовом и Валей. Какого цвета платье у каждой из девочек? | 23. | В семье четверо детей. Им 5, 8, 13 и 15 лет. Зовут их Аня, Боря, Вера и Галя. Сколько лет каждому ребенку, если одна девочка ходит в детский сад, Аня старше Бори, а сумма лет Ани и Веры делится на три? |
| 21. | В Артеке за круглым столом оказалось пятеро ребят из Москвы, Санкт-Петербурга, Новгорода, Перми и Томска: Юра, Толя, Алеша, Коля и Витя. Москвич сидел между Томичем и Витей, санкт-петербуржец – между Юрой и Толей, а напротив него сидел пермяк и Алеша. Коля никогда не был в Санкт-Петербурге, Юра не бывал в Москве и Томске, а Томич с Толей регулярно переписываются. Определите, кто в каком городе живет. | 24. | Беседуют трое друзей – Белокуров, Рыжов и Чернов. Брюнет сказал Белокурову: «Любопытно, что один из нас – блондин, другой – брюнет, третий – рыжий, но ни у кого цвет волос не соответствует фамилии». Какой цвет волос у каждого из друзей? |
Задание: Выполните задание по теме: Сетевые графы: В таблице приведена стоимость перевозок между соседними железнодорожными станциями. Числа, стоящие на пересечениях строк и столбцов означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите схему, соответствующую таблице.
Пояснения к работе:
Необходимые формулы:
Граф- это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Вершины, прилегающие к одному и тому же ребру, называются смежными.
Если ребра ориентированны, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом.
Если ребра не имеют ориентации, граф называется неориентированным.
Петля- это дуга, начальная и конечная вершина которой совпадают.
Простой граф- граф без кратных ребер и петель.
Степень вершины- это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер.
Пустым называется граф без ребер.
Полным называется граф, в котором каждые две вершины смежные.
Путь в ориентированном графе — это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Маршрут в графе путь, ориентацией дуг которого можно пренебречь.
Цепь- маршрут, в котором все ребра попарно различны.
Цикл- замкнутый маршрут, являющийся цепью.
Граф называется связным, если любая пара его вершин связана.
Дерево— это связный граф без циклов.
Содержание отчета
1. Титульный лист в соответствии с СТП1.2-2005.
2. Цель работы
3. Задание
4. Выполненная практическая работа в соответствии с заданием
5. Ответы на контрольные вопросы
6. Вывод
Контрольные вопросы:
1. Дайте определение графа.
2. Сформулируйте понятие смежных ребер.
3. Дайте определение правильного графа.
4. Запишите формулу суммы степеней графа.
5. Дайте определение изолированной вершины графа.
