Сколько ребер в дереве в котором 7 вершин

Теория графов – деревья

Деревья – это графики, которые не содержат ни одного цикла. Они представляют иерархическую структуру в графической форме. Деревья относятся к простейшему классу графов. Несмотря на их простоту, они имеют богатую структуру.

Деревья предоставляют целый ряд полезных приложений, от простого семейного дерева до сложных в структурах данных компьютерной науки.

дерево

Связный ациклический граф называется деревом. Другими словами, связный граф без циклов называется деревом.

Края дерева известны как ветви . Элементы деревьев называются их узлами . Узлы без дочерних узлов называются листовыми узлами .

Дерево с ‘n’ вершинами имеет ‘n-1’ ребер. Если у него есть еще одно ребро, превышающее ‘n-1’, то это дополнительное ребро, очевидно, должно соединиться с двумя вершинами, что приводит к образованию цикла. Затем он становится циклическим графом, что является нарушением для графа дерева.

Пример 1

График, показанный здесь, является деревом, потому что у него нет циклов, и он связан. Он имеет четыре вершины и три ребра, т. Е. Для ‘n’ вершин ‘n-1’ ребер, как указано в определении.

Примечание. Каждое дерево имеет как минимум две вершины первой степени.

Пример 2

В приведенном выше примере вершины «a» и «d» имеют степень один. А две другие вершины ‘b’ и ‘c’ имеют второй уровень. Это возможно, потому что для того, чтобы не формировать цикл, в диаграмме должно быть как минимум два отдельных ребра. Это не что иное, как два ребра со степенью один.

Несвязный ациклический граф называется лесом. Другими словами, непересекающаяся коллекция деревьев называется лесом.

пример

Следующий график выглядит как два подграфа; но это один несвязный граф. На этом графике нет циклов. Отсюда ясно, что это лес.

Охватывающие деревья

Пусть G – связный граф, тогда подграф H в G называется остовным деревом в G, если –

• H это дерево
• H содержит все вершины G.

Остовное дерево T неориентированного графа G является подграфом, который включает в себя все вершины G.

пример

В приведенном выше примере G является связным графом, а H является подграфом G.

Ясно, что граф H не имеет циклов, это дерево с шестью ребрами, которое на единицу меньше общего числа вершин. Следовательно, H – остовное дерево группы G.

Circuit Rank

Пусть «G» связный граф с «n» вершинами и «m» ребрами. Остовное дерево ‘T’ группы G содержит (n-1) ребер.

Следовательно, количество ребер, которые нужно удалить из ‘G’, чтобы получить остовное дерево = m- (n-1), которое называется рангом схемы G.

Эта формула верна, потому что в остовном дереве вам нужно иметь ребра n-1. Из «m» ребер вам нужно сохранить «n – 1» ребер в графе.

Следовательно, удаление ребер n – 1 из m дает ребра, которые нужно удалить из графа, чтобы получить остовное дерево, которое не должно образовывать цикл.

пример

Посмотрите на следующий график –

Для графика, приведенного в примере выше, у вас есть m = 7 ребер и n = 5 вершин.

Тогда ранг цепи

пример

Пусть ‘G’ – связный граф с шестью вершинами, а степень каждой вершины равна трем. Найдите звание цепи «G».

По сумме теоремы о степени вершин

Схема ранг = | E | – (| V | – 1)

Теорема Кирхгофа

Теорема Кирхгофа полезна для нахождения числа связующих деревьев, которые могут быть сформированы из связного графа.

пример

Матрица «А» заполняется так, как если между двумя вершинами есть ребро, то она должна быть задана как «1», иначе «0».

Р ешить задачу

Введите текст одной задачи по математике (без ошибок, сокращений и с сохранением всех знаков препинания, как в учебнике) и нажмите кнопку “Решить задачу” . Или выберите задачу из учебника.

Можно задать текст голосом по одному предложению, нажимая на

Р ешение

Ответ

В ариант решения (Универсальный)

Универсальный способ состоит в том, чтобы читать условие задачи, выделять все известные и неизвестные числовые величины, относящиеся к вычислениям, обозначать неизвестные значками x, y, z . (можно любыми другими, но традиционно используют такие). Составлять простые уравнения вида a=b+c, a=b-c, a=b⋅c или a=b:c там, где это возможно, но не пытаться составлять более сложные уравнения — пусть лучше будет много простых уравнений, чем мало сложных. Давайте внимательно читать условие задачи:

