Учебник reknow · 7 класс

Вероятность и статистика: теория

10 тем — объяснения простым языком, формулы, рисунки и разобранные примеры. К каждой теме — тренажёр.

Классы:7 8 9 Математика по всем классам →

Чтение диаграмм и таблиц
Круговые диаграммы
Графики реальных процессов
Среднее арифметическое
Медиана, размах, крайние значения
Случайная изменчивость
Случайный опыт и событие
Монета и игральная кость
Графы: вершины и рёбра
Пути, циклы и эйлеров обход

Тема 1 · Вероятность и статистика

Чтение диаграмм и таблиц

Потренироваться: задания по теме →

Диаграммы: столбчатая, круговая и таблица

Простыми словами

В дневнике погоды записано, сколько миллиметров осадков выпало в каждый день. В таблице числа точные, но сравнивать их глазами долго. На столбиковой диаграмме сразу видно: где столбик выше — там больше.

ТаблицаТочные значения. Удобно найти конкретное число по строке и столбцу.

Столбиковая диаграммаНаглядное сравнение. Значение снимают по вертикальной шкале — иногда приблизительно.

Как читать диаграмму

Прочитать заголовок и подписи осей: что показано и в каких единицах.
Определить цену деления шкалы: разность соседних подписей : число делений между ними.
Найти нужный столбик и провести от его верха горизонталь к шкале.
Снять значение по шкале.

Осадки за неделю, мм. Цена деления — 5 мм; наибольшее значение — 22 мм (среда)

Шкала может начинаться не с нуля, а цена деления — быть 2, 5, 20… Сначала посчитайте цену деления, потом читайте значения.

Типовые вопросы

Вопрос	Что делать	По рисунку
Значение в пятницу	Найти столбик «пт» и снять высоту	7
Наибольшее значение	Самый высокий столбик	22 (ср)
Наименьшее значение	Самый низкий столбик	7 (пт)
На сколько больше	Вычесть: большее − меньшее	ср − пн: $22 - 12 = 10$
Во сколько раз больше	Разделить большее на меньшее	вт : пн $= 18 : 12 = 1, 5$
Сумма за неделю	Сложить все значения	$12 + 18 + 22 + 15 + 7 = 74$
Сколько дней больше 14	Провести линию на уровне 14 и посчитать столбики выше неё	3 (вт, ср, чт)

По таблице: в 7«А» 28 учеников, в 7«Б» 25, в 7«В» 31. На сколько в самом большом классе больше учеников, чем в самом маленьком?

Наибольшее — 31, наименьшее — 25.
$31 - 25 = 6$ .

Сначала ответьте себе: «что по оси $x$ , что по оси $y$ , какая цена деления?» — и только потом смотрите на столбики.

Ещё вопросы по диаграмме

Сколько всего данных — сколько столбиков (дней, классов) на диаграмме, а не сумма значений.
Сумма двух наибольших — найти два самых высоких столбика и сложить их значения.
«Верно ли, что значение за вт наибольшее?» — сравнить столбик «вт» со всеми остальными: «да», только если выше него нет ни одного.
Разность значений за два дня — из значения первого названного дня вычесть значение второго.
Сумма всех значений и наибольшее значение — разные величины: наибольшее — высота одного столбика, сумма — итог всех.

Тема 2 · Вероятность и статистика

Круговые диаграммы

Потренироваться: задания по теме →

Диаграммы: столбчатая, круговая и таблица

Простыми словами

Пиццу разрезали между друзьями неравными кусками. Сразу видно, кому досталось больше, а вся пицца — это 100%. Круговая диаграмма устроена так же: круг — целое, секторы — его части.

Весь круг — это 100% и 360°. Сумма долей всех секторов равна 100%, сумма их углов — 360°. Чем больше сектор, тем больше доля.

Проценты и градусы

Сумма:

40 + 25 + 20 + 15 = 100%

144 + 90 + 72 + 54 = 36 0^{\circ}

