Методическое пособие содержит достаточное количество упражнений разной степени сложности для аудиторной и самостоятельной работ, которые предусмотрены для студентов с разной теоретической подготовкой
|
Скачать 338.77 Kb.
|
|
2. Граф задан диаграммой. 1) Составьте для него матрицу смежности. 2) Постройте матрицу инцидентности. 3) Укажите степени вершин графа. 4) Составьте маршруты длины 5 из вершиныV2 в вершину V5. Составьте простую цепь, соединяющую эти вершины. 5) Постройте простой цикл, содержащий вершину V4. 6)Определите вид заданного графа. в а б V1 V2 V3 V4 V7 V5 V6 V1 V2 V3 V4 V5 V6 V1 V2 V3 V4 V5 V6 V7 V7 ж))) V7 V1 V2 V3 V4 V5 V6 е V1 V2 V3 V4 V5 V6 V7 V1 V2 V3 V4 V5 V6 V7 д г V1 V2 V3 V4 V5 V6 V7 3. Найдите объединение и пересечение графов G1и G2, дополнение графа G1. V1 V5 V3 V2 V3 V1 V2 V1 V2 V4 V5 V3 V5 V4 V3 V2 V1 в б G2 G2 G1 G1 a G2 G1 V5 V4 V3 V1 V2 V3 V4 V5 V2 V1 V5 V4 V2 V1 V5 V4 V3 V3 V2 V1 д G2 G1 д G2 G2 G1 V5 V3 V4 V1 V2 V1 V4 г G1 V5 V3 V4 V1 V5 V3 V2 V1 4. Составьте все возможные планы маршрута путешествия по историческим местам, если автотуристам надо проехать из пункта М в пункт N, осмотрев все памятники архитектуры не более одного раза. Как называется такой маршрут? K D E F N С В А M 5. Составьте сценарий и по нему постройте сетевой граф, изображающий порядок выполнения операций, для того чтобы: 1) подготовить и провести неделю информатики в колледже; 2) посадить и вырастить цветы вокруг колледжа; 3) организовать работу торговой точки; 4) выпустить газету к празднику; 5) организовать и осуществить поездку в другой город. 6.Ориентированный граф G = (V,X) с множеством вершин V = {1,2,3,4,5,6,7}задан списком дугX: a) X = {(1,2),(2,3),(4,3),(4,5),(6,5),(7,6),(7,1),(7,7),(7,2), (6,4), (4,4),(2,7),(6,4),(5,3)}; б) X = {(1,4),(2,1),(4,3),(4,5),(2,6),(7,1),(7,6),(3,2),(5,4),(3,4), (2,2),(6,2),(5,5)(2,6)} в) X = {(1,5),(2,3),(2,3),(4,5),(4,6),(5,6),(5,1),(6,6),(3,2),(5,4), (6,4),(7,2),(6,7),(7,5)} 1) Постройте реализацию графа G. 2) Постройте матрицу инцидентности графа G. 3) Постройте матрицу смежностиG. 4) Укажите степени вершин полученных графов. 7. Решите задачи «о переправах», изобразите решение графом. а) Три генерала – Строгий, Лихой и Грозный – со своими адъютантами переправлялись через реку с помощью двухместной лодки. Адъютант может либо перевозить своего генерала, либо переправляться с другим адъютантом. Однако ни один из генералов не разрешил своему адъютанту ни оставаться с другим генералом вдвоем на берегу, ни переправляться с ним через реку. Как они переправились через реку? б) Трое мужчин и три женщины должны переправиться через реку. У них была одна лодка, которая вмещала только двух человек. Грести умели все мужчины и только одна женщина. Кроме того, женщины требовали, чтобы ни на обном берегу не оставалось женщин больше, чем мужчин. Как им переправиться через реку? в) Муж, жена и двое детей должны переправиться на противоположный берег реки при помощи лодки. Муж и жена весят по 100 кг, а дети – по 50. Как им быть, если лодка вмещает до 100 кг и каждый из них умеет грести? г) Человеку необходимо было переправить через реку с помощью лодки волка, козу и капусту. В лодке мог поместиться только человек, а с ним или волк, или коза, или капуста. Но если оставить волка с козой без человека, то волк съест козу, если оставить козу с капустой, то она съест капусту, а в присутствии человека никто никого не ел. Человек все-таки перевез через реку и волка, и козу, и капусту. Как он это сделал? 8. Решите при помощи графов задачи на поиск «фальшивой монеты». а) Из 9 монет одна фальшивая (более легкая). Как двумя взвешиваниями на чашечных весах определить фальшивую монету? б) Из 80 одинаковых по виду монет одна фальшивая (более легкая). Как четырьмя взвешиваниями на чашечных весах определить фальшивую монету? в) Из 8 монет одна более легкая (фальшивая). Как при помощи 4 взвешиваний на чашечных весах определить фальшивую монету? г) Из 27 монет одна фальшивая (более легкая). Как тремя взвешиваниями на чашечных весах определить фальшивую монету? д) Из 81 монеты одна фальшивая (более легкая). Как четырьмя взвешиваниями на чашечных весах определить фальшивую монету? е) Из 82 монет одна фальшивая (более легкая). Какое наименьшее число взвешиваний необходимо для определения этой монеты? ж) Из m одинаковых по виду монет одна фальшивая (более легкая). Указать наименьшее число взвешиваний, необходимых для определения фальшивой монеты? 9. Решите задачи, используя графы. а) Атос поскакал в гости к Портосу, взяв с собой карту (рис. ). Числа на схеме обозначают время движения в часах от пункта до пункта. Помогите Атосу найти кратчайший путь от своего поместья в пункте Е до поместья Портоса в пункте Д. Перечислите пункты, которые должен проехать Атос, и подсчитайте время, которое он затратит на весь путь. Ж К Г В А Е З 3 1 Б Д 10 10 10 1 1 3 3 6 9 5 2 2 8 5 5 2 6 5 К З Б 5 10 10 А В Ж И Д Г 25 15 15 10 10 25 15 5 10 10 30 20 б) Вини-пух вышел на прогулку, взяв с собой карту (рис. ). Числа на схеме обозначают время движения в минутах от пункта до пункта. Помогите Вини-пуху найти кратчайший путь от своего дома в пункте А до дома Пятачка в пункте К. Перечислите пункты, которые должен пройти Вини-пух, и подсчитайте время, которое он затратит на весь путь. Контрольные вопросы Что называется графом? Ориентированным графом? Приведите примеры. Перечислите и сформулируйте основные понятия, связанные с неориентированными графами. Перечислите основные понятия, связанные с орграфами. Какие два графа называются изоморфными. Что называется маршрутом, циклом, путем и цепью графа. Сформулируйте понятие связности графа. Дайте определение эйлерова графа. Какой граф называют гамильтоновым? Дайте понятие дерева и перечислите его свойства. Перечислите операции над графами. Перечислите способы задания графов. В чем состоит аналитический способ задания графа? В чем состоит геометрический способ задания графа? В чем состоит матричный способ задания графа? Какая матрица называется матрицей смежности графа? Какая матрица называется матрицей инцидентности графа? Список литературы
Содержание:
3.1. Основные понятия теории графов………….………..9 3.2. Связность графов…………………………………….12 3.3. Деревья…………………………………………….….13 3.4. Ориентированные графы……………………………15 3.5. Эйлеровы графы……………………………………..16 3.6. Гамильтоновы графы……………………………...…18 3.7. Операции над графами……………………………....19 3.8. Способы задания графов………………………….…21 3.9. Раскраска графа…………………………………..…..25 3.10.Сетевые графы…………………………………...…..25
|
Похожие:
 |