Фрагмент текста задачи	Величины	Уравнения	Объяснение
в графе 7 вершин степени которых 1.1.2.2.2.3.	7 ←вел.1	Величина №1 известна и равна 7.
3 сколько ребер в этом графе? ответ	3 ←вел.2 x ←ответ	x = 3 ⋅ 7	Величина №2 известна и равна 3. Результат (ребро) пока неизвестен, обозначим его как «x» ( это будет ответ ), он есть произведение величин №2 и №1.

1. x = 3 ⋅ 7

Уравнение 1	Комментарий
0 шаг	x = 3 ⋅ 7	Исходная система уравнений
1 шаг	x = 21 ребро	Готово!

Если Вы считаете, что задача решена роботом неправильно, то нажмите кнопку, чтобы разработчики смогли объяснить роботу правильное решение

Сколько ребер в дереве в котором 7 вершин

Задание 6.1. Нарисуйте граф с семью вершинами и шестью ребрами, не имеющий ни одного цикла.
Задание 6.2. Нарисуйте связный граф с семью вершинами и шестью ребрами.
Задание 6.3. Нарисуйте граф с семью вершинами, в котором для любых двух вершин существует один и только один связывающий их путь.
Все предлагаемые решения выносим на доску, обсуждая каждый предложенный ребятами вариант.
Рассмотрим внимательно рисунки, которые строили при ре­шении этих заданий. Что характерно для всех построенных графов? Во-первых, они связные; во-вторых, они не содержат цик­лов. Такие графы выделяются в отдельный класс, представители которого именуются деревьями.

Рис 36
Деревом называется всякий связный граф, не имеющий циклов (рис. 36).
Будем считать, что граф, состоящий из одной изолирован­ной вершины, тоже является деревом.
Вершина дерева, степень которой равна единице, называется висячей вершиной (на рисунке 36 висячие вершины выделенызакрашенными кружками).

Рис. 37
Лесом называется несвязный граф, представляющий объединение деревьев (рис. 37).
Задача 6.1.
В парке "Лотос" невозможно найти такой маршрут для прогулок по
его дорожкам, который начинается и оканчивается в одной и той же точке и каждую дорожку парка содержит не более раза. Докажите, что некоторые дорожки парка приводят в тупик.
Решение.
Построим граф G, в котором вершины соответствуют перекресткам и тупикам парка, а ребра — его дорожкам.
По условию задачи в графе Gнет циклов, и он является деревом. Существование тупиков в парке эквивалентно существованию висячих вершин в построенном дереве.
Предложение 2. В любом дереве есть висячая вершина. Предположим противное. Рассмотрим произвольную вершину v1 и перейдем из нее по любому ребру в вершину v2. Поскольку степень вершины v2не меньше двух, то из нее по новому ребру можно перейти в вершину v3 и так далее. Но число вершин в графе G конечно. Поэтому, в конце концов, мы приедем в одну из тех вершин, в которых были раньше (см. рис. 38).

Рис. 38
Это означает существование цикла в дереве G, что противоречит условию. Следовательно, в графе есть висячая вершина. Эта вершина будет соответствовать тупику в парке.
Задача 6.2.
Администрация парка "Лотос" (см. предыдущую задачу) решила про­
вести реконструкцию освещения парка. По новому проекту каждый
перекресток и тупик, должен будет освещаться четырьмя светильника­ми, а аллея, соединяющая два перекрестка или перекресток и тупик – шестью. Сколько светильников будет установлено, если в парке 18 перекрестков и тупиков.
Решение.
В предыдущей задаче мы установили, что граф G, описываю­щий перекрестки, тупики и аллеи парка "Лотос" является деревом. Най­дем соотношение между числом вершин и ребер любого дерева. Каждое дерево имеет висячую вершину (см. предыдущую задачу). Удалим вися­чую вершину v0 из дерева Gвместе с ребром, выходящим из этой вер­шины. Полученный граф G1 будет связным, и в нем будут отсутствовать циклы, т.е. граф G1 – также дерево. Из графа G1, найдя и затем удалив висячую вершину v1 вместе с выходящим из нее ребром, можно получить дерево G2 и так далее. Выполнив такие операции, мы получим последо­вательность деревьев, которая оканчивается деревом, состоящим из од­ной вершины и не имеющим ребер. Для этого дерена выполняется соот­ношение: m = n – 1, где n – число вершин графа, а m – число его ребер. Теперь будем добавлять в обратном порядке ранее удаленные вершины и ребра. При каждом возвращении добавляется одна вершина и одно ребро, и для каждого получающегося графа соотношение m = n – 1 будет выпол­няться. Следовательно, мы доказали теорему 9: в любом дереве число ребер на единицу меньше числа вершин.

