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

Главная / Геометрия / Определение графа
X Код для использования на сайте:

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

X

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

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

Кнопки:

Презентация на тему: Определение графа


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

Презентация на тему: Определение графа


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



№ слайда 1 Определение графаФигура, образованная конечным набором точек плоскости и отрезко
Описание слайда:

Определение графаФигура, образованная конечным набором точек плоскости и отрезков, соединяющих некоторые из этих точек, называется плоским графом, или просто графом. Точки называются вершинами, а отрезки – ребрами графа.Граф называется связным, если любые две его вершины можно соединить ломаной, состоящей из ребер графа.Граф называется простым, если его ребра не пересекаются, т.е. не имеют общих внутренних точек.Вместо отрезков в качестве ребер графов рассматриваются также кривые линии.

№ слайда 2 Задача ЭйлераТеория графов зародилась в ходе решения головоломок двести с лишним
Описание слайда:

Задача ЭйлераТеория графов зародилась в ходе решения головоломок двести с лишним лет назад. Одной из таких задач-головоломок была задача о кенигсбергских мостах, которая привлекла к себе внимание Леонарда Эйлера (1707-1783), долгое время жившего и работавшего в России (с 1727 по 1741 год и с 1766 до конца жизни).Задача. В г. Кёнигсберге (ныне Калининград) было семь мостов через реку Прегель (Л - левый берег, П - правый берег, А и Б - острова). Можно ли, прогуливаясь вдоль реки, пройти по каждому мосту ровно один раз?

№ слайда 3 Уникурсальные графыНа рисунке представлен граф, соответствующий задаче Эйлера, в
Описание слайда:

Уникурсальные графыНа рисунке представлен граф, соответствующий задаче Эйлера, в котором ребра соответствуют мостам, а вершины – берегам и островам. Требуется выяснить, можно ли нарисовать этот граф «одним росчерком», т.е. не отрывая карандаша от бумаги и проходя по каждому ребру ровно один раз. Такие графы называются уникурсальными.

№ слайда 4 ТеоремаИндексом вершины графа называется число ребер, сходящихся в этой вершине
Описание слайда:

ТеоремаИндексом вершины графа называется число ребер, сходящихся в этой вершине (ребра, с началом и концом в данной вершине считаются дважды). Теорема. Для уникурсального графа число вершин нечетного индекса равно нулю или двум. Доказательство. Если граф уникурсален, то у него есть начало и конец обхода. Остальные вершины имеют четный индекс, так как с каждым входом в такую вершину есть и выход. Если начало и конец не совпадают, то они являются единственными вершинами нечетного индекса. У начала выходов на один больше, чем входов, а у конца входов на один больше, чем выходов. Если начало совпадает с концом, то вершин с нечетным индексом нет. Верно и обратное: Если у связного графа число вершин нечетного индекса равно нулю или двум, то он является уникурсальным.

№ слайда 5 Решение задачи ЭйлераРешение задачи Эйлера. Найдем индексы вершин графа задачи Э
Описание слайда:

Решение задачи ЭйлераРешение задачи Эйлера. Найдем индексы вершин графа задачи Эйлера. Вершина А имеет индекс 5, Б - 3, П - 3 и Л - 3. Таким образом, мы имеем четыре вершины нечетного индекса, и, следовательно, данный граф не является уникурсальным. Значит, нельзя пройти по каждому из семи мостов только один раз.

№ слайда 6 Вопрос 1Какая фигура называется графом? Ответ: Графом называется фигура, образов
Описание слайда:

Вопрос 1Какая фигура называется графом? Ответ: Графом называется фигура, образованная конечным набором точек плоскости и отрезков, соединяющих некоторые из этих точек.

№ слайда 7 Вопрос 2Какой граф называется уникурсальным? Ответ: Граф называется уникурсальны
Описание слайда:

Вопрос 2Какой граф называется уникурсальным? Ответ: Граф называется уникурсальным, если его можно ли нарисовать «одним росчерком», т.е. не отрывая карандаша от бумаги и проходя по каждому ребру ровно один раз.

№ слайда 8 Вопрос 3Что называется индексом вершины графа? Ответ: Индексом вершины графа наз
Описание слайда:

Вопрос 3Что называется индексом вершины графа? Ответ: Индексом вершины графа называется число ребер, сходящихся в этой вершине (ребра, с началом и концом в данной вершине считаются дважды).

№ слайда 9 Вопрос 4Что можно сказать об индексах вершин уникурсального графа?Ответ: Для уни
Описание слайда:

