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

Презентация:



Advertisements
Похожие презентации
Задача Эйлера То, что не получилось на рисунке, не является доказательством невозможности соединения дорожками домиков и колодцев. Для доказательства воспользуемся.
Advertisements

Вершины, ребра и грани Рассмотрим известные нам многогранники и заполним следующую таблицу, в которой В – число вершин, Р – число ребер, Г – число граней.
Вершины, ребра и грани Рассмотрим известные нам многогранники и заполним следующую таблицу, в которой В – число вершин, Р – число ребер, Г – число граней.
Координаты вектора Пусть на плоскости задана прямоугольная система координат. Определим понятие координат вектора. Для этого отложим вектор так, чтобы.
ВЫПУКЛЫЕ МНОГОГРАННИКИ Многогранник называется выпуклым, если он является выпуклой фигурой, т. е. вместе с любыми двумя своими точками целиком содержит.
Определение графа Фигура, образованная конечным набором точек плоскости и отрезков, соединяющих некоторые из этих точек, называется плоским графом, или.
Определение. Две прямые в пространстве называются скрещивающимися, если они не лежат в одной плоскости. СКРЕЩИВАЮЩИЕСЯ ПРЯМЫЕ.
Определение. Две прямые в пространстве называются скрещивающимися, если они не лежат в одной плоскости. СКРЕЩИВАЮЩИЕСЯ ПРЯМЫЕ.
Полувписанная сфера Сфера называется полувписанной в многогранник, если она касается всех его ребер. Центром полувписанной сферы является точка, равноудаленная.
КООРДИНАТЫ ВЕКТОРА Отложим вектор так, чтобы его начало совпало с началом координат. Тогда координаты его конца называются координатами вектора. Обозначим,,
Презентация к уроку по геометрии (9 класс) по теме: Презентация "Координаты вектора"
Теорема 1 Каждая сторона треугольника меньше суммы двух других сторон. Доказательство. Рассмотрим треугольник АВС. Отложим на продолжении стороны АВ отрезок.
Графы Степень вершины Подсчет числа ребер графа. Разминка… Вставьте недостающие слова в предложения (граф, титул, ребро, вершина) Всем известно, что слово.
Определение. Прямая называется параллельной плоскости, если она не имеет с ней ни одной общей точки. ПАРАЛЛЕЛЬНОСТЬ ПРЯМОЙ И ПЛОСКОСТИ.
Равносоставленность Две фигуры называются равносоставленными, если они могут быть разрезаны на одинаковое число попарно равных фигур. Из свойств площади.
ПРАВИЛЬНЫЕ МНОГОГРАННИКИ На рисунке изображены правильные многогранники. Их гранями являются равные правильные многоугольники, и в вершинах каждого многогранника.
Теорема 1 Каждая сторона треугольника меньше суммы двух других сторон. Доказательство. Рассмотрим треугольник АВС. Отложим на продолжении стороны АВ отрезок.
Равносоставленность Две фигуры называются равносоставленными, если они могут быть разрезаны на одинаковое число попарно равных фигур. Из свойств площади.
Сфера и шар Сферой называется фигура, состоящая из всех точек пространства, удаленных от данной точки, называемой центром, на данное расстояние, называемое.
Коллинеарные и компланарные векторы Два вектора называются коллинеарными, если при откладывании их от одной точки они располагаются на одной прямой. Теорема.
Транксрипт:

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

Теорема Эйлера Теорема. Для связного простого графа имеет место равенство В - Р + Г = 2, где В - число вершин, Р - общее число ребер, Г - число областей (граней), на которые граф разбивает плоскость. Например, для графа, изображенного на рисунке, В = 8, Р = 12, Г = 6. Граф называется простым, если его ребра или не имеют общих точек, или имеют только общие вершины.

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

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

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

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

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

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

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

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

Упражнение 7 Пять соседей имеют пять общих колодцев. Можно ли провести непересекающиеся дорожки так, чтобы каждый домик был соединен с четырьмя колодцами и каждый колодец соединен с четырьмя домиками? Решение. Если это сделать можно, то для соответствующего графа В = 10, Р = 20, следовательно, Г= 12. С другой стороны, поскольку каждая область ограничена, по крайней мере четырьмя ребрами, то число ребер должно быть больше или равно 24. Противоречие.

Упражнение 8 Шесть соседей имеют шесть общих колодцев. Можно ли провести непересекающиеся дорожки так, чтобы каждый домик был соединен с четырьмя колодцами и каждый колодец соединен с четырьмя домиками? Ответ. Нет. Решение аналогично предыдущему.

Упражнение 9 Имеется 100 домиков и 100 колодцев. Можно ли провести непересекающиеся дорожки так, чтобы каждый домик был соединен с тремя колодцами и каждый колодец соединен с тремя домиками? Ответ. Да. Разобьем домики и колодцы на 25 групп по 4 домика и 4 колодца в каждой. В этих группах, согласно упражнению 5, можно провести дорожки. Следовательно, дорожки можно провести для всех домиков и колодцев.

Упражнение 10 Имеется 100 домиков и 100 колодцев. Можно ли провести непересекающиеся дорожки так, чтобы каждый домик был соединен с четырьмя колодцами и каждый колодец соединен с четырьмя домиками? Ответ. Нет.