Поскольку в парке 18 перекрестков и тупиков, то дерево Gбудет иметь 18 вершин и 17 ребер. В парке необходимо установить 18*4 + 17*6 = 174 светильника.

Решение простых комбинаторных задач с помощью графов

Кроме таблиц, удобным инструментом для перебора и подсчёта различных комбинаций является граф.

Граф – это абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.

Граф из 6 вершин и 7 ребёр.

Сколько различных трёхзначных чисел можно написать с помощью цифр 0 и 1?

Получаем 4 числа: 100,101,110 и 111

Полный граф в комбинаторике

Полный граф – это граф со всеми возможными ребрами.

С помощью полного графа удобно решать задачи полного перебора про «всех со всеми».

5 школьных команд по волейболу сыграли серию игр. Каждая команда провела с другими командами по одному матчу. Сколько всего матчей было сыграно?

Изобразим полный граф с 5-ю вершинами и посчитаем количество ребёр.

N = 10. Значит, было сыграно 10 матчей.

Граф-дерево

Дерево – это граф без циклов, у которого между парами вершин имеется только одно ребро.

Граф-дерево с 9 узлами и 8 ребрами.

Из каждого узла выходит не более 2 ребер.

Такое дерево называют бинарным.

С помощью дерева удобно составлять упорядоченные комбинации элементов.

На столе стоит три стакана сока – апельсиновый, виноградный и яблочный. Можно взять только два стакана. Сколько есть возможных вариантов и каких?

По правилу произведения число возможных вариантов: $3 \cdot 2 = 6$. Поскольку, порядок выбора неважен, остаётся $\frac = 3$ варианта. Построим граф:

3 варианта: 1) апельсиновый + яблочный, 2)апельсиновый + виноградный, 3) виноградный + яблочный.

Примеры

Пример 1. Вася, Петя, Коля и Толя хотят быть дежурными в столовой. Но можно выбрать только троих. Сколько вариантов выбора есть?

Построим полный граф.

Каждая тройка ребят соответствует треугольнику в этом графе.

Например, Вася образует три треугольника с оставшимися тремя ребятами:

$ \frac = 3$ — ВПК, ВТК и ВТП

Без Васи есть только один треугольник – ПКТ

Общее количество треугольников 3+1=4

Ответ: 4 варианта

Пример 2. Под рукой есть 6 видов овощей (капуста, морковь, лук, помидоры, огурцы и перец). Для салата нужно 3 вида овощей. Сколько всего различных салатов можно приготовить?

Построим полный граф.

Каждые три овоща на полном графе образуют треугольник.

Например, капуста образует треугольники с оставшимися 5 овощами. Таких треугольников $ \frac = 10$, где деление на 2 учитывает повторение ребра в каждой паре («лук-огурец» = «огурец-лук» и т.д.).

Количество треугольников, в которые не входит капуста: $ \frac = 6$

Количество треугольников, в которые не входят капуста и морковь: $ \frac = 3$

Количество треугольников, в которые не входят капуста, морковь и перец: $ \frac = 1$

Итого 10+6+3+1 = 20 различных треугольников.

Ответ: 20 салатов

Примечание: по расчетной формуле $C_6^3 = \frac = 20$ — ответ правильный.

Пример 3*. Сколько существует способов занять 1,2 и 3 места на чемпионате, в котором участвуют 11 команд? Решите задачу с помощью полного графа.

Если построить полный граф с 11-ю вершинами, каждая тройка команд в нём образует треугольник.

По аналогии с примерами 1 и 2, общее количество треугольников:

Так, как порядок мест важен, в каждом треугольнике $– 3\cdot2 = 6$ вариантов распределения медалей.

По правилу произведения: $6\cdot165 = 990$ — общее количество способов.

Ответ: 990 вариантов