Вопрос 4Что можно сказать об индексах вершин уникурсального графа?Ответ: Для уникурсального графа число вершин нечетного индекса равно нулю или двум.

№ слайда 10 Упражнение 1В графе 4 вершин, каждая из которых имеет индекс 3. Сколько у него р
Описание слайда:

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

№ слайда 11 Упражнение 2В графе 5 вершин, каждая из которых имеет индекс 4. Сколько у него р
Описание слайда:

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

№ слайда 12 Упражнение 3Выясните, какие графы, изображенные на рисунке, являются уникурсальн
Описание слайда:

Упражнение 3Выясните, какие графы, изображенные на рисунке, являются уникурсальными?

№ слайда 13 Упражнение 4Может ли граф иметь: а) одну вершину нечетного индекса; б) две верши
Описание слайда:

Упражнение 4Может ли граф иметь: а) одну вершину нечетного индекса; б) две вершины нечетного индекса; в) три вершины нечетного индекса; г) четыре вершины нечетного индекса?

№ слайда 14 Упражнение 5Какое наименьшее число мостов в задаче о кёнигсбергских мостах приде
Описание слайда:

Упражнение 5Какое наименьшее число мостов в задаче о кёнигсбергских мостах придется пройти дважды, чтобы пройти по каждому мосту?

№ слайда 15 Упражнение 6Можно ли обойти все ребра тетраэдра, пройдя по каждому ребру ровно о
Описание слайда:

Упражнение 6Можно ли обойти все ребра тетраэдра, пройдя по каждому ребру ровно один раз?

№ слайда 16 Упражнение 7Какое наименьшее число ребер придется пройти дважды, чтобы обойти вс
Описание слайда:

Упражнение 7Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра тетраэдра?

№ слайда 17 Упражнение 8Какое наименьшее число ребер придется пройти дважды, чтобы обойти вс
Описание слайда:

Упражнение 8Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра тетраэдра и вернуться в исходную вершину?

№ слайда 18 Упражнение 9Можно ли обойти все ребра куба, пройдя по каждому ребру ровно один р
Описание слайда:

Упражнение 9Можно ли обойти все ребра куба, пройдя по каждому ребру ровно один раз?

№ слайда 19 Упражнение 10Какое наименьшее число ребер придется пройти дважды, чтобы обойти в
Описание слайда:

Упражнение 10Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра куба?

№ слайда 20 Упражнение 11Какое наименьшее число ребер придется пройти дважды, чтобы обойти в
Описание слайда:

Упражнение 11Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра куба и вернуться в исходную вершину?

№ слайда 21 Упражнение 12Можно ли обойти все ребра октаэдра, пройдя по каждому ребру ровно о
Описание слайда:

Упражнение 12Можно ли обойти все ребра октаэдра, пройдя по каждому ребру ровно один раз?

№ слайда 22 Упражнение 13Можно ли обойти все ребра икосаэдра, пройдя по каждому ребру ровно
Описание слайда:

Упражнение 13Можно ли обойти все ребра икосаэдра, пройдя по каждому ребру ровно один раз?

№ слайда 23 Упражнение 14Какое наименьшее число ребер придется пройти дважды, чтобы обойти в
Описание слайда:

Упражнение 14Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра икосаэдра?

№ слайда 24 Упражнение 15Какое наименьшее число ребер придется пройти дважды, чтобы обойти в
Описание слайда:

Упражнение 15Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра икосаэдра и вернуться в исходную вершину?

№ слайда 25 Упражнение 16Можно ли обойти все ребра додекаэдра, пройдя по каждому ребру ровно
Описание слайда:

Упражнение 16Можно ли обойти все ребра додекаэдра, пройдя по каждому ребру ровно один раз?

№ слайда 26 Упражнение 17Какое наименьшее число ребер придется пройти дважды, чтобы обойти в
Описание слайда:

Упражнение 17Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра додекаэдра?

№ слайда 27 Упражнение 18Какое наименьшее число ребер придется пройти дважды, чтобы обойти в
Описание слайда:

Упражнение 18Какое наименьшее число ребер придется пройти дважды, чтобы обойти все ребра додекаэдра и вернуться в исходную вершину?

№ слайда 28 Упражнение 19Каким правильным многогранникам соответствуют графы, изображенные н
Описание слайда:

Упражнение 19Каким правильным многогранникам соответствуют графы, изображенные на рисунке? Ответ: а) куб; б) октаэдр; в) додекаэдр; г) икосаэдр.

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


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