<<
>>

Задачи для самостоятельного решения

№ 2.1 Показать, что два графа на рис. 2.6 изоморфны.

Рис. 2.6

№ 2.2 «Три дома и три колодца». Три поссорившихся соседа имеют три общих колодца.

Можно ли провести непересекающиеся дорожки от каждого дома к колодцу?

№ 2.3 Найти степени и числа вершин для графов пяти правильных многогранников.

№ 2.4 Для графов, изображенных на рис. 2.7, указать пары, изоморфные друг другу.

А Б В

Г Д Е

Ж З И

Ж З И

К Л М

Рис.2.7

№ 2.5 Среди графов, указанных на рис. 2.8, выделить полные графы (без учета петель).

А Б В Г

Д Е Ж

И К Л М

Рис. 2.8

№ 2.6 Дан граф G (Рис. 2.9). Указать, какие из графов, изображенных на рис. 2.9б, являются частями графа G и какие – подграфами.

Рис. 2.9

А Б В

Г Д Е

Ж З И

К Л М Н

Рис. 2.9б.

№ 2.8 Какие из графов, приведенных на рис.2.8 и 2.9, являются плоскими?

№ 2.9.

Составить матрицы смежности и инцидентности для правильных многогранников.

№ 2.10. Построить матрицы смежности графов, изображенных на рис. 2.9.

№ 2.11 Для заданного на рис. 2.10 (а¸к) графа построить: матрицу смежности, матрицу инциденции, матрицу достижимостей. Найти число внутренней устойчивости. Найти число внешней устойчивости.

А Б В

Г Д Е Ж

З И К

Рис. 2.10.

№ 2.12. Для приведенных на рис. 2.11. графов G1 и G2 найти , , .

А Б

В Г

Д Е

Ж З

Рис. 2.11

№ 2.13. Построить графы, матрицы смежности которых указаны:

№ 2.14. Построить графы, матрицы инцидентности которых указаны:

;

№ 2.15 Груз доставляется из пункта Х0 в пункт Х7 через перевалочные пункты Х0…Х7 (Рис.2.12). Расстояния между пунктами ХiXj указаны на соответствующем графе. Найти путь минимальной длины между Х0 и Х7 и его длину.

А Б

В Г

Рис. 2.12

№ 2.16 Задан сетевой граф проекта (Рис.2.12). Найти критический путь и минимальное время проекта

<< | >>
Источник: Алексеев В.В.. Элементы теории множеств и теории графов (Сборник задач и упражнений по курсу “Дискретная математика”). 2001

Еще по теме Задачи для самостоятельного решения:

  1. Задача № 14. Какое постановление (решение или определение) должен вынести суд
  2. Решение логических задач
  3. Технология выработки и реализации управленческих решений.
  4. § 66. Двойственные задачи .линейного программирования и решение их двойственным симплексным методом
  5. Психолого-педагогическая диагностика: проблемы и задачи
  6.   2. X съезд партии и его исторические решения  
  7. Цели и задачи судебно-экспертного исследования.
  8. Тактические принципы и методика экспертиз при решении ситуационных задач.
  9. Урок 16. Логические задач
  10. Бюджетные средства - решение ДВУХ ГЛАВНЫХ ПРОБЛЕМ СОДЕРЖАНИЯ МНОГОКВАРТИРНЫХ ДОМОВ
  11. Цели и задачи деятельности товариществ собственников жилья
  12. Задачи для самостоятельного решения
  13. Задачи для самостоятельного решения
  14. Задачи для самостоятельного решения
  15. Задачи для самостоятельного решения