https___authedu.mosreg.ru_ej_attachments_files_068_308_979_original_%D0%93%D1%80%D0%B0%D1%84%D1%8B

1. Графы

2.

3.

4.

Е
Б
В
Д
А
Г
Изолированная вершина
Петля
Висячая вершина
Степень вершины; связь с количеством ребер
Сумма степеней всех вершин четна и равна
удвоенному числу ребер

5.

Б
А
В
Д
Г
Путь в графе
Цепь (простой путь) (вершины и
ребра не повторяются)
Цикл в графе (замкнутый путь без
повторения ребер и вершин)

6.

Б
А
В
Д
Г
Связный граф (любые вершины в
этом графе соединены путем)
Эйлеров путь (путь, проходящей
ровно один раз по каждому ребру)

7.

Б
В
А
Г

8.

9. ЗАДАЧИ

10.

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

11.

2)В Солнечной системе введено космическое
сообщение. Корабли осуществляют рейсы в обе
стороны по следующим маршрутам: Земля –
Меркурий, Марс – Венера, Уран – Нептун. Марс –
Меркурий. Юпитер – Плутон. Меркурий –
Венера, Нептун – Сатурн. Сатурн – Юпитер.
Плутон – Уран. Можно ли добраться с Земли до
Плутона?

12.

3)Архипелаг Числовой состоит из 9 островов, у
которых вместо названий номера от 1 до 9.
Между двумя островами есть паромная
переправа тогда и только тогда, когда сумма
номеров этих островов делится на 3. Можно ли
перебраться на паромах с острова 3 на остров 4?

13.

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

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

15.

1) Изобразить граф, в котором
А) 6 вершин со степенями
1,1,2,2,3,3
Б) 5 вершин со степенями 1,2,2,3,3

16.

2)
В классе 30 человек. Может ли быть
так, что 9 из них имеют по 3
друга (в этом классе), 11 – по 4 друга, а
10 – по 5 друзей?

17.

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