Сергей Николаевич Бердышев Технологии работы с клиентами разной трудности Пособие содержит большое количество кейсов, с помощью которых легко понять особенности работы с различными заказчиками. Книга рассчитана... |
|
Наркотическая угроза: знать, чтобы выжить! Теперь совершенно очевидно, что она характерна не только для стран Западного мира. Этим злом оказались поражены народы всех континентов... |
 |
Методические указания по написанию контрольных работ 26 Ким для аттестации остаточных знаний 28 Учебно-методическое пособие предназначено для студентов направления: 080100, 080200, 100100, 100400, 230400, 072500 |
|
Международные валютные отношения и валютный рынок Методическое пособие Методическое пособие предназначено для студентов, обучающихся по специальности «Финансы и кредит» заочной формы обучения |
|
Учебно-методическое пособие для студентов Нижний Новгород 2009 Темперамент, Характер. Воля: Учебно-методическое пособие для студентов. Н. Новгород: нгпу, 2009. 42с |
|
Учебно-методическое пособие для проведения практических занятий для... Методы научных исследований: учебно-методическое пособие для проведения практических |
|
Учебно-методическое пособие Н. Новгород ... |
|
Учебно-методическое пособие для студентов специальностей «История» Шинаков Е. А., Поляков Г. П., Чубур А. А. Основы восточноевропейской археологии (учебно-методическое пособие). – Брянск, рио бгу,... |
|
И самостоятельной работы студентов Учебное пособие предназначено для студентов Волжского государственного инженерно-педагогического университета, обучающихся по специальности... |
|
Учебное пособие Текст предоставлен правообладателем Логопатопсихология:... «Логопатопсихология: учеб пособие для студентов / под ред. Р. И. Лалаевой, С. Н. Шаховской.»: Гуманитарный издательский центр владос;... |