какое наибольшее число ребер может быть в двудольном графе на 1212 вершинах
Какое наибольшее число ребер может быть в двудольном графе на 1212 вершинах
а) Какое наибольшее число рёбер может быть в 30-вершинном графе, в котором нет треугольников?
б) Какое наибольшее число рёбер может быть в 30-вершинном графе, в котором нет полного подграфа из четырёх вершин?
Подсказка
Выберите вершину наибольшей степени.
Решение
а) Оценка. Выберем вершину A наибольшей степени n и рассмотрим подграф G, образованный вершинами, куда ведут рёбра из A. Ясно, что в этом подграфе рёбер нет. Каждая вершина, не входящая в G имеет степень не больше n, а выходящие из них рёбра – это все рёбра исходного графа. Таким образом, общее число рёбер исходного графа не превосходит n(30 – n) ≤ 15².
Пример. Разобьём 30 вершин на две группы по 15 и проведём все рёбра, соединяющие вершины из разных групп. Получился граф без треугольников с 225 рёбрами.
б) Оценка. Выберем вершину A наибольшей степени n и рассмотрим подграф G, образованный вершинами, куда ведут рёбра из A. Ясно, что в этом подграфе нет треугольников, поэтому, как фактически доказано в а), число его рёбер не превосходит ( n /2)². Таким образом, общее число рёбер исходного графа не превосходит (n/2)² + n(30 – n) = 3 /4 n(40 – n) ≤ 3 /4·20² = 300.
Пример. Разобьём 30 вершин на три группы по 10 и проведём все рёбра, соединяющие вершины из разных групп. Получился граф без полных 4-подграфов с 300 рёбрами.
Ответ
Замечания
Эти задачи – частные случаи теоремы Турана (см. статью в Википедии).
Какое наибольшее число ребер может быть в двудольном графе на 1212 вершинах
Получите 30₽ за публикацию своей разработки в библиотеке «Инфоурок»
и получить бесплатное свидетельство о размещении материала на сайте infourok.ru
Попробуйте УМНЫЙ ПОИСК по курсам повышения квалификации и профессиональной переподготовки
Граф называется двудольным, если его вершины можно разбить на две группы (две доли) так, что каждое ребро в этом графе соединяет вершины, принадлежащие разным группам.
Двудольный граф удобно изображать, нарисовав отдельно вершины двух долей.
Пример.
На школьном балу каждый мальчик станцевал с тремя девочками, а каждая девочка — с четырьмя мальчиками.
Этот граф может выглядеть следующим образом:
Не все графы являются двудольными. Например, граф с тремя вершинами, в котором каждые две вершины соединены ребром, не является двудольным.
Утверждение.
Сумма степеней всех вершин одной доли двудольного графа равна сумме степеней всех вершин другой его доли и равна общему числу рёбер в двудольном графе.
ЗАДАЧА 1. (Поиск количества вершин в одной доле по известным степеням всех вершин и количеству вершин в другой доле.)
На школьном балу каждый мальчик станцевал с тремя девочками, а каждая девочка — с четырьмя мальчиками. Сколько мальчиков пришло на бал, если всего было 9 девочек?
РЕШЕНИЕ.
Пусть на бал пришли х мальчиков.
Каждая девочка станцевала ровно с 4 мальчиками. Значит, степень каждой вершины в левой доле графа равна 4.
Каждый мальчик станцевал ровно с 3 девочками. Значит, степень каждой вершины в правой доле графа равна 3.
Причём в левой доле 9 вершин (9 девочек), а в правой доле – неизвестно (обозначим х).
Тогда можно составить уравнение:
х = 12.
ОТВЕТ: 12 мальчиков.
ЗАДАЧА 2. (Поиск количества вершин в одной доле по известным степеням всех вершин и количеству вершин в другой доле.)
Десять хулиганов кидали снежки в окна школы. Первый хулиган попал в окно ровно 1 раз, второй — ровно 2 раза, …, десятый — ровно 10 раз, причём никакой хулиган не попал в одно и то же окно дважды. В каждое школьное окно либо попали снежком 5 раз, либо не попали вовсе. Сколько школьных окон пострадали от снежков?
РЕШЕНИЕ.
Рассмотрим двудольный граф.
Левая доля графа состоит из 10 вершин (10 хулиганов).
Правая доля состоит из х вершин (количество пострадавших окон).
Если хулиган попал в какое-то окно, то соответствующие вершины будем соединять ребром.
Степени вершин в левой доле: 1, 2, 3, …, 10 (количество попаданий в окна каждым хулиганом).
Степень каждой «пострадавшей» вершины в правой доле графа равна 5 (т.к. в каждое окно либо попали 5 раз, либо ни разу не попали, а количество окон, которые не пострадали, нас не интересует).
Тогда можно составить уравнение:
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 5 ∙ х,
х = 11.
ОТВЕТ: 11 окон.
ЗАДАЧА 3. (Равенство сумм степеней вершин в долях используется для составления уравнения.)
В школе олимпийского резерва каждый хоккеист дружит с 5 гимнастками и 5 хоккеистами из школы, а каждая гимнастка дружит с 4 гимнастками и 4 хоккеистами. Какое наименьшее суммарное количество хоккеистов и гимнасток может учиться в школе олимпийского резерва?
РЕШЕНИЕ.
Рассмотрим двудольный граф.
Вершины левой доли – это хоккеисты и хоккеистки (их количество обозначим Х). Каждый хоккеист дружит с 5 гимнастами. Тогда сумма степеней вершин левой доли равна 5Х.
Вершины правой доли – гимнасты и гимнастки (их количество обозначим Г). Каждый гимнаст дружит с 4 хоккеистами. Тогда сумма степеней вершин правой доли равна 4Г.
Эти суммы должны быть равны.
Составим уравнение:5Х = 4Г.
В этом уравнении левая часть должна делиться на 4, а правая часть должна делиться на 5.
Чтобы левая часть делилась на 4, число Х нужно брать из набора <4, 8, 12, …>.
При этом число Х должно быть больше 4, т.к. каждый хоккеист дружит с 5 хоккеистками.
Значит, число 4 не подходит.
Если Х = 8, то Г = 10.
Всего общее количество составит минимум Х + Г = 8 + 10 = 18.
Максимальное число ребер в графе без простых циклов
Каково максимальное число ребер в графе с n вершинами, который не содержит простых циклов.
Помощь в написании контрольных, курсовых и дипломных работ здесь.
Максимальное количество рёбер в простом двудольном графе
Добрый вечер. Было бы хорошо разобраться с этой задачей: Определите максимальное количество.
Найти в графе максимальное подмножество попарно несмежных ребер
Доброго всем времени суток. Стоит задача, найти в графе максимальное подмножество попарно.
Поиск простых циклов в графе
Есть ориентированный граф(задан списком смежности, или матрицей смежности, не критично), необходимо.
Поиск простых циклов в ориентированном графе
Есть ориентированный граф(задан списком смежности, или матрицей смежности, не критично), необходимо.
Вопрос: Каково максимальное число ребер в ориентированном графе с n вершинами?
Предположим, что самоциклов нет.
Предположим, что существует не более одного ребра от заданной начальной вершины до заданной конечной вершины.
Каждое ребро определяется его начальной вершиной и конечной вершиной. Существует n вариантов для начальной вершины. Так как нет петель, есть n-1 вариантов для конечной вершины. Умножение их вместе подсчитывает все возможные варианты.
Вопрос: Каково максимальное число ребер в неориентированном графе с n вершинами?
Предположим, что самоциклов нет.
Предположим, что существует не более одного ребра от заданной начальной вершины до заданной конечной вершины.
В неориентированном графе каждое ребро задается двумя его конечными точками и порядок не имеет значения. Таким образом, число ребер-это число подмножеств размера 2, выбранных из множества вершин. Поскольку множество вершин имеет размер n, то число таких подмножеств задается биномиальный коэффициент C (n, 2) (также известный как «n выбирает 2»). Используя формулу для биномиальных коэффициентов, C(n,2) = n (n-1)/2.
Какое наибольшее число ребер может быть в двудольном графе на 1212 вершинах
Задача 1: В классе каждый мальчик дружит с тремя девочками, а каждая девочка – с пятью мальчиками. 17 из них любят играть в матбой, и в классе 15 парт. Сколько всего ребят в классе?
Задача 2: В прошлом учебном году в городе прошли такие мат.олимпиады: городская, областная, и турнир городов. В каждой из них участвовало нечетное число учеников маткласса, причем участник участвовал в нечетном числе олимпиад. Всего в матклассе 20 учеников. Докажите, что кое-кто из них не был ни на одной олимпиаде.
Задача 3: В двудольном графе сумма степеней вершин каждого цвета равны между собой.
Задача 4: Если в двудольном графе степени всех вершин одинаковы, то вершин каждого цвета поровну.
Задача 5: Какое наибольшее число ребер может быть в двудольном графе с b белыми и r черными вершинами?
Задача 6: Какое наибольшее число ребер может быть в двудольном графе а) с 2n вершинами; б) с 2n+1 вершиной?
Задача 7: В строку выписано 11 целых чисел. Для любой группы подряд идущих чисел подсчитана ее сумма (группы из одного числа тоже учитывались). Какое наибольшее количество сумм могло оказаться нечетными?
Задача 8: Может ли конь обойти шахматную доску 7 × 7 так, чтобы побывать на каждом поле ровно по одному разу и вернуться последним ходом на исходное поле?
Задача 9: Докажите, что в двудольном графе нет нечетных циклов.
Задача 10: У куба отмечены вершины и центры граней, а также проведены диагонали всех граней. Можно ли по отрезкам этих диагоналей обойти все отмеченные точки, побывав в каждой из них ровно по одному разу?
Задача 11: Пусть Γ – двудольный граф с черными и белыми вершинами. а) Если в Γ есть замкнутый цикл, проходящий через каждую вершину ровно по одному разу, то вершин каждого цвета – поровну. б) Если в Γ есть путь, проходящий через каждую вершину ровно по одному разу, то что число белых вершин отличается от числа черных вершин не более чем на 1.
Задача 12: Замок в форме треугольника со стороной 50 метров разбит на 100 треугольных залов со сторонами 5 м. В каждой стенке между залами есть дверь. Какое наибольшее число залов сможет обойти турист, не заходя ни в какой зал дважды?
Задача 13: Несколько равносторонних треугольников на плоскости не перекрываются. Всегда ли можно раскрасить их в два цвета так, чтобы треугольники с общим отрезком границы были разного цвета?
Задача 14: Докажите, что дерево – двудольный граф.
Задача 15: (критерий двудольного графа) Граф – двудольный если и только если нём нет нечетных циклов.
Задача 16: При каких n можно в вершинах n-угольника расставить натуральные числа так, чтобы на каждой стороне одно число делилось на другое, а для всех остальных пар чисел такого не было?
Задача 17: а) В клетки доски 8 × 8 записали числа 1, 2, …, 64 в неизвестном порядке. Разрешается узнать сумму чисел в любой паре клеток с общей стороной. Всегда ли можно узнать расположение всех чисел? б) То же для доски 9 × 9.
Задача 18: Можно ли в клетки шахматной доски расставить натуральные числа так, чтобы для любых клеток с общей стороной одно из чисел делилось на другое, а для всех остальных пар клеток такого не было. б) Тот же вопрос для пар клеток с общей стороной или вершиной.
Задача 19: Гриша записал в клетки шахматной доски числа 1, 2, …, 64 в неизвестном порядке. Он сообщил Леше сумму чисел в каждом прямоугольнике из двух клеток и добавил, что 1 и 64 лежат на одной диагонали. Докажите, что по этой информации Леша может точно определить, где какое число записано.
Задача 20: Вершины конечного графа как-то пронумеровали от 1 до n, затем на каждом ребре записали сумму номеров в его концах, а номера в вершинах стерли. Докажите, что
а) Если граф не двудольный, то нумерация однозначно восстанавливается.
б) Если нумерация однозначно не восстанавливается, то этот граф двудольный с равным количеством вершин обоих цветов.