1% = \frac{36 0 ^{\circ}}{100} = 3, 6^{\circ}

градусы

=

проценты

\cdot 3, 6

; проценты

=

градусы

: 3, 6

Половина50% — 180°, сектор-полукруг.

Четверть25% — 90°, прямой угол.

Восьмая часть12,5% — 45°.

Опорные доли видно на глаз: прямой угол — четверть круга, развёрнутый — половина. Сравнивайте сектор с ними, чтобы оценить долю без транспортира.

Типовые задачи

По диаграмме определите долю части А в процентах.

Сектор А чуть меньше половины круга, его угол $14 4^{\circ}$ .
$144 : 3, 6 = 40%$ .

Какая часть занимает наибольшую долю?

Ищем самый большой сектор — это А (40%).

Опрошено 300 человек, доля ответа Б — 25%. Сколько человек выбрали Б?

25% — это четверть: $300 \cdot 0, 25 = 75$ человек.

Доли А, Б, В известны: 40%, 25%, 20%. Найдите долю Г.

Вместе все доли — 100%: $100 - 40 - 25 - 20 = 15%$ .

Проценты на диаграмме — доли от целого, а не количества. «Б — 25%» не значит «25 человек». Чтобы найти количество, нужно знать целое.

Круговая диаграмма хороша, чтобы показать доли одного целого, но плохо подходит для сравнения близких величин: секторы 24% и 26% на глаз почти не различить — для этого лучше столбиковая диаграмма.

Тема 3 · Вероятность и статистика

Графики реальных процессов

Потренироваться: задания по теме →

Простыми словами

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

По горизонтальной оси обычно откладывают время (или номер измерения), по вертикальной — значение величины. Каждая точка графика — пара «момент → значение».

Как снять значение

От точки

t = 3

поднимаемся до графика и идём влево к оси: значение 6

Найти на горизонтальной оси нужный момент (например, $t = 3$ ).
Подняться вертикально до графика.
Пройти горизонтально к вертикальной оси и прочитать значение: $6$ .

Проверьте цену деления по каждой оси. На рисунке одна клетка по вертикали — это 2 единицы, а не 1.

Что ещё спрашивают

РостГрафик идёт вверх (слева направо) — величина возрастает: на рисунке от 0 до 2 и от 3 до 5.

УбываниеГрафик идёт вниз — величина убывает: от 2 до 3 и от 5 до 7.

ПостоянствоГоризонтальный участок — величина не менялась: от 7 до 8.

Вопрос	Как найти	По рисунку
Наибольшее значение	Самая высокая точка графика	15 (при $t = 5$ )
Наименьшее значение	Самая низкая точка	4 (при $t = 0$ )
Когда было наибольшее	Абсцисса самой высокой точки	$t = 5$
На сколько изменилось	Разность значений в двух моментах	от $t = 3$ до $t = 5$ : $15 - 6 = 9$
Сколько раз было равно 10	Провести горизонталь на уровне 10 и сосчитать пересечения	2 раза

Не путайте вопросы «какое наибольшее значение» (ответ по вертикальной оси: 15) и «в какой момент оно достигнуто» (ответ по горизонтальной: 5).

Читайте график слева направо, как текст: «вверх» — растёт, «вниз» — падает, «ровно» — не меняется.

Ещё вопросы по графику

«На сколько выросло с момента 1 до момента 2» — значение во втором моменте минус значение в первом. Если величина уменьшилась, ответ отрицательный: было 24, стало 17 → $17 - 24 = - 7$ .
Сколько раз росла (убывала) — сравнить каждую пару соседних точек и посчитать подъёмы (спуски).
«Верно ли, что значение всё время росло?» — «да», только если каждая следующая точка выше предыдущей.
Среднее первых двух значений — их сумма, делённая на 2; сумма первого и последнего — значения в крайних точках.
Сколько измерений — число точек на графике. Сравнение моментов: «больше ли значение в момент 5, чем в момент 1» — сравнить высоты точек.
Первым делом — прочитать подписи осей и единицы измерения.

