Упражнения по теории графов

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

а) б)

V V1 V2 V3 V4 V5 V6 V V1 V2 V3 V4 V5 V6
V1         V1        
V2         V2        
V3           V3      
V4             V4      
V5         V5      
V6           V6        

в) г)

V V1 V2 V3 V4 V5 V6 V V1 V2 V3 V4 V5 V6
V1           V1 2        
V2   2       V2        
V3         V3      
V4       V4 1      
V5             V5        
V6         V6      

д) е)

V V1 V2 V3 V4 V5 V6 V V1 V2 V3 V4 V5 V6
V1           V1        
V2   2         V2        
V3             V3      
V4         V4      
V5           V5        
V6         V6      

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

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

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

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

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

 

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

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

2.3. Найдите объединение и пересечение графов G1и G 2, дополнение для графа G1 (рис. 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.)

а) б)