Студопедия — ЗАНЯТИЕ 1
Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

ЗАНЯТИЕ 1

2.1. Пусть орграф задан матрицей смежности. Постройте изображение этого графа, укажите степени вершин графа. По матрице смежности постройте матрицу инцидентности этого графа:

а) б)

V V 1 V 2 V 3 V 4 V 5 V 6   V V 1 V 2 V 3 V 4 V 5 V 6
V 1               V 1            
V 2               V 2            
V 3               V 3            
V 4               V 4            
V 5               V 5            
V 6               V 6            

в) г)

V V 1 V 2 V 3 V 4 V 5 V 6   V V 1 V 2 V 3 V 4 V 5 V 6
V 1               V 1 2          
V 2   2           V 2            
V 3               V 3            
V 4               V 4 1          
V 5               V 5            
V 6               V 6            

д) е)

V V 1 V 2 V 3 V 4 V 5 V 6   V V 1 V 2 V 3 V 4 V 5 V 6
V 1               V 1            
V 2   2           V 2            
V 3               V 3            
V 4               V 4            
V 5               V 5            
V 6               V 6            

2.2. Граф G задан диаграммой (рис. 2.27).

1. Составьте для него матрицу смежности.

2. Постройте матрицу инцидентности.

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

4. Найдите длину пути из вершины V2 в вершину V5, составьте маршруты длины 5, цепь и простую цепь, соединяющие вершин V 2 и вершину V 5.

 

5. Постройте простой цикл, содержащий вершину V 4.

6. Найдите цикломатическое число графа G 1. Определите вид заданного графа.

2.3. Найдите объединение и пересечение графов G 1и G 2, дополнение для графа G 1 (рис. 2.28).

2.4. Постройте матрицу смежности и матрицу инцидентности для отношений, заданных графом О. Найдите число степеней входа и выхода этого графа, дайте ему характеристику (рис. 2.29).

2.5. Орграф задан матрицей смежности. Постройте его рисунок (схему, диаграмму), определите степени вершин графа и найдите маршрут длины 5. Есть ли среди них изоморфные?

2.6. Составьте все возможные планы маршрута путешествия по историческим местам, если автотуристам надо проехать из пункта М в пункт N, осмотрев все памятники архитектуры не более одного раза. Как называется такой маршрут (рис. 2.30)?

 
Рис. 2.30. Граф путешествия по историческим местам

2.7. Ориентированный граф G(V, X) с множеством вершин V= {1, 2, 3, 4, 5, 6, 7} задан списком дуг X.

1. Постройте реализацию графа G.

2. Постройте матрицу инцидентности графа G.

3. Постройте матрицу смежности G.

4. Задайте соответствующий неориентированный граф матрицей смежности.

5. Укажите степени вершин полученных графов, найдите цикломатическое число графа G.

а) Х= {(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)};

б) Х= {(1, 4), (2, 1), (4, 3), (4, 5), (2, 6), (2, 6), (7, 1), (7, 6), (3, 2), (5, 4), (3, 4), (2, 2), (6, 2), (5, 5)};

в) Х= {(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, 1), (2, 2), (2, 3), (3, 5), (4, 6), (4, 6), (5, 1), (5, 6), (5, 2), (6, 4), (7, 4), (7, 2), (7, 2), (7, 5)};

д) Х= {(1, 1), (1, 3), (1, 3), (2, 5), (2, 6), (3, 6), (3, 1), (3, 6), (3, 7), (4, 4), (4, 6), (5, 2), (6, 3), (6, 5)};

е) Х= {(1, 3), (2, 3), (2, 3), (3, 5), (3, 6), (2, 7), (4, 1), (4, 6), (4, 2), (6, 4), (6, 4), (7, 2), (6, 6), (7, 6)}.

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

а) выпустить газету;

б) провести шахматный турнир на первенство колледжа;

в) подготовить и провести в колледже КВН;

г) посадить и вырастить картофель;

д) организовать работу торговой точки;

е) изготовить табурет.

2.9. Решите задачи «о переправах», изобразите решение графом.

1. Три генерала — Строгий, Лихой и Грозный — со своими адъютантами переправлялись через реку с помощью двухместной лодки. Адъютант может либо перевозить своего генерала, либо переправляться с другим адъютантом. Однако ни один из генералов не разрешил своему адъютанту ни оставаться с другим генералом вдвоем на берегу, ни переправляться с ним через реку. Как они переправились через реку?

2. Трое мужчин и три женщины должны переправиться через реку. У них была одна лодка, которая вмещала только двух человек. Грести умели все мужчины и только одна женщина. Кроме того, женщины требовали, чтобы ни на одном берегу не оставалось больше женщин, чем мужчин. Как им переправиться через реку?