Тема 4 · Вероятность и статистика

Среднее арифметическое

Потренироваться: задания по теме →

Среднее и медиана Среднее, медиана, мода

Простыми словами

Пятеро друзей собрали грибы: кто 3, кто 9, кто 6… Если сложить все грибы и поделить поровну, каждому достанется среднее количество. Среднее арифметическое — это «сколько было бы у каждого, если всё разделить поровну».

\overline{x} = \frac{x _{1} + x _{2} + \dots + x _{n}}{n}

\overline{x}

— среднее,

x_{1}, \dots, x_{n}

— числа набора,

n

— их количество

Коротко: среднее $=$ сумма $:$ количество. Отсюда сумма $=$ среднее $\cdot$ количество.

Как вычислить

Найдите среднее арифметическое чисел 28, 21, 13, 24, 25.

Сумма: $28 + 21 + 13 + 24 + 25 = 111$ .
Количество: $n = 5$ .
$\overline{x} = 111 : 5 = 22, 2$ .

Сумма пяти чисел равна 88. Найдите их среднее.

$88 : 5 = 17, 6$ .

Среднее четырёх чисел равно 15, три из них — 10, 12, 20. Найдите четвёртое.

Сумма всех четырёх: $15 \cdot 4 = 60$ .
Четвёртое: $60 - 10 - 12 - 20 = 18$ .

Излишки над линией среднего (

3 + 2 = 5

) ровно заполняют недостачи под ней (

3 + 2 = 5

)

Свойства среднего

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

2) Если ко всем числам прибавить одно и то же число $c$ , среднее увеличится на $c$ .

3) Если все числа умножить на $k$ , среднее тоже умножится на $k$ .

4) Сумма отклонений чисел от среднего равна нулю.

Среднее чисел 10, 20, 30 равно 20. Среднее чисел 15, 25, 35 (каждое больше на 5) равно $20 + 5 = 25$ .

Не забудьте разделить на количество чисел, а не на последнее число или на 10. И считайте все числа, включая нули: среднее чисел 0, 4, 8 равно $12 : 3 = 4$ , а не $12 : 2$ .

Одно очень большое или очень маленькое число (выброс) сильно сдвигает среднее. В таких случаях «типичное» значение лучше описывает медиана.

Проверка на глаз: ответ должен оказаться между наименьшим и наибольшим числом. Если среднее чисел от 13 до 28 получилось 42 — где-то ошибка.

Ещё задачи на среднее

Неизвестное число: среднее чисел 7 и $x$ равно 10 → сумма $20$ , $x = 13$ .
Добавили число: среднее четырёх чисел 8, пятое 12 → $\frac{4 \cdot 8 + 12}{5} = \frac{44}{5} = 8, 8$ . Если добавить число, близкое к среднему (к набору со средним 13 добавили 13), среднее почти не изменится; число больше среднего его увеличивает, меньше — уменьшает. Заменили наибольшее число нулём — среднее уменьшится.
Среднее чисел от 1 до 10: $\frac{55}{10} = 5, 5$ . Среднее не может быть больше наибольшего значения.
Делить нужно на количество всех чисел (с повторами): если разделить на количество различных значений, получится неверный, завышенный результат.

Тема 5 · Вероятность и статистика

Медиана, размах, крайние значения

Потренироваться: задания по теме →

Среднее и медиана Ящик с усами: квартили и выбросы Среднее, медиана, мода

Простыми словами

Выстроим пятерых школьников по росту. Тот, кто стоит ровно посередине, имеет «серединный» рост — это медиана. А разница между самым высоким и самым низким — размах: он показывает, насколько ребята разные.

Крайние значения — наименьшее и наибольшее числа набора.
Размах — разность наибольшего и наименьшего значений.
Медиана — число, которое стоит посередине упорядоченного набора.

R = x_{m a x} - x_{m i n}

R

— размах,

x_{m a x}

— наибольшее значение,

x_{m i n}

— наименьшее

Как найти медиану

Упорядочить набор по возрастанию.
Если чисел нечётное количество — медиана стоит ровно посередине.
Если чётное — посередине два числа; медиана равна их среднему арифметическому (полусумме).

Набор

2, 18, 20, 21, 29

: в середине третье число — 20

Найдите медиану набора $2, 18, 20, 21, 29$ .

Набор уже упорядочен, чисел 5 — нечётное количество.
Середина — третье число: медиана $= 20$ .

Найдите медиану набора $7, 3, 10, 5$ .

Упорядочим: $3, 5, 7, 10$ .
Чисел 4 — в середине $5$ и $7$ .
Медиана $= \frac{5 + 7}{2} = 6$ .

Самая частая ошибка — взять среднее по счёту число без упорядочивания. В наборе $7, 3, 10, 5$ в «середине» стоят 3 и 10, но медиана — 6.

Номер серединного места в наборе из $n$ чисел: $\frac{n + 1}{2}$ . При $n = 5$ — третье место; при $n = 4$ — «место 2,5», то есть между вторым и третьим.

Размах и выбросы

Найдите размах набора $7, 8, 21, 22, 31$ .

Наибольшее — 31, наименьшее — 7.
$R = 31 - 7 = 24$ .

Выброс — значение, сильно отличающееся от остальных (например, опечатка в данных). Он сильно меняет размах и среднее, но почти не влияет на медиану.

Зарплаты: $30, 32, 35, 38, 40$ тыс. ₽ — медиана 35, среднее 35. Заменим 40 на 400: медиана по-прежнему 35, а среднее стало $\frac{30 + 32 + 35 + 38 + 400}{5} = 107$ .

МедианаУстойчива к выбросам. Показывает «типичное» значение.

РазмахЧувствителен к выбросам. Показывает разброс данных.

Тема 6 · Вероятность и статистика

Случайная изменчивость

Потренироваться: задания по теме →

Доска Гальтона Игральная кость: гистограмма частот Монета: частота и вероятность Случайная изменчивость: выборка и гистограмма

Простыми словами

Взвесим десять яблок с одной ветки — массы окажутся разными. Цена хлеба в разных магазинах тоже разная. Даже бросая одну монету, каждый раз получаем разные серии. Такой естественный разброс называют случайной изменчивостью.

Изменчивость не ошибка, а свойство данных. Статистика описывает её числами: размахом, средним, медианой, а для случайных событий — частотой.

Размах — мера разброса

R = x_{m a x} - x_{m i n}

R

— размах,

x_{m a x}

x_{m i n}

— наибольшее и наименьшее значения

Чем больше размах, тем сильнее различаются данные. Единицы размаха те же, что у данных (см, ₽, кг).

Рост учеников меняется от 69 до 93 см. Чему равен размах?

$R = 93 - 69 = 24$ см.

Цена товара в разных магазинах: 72, 84, 96 ₽. Чему равен размах?

Наибольшая цена 96, наименьшая 72.
$R = 96 - 72 = 24$ ₽.

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

Частота и её устойчивость

частота = \frac{k}{N}

k

— сколько раз событие произошло,

N

— число опытов; частота лежит от 0 до 1

В коротких сериях частота «скачет». Но при большом числе опытов она колеблется всё меньше и приближается к постоянному числу — вероятности события. Это называют статистической устойчивостью.

Пример опыта: частота орла сначала сильно колеблется, затем держится около 0,5

Монету бросили 10 раз, орёл выпал 7 раз. Значит ли это, что монета «нечестная»?

Частота $\frac{7}{10} = 0, 7$ .
При 10 бросках такое отклонение от 0,5 — обычное дело. Вывод делать рано: нужны сотни бросков.

Мало опытов — частота случайна; много опытов — частота устойчива. На этом основаны опросы, контроль качества, страхование.

Устойчивость частот проверяли и опытами: например, французский естествоиспытатель Ж. Бюффон в XVIII веке бросил монету 4040 раз и получил частоту орла около 0,5.

