Презентация на тему "Пути в графе"

19.03.2025

КЛАССНАЯ РАБОТА

Расшифруйте ребус

Мемориал воинской Славы героев Великой Отечественной войны

Обелиск героев-пятигорчан

Мемориальный комплекс «Огонь Вечной Славы»

  Стела Братская могила жертв фашистского террора

Памятник 20-летней Нине Павловне Попцовой

Пути в графе. Связные графы.

• Цепь – это путь в графе из одной вершины в другую, в котором вершины и ребра не повторяются.
• Цикл в графе – это замкнутый путь, у которого начало и конец в одной вершине, а ребра и промежуточные вершины не повторяются.

Несвязный граф

Связный граф

Граф называется связным, если две любые вершины в этом графе соединены путем

Задание 1: Рассмотрите рисунок и выпишите номера графом которые: 1) являются связными ______________ 2) содержат цикл ______________

1, 3, 4, 6, 7

1, 2, 3, 5, 6

4.

2.

1.

3.

6.

5.

7.

Задание 2: В деревне 9 домов. Известно, что у Петра соседи Иван и Антон, Максим сосед Ивану и Сергею, Виктор – Диме и Никите, Евгений – сосед Никиты, а больше соседей нет (соседними считаются дворы, у которых есть общий участок забора). Может ли Петр огородами пробраться к Никите за яблоками?

М

А

И

П

С

В

Н

Е

Д

Ответ: нет.

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

Решение:

В

4

7

А

3

Б

5

6

1

2

8

Г

9

Д

Ответ: 10.

10

Задание 4: На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Е?

1

2+1=3

1+1=2

3+3+2=8

2+1=3

1

Отметим на рисунке индексами сверху каждого пункта количество путей, с помощью которых в него можно попасть

ДОМАШНЕЕ ЗАДАНИЕ:

Изучить параграф 20 на странице 86.

Выполнить №137 и № 139

ОЦЕНИ СЕБЯ!

Что выберешь ты?

Чемодан – было несложно, все понятно, полученные знания пригодятся в дальнейшем.

Корзина – немного затруднялся на уроке, но все понятно, информацию возьму в свою копилку.

Мясорубка – было трудно, полученную информацию нужно дома переработать