7 класс Онлайн
Онлайн. Глава 1. Линейное уравнение с одной переменной. § 4. Решение задач с помощью графов. Упражнения №№ 4.1 — 4.14. Итоги главы 1. Мерзляк, Поляков: Алгебра. Углубленный уровень: 7 класс. Учебник — М.: Вентана-Граф (Российский учебник). Электронная ознакомительная версия для покупки пособия. Цитаты из книги использованы в учебных целях.
Алгебра 7 класс Мерзляк, Поляков (угл.изуч.)
§ 4. Решение задач с помощью графов.
Вы хорошо знаете, что составление уравнений — это не единственный способ решения текстовых задач. Также эффективным приёмом является «решение задач по действиям», т. е. арифметическим способом, когда в определённой последовательности находят значения числовых выражений и в конечном итоге получают ответ. Здесь переводом задачи из реальной жизни на математический язык является запись одного или нескольких числовых выражений.
Заметим, что в начальной школе именно с этого способа вы начали знакомство с методами решения текстовых задач.
Методы решения задач, представляющие реальные ситуации, разнообразны и далеко не исчерпываются моделями в виде числовых выражений или уравнений. Изучая математику, вы будете расширять список соответствующих моделей. Сейчас познакомимся с методом, применение которого основано на построении математической модели в виде геометрической фигуры. Заметим, что вы уже использовали элементы этого приёма, когда в задачах на движение строили различные схемы: движения в одном направлении, в противоположных направлениях, навстречу друг другу и т. п.
ПРИМЕР 1. В регионе есть пять городов. Можно ли эти города связать дорогами так, чтобы из каждого города выходили: 1) четыре дороги; 2) три дороги?
Решение. Построим схему, на которой города будут изображены точками А, В, С, D и Е. Дорогу, соединяющую два города, будем изображать в виде отрезка. Например, на рисунке 4.1 показана кольцевая схема дорог.
1) Задача сводится к тому, чтобы выяснить, можно ли пять точек плоскости соединить отрезками так, чтобы из каждой точки выходили четыре отрезка. На рисунке 4.2 показано, как это сделать.
2) Предположим, что такая схема возможна. Подсчитаем, сколько отрезков будет на этой схеме. Имеем: 5*3 = 15 (отрезков). Однако при таком подсчёте каждый отрезок был учтён дважды. Получается, что количество отрезков равно 15/2. Это число не является целым. Получили противоречие.
Ответ: 1) да; 2) нет. ■
В повседневной жизни нам нередко приходится пользоваться рисунками, состоящими из точек, некоторые из которых соединены линиями. Например, на рисунке 4.3 изображена схема метрополитена Санкт–Петербурга.
Такие рисунки называют графами. Точки на рисунке называют вершинами графа, а соединяющие их линии — рёбрами графа.
На рисунке 4.4 приведены ещё несколько примеров графов.
Вооружившись фантазией, можно представить, что эти рисунки иллюстрируют схемы автомобильных дорог, план городка аттракционов и даже отношения между людьми, например такие как дружба.
Любопытно, что рисунки такого вида и дворянский титул имеют одинаковое название — граф. Это слово произошло от латинского grafito — пишу.
Графами удобно пользоваться тогда, когда хотят описать связь между объектами, событиями или процессами. Проиллюстрируем сказанное на примере решения следующей задачи.
ПРИМЕР 2. Существует ли компания из 16 человек, в которой каждый дружит ровно с 6 другими людьми из этой компании?
Решение. Нарисуем 16 точек так, как показано на рисунке 4.5. Эти точки изображают 16 человек данной компании. Возьмём произвольную точку и соединим её со всеми точками, находящимися с ней на одной горизонтали или вертикали. Получили 6 рёбер графа, которые соответствуют дружеским связям. Так можно поступить с каждой из 16 точек.
Ответ: существует. ■
Количество рёбер, выходящих из вершины графа, называют степенью этой вершины. Например, степень каждой вершины, изображённой на рисунке 4.1, равна 2.
Заметим, что решение задачи 2 из примера 1 свелось к выяснению вопроса: существует ли пятивершинный граф, степень каждой вершины которого равна 3? Ответ на этот вопрос оказался отрицательным. На самом деле имеет место более общий факт: в любом графе количество вершин, степень которых нечётная, является чётным числом. Он следует из того, что сумма степеней всех вершин графа равна удвоенному количеству его рёбер, а следовательно, является чётным числом.
При проектировании системы транспортных маршрутов важнейшим требованием является возможность попасть из любого населённого пункта в любой другой. На языке теории графов это означает, что соответствующий граф должен обладать таким свойством: любые две вершины графа соединены некоторым путём, т. е. последовательностью рёбер, каждое следующее из которых начинается в конце предыдущего. Граф, обладающий описанным свойством, называют связным.
На рисунке 4.6 изображён связный граф, а граф, изображённый на рисунке 4.7, связным не является.
ПРИМЕР 3. В некотором регионе 9 городов. Из каждого города выходят 4 дороги, связывающие его с четырьмя городами этого региона. Докажите, что из любого города можно проехать в любой другой город.
Решение. Предположим, что не существует пути, соединяющего города А и В. Каждый их этих двух городов соединён с четырьмя другими (отличными от А и В).
Если город А и город В соединены с одним и тем же городом, это означает, что существует путь, соединяющий города А и В. Следовательно, чтобы такого пути не существовало, все 8 городов, с которыми соединены города А и В, должны быть различными. Добавив к ним города А и В, получаем, что количество городов в данном регионе не меньше 10, что противоречит условию задачи. Следовательно, наше предположение неверно. ■
Рассмотренный пример иллюстрирует следующий общий факт: если граф имеет n вершин и степень каждой вершины не меньше, чем (n — 1)/2, то такой граф является связным.
Воспользовавшись идеей решения задачи из примера 3, докажите этот факт самостоятельно.
ИТОГИ ГЛАВЫ 1.
Ознакомительная версия для принятия решения о покупке книги: Мерзляк, Поляков: Алгебра. Углубленный уровень: 7 класс. Учебник — М.: Вентана-Граф, 2019 (Российский учебник). 4. Решение задач с помощью графов.
Сколько рёбер в этом графе (см)?
У графа пять вершин имеют степень 5, шесть вершин — степень 6, семь вершин — степень 7. Сколько рёбер в этом графе?
Для начала отметим, что степень вершины графа (узла) это число ребер, которые соединяют эту вершину с другими вершинами. Понятно, что если у обычного графа две вершины, то степень каждой вершины 1, ребро только одно, если три вершины, то степень каждой равен 2, а ребер 2. И так далее, получается, что число ребер равно половине суммы всех степеней графа (так как при подсчете каждое ребро учитывается дважды). Сумма степеней данного графа равна 5*5 + 6*6 + 7*7 = 25+36+49=110. Значит ребер 55 (110/2). Ответ: 55.
В некотором графе 5 вершин степени которых равны 4 2 1 2 1 сколько ребер в этом графе
7, но только в том случае, если между любыми двумя вершинами существует не более одного ребра
Хотя нет всегда будет 7
Ответ: 7
Пошаговое объяснение:
Очевидно, что две вершинами данного графа могут быть соединены не более чем тремя различными ребрами, ибо если бы можно было соединить 4-мя и более ребрами, то было бы две степени вершин не менее чем 4.
Достроим данный граф таким образом, чтобы любые две его вершины были соединены ровно тремя ребрами.
Достроенные ребра будут иметь красный цвет, а ребра изначального графа будут иметь синий цвет.
У каждого ребра поставим стрелочки прямого и обратного пути. (число стрелок вдвое больше чем ребер, цвет стрелки такой же как и у ребра)
Тогда, поскольку всего 6 вершин, то общее количество стрелочек в достроенном графе равно 15*6. (общее число стрелок равно сумме количеств всех стрелок прямого пути от каждой вершины).
Пусть степень некоторой вершины изначального графа равна n<=4, тогда количество идущих от него прямых синих стрелок равно n, а количество прямых красных стрелок равно: 5*3 — n = 15 — n.
Таким образом, общее количество красных стрелок равно:
(15-4) + (15 -3) + (15 — 3) + (15-2) + (15 — 1) +(15 -1) = 15*6 — 14
Тогда количество синих стрелок равно: 15*6 -( 15*6 — 14 ) = 14
А количество cиних ребер изначального графа равно: 14/2 = 7
P.S используя данный метод можно доказать, что у любого графа число ребер равно полусумме степеней его вершин.
В некотором графе 5 вершин степени которых равны 4 2 1 2 1 сколько ребер в этом графе
Задача 1:
В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими?
Решение:
Предположим, что это возможно. Рассмотрим тогда граф, вершины которого соответствуют телефонам, а ребра – соединяющим их проводам. В этом графе 15 вершин, степень каждой из которых равна пяти. Подсчитаем количество ребер в этом графе. Для этого сначала просуммируем степени всех его вершин. Ясно, что при таком подсчете каждое ребро учтено дважды (оно ведь соединяет две вершины!). Поэтому число ребер графа должно быть равно 15 • 5/2. Но это число нецелое! Следовательно, такого графа не существует, а значит, и соединить телефоны требуемым образом невозможно.
При решении этой задачи мы выяснили, как подсчитать число ребер графа, зная степени всех его вершин. Для этого нужно просуммировать степени вершин и полученный результат разделить на два.
Задача 2:
В государстве 100 городов, и из каждого из них выходит 4 дороги. Сколько всего дорог в государстве?
Решение:
Общее число дорог равно 100 • 4/2 = 200.
Задача 3:
В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 – по 4 друга, а 10 – по 5 друзей?
Решение:
Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 – степень 4, 10 – степень 5. Однако у такого графа 19 нечетных вершин, что противоречит теореме.
Задача 4:
В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы было 4 телефона, каждый из которых соединен с тремя другими, 8 телефонов, каждый из которых соединен с шестью, и 3 телефона, каждый из которых соединен с пятью другими?
Решение:
Нельзя. Примените теорему о числе нечетных вершин.
Задача 5:
У короля 19 баронов-вассалов. Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств?
Решение:
Нет, не может. В противном случае получился бы граф соседства баронств с нечетным количеством нечетных вершин.
Задача 6:
Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?
Решение:
Если в государстве k городов, то дорог – 3k/2. Это число не может быть равно 100.
Задача 7:
Джон, приехав из Диснейленда, рассказывал, что там на заколдованном озере имеются 7 островов, с каждого из которых ведет 1, 3 или 5 мостов. Верно ли, что хотя бы один из этих мостов обязательно выходит на берег озера?
Решение:
Да, верно, иначе нарушается теорема о числе нечетных вершин.
Задача 8:
Докажите, что число людей, когда-либо живших на Земле и сделавших нечетное число рукопожатий, четно.
Решение:
Это в точности теорема о нечетных вершинах.
Задача 9:
Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими?
Решение:
Нет, нельзя. Примените теорему к графу, вершины которого – данные отрезки, а ребро соединяет две вершины тогда, когда два соответствующих отрезка пересекаются.