Сколько ребер в графе у олеси
- углубишься в решение практических задач;
- узнаешь все про сложные алгоритмы, сортировки, сжатие данных и многое другое.
Рис. 1. Визуализация терминологии графов
графы — Сколько ребер?
Сколько ребер в графе дополнение к $%K_
задан 20 Ноя ’20 17:04
По-моему, это у тестировщиков что-то неправильно 🙂
Может, они ожидали ответа в виде (m+n)(m+n-1)/2-mn? Одно тождественно равно другому, и Ваша форма ответа проще.
Только в графе дополнениЯ.
@falcao: да, у них ошибка была в тесте, спасибо.
а откуда сразу было известно, что это из теста?
@knop: из общих соображений — я сразу подумал на то, что ответ куда-то вводился, а выражение тут неоднозначное. Робота, видимо, недонастроили 🙂
Здравствуйте
Математика — это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Подсчет количества ребер и вершин при операциях над графами
Над графами, как и над другими математическими объектами, можно производить ряд операций. Рассмотрим основные из них.
Удаление вершины. Пусть б= (Е, Ц) — граф и у є 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.4. Условие для задач 2.5—2.13
Этот случай является наиболее простым, так как ни один из графов не имеет общих вершин с другим, а потому результирующий граф будет выглядеть точно так же, как в условии выглядят три исходных графа (см. рис. 2.4). Характеристики графа: количество вершин — 15, ребер — 13.
Задача 2.6. Для графов б2 и б5 (см. рис. 2.4) определить число вершин и ребер, а также нарисовать граф, получаемый в результате операции объединения этих двух графов при условии, что они имеют одну общую вершину.
Решение этой задачи необходимо начать с определения вершины, общей для обоих графов. Как несложно заметить, для графа б2 совершенно безразличен выбор вершины, общей с графом б5, так как изменение выбора этой вершины никак не отразится на характеристиках результирующего графа, а лишь повернет в графическом представлении часть графа б2 по или против часовой стрелки. Для графа б5 ситуация аналогична. Выбор общей (или общих) вершин редко сводится к поиску определенной вершины, а чаще всего — к разбиению всех вершин графа на классы, внутри которых выбор вершины влияет на результирующий граф с точностью до переобозначения вершин.
Результирующий граф будет представлять из себя присоединение ребра, инцидентного общей вершине в графе б5, к общей вершине в графе б2. Результат объединения двух графов представлен на рис. 2.5.
Рис. 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?
6.10.3. Оценка количества ребер сверху и снизу
Оценка количества ребер сверху и снизу проводится на основе нескольких фактов.
1. Степень каждой вершины полного графа на единицу меньше числа его вершин, полный граф на n вершинах всегда является регулярным графом степени ( n – 1), суммарная степень его вершин равна n ( n + 1), а значит, количество ребер в полном графе равно n ( n +1)/2. Это и есть ограничение количества ребер сверху – построить больше на n вершинах нельзя. Например, у графа на 7 вершинах максимально может быть 21 ребро.
2. Максимальное число ребер на n вершинах можно построить именно в случае, когда граф связный. Иначе их будет еще меньше, например, у несвязного графа на n вершинах в лучшем случае количество ребер равно ( n –1)·( n – 2)/2 (лучший случай попытки разместить максимальное число ребер – это отделить одну изолированную вершину и построить полный граф на оставшихся ( n – 1) вершине). Например, у несвязного графа на 7 вершинах максимально может быть 15 ребер.
3. Оценка снизу чаще всего сводится к оценке количества ребер, необходимых для образования именно связного графа. Минимальная с точки зрения расхода ребер конфигурация состоит именно в построении дерева. В дереве на n вершинах содержится всегда
4. Если помимо условия ацикличности поставлено также требование обеспечить несвязность графа, то ребер удастся разместить
еще меньше. Их будет столько же, сколько ребер в остовном лесе: на n вершинах при k компонентах связности ациклический граф содержит в общем случае ( n – k ) ребер.
5. Если речь идет о двудольных графах, полезно помнить, что число ребер в полном двудольном графе с n 1 и n 2 вершинами в соответствующих долях равно n 1 ·n 2
В ряде случаев эти факты позволяют либо доказать невозможность построения графа с заданными характеристиками, либо помогают сформировать представление о свойствах графа.
Задача 6.20. Построить или обосновать невозможность построения несвязного графа на 12 вершинах, имеющего 56 ребер.
Решение. Несвязный граф состоит минимум из двух компонент, при этом наиболее экономичный в плане потенциально наибольшего количества ребер способ распределения вершин это 1 вершина в первой компоненте и остальные 11 – во второй. На 11 вершинах можно построить максимально 11·10/2=55 ребер, таким образом ,получим полный граф на 11 вершинах. Следовательно, графа, соответствующего условию задачи, не существует.
Задача 6.21. Построить или обосновать невозможность построения связного графа на 11 вершинах, имеющего следующее распределение степеней вершин: две вершины степени 3, три вершины степени 2, шесть вершин степени 1.
Решение. Суммарная степень всех вершин равна 2·3+3·2+6·1=18, следовательно, в графе должно быть 18/2=9 ребер. Однако для построения связного графа на 11 вершинах необходимо как минимум 10 ребер. Следовательно, графа, соответствующего условию задачи, не существует.
Задача 6.22. Построить или обосновать невозможность построения бихроматического графа на 13 вершинах, имеющего 41 ребро.
Решение. Бихроматическими являются двудольные графы, значит, имеющиеся 13 вершин нужно распределить на 2 доли так, чтобы удалось провести максимальное количество ребер. Самое выгодное разбиение – это соотношение по 50%, в данном случае это 6 и 7 вершин соответственно. При таком разбиении можно максимально построить 6·7=42 ребра. Нам нужно 41, значит, ответом яв-
ляется полный граф K 6,7 , у которого удалили одно ребро. Граф, являющийся ответом на задачу 6.22, представлен на рис. 6.62.
6.10.4. Получение недостающих данных на основе формул
В ряде задач на построение дополнительную информацию о структуре графа можно получить на основе численных характеристик, таких, как цикломатическое число, ранг, хроматическое число графа, числа внешней и внутренней устойчивости и другие характеристики. Во всех этих случаях из приведенных в условии задачи данных желательно извлечь дополнительные сведения, которые могут помочь в непосредственном построении графа.
В качестве примера приведем несколько типовых задач.
Задача 6.23. Построить или обосновать невозможность построения связного графа на 7 вершинах, цикломатическое число
которого равно 13.
Решение. В силу того, что граф
связный, k = 1, по условию n = 1. Из
формулы (5.1) получим: 13 = m – 7 + 1,
откуда m = 19. В графе на 7 вершинах
максимально можно построить 7·6/2 =
= 21 ребро. Значит, искомый граф
представляет собой полный граф на 7
вершинах, в котором удалено два реб-
ра. Граф, являющийся ответом на за-
дачу 6.23, представлен на рис. 6.63.
Задача 6.24. Построить или обосновать невозможность построения бихроматического связного графа, у которого ранг равен 12, а цикломатическое число равно 28.
Решение. Согласно формулам вычисления цикломатического числа и ранга получим:
γ( G )= m – n + k = m – ( n – k ) = 28.
Решив систему уравнений, получим 28 = m– 12, откуда m = 40. Поскольку граф связный, k = 1 и, значит, n = 13. Бихроматическими являются двудольные графы, значит, нужно разбить множество из 13 вершин на два подмножества так, чтобы удалось построить нужное количество ребер. Наиболее рациональный способ такого разбиения – пополам, что в данном случае соответствует 6 и 7 вершинам в каждой доле двудольного графа. При этом максимальное число ребер в полном двудольном графе K 6,7 равно 6·7 = 42, а значит 40 ребер можно построить на данном количестве вершин. Граф, являющийся ответом на задачу 6.24, представлен на рис. 6.64.
Рис. 6.64 
Задача 6.25. Построить или обосновать невозможность построения двухкомпонентного графа на 18 вершинах, имеющего 15 ребер.
Решение. Исходя из условия задачи k = 2, n = 18, m = 15. Применим формулу нахождения цкломатического числа:
γ( G ) = m – n + k = 15 – 18 + 2 = – 1.
Однако цикломатическое число не может быть отрицательным. Следовательно, графа, соответствующего условию задачи, не существует.