Как найти количество ребер в графе зная степени вершин

Как найти число вершин и ребер в графе окресности каждой пары вершин
Как найти число вершин и ребер в графе окресности каждой пары вершин? Добавлено через 5 минут В.

Найти число вершин и ребер в графе окресности каждой пары вершин (алгоритм решения)
Как найти число вершин и ребер в графе окресности каждой пары вершин? В принципе, я написал, но.

Определить в графе цикл, имеющий наибольшее число рёбер
Помогите с лабораторной пожалуйста Есть граф graph(). Определить цикл, что имеет наибольшее число.

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

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

Найти все мосты в графе (без петель и кратных ребер)
Всем добрый день! Столкнулся с такой задачей: поиск мостов в графе. В инете много алгоритмов для.

Требуется найти количество простых циклов на этом графе
Необходимо сложить значения там где на выводе 1-но число.То есть Cycl 1 + Cycl 3 и вывести.То есть.

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.

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

Степени вершин и подсчет числа ребер графа

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

Понятие графа

Рассмотрим две задачи.

Задача 1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса?

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

Теперь сразу видно, что долететь с Земли до Марса нельзя.

Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4×4 убрать угловые клетки.

Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу?

Решение: Занумеруем последовательно клетки доски:

А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен:

Мы рассмотрели две непохожие задачи. Однако решения этих двух задач объединяет общая идея – графическое представление решения. При этом и картинки, нарисованные для каждой задачи, оказались похожими: каждая картинка – это несколько точек, некоторые из которых соединены линиями.

Такие картинки и называются графами. Точки при этом называются вершинами, а линии – ребрами графа. Заметим, что не каждая картинка такого вида будет называться графом. Например.если вас попросят нарисовать в тетради пятиугольник, то такой рисунок графом не будет. Будем называть что рисунок такого вида, как в предыдущих задачах, графом, если есть какая-то конкретная задача для которой такой рисунок построен.

Другое замечание касается вида графа. Попробуйте проверить, что граф для одной и той же задачи можно нарисовать разными способами; и наоборот для разных задач можно нарисовать одинаковые по виду графы. Здесь важно лишь то, какие вершины соединены друг с другом, а какие – нет. Например, граф для задачи 1 можно нарисовать по-другому:

Такие одинаковые, но по-разному нарисованные графы, называются изоморфными.

Степени вершин и подсчет числа ребер графа

Запишем еще одно определение: Степенью вершины графа называется количество выходящих из нее ребер. В связи с этим, вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной.

С понятием степени вершины связана одна из основных теорем теории графов –теорема о честности числа нечетных вершин. Докажем ее мы немного позднее, а сначала для иллюстрации рассмотрим задачу.

Задача 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?

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

Ответ. Соединить телефоны таким образом невозможно.

Теорема: Любой граф содержит четное число нечетных вершин.

Доказательство: Количество ребер графа равно половине суммы степеней его вершин. Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной. А это возможно только в том случае, если граф содержит четное число нечетных вершин.

Связность графа

Есть еще одно важное понятие, относящееся к графам – понятие связности.

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

Задача 4. В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой.

Доказательство: Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:

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

Если принять во внимание предыдущее определение, то утверждение задачи можно переформулировать и по-другому: “Доказать, что граф дорог страны Семерка связен.”

Теперь вы знаете, как выглядит связный граф. Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф. Пример несвязного графа вы видите на рисунке:

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

Задача 5. В Тридевятом царстве только один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов, – по 20. Докажите, что из столицы можно долететь в город Дальний.

Доказательство: Понятно, что если нарисовать граф ковролиний Царства, то он может быть несвязным. Рассмотрим компоненту связности, которая включает в себя столицу Царства. Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний – по 20, поэтому, чтобы выполнялся закон о четном числе нечетных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности. А так как компонента связности – связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать.

Графы Эйлера

Вы наверняка сталкивались с задачами, в которых требуется нарисовать какую-либо фигуру не отрывая карандаш от бумаги и проводя каждую линию только один раз. Оказывается, что такая задача не всегда разрешима, т.е. существуют фигуры, которые указанным способом нарисовать нельзя. Вопрос разрешимости таких задач также входит в теорию графов. Впервые его исследовал в 1736 году великий немецкий математик Леонард Эйлер, решая задачу о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами.

Задача 6. Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз?

Решение. Если мы будем рисовать граф так, как сказано в условии, то в каждую вершину, кроме начальной и конечной, мы войдем столько же раз, сколько выйдем из нее. То есть все вершины графа, кроме двух должны быть четными. В нашем же графе имеется три нечетные вершины, поэтому его нельзя нарисовать указанным в условии способом.

Сейчас мы доказали теорему об Эйлеровых графах:

Теорема: Эйлеров граф должен иметь не более двух нечетных вершин.

И в заключение – задача о Кенигсбергских мостах.

Задача 7. На рисунке изображена схема мостов города Кенигсберга.

Можно ли совершить прогулку так, чтобы пройти по каждому мосту ровно 1 раз?

3. Задачи к теме “Графы”

Понятие графа.

1. На квадратной доске 3×3 расставлены 4 коня так, как показано на рис.1. Можно ли сделав несколько ходов конями, переставить их в положение, показанное на рис.2?

Решение. Занумеруем клетки доски, как показано на рисунке:

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

При любой последовательности ходов конями порядок их следования, очевидно, измениться не может. Поэтому переставить коней требуемым образом невозможно.

2. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9?

Решение. Поставив в соответствие каждому городу точку и соединив точки линией, если сумма цифр делится на 3, получим граф, в котором цифры 3, 5, 9 связаны между собой, но не связаны с остальными. Значит долететь из города 1 в город 9 нельзя.

Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями: