PPt4Web Хостинг презентаций

Главная / Геометрия / Задача Эйлера
X Код для использования на сайте:

Скопируйте этот код и вставьте его на свой сайт

X

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

После чего скачивание начнётся автоматически!

Кнопки:

Презентация на тему: Задача Эйлера


Скачать эту презентацию

Презентация на тему: Задача Эйлера


Скачать эту презентацию

№ слайда 1 Задача ЭйлераЗадача. Три соседа имеют три общих колодца. Можно ли провести непер
Описание слайда:

Задача ЭйлераЗадача. Три соседа имеют три общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?То, что не получилось на рисунке, не является доказательством невозможности соединения дорожками домиков и колодцев. Для доказательства воспользуемся следующей теоремой Эйлера.

№ слайда 2 Теорема ЭйлераТеорема. Для связного простого графа имеет место равенство В - Р +
Описание слайда:

Теорема ЭйлераТеорема. Для связного простого графа имеет место равенство В - Р + Г = 2, где В - число вершин, Р - общее число ребер, Г - число областей (граней), на которые граф разбивает плоскость.Доказательство. Стянем какое-нибудь ребро графа, соединяющее две вершины, в точку. При этом число ребер и число вершин уменьшаться на единицу и, следовательно, В – Р + Г не измениться. Продолжая стягивать ребра, мы придем к графу, у которого имеется одна вершина, а ребрами являются петли. Уберем какое-нибудь ребро. При этом число ребер и число областей уменьшаться на единицу и, следовательно, В – Р + Г не изменится. Продолжая убирать ребра, мы придем к графу, у которого имеется одна вершина и одно ребро. У этого графа В = 1, Р = 1, Г = 2 и, следовательно, В – Р + Г = 2. Значит, для исходного графа также выполняется равенство В – Р + Г = 2.

№ слайда 3 Решение задачи ЭйлераПредположим, что можно провести непересекающиеся дорожки от
Описание слайда:

Решение задачи ЭйлераПредположим, что можно провести непересекающиеся дорожки от каждого дома к каждому колодцу. Рассмотрим граф, вершинами которого являются домики и колодцы, а ребрами – дорожки. У него В = 6, Р = 9 и, следовательно, Г = 5. Каждая из пяти областей ограничена, по крайней мере, четырьмя ребрами, поскольку, по условию задачи, ни одна из дорожек не должна непосредственно соединять два дома или два колодца. Так как каждое ребро разделяет две области, то количество ребер должно быть не меньше (5∙4)/2 = 10, что противоречит тому, что их число равно 9.

№ слайда 4 Упражнение 1Посчитайте число вершин (В), ребер (Р) и областей (Г) для графов, из
Описание слайда:

Упражнение 1Посчитайте число вершин (В), ребер (Р) и областей (Г) для графов, изображенных на рисунке.Ответ: а) В = 8, Р = 12, Г = 6; б) В = 6, Р = 12, Г = 8; в) В = 20, Р = 30, Г = 12; г) В = 12, Р = 30, Г = 20.

№ слайда 5 Упражнение 2Посчитайте число вершин (В), ребер (Р) и граней (Г) для многогранник
Описание слайда:

Упражнение 2Посчитайте число вершин (В), ребер (Р) и граней (Г) для многогранников, изображенных на рисунке. Чему равно В – Р + Г?Ответ: а) В = 4, Р = 6, Г = 4; б) В = 8, Р = 12, Г = 6; в) В = 6, Р = 12, Г = 8; г) В = 20, Р = 30, Г = 12; д) В = 12, Р = 30, Г = 20.

№ слайда 6 Упражнение 3Два соседа имеют: а) три общих колодца; б) четыре общих колодца. Мож
Описание слайда:

Упражнение 3Два соседа имеют: а) три общих колодца; б) четыре общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?

№ слайда 7 Упражнение 4Три соседа имеют: а) два общих колодца; б) четыре общих колодца. Мож
Описание слайда:

Упражнение 4Три соседа имеют: а) два общих колодца; б) четыре общих колодца. Можно ли провести непересекающиеся дорожки от каждого дома к каждому колодцу?

№ слайда 8 Упражнение 5Четыре соседа имеют четыре общих колодца. Можно ли провести непересе
Описание слайда:

Упражнение 5Четыре соседа имеют четыре общих колодца. Можно ли провести непересекающиеся дорожки так, чтобы каждый домик был соединен с тремя колодцами?

№ слайда 9 Упражнение 6Докажите, что пять домиков нельзя соединить непересекающимися дорожк
Описание слайда:

Упражнение 6Докажите, что пять домиков нельзя соединить непересекающимися дорожками так, чтобы каждый домик был соединен с тремя колодцами?Предположим, что это сделать можно. Тогда мы имеем связный простой граф, у которого В = 5, Р = 10 и, следовательно, Г = 7. С другой стороны, поскольку каждая область ограничена, по крайней мере тремя ребрами, то число ребер должно быть больше или равно Противоречие.

Скачать эту презентацию

Презентации по предмету
Презентации из категории
Лучшее на fresher.ru