3. Муж, жена и двое детей должны переправиться на противоположный берег реки при помощи лодки. Муж и жена весят по 100 кг, а дети — по 50. Как им быть, если лодка вмещает до 100 кг и каждый из них умеет грести?

4. Человеку необходимо было переправить через реку с помощью лодки волка, козу и капусту. В лодке мог поместиться только человек, а с ним или волк, или коза, или капуста. Но если оставить волка с козой без человека, то волк съест козу, если оставить Козу с капустой, то она съест капусту, а в присутствии человека Никто никого не ел. Человек все-таки перевез через реку и волка, и козу, и капусту. Как он это сделал?

2.10. Задачи на поиск «фальшивой монеты» решите с помощью графов.

1. Из 9 монет одна фальшивая (более легкая). Как двумя взвешиваниями на чашечных весах определить фальшивую монету? /

2. Из 80 одинаковых по виду монет одна более легкая (фальшивая). Как четырьмя взвешиваниями на чашечных весах определить фальшивую?

3. Из 28 монет одна более легкая. Как при помощи 4 взвешиваний определить ее?

4. Из 27 монет одна более легкая. Как при помощи 3 взвешиваний определить ее?

5. Из 81 монеты одна более легкая. Показать, что 4 взвешиваний достаточно, чтобы ее определить.

6. Из 82 монет одна более легкая. Какое наименьшее число взвешиваний необходимо для определения этой монеты?

7. Из т одинаковых по виду монет одна фальшивая (более легкая). Указать наименьшее число взвешиваний, необходимых для определения фальшивой монеты.

2.12. Решите задачи, используя графы (рис. 2.31).

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

2. Атос поскакал в гости к Портосу, взяв с собой карту (рис. 2.31, б). Числа на рисунке обозначают время движения (в часах) от пункта до пункта. Помогите Атосу найти кратчайший путь от своего поместья в пункте Е до поместья Портоса в пункте Д. Пе­речислите пункты, через которые должен проехать Атос, и под­считайте время, которое он затратит на весь путь.

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

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

5. Перед вами — карта (рис. 2.31, д). Числа на карте обозначают время движения (в часах) от пункта до пункта. Можно ли успеть доехать из пункта А в пункт О за 22 часа? В случае положительного ответа укажите маршрут, в случае отрицательного ответа обоснуйте его.

6. Придумайте и решите аналогичную задачу.

Рис. 2.31. Графы к упр. 2.12: а — задание 1; б — задание 2; в — задание 3; г — задание 4; д — задание 5

2.13. Пусть граф задан матрицей смежности. Постройте изображение этого графа, укажите степени вершин графа. По матрице смежности постройте матрицу инцидентности этого графа (Аляев Ю.А, Тюрин С. Ф. Дискретная математика и математическая логика. С. 67.)

а) б)

V V 1 V 2 V 3 V 4 V 5 V 6   V V 1 V 2 V 3 V 4 V 5 V 6
V 1               V 1            
V 2               V 2            
V 3               V 3            
V 4               V 4            
V 5               V 5            
V 6               V 6            

ЗАНЯТИЕ 1.




<== предыдущая лекция | следующая лекция ==>
Упражнения по теории графов | 

Дата добавления: 2014-11-10; просмотров: 1490. Нарушение авторских прав; Мы поможем в написании вашей работы!



Обзор компонентов Multisim Компоненты – это основа любой схемы, это все элементы, из которых она состоит. Multisim оперирует с двумя категориями...

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

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

ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...

Ситуация 26. ПРОВЕРЕНО МИНЗДРАВОМ   Станислав Свердлов закончил российско-американский факультет менеджмента Томского государственного университета...

Различия в философии античности, средневековья и Возрождения ♦Венцом античной философии было: Единое Благо, Мировой Ум, Мировая Душа, Космос...

Характерные черты немецкой классической философии 1. Особое понимание роли философии в истории человечества, в развитии мировой культуры. Классические немецкие философы полагали, что философия призвана быть критической совестью культуры, «душой» культуры. 2. Исследовались не только человеческая...

Законы Генри, Дальтона, Сеченова. Применение этих законов при лечении кессонной болезни, лечении в барокамере и исследовании электролитного состава крови Закон Генри: Количество газа, растворенного при данной температуре в определенном объеме жидкости, при равновесии прямо пропорциональны давлению газа...

Ганглиоблокаторы. Классификация. Механизм действия. Фармакодинамика. Применение.Побочные эфффекты Никотинчувствительные холинорецепторы (н-холинорецепторы) в основном локализованы на постсинаптических мембранах в синапсах скелетной мускулатуры...

Шов первичный, первично отсроченный, вторичный (показания) В зависимости от времени и условий наложения выделяют швы: 1) первичные...

Studopedia.info - Студопедия - 2014-2024 год . (0.013 сек.) русская версия | украинская версия