Ещё вопросы об изменчивости

Случайная изменчивость — различие значений одной величины при повторных измерениях или наблюдениях. Сильнее ей подвержен рост случайного прохожего, чем число сторон квадрата или минут в часе.
За результат нескольких измерений разумно принять их среднее: 66, 67, 68 см → 67 см; 88, 96, 80 → $264 : 3 = 88$ . Чем больше измерений, тем среднее устойчивее. Среднее может не совпадать ни с одним значением: в классе может не оказаться ни одного ученика ровно среднего роста.
Размах равен нулю — все значения одинаковы.
Частота не бывает больше 1. Число наступлений = частота × число опытов: $0, 4 \cdot 50 = 20$ .

Тема 7 · Вероятность и статистика

Случайный опыт и событие

Потренироваться: задания по теме →

Монета: частота и вероятность

Простыми словами

Вытягиваем билет на экзамене, бросаем кость, ждём автобус — результат заранее не известен. Такое действие называют случайным опытом, а его возможные результаты — исходами. Событие — то, что может произойти в результате опыта: «выпало чётное число», «попался выученный билет».

ДостоверноеПроисходит всегда. «На кости выпало число меньше 7».

P = 1

НевозможноеНе происходит никогда. «На кости выпало 8».

P = 0

СлучайноеМожет произойти, а может и нет. «Выпала шестёрка».

0 < P < 1

Вероятность события

Если все исходы опыта равновозможны (ни один не «предпочтительнее»), вероятность считают так:

P (A) = \frac{m}{n}

n

— число всех равновозможных исходов,

m

— число исходов, благоприятных событию

A

Благоприятный исход — тот, при котором событие $A$ наступает. Так как $0 \leq m \leq n$ , всегда $0 \leq P (A) \leq 1$ .

Все вероятности лежат на отрезке от 0 до 1; ближе к 1 — событие вероятнее

В опыте 10 равновозможных исходов, событию благоприятны 6. Найдите вероятность.

$n = 10$ , $m = 6$ .
$P = \frac{6}{10} = 0, 6$ .

В коробке 4 красных и 16 синих шаров. Наугад берут один. Какова вероятность, что он красный?

Всего шаров (исходов) $n = 4 + 16 = 20$ .
Красных $m = 4$ .
$P = \frac{4}{20} = 0, 2$ .

$n$ — все исходы, а не «неблагоприятные». В примере с шарами делим на 20, а не на 16.

Противоположное событие

Событие $\overline{A}$ («не $A$ ») — противоположное событию $A$ : оно наступает тогда и только тогда, когда $A$ не наступает. Вместе они дают все исходы.

P (\overline{A}) = 1 - P (A)

вероятности противоположных событий в сумме дают 1

Вероятность события равна 0,96. Найдите вероятность противоположного события.

$1 - 0, 96 = 0, 04$ .

Вероятность, что ручка пишет плохо, 0,07. Найдите вероятность, что купленная ручка пишет хорошо.

«Пишет хорошо» — противоположное событие: $1 - 0, 07 = 0, 93$ .

Если считать «да» сложно, посчитайте «нет» и вычтите из 1.

Вероятность не бывает больше 1 и меньше 0. Получили $1, 2$ или $- 0, 3$ — ищите ошибку.

Ещё вопросы о вероятности

Ожидаемое число наступлений ≈ вероятность × число опытов: при $P = 0, 5$ за 20 опытов — примерно 10 раз (но не обязательно ровно 10).
Число благоприятных исходов = вероятность × число всех исходов: $0, 2 \cdot 10 = 2$ ; неблагоприятных — остальные: из 25 исходов при 14 благоприятных неблагоприятны 11.
Маловероятному событию соответствует вероятность, близкая к 0 (например, $0, 01$ ); событие с вероятностью $0, 59$ вероятнее, чем с $0, 41$ .
Вероятность записывают дробью «благоприятные : все», а не отношением благоприятных к неблагоприятным.

Тема 8 · Вероятность и статистика

