Урок по ВиС "графы"

И А

Графы

• Обитает чёрный гриф в Северной Африке, Южной Европе, горных системах Азии. В России размножается на Кавказе, Алтае и Тыве.
• На Дальнем Востоке встречается в холодную часть года, причём если в Приморском крае это регулярно зимующая птица, то для Амурской области чёрный гриф является лишь залётным видом.

Ответьте на вопросы

• Что такое граф?
• Что такое степень графа?
• Чему равно количество ребер графа?
• Что такое путь?
• Что такое цикл?
• Какой граф называется связным?

Леонард Эйлер

(1707г – 1783гг)

Швейцарский, прусский и российский математик

Итак, как вы все знаете, 1ая работа по теории графов принадлежит Леонарду Эйлеру. Ещё в 1736 году в одном из своих писем итальянскому математику и инженеру Мариони он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов. Но при решении этой задачи сам Эйлер не использует термин «граф». Только через 200 лет, в 1936 году, этот термин был предложен венгерским математиком Денешом Кёнигом в его работе «Теории конечных и бесконечных графов». В начале 20 века наряду с термином «граф» употреблялись и другие: карта, комплекс, диаграмма, сеть, лабиринт и т.п. В настоящее время, термин «граф» считается устоявшимся, хотя в прикладной математике, наряду с ним употребляется и термин «сеть» (сети Петри, нейронные сети и т.д.)

Задача 1

В графе 3 вершины, каждая из которых имеет степень 2 . Сколько у него ребер? Нарисуйте такой граф.

Задача 1 (решение)

В графе 3 вершины, каждая из которых имеет степень 2 . Сколько у него ребер? Нарисуйте такой граф.

В режиме слайдов ответы появляются после кликанья мышкой

Ответ: 3.

Задача 2

В первенстве класса по настольному теннису принимали участие 5 учеников:

Андрей, Борис, Галина, Олег, Елена.

Первенство проводилось по круговой системе – каждый участник играет с каждым из остальных один раз.

К настоящему моменту некоторые игры уже проведены:

• Андрей сыграл с Борисом, Галиной и Еленой;
• Борис с Андреем и Галиной;
• Галина с Андреем и Олегом.

Сколько игр проведено к настоящему

моменту и сколько ещё осталось?

Задача 2 (решение)

• Андрей сыграл с Борисом, Галиной и Еленой;
• Борис с Андреем и Галиной;
• Галина с Андреем и Олегом.

Андрей

Галина

Борис

Олег

Елена

Ответ: сыграно 5 партий,

осталось 5 партий.

Задача 3 По окончании деловой встречи специалисты обменялись визитными карточками ( каждый вручил свою карточку другому). Сколько всего визитных карточек было роздано, если во встрече участвовало 4 человека?

Задача 3 (решение) По окончании деловой встречи специалисты обменялись визитными карточками (каждый вручил свою карточку каждому). Сколько всего визитных карточек было роздано, если во встрече участвовали 4 человека?

2

1

3

4

Ответ: 12.

Задача 3

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

Задача 3 (решение)

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

1 клетка

2 клетка

3 клетка

Ответ: 6 вариантов

Электронная физкультминутка

для глаз

Берегите зрение!

Задача №1

Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу).

Сколько всего рукопожатий было сделано?

Решение:

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

Воспользуемся формулой: количество рёбер в графе равно сумме степеней его вершин, делённой на 2 .

(5 ∙ 4) : 2=10.

Ответ:10 рукопожатий

Задача №2

В ДВФО 68 городов, а из каждого города выходит 4 дороги. Сколько всего дорог в ДВФО?

Решение:

Воспользуемся формулой: количество рёбер в графе равно сумме степеней его вершин, делённой на 2 .

Ответ: 136 дорог.

(68 ∙ 4) : 2 = 136.

Задача №3

Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?

Решение:

Воспользуемся формулой: количество рёбер в графе равно сумме степеней его вершин, делённой на 2

Нет, не может

Если X - число городов

Самостоятельная работа

Домашнее задание

повторить п.18-20, №139

Рефлексия

Спасибо за урок!