Школьная математика: подготовка к ОГЭ и ЕГЭ

Что такое граф?

Граф — это рисунок объектов – точек и связей между ними – соединяющих их линий. (например, схема метро, карта дорог, электросхема и т.п.)

Точки — вершины. Это объекты: люди, места, события.

Линии — ребра. Это связи между ними: дороги, знакомства, переходы. Каждое ребро соединяет ровно две вершины.

Правила:

1. Ребро соединяет ровно две вершины.
2. Форма линии (прямая или кривая) не важна.
3. Вершины можно рисовать где угодно.
4. Если линии пересеклись не в вершине — новая вершина (точка) не образовалась! Линии просто пересеклись

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

Нам важно – какие именно пуговицы соединены!

Пример 1: Граф-расписание

Вершины: Уроки: Математика (М), Русский язык (Р), Физкультура (Ф), История (И).

Ребра: связывают уроки, которые идут друг за другом (парами).

М — Р (с математики идешь на русский)

Р — Ф (с русского на физкультуру)

Ф – И ( с физкультуры на историю)

Получается цепочка: М–Р–Ф–И. Это путь по графу, где вершины и ребра не повторяются. Если граф состоит из одной единственной цепи, то такой граф называется цепью.

Граф: М — Р — Ф — И.

Пример 2: Граф-маршрут

Прямой дороги в школу нет. В школу можно пройти двумя маршрутами: через парк и через булочную.

Построим граф.

Места: Дом (Д), Парк (П), Булочная (Б), Школа (Ш). Дорожки между ними.
Граф показывает 2 пути: Д–П–Ш и Д–Б–Ш

Степень вершины. Теорема о сумме степеней вершины.

Степень вершины — это количество ребер, которые из неё выходят.

На графе – маршруте:

• Степень вершины Д (Дом) = 2 (ведет в Парк и в Булочную).
• Степень вершины Ш (Школа) = 2 (ведет в Парк и в Булочную).
• Степень вершины П (Парк) = 2 (ведет в Дом и в Школу).
• Степень вершины Б (Булочная) = 2 (ведет в Дом и Школу).

Теорема о сумме степеней вершины. В любом графе сумма степеней всех вершин является четным числом.

У каждого ребра два конца, поэтому сумма степеней всех вершин в два раза больше числа ребер, то есть четное число.

ПРАВИЛО: Сумма степеней всех вершин графа равна удвоенному числу ребер.

Свойство: В любом графе количество вершин нечетной степени четно.

Задачи.

№ 127 (Учебник)

На конференцию собрались ученые. Могло ли оказаться так, что пятеро из них знакомы ровно с тремя другими, а все остальные имеют ровно четверых знакомых среди собравшихся?

Решение:

По условию, дано 5 вершин с нечетной степенью 3.

Так как, согласно свойству, количество вершин нечетной степени четно, ответ - нет не может.

№ 130 (Учебник)

В некотором графе 6 вершин 6 вершин, степени которых равны

а) 2, 2, 3, 3, 4, 4;

б) 0, 1, 2, 2, 3, 4.

Сколько ребер в этом графе?

Решение:

Сумма степеней всех вершин в два раза больше числа ребер.

а) Сумма степеней равна: 2+2+3+3+4+4=18

значит количество ребер равно 18:2 = 9

Ответ: 9 ребер.

б) Сумма степеней вершин равна: 0+1+2+2+3+4=12

значит количество ребер: 12:2=6

Ответ: 6 ребер.

Подготовка к ВПР

Задача 1.1. 

Нарисуй граф для троих друзей: Аня, Боря, Ваня, если все они дружат между собой. Сколько ребер?

Решение: Вершины: А, Б, В. Ребра: А–Б, А–В, Б–В.

Ответ: 3 ребра. Граф — треугольник.

Задача 1.2 (Аналог ВПР). 

В графе пять вершин: А, Б, В, Г, Д. Известны рёбра: А–Б, А–В, Б–В, Б–Г, Г–Д. Найдите степень вершины Б.

Решение: Выпишем все рёбра, где есть вершина Б: А–Б, Б–В, Б–Г.

Ответ: Степень вершины (Б) = 3.

Задача 2.1

В графе 6 вершин. Степени пяти вершин равны: 3, 3, 2, 2, 2. Сколько в графе ребер, если степень шестой вершины равна 1?

Решение:

Сумма степеней равна: 3+3+2+2+2+1 = 13.

Количество ребер равно:  13 :2 = 6,5 — получается нецелое число! 

Сумма степеней должна быть четным числом

Ответ: Такого графа не существует

Задача 2.2

В графе 5 вершин. Степени четырех вершин: 2, 2, 1, 1. Чему равна степень пятой вершины, если в графе всего 4 ребра?

Решение:

Пусть х – степень пятой вершины, тогда

Сумма степеней вершин 2 + 2 + 1 + 1 + х

число ребер равно 4.  Сумма степеней равна удвоенному количеству ребер графа. Запишем уравнение: 2+2+1+1 + x = 8, решим его и получим

x = 2.

Ответ: Степень пятой вершины равна 2.

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

Определение: Граф называется полным, если любые две его вершины соединены ребром (см. рисунок).

Число ребер в полном графе с n вершинами равно     

Задачи.

Задача (Аналог ВПР). 

В компании 7 человек обменялись рукопожатиями (каждый с каждым по разу). Сколько всего было рукопожатий?

Решение:

Первый пожал руку шестерым – всего 6 рукопожатий;

Второй уже пожал руку первому, поэтому осталось 5 рукопожатий.

Продолжаем рассуждать аналогично, в результате получим: 6 + 5 + 4 + 3 + 2 + 1 = 21.

Второй способ:

Это полный граф с 7 вершинами. Каждое ребро — рукопожатие.

Используем формулу

Ответ: 21.

Задача 3.1

Маша, Даша, Глаша и Саша перед уроком физкультуры обменялись друг с другом «дай пять!» ровно по одному разу. Сколько всего было «дай пять!»? Нарисуй граф.

Решение: 

Аналогично рукопожатиям для 4-х человек. Граф — полный с 4 вершинами.

Ответ: 6

Задача 3.2 (аналог ВПР).

В классе 15 человек. У каждого есть ровно 3 друга в этом классе (дружба взаимная). Может ли так быть? Ответ объясните.

Решение: 

Применим теорему. Если у каждого 3 друга, то степень каждой вершины = 3.

Сумма степеней = 15 * 3 = 45.

Значит, число ребер 45 : 2 = 22,5.

Число ребер не может быть дробным.

Ответ: нет, не может. Сумма степеней всех вершин должна быть чётной.