Монета и игральная кость

Потренироваться: задания по теме →

Дерево вероятностей Игральная кость: гистограмма частот Монета: частота и вероятность Сумма на двух кубиках Вероятность

Простыми словами

Монета падает орлом или решкой, кость — одной из шести граней. Если монета и кость «честные», ни один исход не имеет преимущества — исходы равновозможны. Поэтому вероятность здесь легко посчитать: надо просто сосчитать исходы.

P (A) = \frac{m}{n}

n

— число всех равновозможных исходов,

m

— число исходов, благоприятных событию

A

Монета

Один бросок — 2 исхода (О, Р), $P (орёл) = \frac{1}{2} = 0, 5$ . При нескольких бросках исходы удобно перебирать деревом: каждый бросок удваивает число ветвей.

Два броска —

2 \cdot 2 = 4

равновозможных исхода

При $k$ бросках монеты число исходов $n = 2^{k}$ : 1 бросок — 2, два — 4, три — 8, четыре — 16.

Монету бросают дважды. Найдите вероятность, что орёл выпадет ровно один раз.

Всего исходов $n = 4$ : ОО, ОР, РО, РР.
Благоприятные: ОР и РО, $m = 2$ .
$P = \frac{2}{4} = 0, 5$ .

ОР и РО — разные исходы (орёл в первый раз или во второй). Если считать их одним, получится неверное $n = 3$ .

Игральная кость

У кости 6 граней: 1, 2, 3, 4, 5, 6. Например, $P (чётное) = \frac{3}{6} = 0, 5$ , $P (больше 4) = \frac{2}{6} = \frac{1}{3}$ .

При броске двух костей исходов $6 \cdot 6 = 36$ — их выписывают таблицей: строка — первая кость, столбец — вторая, в клетке — сумма очков.

	1	2	3	4	5	6
1	2	3	4	5	6	7
2	3	4	5	6	7	8
3	4	5	6	7	8	9
4	5	6	7	8	9	10
5	6	7	8	9	10	11
6	7	8	9	10	11	12

Бросают две кости. Найдите вероятность, что в сумме выпадет 7.

Всего исходов $n = 36$ .
Сумма 7 — на диагонали таблицы, $m = 6$ .
$P = \frac{6}{36} = \frac{1}{6} \approx 0, 17$ .

Частота и вероятность

Частота события — доля опытов, в которых оно произошло:

частота = \frac{k}{N}

k

— сколько раз событие наступило,

N

— сколько проведено опытов

Монету бросили 20 раз, орёл выпал 14 раз. Найдите частоту орла.

$\frac{14}{20} = 0, 7$ .

ВероятностьСчитается заранее, по числу исходов: для орла всегда

0, 5

ЧастотаПолучается из опыта и каждый раз немного разная:

0, 7

0, 45

0, 52

…

При большом числе бросков частота орла становится близкой к $0, 5$ — это статистическая устойчивость.

Вероятность — «что должно быть в теории», частота — «что получилось на практике».

Ещё типы вопросов

Невозможное и достоверное: семёрка на одной кости не выпадет никогда — вероятность $0$ ; «не больше шести очков» выпадет всегда — вероятность $1$ .
Хотя бы один орёл при двух бросках: из ОО, ОР, РО, РР подходят три — $P = \frac{3}{4}$ ; все орлы при двух бросках — $\frac{1}{4} = 0, 25$ . При пяти бросках исходов $2^{5} = 32$ .
Две кости: исходов 36 (а не 12): каждой грани первой кости соответствуют 6 граней второй. Сумма 3 — два исхода (1+2, 2+1); сумма 9 — четыре (3+6, 4+5, 5+4, 6+3), $P = \frac{4}{36} \approx 0, 11$ ; «по 5 на обеих» — один исход, $P = \frac{1}{36} \approx 0, 03$ .
Кость: «ровно 2 очка» — $\frac{1}{6} \approx 0, 17$ ; «больше 2» — грани 3, 4, 5, 6: $\frac{4}{6} \approx 0, 67$ .
Вероятность не гарантирует результат серии: при двух бросках орёл не обязательно выпадет ровно один раз. Частота 5 орлов из 10 — $0, 5$ , она совпала с вероятностью (отличие $0$ ).

