Контрольные вопросы и задания

  • 1. Дайте понятие графов. Какие два основные вида графов вы знаете?
  • 2. Перечислите способы задания графов. Что такое матрицы смежности и инцидентности?
  • 3. Что такое операции дополнения, объединения, пересечения графов?
  • 4. Что такое маршруты и циклы в неориентированном графе?
  • 5. Что такое пути и контуры в ориентированном графе?
  • 6. Дайте определение неориентированным, ориентированным и остовым деревьям.
  • 7. Что такое взвешенные графы, длина пути, расстояние?
  • 8. Что такое эйлеровы графы? Приведите теорему Эйлера.
  • 9. Что такое гамильтонов граф? Приведите теорему Кенига.

Задания для самостоятельной работы

  • 1. Могут ли существовать графы, у которых п вершин и степени которых равны:
    • а) п = 5;d (1) = 6,d (2) = A,d (3) = 4, d (4) = 3,d (5) = 1;
    • б) n = 6, d(l) = 6, d(2) = 3,d(3) = 3, <7(4) = 3,d (5) = ,d(6) = 1;
    • в) «-5;

r) n = 5; d () = 4, d (2) = 3, <7 (3) = 2,d (4) — 2, (5) — 1;

  • д) n = 6;d (I) = 4, d (2) = 3, d (3) = 3, d (4) = 3, d (5) = 1, <7(6) = 1;
  • е) n = 6; d (1) = 4, d (2) = 3, d (3) = 3, d (4) = 3, d (5) = 2, d (6) = 1;
  • ж) w = 7;c/(l) = 6,d(2) = A,d(3) = 3,d(4) = 3, <7(5) =3,d(6) = 3, d( 7)=1.
  • 2. Покажите, что два графа на рис. 3.39 изоморфны.
  • 3. Среди приведенных на рис. 3.40 графов найдите все пары изоморфных графов.
  • 4. Какие из графов, изображенных на рис. 3.41, являются планарными?
  • 5. Укажите, какие из графов, которые изображены на рис. 3.42, являются псевдографами, мультиграфами и простыми графами.
Графы к заданию 2

Рис. 3.39. Графы к заданию 2

Графы к заданию 3

Рис. 3.40. Графы к заданию 3

Графы к заданию 4

Рис. 3.41. Графы к заданию 4

Графы к заданию 5

Рис. 3.42. Графы к заданию 5

  • 6. Для графа, изображенного на рис. 3.43, найдите:
    • а) матрицу смежности (вершин);
    • б) матрицу инциденций.
Граф к заданию 6

Рис. 3.43. Граф к заданию 6

7. Найдите степени вершин хt, х2, х34 графа Gj и полустепени исхода и захода вершинxt,x2,x3,x41рафа С2, изображенных на рис. 3.44.

Граф к заданию 7

Рис. 3.44. Граф к заданию 7

8. Превратите каждый из графов, изображенных на рис. 3.45, в два разных ориентированных графа и укажите число полустепсней захода и полустепеней исхода их вершин.

Граф к заданию 8

Рис. 3.45. Граф к заданию 8

9. На рис. 3.46 даны два графа Е{), G2(V2, Е2).

Граф к заданию 9

Рис. 3.46. Граф к заданию 9

Изобразите геометрически объединение графов G{ u G2; пересечение графов Gj n G2 и сумму по модулю два Gt 0 G2.

  • 10. Одиннадцать школьников, уезжая на каникулы, договорились, что каждый из них пошлет открытки трем из остальных. Может ли оказаться так, что каждый получит открытки именно от тех, кому напишет сам?
  • 11. В классе 12 мальчиков и 16 девочек. Каждая девочка дружит ровно с тремя мальчиками. Количество девочек, с которыми дружат мальчики, одинаково. Со сколькими девочками дружит каждый мальчик?
  • 12. На математической олимпиаде каждый из трех призеров решил ровно шесть задач. Известно, что каждую задачу решило ровно два призера. Сколько было задач?
  • 13. Четыре друга (Илья, Андрей, Петр, Борис) хотят поехать вместе отдыхать. После обсуждения всех возможных мест для поездки они остановились на четырех вариантах: Прага (И), Лондон (Л), Рим (Р), Вена (В). У каждого из друзей есть свои предпочтения при выборе места отдыха (рис. 3.47). Они договорились о следующей схеме голосования:
  • 1) П или Л;
  • 2) результат (1) или Р;
  • 3) результат (2) или В.

Куда поедут отдыхать друзья в этом году? Может ли измениться конечная цель поездки при изменении порядка голосования? Существует ли возможность поехать в Прагу при каком-либо из вариантов выбора порядка голосования?

Графы предпочтений к заданию 13

Рис. 3.47. Графы предпочтений к заданию 13

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >