Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow Дискретная математика. Сборник задач

Подсчет количества ребер и вершин при операциях над графами

Теоретические сведения

Над графами, как и над другими математическими объектами, можно производить ряд операций. Рассмотрим основные из них.

Удаление вершины. Пусть б= (Е, Ц) — граф и у є V. Удалить вершину у из графа б значит построить новый граф б' = (У', (/'), в котором V' = У {г} и и' получается из б удалением всех ребер, инцидентных вершине V.

Удаление ребра. Пусть б = (V, б) граф и и є и. Удалить ребро и — значит построить новый граф б' = (V', б'), в котором У'= Уи и'=и{и}.

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

Объединение графов. Пусть даны два графа = (6(6]), 6(6,)), б2 = (У(С2), б(б2)), причем множества Е(б[), б(б2) не пересекаются. Пусть У(вх) = п{, |б(б2)| = п2, |б(б|)| = т|, |б(б2)| = т2. Объединением графов (7[, б2 называется граф б = и б2 с множеством вершин У(Оі) и б(б2) И семейством ребер б(б,) и б(б2).

Сложение графов. Пусть даны два графа б, = (6(6,), 6(6^), б2 = (б(б2), б(б2)), причем множества Е(б[), б(б2) не пересекаются. Тогда суммой графов б1; б2 называется граф б = б1 + б2, полученный как их объединение, при этом каждая вершина б] соединяется ребром с каждой вершиной графа б2.

Если множества У(СХ), б(б2) пересекаются, т.е. исходные графы имеют общие вершины, операции объединения и сложения осуществляются так же, за исключением того, что общие вершины склеиваются или сливаются в одну единую вершину. Если общие вершины в двух исходных графах соединены ребром, то эти ребра тоже склеиваются. При операции сложения общие (склеенные) вершины не участвуют в построении новых ребер.

Задачи

Задача 2.5. Для графов б), б3, б5 (рис. 2.4) определить число вершин и ребер, а также нарисовать граф, получаемый в результате операции объединения этих трех графов при отсутствии общих вершин.

Условие для задач 2.5—2.13

Рис. 2.4. Условие для задач 2.5—2.13

очз

О,

Решение.

Этот случай является наиболее простым, так как ни один из графов не имеет общих вершин с другим, а потому результирующий граф будет выглядеть точно так же, как в условии выглядят три исходных графа (см. рис. 2.4). Характеристики графа: количество вершин — 15, ребер — 13.

Задача 2.6. Для графов б2 и б5 (см. рис. 2.4) определить число вершин и ребер, а также нарисовать граф, получаемый в результате операции объединения этих двух графов при условии, что они имеют одну общую вершину.

Решение.

Решение этой задачи необходимо начать с определения вершины, общей для обоих графов. Как несложно заметить, для графа б2 совершенно безразличен выбор вершины, общей с графом б5, так как изменение выбора этой вершины никак не отразится на характеристиках результирующего графа, а лишь повернет в графическом представлении часть графа б2 по или против часовой стрелки. Для графа б5 ситуация аналогична. Выбор общей (или общих) вершин редко сводится к поиску определенной вершины, а чаще всего — к разбиению всех вершин графа на классы, внутри которых выбор вершины влияет на результирующий граф с точностью до переобозначения вершин.

Результирующий граф будет представлять из себя присоединение ребра, инцидентного общей вершине в графе б5, к общей вершине в графе б2. Результат объединения двух графов представлен на рис. 2.5.

Решение задачи 2.6

Рис. 2.5. Решение задачи 2.6

Характеристики графа: количество вершин — 10, ребер — 8.

Задача 2.7. Для графов б4 и б3 (см. рис. 2.4) определить число вершин и ребер, а также нарисовать графы, получаемые в результате операции объединения этих двух графов при условии, что у них одна общая вершина степени 3.

Задача 2.8. Для графов б4 и б5 (см. рис. 2.4) определить число вершин и ребер, а также нарисовать графы, получаемые в результате операции объединения этих двух графов при условии, что у них три общие вершины степени 1.

Задача 2.9. Для графов б] и б5 (см. рис. 2.4) определить число вершин и ребер, а также нарисовать графы, получаемые в результате операции сложения этих двух графов при отсутствии общих вершин.

Задача 2.10. Для графов б[ и б2 (см. рис. 2.4) определить число вершин и ребер, а также нарисовать графы, получаемые в результате операции сложения этих двух графов при отсутствии общих вершин.

Задача 2.11. Для графов б, и б3 (см. рис. 2.4) определить число вершин и ребер, а также нарисовать графы, получаемые в результате операции сложения этих двух графов при условии, что у них две общие вершины степени 2, несмежные в обоих графах.

Задача 2.12. Для графов и б3 (см. рис. 2.4) определить число вершин и ребер, а также нарисовать графы, получаемые в результате операции сложения этих двух графов при условии, что у них три общие вершины, попарно несмежные в обоих графах.

Задача 2.13. Для графов б3 и б3 (см. рис. 2.4) определить число вершин и ребер, а также нарисовать графы, получаемые в результате операции сложения этих двух графов при условии, что у них три общие вершины, попарно несмежные в обоих графах.

Задача 2.14. Сколько вершин и ребер имеет:

  • а) дополнение графа К8 5;
  • б) дополнение графа АГ12?

Задача 2.15. Какое максимальное число ребер имеет:

  • а) двудольный граф с долями 6 и 11;
  • б) произвольный граф на семи вершинах?

Задача 2.16. Сколько вершин и ребер имеет граф, полученный в результате объединения регулярного графа степени 3 на восьми вершинах и полного графа К9‘?

  • а) графы не имеют общих вершин;
  • б) графы имеют одну общую вершину

Задача 2.17. Сколько вершин и ребер имеет граф, полученный в результате сложения регулярного графа степени 3 на восьми вершинах и полного графа К9?

  • а) графы не имеют общих вершин;
  • б) графы имеют одну общую вершину.

Задача 2.18. Сколько вершин и ребер имеет граф, полученный в результате объединения полного двудольного графа К7 8 и пустого графа на шести вершинах?

  • а) графы не имеют общих вершин;
  • б) графы имеют одну общую вершину.

Задача 2.19. Сколько вершин и ребер имеет граф, полученный в результате сложения полного двудольного графа К7 8 и полного графа на шести вершинах?

  • а) графы не имеют общих вершин;
  • б) графы имеют одну общую вершину.

Задача 2.20. Сколько вершин и ребер имеет граф, полученный в результате объединения регулярного графа степени 5 на десяти вершинах и полного графа К4?

  • а) графы не имеют общих вершин;
  • б) графы имеют одну общую вершину.
 
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ   След >
 

Популярные страницы