Тема 9 · Вероятность и статистика

Графы: вершины и рёбра

Потренироваться: задания по теме →

Простыми словами

Схема метро, карта дорог между городами, список «кто с кем дружит» — всё это можно нарисовать точками и линиями. Точки — объекты, линии — связи между ними. Такой рисунок называют графом.

Граф — набор точек (вершин) и линий, соединяющих некоторые пары вершин (рёбер). Важно только, какие вершины соединены; длина и форма линий значения не имеют.

Степень вершины

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

6 вершин, 7 рёбер; сумма степеней

2 + 3 + 3 + 2 + 3 + 1 = 14 = 2 \cdot 7

d_{1} + d_{2} + \dots + d_{n} = 2 m

сумма степеней всех вершин равна удвоенному числу рёбер

Здесь $d_{1}, \dots, d_{n}$ — степени вершин, $m$ — число рёбер. Причина: каждое ребро имеет два конца и потому учтено в степенях двух вершин.

Следствия: сумма степеней всегда чётна; число вершин нечётной степени чётно.

Как считать вершины и рёбра

У графа 5 вершин, степень каждой равна 4. Сколько рёбер?

Сумма степеней: $5 \cdot 4 = 20$ .
Рёбер вдвое меньше: $m = 20 : 2 = 10$ .

Может ли быть граф со степенями вершин 3, 3, 2, 1?

Сумма: $3 + 3 + 2 + 1 = 9$ — нечётна.
А должна быть $2 m$ — чётной. Такого графа нет.

Считая рёбра по рисунку, отмечайте каждое посчитанное ребро галочкой — иначе легко посчитать одно дважды. Для проверки сложите степени и разделите на 2.

Пересечение двух линий на рисунке — ещё не вершина. Вершины обычно обозначены жирными точками.

Связность

Граф связный, если из любой вершины можно дойти по рёбрам до любой другой. Иначе он распадается на несколько компонент связности — отдельных «кусков».

Чтобы связать $n$ вершин, нужно не меньше $n - 1$ рёбер. Связный граф ровно с $n - 1$ ребром не имеет циклов — это дерево.

Нужно соединить дорогами 8 деревень так, чтобы из любой можно было доехать в любую. Наименьшее число дорог: $8 - 1 = 7$ .

Равенство «сумма степеней $= 2 m$ » называют леммой о рукопожатиях: если каждый гость сосчитает свои рукопожатия, в сумме получится удвоенное число рукопожатий.

Тема 10 · Вероятность и статистика

Пути, циклы и эйлеров обход

Потренироваться: задания по теме →

Простыми словами

Можно ли нарисовать «конверт», не отрывая карандаша от бумаги и не проводя линию дважды? Это задача об эйлеровом пути: пройти по всем рёбрам графа ровно по одному разу. Ответ даёт простое правило про степени вершин.

Цепь (путь) — последовательность рёбер, где каждое следующее начинается там, где закончилось предыдущее.
Цикл — замкнутая цепь без повторения рёбер: начало и конец совпадают.

Граф-цикл

Если $n$ вершин соединены «по кругу», получается цикл из $n$ вершин.

Слева — цикл: у каждой вершины степень 2. Справа — степени вершин «конверта»

В цикле из $n$ вершин ровно $n$ рёбер, и степень каждой вершины равна 2.

Цикл из 7 вершин: рёбер 7, степень каждой вершины 2 (сумма степеней $7 \cdot 2 = 14 = 2 \cdot 7$ ✓).

Эйлеров путь и цикл

Эйлеров путь проходит по каждому ребру ровно один раз. Если он ещё и возвращается в начальную вершину — это эйлеров цикл.

Для связного графа считаем вершины нечётной степени:

• $0$ нечётных вершин — есть эйлеров цикл (начать можно где угодно);
• $2$ нечётные вершины — есть эйлеров путь, он начинается в одной нечётной вершине и кончается в другой;
• больше двух — обойти все рёбра по одному разу нельзя.

Можно ли нарисовать «конверт» одним росчерком?

Степени: 3, 3, 4, 4, 2.
Нечётных вершин две (нижние) — эйлеров путь есть.
Начинать нужно в нижней вершине, закончим в другой нижней.

Почему так: проходя через вершину, мы «входим и выходим» — тратим 2 ребра. Нечётное число рёбер может остаться только у начала и конца пути.

Задача о семи мостах Кёнигсберга: обойти город, пройдя по каждому мосту один раз. Л. Эйлер в 1736 году показал, что это невозможно: в соответствующем графе все четыре вершины нечётные.

Деревья и ориентированные графы

Дерево — связный граф без циклов.

В дереве с $n$ вершинами ровно $n - 1$ ребро, а путь между любыми двумя вершинами единственный. Удалите любое ребро — дерево распадётся на две части.

В дереве 12 вершин. Сколько рёбер? $12 - 1 = 11$ .

Ориентированный граф — граф, у рёбер которого есть направление (стрелки), как улицы с односторонним движением. Двигаться по ребру можно только по стрелке.

Не путайте: в цикле рёбер столько же, сколько вершин ( $n$ ), а в дереве — на одно меньше ( $n - 1$ ).

Ещё задачи о графах

Полный граф («каждая вершина соединена с каждой»): степень каждой вершины $n - 1$ , рёбер $\frac{n ( n - 1 )}{2}$ ; при $n = 3$ — 3 ребра, при $n = 5$ степени по 4.
Дерево: в дереве с $n \geq 2$ вершинами не меньше двух висячих вершин (степени 1). Если к дереву добавить одно ребро, появится ровно один цикл; если из цикла удалить одно ребро, получится дерево (цепь). Связный граф с 7 вершинами и 6 рёбрами — дерево, циклов нет; связный граф с 3 вершинами и 3 рёбрами — один цикл. Дерево из 4 вершин в виде цепи превращается в цикл добавлением одного ребра.
Пути по циклу: между двумя вершинами цикла ровно два пути без повторов рёбер — по часовой стрелке и против; к соседней вершине по часовой стрелке — одно ребро. Самый длинный путь без повторов рёбер в цикле из 7 вершин — 7 рёбер (весь цикл); обойти все 8 рёбер цикла и вернуться — 8 рёбер.
Не в любом связном графе есть эйлеров цикл; если все степени чётны — есть (а значит, и эйлеров путь). При ровно двух нечётных вершинах эйлеров путь есть, но цикла нет.

Вероятность и статистика: теория

Оглавление

Чтение диаграмм и таблиц

Простыми словами

Как читать диаграмму

Типовые вопросы

Ещё вопросы по диаграмме

Круговые диаграммы

Простыми словами

Проценты и градусы

Типовые задачи

Графики реальных процессов

Простыми словами

Как снять значение

Что ещё спрашивают

Ещё вопросы по графику

Среднее арифметическое

Простыми словами

Как вычислить

Свойства среднего

Ещё задачи на среднее

Медиана, размах, крайние значения

Простыми словами

Как найти медиану

Размах и выбросы

Случайная изменчивость

Простыми словами

Размах — мера разброса

Частота и её устойчивость

Ещё вопросы об изменчивости

Случайный опыт и событие

Простыми словами

Вероятность события

Противоположное событие

Ещё вопросы о вероятности

Монета и игральная кость

Простыми словами

Монета

Игральная кость

Частота и вероятность

Ещё типы вопросов

Графы: вершины и рёбра

Простыми словами

Степень вершины

Как считать вершины и рёбра

Связность

Пути, циклы и эйлеров обход

Простыми словами

Граф-цикл

Эйлеров путь и цикл

Деревья и ориентированные графы

Ещё задачи о графах