Примечание: по расчетной формуле $A_3^ = 11\cdot10\cdot9 = 990 $ — ответ правильный.

Пример 4. В столовой есть на выбор

• два первых блюда: щи (Щ) и борщ (Б)
• три вторых блюда: мясо (М), рыба (Р), блинчики с творогом (Т)
• два напитка: компот (К) и сок (С)

Сколько вариантов обедов можно составить из этих блюд и каких?

По правилу произведения общее количество вариантов обедов: $2\cdot3\cdot2 = 12$

Теория графов – деревья

Деревья – это графики, которые не содержат ни одного цикла. Они представляют иерархическую структуру в графической форме. Деревья относятся к простейшему классу графов. Несмотря на их простоту, они имеют богатую структуру.

Деревья предоставляют целый ряд полезных приложений, от простого семейного дерева до сложных в структурах данных компьютерной науки.

дерево

Связный ациклический граф называется деревом. Другими словами, связный граф без циклов называется деревом.

Края дерева известны как ветви . Элементы деревьев называются их узлами . Узлы без дочерних узлов называются листовыми узлами .

Дерево с ‘n’ вершинами имеет ‘n-1’ ребер. Если у него есть еще одно ребро, превышающее ‘n-1’, то это дополнительное ребро, очевидно, должно соединиться с двумя вершинами, что приводит к образованию цикла. Затем он становится циклическим графом, что является нарушением для графа дерева.

Пример 1

График, показанный здесь, является деревом, потому что у него нет циклов, и он связан. Он имеет четыре вершины и три ребра, т. Е. Для ‘n’ вершин ‘n-1’ ребер, как указано в определении.

Примечание. Каждое дерево имеет как минимум две вершины первой степени.

Пример 2

В приведенном выше примере вершины «a» и «d» имеют степень один. А две другие вершины ‘b’ и ‘c’ имеют второй уровень. Это возможно, потому что для того, чтобы не формировать цикл, в диаграмме должно быть как минимум два отдельных ребра. Это не что иное, как два ребра со степенью один.

Несвязный ациклический граф называется лесом. Другими словами, непересекающаяся коллекция деревьев называется лесом.

пример

Следующий график выглядит как два подграфа; но это один несвязный граф. На этом графике нет циклов. Отсюда ясно, что это лес.

Охватывающие деревья

Пусть G – связный граф, тогда подграф H в G называется остовным деревом в G, если –

• H это дерево
• H содержит все вершины G.

Остовное дерево T неориентированного графа G является подграфом, который включает в себя все вершины G.

пример

В приведенном выше примере G является связным графом, а H является подграфом G.

Ясно, что граф H не имеет циклов, это дерево с шестью ребрами, которое на единицу меньше общего числа вершин. Следовательно, H – остовное дерево группы G.

Circuit Rank

Пусть «G» связный граф с «n» вершинами и «m» ребрами. Остовное дерево ‘T’ группы G содержит (n-1) ребер.

Следовательно, количество ребер, которые нужно удалить из ‘G’, чтобы получить остовное дерево = m- (n-1), которое называется рангом схемы G.

Эта формула верна, потому что в остовном дереве вам нужно иметь ребра n-1. Из «m» ребер вам нужно сохранить «n – 1» ребер в графе.

Следовательно, удаление ребер n – 1 из m дает ребра, которые нужно удалить из графа, чтобы получить остовное дерево, которое не должно образовывать цикл.

пример

Посмотрите на следующий график –

Для графика, приведенного в примере выше, у вас есть m = 7 ребер и n = 5 вершин.

Тогда ранг цепи

пример

Пусть ‘G’ – связный граф с шестью вершинами, а степень каждой вершины равна трем. Найдите звание цепи «G».

По сумме теоремы о степени вершин

Схема ранг = | E | – (| V | – 1)

Теорема Кирхгофа

Теорема Кирхгофа полезна для нахождения числа связующих деревьев, которые могут быть сформированы из связного графа.

пример

Матрица «А» заполняется так, как если между двумя вершинами есть ребро, то она должна быть задана как «1», иначе «0».

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.

Однако цикломатическое число не может быть отрицательным. Следовательно, графа, соответствующего условию задачи, не существует.

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.

Однако цикломатическое число не может быть отрицательным. Следовательно, графа, соответствующего условию задачи, не существует.