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

Главная / Биология / Факультативный курс "Деревья"
X Код для использования на сайте:

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

X

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

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

Кнопки:

Презентация на тему: Факультативный курс "Деревья"


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

Презентация на тему: Факультативный курс "Деревья"


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

№ слайда 1
Описание слайда:

№ слайда 2 Общие понятия теории графов Общие понятия теории графов Занимательные задачи тео
Описание слайда:

Общие понятия теории графов Общие понятия теории графов Занимательные задачи теории графов Деревья и их свойства Остовные деревья История Формулы комбинаторики Деревья в теории вероятностей

№ слайда 3 Определение 1. Графом называется совокупность двух множеств: непустого множества
Описание слайда:

Определение 1. Графом называется совокупность двух множеств: непустого множества точек (вершин) и множества линий, соединяющих эти точки (ребер). Определение 1. Графом называется совокупность двух множеств: непустого множества точек (вершин) и множества линий, соединяющих эти точки (ребер). Иногда каждому ребру графа присваивают некоторое число, которое называется весом данного ребра. Пример. Граф с вершинами A, B, C, D, E, ребрами (A, B), (B, D), (C, E), (E, D). 20 – вес ребра (А, В), 15 – вес ребра (С, Е) и т.д. Задание. На каком рисунке точка пересечения диагоналей не является вершиной графа?

№ слайда 4 Определение 2. Определение 2. Вершина графа, не принадлежащая ни одному ребру на
Описание слайда:

Определение 2. Определение 2. Вершина графа, не принадлежащая ни одному ребру называется изолированной. Пример. Вершина 5 является изолированной. Задание. Вершины графа представляют жителей городка N, а ребра, соединяющие две вершины, - тот факт, что эти люди знакомы. Какую ситуацию изображает приведенный на рисунке граф?

№ слайда 5 Определение 3. Определение 3. Вершина А графа Г, принадлежащая одному ребру, наз
Описание слайда:

Определение 3. Определение 3. Вершина А графа Г, принадлежащая одному ребру, называется висячей. Пример Вершины А и Б - висячие. Задание Укажите висячие вершины. Есть ли здесь изолированные вершины? Задание Начертите граф, содержащий шесть висячих и две изолированные вершины. Задание Начертите граф, содержащий шесть висячих и две изолированные вершины.

№ слайда 6 Определение 4. Определение 4. Степенью вершины А графа Г называется количество р
Описание слайда:

Определение 4. Определение 4. Степенью вершины А графа Г называется количество ребер графа Г, которым данная вершина принадлежит. Обозначение : d(A). Пример М и N – изолированные вершины. d(M)=.d(N)=0; для висячей вершины d(A)=d(C)=1. Задание В следующих графах найдите степени каждой из вершин. Ответ: а) d(1)=d(2)=d(3)=d(4)=d(5)=2; б) d(1)=d(2)=d(4)=1 – висячие вершины, d(5)=0 – изолированная вершина, d(3)=2, d(6)=3

№ слайда 7 Задание Найдите количество ребер Р графа Г и сумму степеней С всех его вершин. З
Описание слайда:

Задание Найдите количество ребер Р графа Г и сумму степеней С всех его вершин. Задание Найдите количество ребер Р графа Г и сумму степеней С всех его вершин. Ответ: Р=4, С=1+2+3+2=8. Ответ: Р=5, С=2+3+2+3=10. Ответ: Р=1, С=1+1+0=2.   Ответ: Р=7, С=4+3+2+2+3=14. Теорема 1. Сумма степеней вершин графа Г равна удвоенному числу ребер, то есть , где r – число ребер.

№ слайда 8 Определение 5. Определение 5. Пусть дан граф Г с вершинами A1, A 2,…An. Путем в
Описание слайда:

Определение 5. Определение 5. Пусть дан граф Г с вершинами A1, A 2,…An. Путем в графе Г называется последовательность ребер A1A2, A2A3,.., An-1An. Вершина A1 -начало пути, вершина An – конец пути. Пример (M, B), (B, D), (D, E), (E, C), (C, N) – путь из вершины М в вершину N. M – начало пути; N – конец пути. Задание Являются ли путями из вершины 1 в вершину 5 следующие последовательности ребер: А) (1,2),(3,4),(4,5) Б) (1,2),(2,3),(3,4) В) (1,2),(2,4),(4,3),(3,2),(2,4),(4,5) Найдите путь от вершины 1 к вершине 5 Ответ: (1,2),(2,3),(3,4),(4,5) или (1,2),(2,4),(4,5).

№ слайда 9 Определение 6. Определение 6. Длиной пути в графе Г называется количество входящ
Описание слайда:

Определение 6. Определение 6. Длиной пути в графе Г называется количество входящих в этот путь ребер. Пример (M, B), (B, D), (D, E), (E, C), (C, N) – путь из вершины М в вершину N.   Задание Укажите все пути, соединяющие вершины 1 и 4 в графе. Сколько существует путей длины два в этом графе? Ответ: (1,4) и (1,2),(2,3),(3,4). Существует восемь путей длины два.

№ слайда 10 Определение 7. Определение 7. Циклом графа Г называется такой путь в этом графе,
Описание слайда:

Определение 7. Определение 7. Циклом графа Г называется такой путь в этом графе, у которого начало совпадает с концом. Пример (M, B), (B, D), (D, E), (E, C), (C, N), (N, M) – цикл в данном графе. (A, B), (B, D), (D, A) – цикл в данном графе.     Задание Является ли циклом последовательность ребер: А) (A,B),(B,E),(E,D),(D,B),(B,A); Б) (D,E),(E,B),(B,D),(D,C); В) (D,C),(C,B),(B,E),(E,D); Г) (B,E),(D,C),(C,B)?

№ слайда 11 Определение 8. Длиной цикла называется количество входящих в него ребер. Определ
Описание слайда:

Определение 8. Длиной цикла называется количество входящих в него ребер. Определение 8. Длиной цикла называется количество входящих в него ребер. Задание Для каждого графа назвать все содержащиеся в них циклы и выбрать наибольший и наименьший по длине цикл. Ответ: а) (1,2),(2,3),(3,4),(4,5),(5,6),(6,7),(7,1) – самый длинный цикл; (1,2),(2,6),(6,7),(7,1); (2,3),(3,4),(4,6),(6,2); (1,2),(2,3),(3,4),(4,6),(6,7),(7,1); (2,3),(3,4),(4,5),(5,6),(6,2); (4,5),(5,6),(6,4) – самый короткий цикл; б) (2,3),(3,5),(5,4),(4,2) – единственный цикл в этом графе; в) (2,3),(3,5),(5,2) и (2,4),(4,5),(5,2) – самые короткие циклы; (2,3),(3,5),(5,4),(4,2) – самый длинный цикл. Можно ли найти путь из вершины 1 в вершину 2 на рисунке б)? А на рисунке в)?

№ слайда 12 Определение 9. Граф называется связным, если между любыми двумя его вершинами су
Описание слайда:

Определение 9. Граф называется связным, если между любыми двумя его вершинами существует путь. В противном случае граф называется несвязным. Определение 9. Граф называется связным, если между любыми двумя его вершинами существует путь. В противном случае граф называется несвязным. Примеры       Чтобы доказать, что граф связный, нужно доказать, что каждые две его вершины являются связными. А чтобы доказать, что граф несвязный – нужно указать в нем две несвязные вершины. Задание Какие из графов являются связными? Почему?

№ слайда 13 Определение 10. Определение 10. Ребро (А, В) называется мостом графа Г, если в г
Описание слайда:

Определение 10. Определение 10. Ребро (А, В) называется мостом графа Г, если в графе, полученном после удаления из Г ребра (А, В), вершины А и В оказываются несвязными. Пример Задание Выделите в графе, изображенном на рисунке, ребра, которые являются мостами. Ответ:

№ слайда 14 Теорема 2. Ребро (А, В) является мостом Теорема 2. Ребро (А, В) является мостом
Описание слайда:

Теорема 2. Ребро (А, В) является мостом Теорема 2. Ребро (А, В) является мостом в том и только том случае, если (А, В) – единственный путь, соединяющий вершины А и В.     Теорема 3. Ребро (А, В) является мостом в том и только том случае, если найдутся две вершины С, D такие, что каждый путь, соединяющий их, содержит вершины А и В.   Теорема 4. Ребро (А, В) является мостом в том и только том случае, если оно не принадлежит ни одному циклу.

№ слайда 15 Задача 1. Задача 1. Герой произведения Н.В.Гоголя «Мертвые души» Плюшкин из экон
Описание слайда:

Задача 1. Задача 1. Герой произведения Н.В.Гоголя «Мертвые души» Плюшкин из экономии разрезает каждый лист бумаги на три части. Некоторые из полученных листов он также режет на три части и т.д. Сколько листков бумаги он получит, если разрежет k листов? K=1 K=2 K=3 Ответ При разрезании k листов,образуется1+2·k листиков.

№ слайда 16 Задача 2. Задача 2. В соревнованиях по шашкам участвует 6 человек: Кирилл, Денис
Описание слайда:

Задача 2. Задача 2. В соревнованиях по шашкам участвует 6 человек: Кирилл, Денис, Ольга, Сергей, Полина и Андрей. Соревнование проводится по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту : Кирилл сыграл с Денисом, Сергеем и Андреем; Денис, с Кириллом и еще с Сергеем; Ольга – с Сергеем, Полиной, Андреем; Сергей – с Кириллом, Денисом и Ольгой; Полина – с Ольгой, а Андрей – с Кириллом и Ольгой. Сколько игр проведено к настоящему моменту и сколько еще осталось? Ответ. 8

№ слайда 17 Задача 3 Задача 3 Чичиков, погостив у Манилова, посетил по одному разу Коробочку
Описание слайда:

Задача 3 Задача 3 Чичиков, погостив у Манилова, посетил по одному разу Коробочку, Ноздрева, Собакевича, Плюшкина, Тентетникова, Бетрищева, Петуха, Констанжогло и Кошкарева в указанном порядке. Имеется схема расположения имений и соединяющих их дорог. Установить, какое имение кому принадлежит, если ни по одной дороге Чичиков не проезжал более одного раза. Начал свое путешествие Чичиков из дома Манилова, обозначенного на схеме буквой А. Ответ А, В, С, D, Е, М, N, Р, К, О.

№ слайда 18 Задача4. Задача4. В решили поставить спектакль «Ревизор». Разгорелся спор. - Ляп
Описание слайда:

Задача4. Задача4. В решили поставить спектакль «Ревизор». Разгорелся спор. - Ляпкиным-Тяпкиным (1) буду я! – решительно заявил Гена. - Нет, я буду Ляпкиным-Тяпкиным, - возразил Дима. - Ну, хорошо, согласен уступить эту роль, если мне дадут сыграть Хлестакова (2), - проявил великодушие Гена. - …А мне Осипа (3), - не уступил ему в великодушии Дима. - Хочу быть Земляникой (4) или Городничим (5), сказал Вова. - Нет, Городничим буду я, - хором закричали Алик и Боря. – Или Хлестаковым, - добавили они одновременно. Удастся ли распределить роли, чтобы все исполнители были довольны? Ответ

№ слайда 19 Задача5 Задача5 Жители пяти домов поссорились друг с другом, и, чтобы не встреча
Описание слайда:

Задача5 Задача5 Жители пяти домов поссорились друг с другом, и, чтобы не встречаться около колодцев, решили поделить колодцы так, чтобы хозяин каждого дома ходил к «своему» колодцу по «своей» тропинке. Удастся ли им это сделать? Задача 6 В 5 корзинах лежат яблоки 5 разных сортов. Яблоки первого сорта лежат в корзинах Г и Д; яблоки второго сорта – в корзинах А, Б и Г; в корзинах А, Б и В имеются яблоки пятого сорта; в корзине В имеются к тому же яблоки четвертого сорта, а в корзине Д – третьего. Требуется дать каждой корзине номер, но так, чтобы в корзине №1 были яблоки первого сорта, в корзине №2 – второго и т.д.  

№ слайда 20 Задача 7. Задача 7. Являются ли графы на рисунках связными? Можно ли из этих гра
Описание слайда:

Задача 7. Задача 7. Являются ли графы на рисунках связными? Можно ли из этих графов получить связные графы, добавив1 ребро, 2 ребра? Ответ: нет. а) нет, да; б) да, да; в) нет, нет. «Кусочки» несвязного графа называют компонентами данного несвязного графа. Чтобы из несвязного графа, содержащего n компонент, получить связный, надо добавить не менее чем (n-1) ребро.

№ слайда 21 Задача 8. Задача 8. «Дорисуйте» граф так, чтобы он стал связным. Задача 9. Из гр
Описание слайда:

Задача 8. Задача 8. «Дорисуйте» граф так, чтобы он стал связным. Задача 9. Из графа Г сделайте несвязный граф, удалив а) 2 ребра, б) 1 ребро. Ответ а) например, б) в первом случае невозможно, а во втором - при удалении ребра из связного графа новый граф может оказаться как связным, так и несвязным.

№ слайда 22 Задание 1. Задание 1. Нарисуйте А) граф с семью вершинами и шестью ребрами, не и
Описание слайда:

Задание 1. Задание 1. Нарисуйте А) граф с семью вершинами и шестью ребрами, не имеющий циклов, Б) связный граф с семью вершинами и шестью ребрами, В) граф с семью вершинами, в котором для любых двух вершин существует один и только один связывающий их путь, Г) связный граф с семью вершинами, каждое ребро которого – мост. Возможные решения:

№ слайда 23 Определение 1. Деревом называется всякий связный граф, не имеющий циклов. Опреде
Описание слайда:

Определение 1. Деревом называется всякий связный граф, не имеющий циклов. Определение 1. Деревом называется всякий связный граф, не имеющий циклов. Граф, состоящий из одной изолированной вершины - дерево. Задание 2. Выберите из приведенных ниже графов те, которые являются деревьями. В выбранных деревьях отметьте висячие вершины.

№ слайда 24 Задание 3. Задание 3. Докажите, что для каждой пары вершин дерева существует еди
Описание слайда:

Задание 3. Задание 3. Докажите, что для каждой пары вершин дерева существует единственный соединяющий их путь. Замечание. Следует : 1) доказать, что для каждой пары вершин дерева существует соединяющий их путь; 2) доказать, что путь, соединяющий любые две вершины дерева, - единственный. Доказательство. 1) Дерево – связный граф. Из определения связности следует существование пути. 2) Предположим, что существует пара вершин данного дерева, у которых есть два соединяющих их пути. Тогда этот граф содержит цикл, то есть не является деревом. Получили противоречие, следовательно, наше предположение было неверным, и путь, соединяющий любые две вершины дерева, - единственный.

№ слайда 25 Задание 4. Задание 4. Какое максимальное число висячих вершин может иметь дерево
Описание слайда:

Задание 4. Задание 4. Какое максимальное число висячих вершин может иметь дерево, построенное на 9 вершинах? Какое минимальное число висячих вершин оно может иметь? Сделайте рисунки таких деревьев. Ответ: 8 вершин и 2 вершины соответственно.

№ слайда 26 Определение 2. Лесом называется несвязный граф, представляющий собой объединение
Описание слайда:

Определение 2. Лесом называется несвязный граф, представляющий собой объединение деревьев. Определение 2. Лесом называется несвязный граф, представляющий собой объединение деревьев. Удобно считать, что граф, состоящий из одного дерева – лес. Задание 5. Выберите из данных графов те, которые являются лесом. Ответ: 1) да, 2) да, 3) нет, 4) да.

№ слайда 27 Теорема 1. Дерево – это минимальный связный граф. Теорема 1. Дерево – это минима
Описание слайда:

Теорема 1. Дерево – это минимальный связный граф. Теорема 1. Дерево – это минимальный связный граф. Задание 6. Постройте какие-нибудь деревья с 3, 4, 5, 6 вершинами и посчитайте число ребер в полученных графах. Возможные варианты ответов: В любом дереве с 3 вершинами 2 ребра, с 4 вершинами – 3, с 5 вершинами – 4, с 6 вершинами – 5, то есть во всех случаях количество ребер на единицу меньше количества вершин дерева.

№ слайда 28 Теорема 2. Число ребер дерева на n вершинах равно n-1. Теорема 2. Число ребер де
Описание слайда:

Теорема 2. Число ребер дерева на n вершинах равно n-1. Теорема 2. Число ребер дерева на n вершинах равно n-1. Следствие. Связный граф на n вершинах имеет не менее чем n-1 ребро. Задание 7. Докажите, что дерево, имеющее не менее двух вершин, содержит, по крайней мере, две висячие вершины. Доказательство. Пусть дано дерево D, имеющее n (n≥2) вершин и r ребер. Дерево – связный граф, следовательно, для любой его вершины . Предположим, что для n-1 вершины их степени строго больше 1, а лишь у одной вершины степень больше или равна 1. Тогда По теореме 1 сумма степеней всех вершин графа равна 2r, то есть d(A1) + d(A2) +…+ d(An) =2r. Но из теоремы 2 следует, что r=n-1. Значит, =2n-2. Таким образом, 2n-2>2n-1. Получили противоречие. Значит, по крайней мере две вершины должны иметь степень, равную 1 (по определению они и есть висячие).

№ слайда 29 Теорема 3. Последовательность целых чисел d1, d2 , …, dn является последовательн
Описание слайда:

Теорема 3. Последовательность целых чисел d1, d2 , …, dn является последовательностью степеней вершин некоторого дерева на n вершинах (n≥2) тогда и только тогда, когда: Теорема 3. Последовательность целых чисел d1, d2 , …, dn является последовательностью степеней вершин некоторого дерева на n вершинах (n≥2) тогда и только тогда, когда: 1) каждое di ≥ 1, I =1, 2, …, n и 2) =2n-2 Задание 8. Дана последовательность чисел А) 1, 1, 2, 3, 5, 5, 6; Б) 4, 5, 6, 7; В) 1, 1, 1, 3; Г) 1, 1, 1, 1, 1, 2, 3, 4. Можно ли построить дерево, такое что данная последовательность чисел являлась бы последовательностью степеней вершин этого дерева? Ответ: А) нет, т.к. ≠2n-2, Б) нет, т.к. нет ни одной висячей вершины, В) да, т.к. выполняются условия теоремы, Г) да, т.к. выполняются условия теоремы.  

№ слайда 30 Задача 1. Задача 1. Лена дружит с Викой, Олей и Сережей, Сережа, кроме того, – с
Описание слайда:

Задача 1. Задача 1. Лена дружит с Викой, Олей и Сережей, Сережа, кроме того, – с Машей и Петей, а Глеб – с Димой и Машей. Изобразите с помощью графа отношение «дружить». В полученном графе выделите те вершины и ребра, которые изображают отношение «Маша дружит с …» Вопрос : - Является ли выделенный набор вершин и ребер графом? Почему? Ответ: да, состоит из множества точек и множества соединяющих их линий.

№ слайда 31 Определение 1. Подграфом данного графа Г называется такой граф Г , что множество
Описание слайда:

Определение 1. Подграфом данного графа Г называется такой граф Г , что множество его вершин лежит во множестве вершин, а множество его ребер – во множестве ребер исходного графа Г. Определение 1. Подграфом данного графа Г называется такой граф Г , что множество его вершин лежит во множестве вершин, а множество его ребер – во множестве ребер исходного графа Г. Пример 1.   Задание 1. В приведенных ниже графах назовите несколько подграфов.

№ слайда 32 Определение 2. Остовным подграфом графа Г называется такой его подграф, который
Описание слайда:

Определение 2. Остовным подграфом графа Г называется такой его подграф, который содержит все вершины графа Г. Определение 2. Остовным подграфом графа Г называется такой его подграф, который содержит все вершины графа Г. Пример 2.     Задание 2. В графах назовите несколько остовных подграфов.

№ слайда 33 Определение 3. Остовной подграф, являющийся деревом, называется остовным деревом
Описание слайда:

Определение 3. Остовной подграф, являющийся деревом, называется остовным деревом. Определение 3. Остовной подграф, являющийся деревом, называется остовным деревом. Пример 3.     Задание 3. А) Приведите пример графа, из которого нельзя выделить остов. Б) Приведите пример графа и нескольких его остовных деревьев Возможные ответы:

№ слайда 34 Определение 4. Минимальным остовным деревом называется остовное дерево с минимал
Описание слайда:

Определение 4. Минимальным остовным деревом называется остовное дерево с минимальным общим весом его ребер Определение 4. Минимальным остовным деревом называется остовное дерево с минимальным общим весом его ребер Задание 4. В приведенном графе выделите минимальное остовное дерево. Задание 5. Из графа Г удалите часть ребер так, чтобы новый граф Г был остовным деревом.

№ слайда 35 Задание 6. Задание 6. Сколько ребер надо удалить из связного графа, имеющего r р
Описание слайда:

Задание 6. Задание 6. Сколько ребер надо удалить из связного графа, имеющего r ребер и n вершин (r≥n), чтобы получить остов? Решение. Остов будет являться деревом на n вершинах. По теореме 2 дерево с n вершинами имеет n-1 ребро. Чтобы из данных r ребер графа получить n-1 ребро, нужно удалить r-(n-1) или r-n+1 ребро. Ответ: r-n+1.

№ слайда 36 Задачи А. Кэли. Задачи А. Кэли. Необходимо соединить n городов железнодорожными
Описание слайда:

Задачи А. Кэли. Задачи А. Кэли. Необходимо соединить n городов железнодорожными линиями так, чтобы не строить лишних дорог. Известна стоимость строительства для каждой пары городов. Какова должна быть сеть дорог, соединяющая все города и имеющая минимальную возможную стоимость? В терминах теории графов. Рассмотрим граф Г, в котором вершины – города, ребра – соединяющие пару городов дороги. Каждому ребру назначим вес – стоимость строительства дороги на этом участке. Нужно построить связный граф, содержащий все вершины, с минимальным весом. Очевидно, что этот граф должен быть деревом – в противном случае, можно было бы удалить одно ребро, не нарушая связности и уменьшая сумму весов его ребер.

№ слайда 37 Выбрать произвольно вершину Х и отметить ее. Выбрать произвольно вершину Х и отм
Описание слайда:

Выбрать произвольно вершину Х и отметить ее. Выбрать произвольно вершину Х и отметить ее. Среди ребер, выходящих из отмеченной вершины Х, выбрать ребро (Х, Y) c наименьшим весом и включить его в дерево Го. Повторяя процесс, выполнить поиск наименьшего по весу ребра, соединяющего вершины Х или Y с некоторой другой (непомеченной) вершиной графа Z. Процесс включения ребер продолжить до тех пор, пока все вершины исходного графа Г не будут включены в дерево Го. Построенное дерево будет минимальным остовным.

№ слайда 38 Задача 2. Задача 2. Было решено соединить пять городов (Серпухов, Коломну, Кашир
Описание слайда:

Задача 2. Задача 2. Было решено соединить пять городов (Серпухов, Коломну, Каширу, Москву и Подольск) железнодорожными линиями так, чтобы не строить лишних дорог. Какова должна быть сеть дорог, соединяющая все города и имеющая минимальную возможную стоимость, если известно, что стоимость строительства дороги от Серпухова до Коломны - 200, до Каширы –100, до Москвы– 75, до Подольска – 80; от Коломны до Каширы – 150, до Москвы – 120, до Подольска – 140; от Каширы до Москвы -90, до Подольска – 105; от Москвы до Подольска – 60? Решение. Затраты на строительство дорог 75+60+90+120=345

№ слайда 39 Задача 3. Задача 3. Задано множество аэродромов, нужно определить минимальный (п
Описание слайда:

Задача 3. Задача 3. Задано множество аэродромов, нужно определить минимальный (по сумме расстояний) набор авиарейсов, позволяющий перелететь с любого аэродрома на любой другой. Известно, что расстояние между аэродромом А и аэродромом Б равно 500 км, между А и В – 400 км, А и Г – 450 км, А и Д – 670 км, А и Е – 800 км; между аэродромом Б и В – 340 км, Б и Г – 460 км, Б и Д – 550 км, Б и Е – 900 км; между В и Г – 280 км, В и Д – 1100 км, В и Е – 870 км, между Г и Д – 630 км, Г и Е – 1200 км, между Д и Е – 1500 км. Ответ:  

№ слайда 40 Задача 4. Задача 4. Постройте минимальное остовное дерево следующего графа:
Описание слайда:

Задача 4. Задача 4. Постройте минимальное остовное дерево следующего графа:

№ слайда 41 Задача о кенигсбергских мостах. Задача о кенигсбергских мостах. В Кенигсберге 1
Описание слайда:

Задача о кенигсбергских мостах. Задача о кенигсбергских мостах. В Кенигсберге 1 есть остров, называемый Кнейпгоф. Река, омывающая его, делится на два рукава через кото­рые перекинуто семь мостов: а. в, с, d, е, f, g. Можно ли обойти все эти мосты, не побывав ни на одном из них более раза?

№ слайда 42 Решение. Решение. Обобщим задачу: начиная с любой вершины, проходя по каждому ре
Описание слайда:

Решение. Решение. Обобщим задачу: начиная с любой вершины, проходя по каждому ребру только один раз, вернуться в исходную вершину. Построим мультиграф, в котором участки суши изобразим как вершины, а дорожки через мосты — как ребра. Найдем критерий существования обхода (специального маршрута) у данного графа: граф должен быть связным и каждая его вершина должна быть связана с четным количеством ребер. Полученный граф связный, но не каждая его вершина связана с четным количеством ребер.

№ слайда 43 - математическая задача, предложенная Ф.Гутри (англ.) в 1852 г. - математическая
Описание слайда:

- математическая задача, предложенная Ф.Гутри (англ.) в 1852 г. - математическая задача, предложенная Ф.Гутри (англ.) в 1852 г. Выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета.

№ слайда 44 основная часть задачи - правильный додекаэдр, сделанный из дерева. Каждая вершин
Описание слайда:

основная часть задачи - правильный додекаэдр, сделанный из дерева. Каждая вершина гамильтонова додекаэдра была помечена названием одного из крупных городов - Брюссель, Дели, Франкфурт и т. д. основная часть задачи - правильный додекаэдр, сделанный из дерева. Каждая вершина гамильтонова додекаэдра была помечена названием одного из крупных городов - Брюссель, Дели, Франкфурт и т. д. Задача : нахождение пути вдоль ребер додекаэдра, проходящего через каждый город в точности по одному разу.

№ слайда 45 Однако такой додекаэдр был слишком громоздким, и Гамильтон предложил другой вари
Описание слайда:

Однако такой додекаэдр был слишком громоздким, и Гамильтон предложил другой вариант своей игры, где многогранник заменялся плоским графом, изоморфным графу, образованному ребрами додекаэдра. Однако такой додекаэдр был слишком громоздким, и Гамильтон предложил другой вариант своей игры, где многогранник заменялся плоским графом, изоморфным графу, образованному ребрами додекаэдра.

№ слайда 46 Год рождения -1707 . Год рождения -1707 . Место рождения - Базель, Швейцария Год
Описание слайда:

Год рождения -1707 . Год рождения -1707 . Место рождения - Базель, Швейцария Год смерти - 1783. Место смерти -Санкт-Петербург, Российская империя. Гражданство - Швейцария . Сфера интересов - математика, механика, физика, астрономия .

№ слайда 47 Биография . Биография . Леонард Эйлер – великий математик, внесший значительный
Описание слайда:

Биография . Биография . Леонард Эйлер – великий математик, внесший значительный вклад в развитие математики, а также механики, физики, астрономии и ряда прикладных наук. Леонард Эйлер родился в 1707 году в семье базельского пастора, друга семьи Бернулли. Рано обнаружил математические способности. Начальное обучение получил дома под руководством отца, учившегося некогда математике у Якоба Бернулли. 20 октября 1720 года 13-летний Леонард Эйлер стал студентом факультета искусств Базельского университета. 8 июня 1724 года 17-летний Леонард Эйлер произнёс на латыни речь о сравнении философских воззрений Декарта и Ньютона и был удостоен учёной степени магистра. В начале зимы 1726 года Эйлеру сообщили из Санкт-Петербурга: по рекомендации братьев Бернулли он приглашен на должность адъюнкта по физиологии с окладом 200 рублей. Получение аванса для компенсации проездных расходов растянулось почти на год, и лишь 5 апреля 1727 года Эйлер навсегда покинул родную Швейцарию.

№ слайда 48 Публикации Публикации Автор более чем 800 работ по математическому анализу, дифф
Описание слайда:

Публикации Публикации Автор более чем 800 работ по математическому анализу, дифференциальной геометрии, теории чисел, приближенным вычислениям, небесной механике, математической физике, оптике, баллистике, кораблестроению, теории музыки и др. Многие его работы оказали значительное влияние на развитие науки. Вклад в науку Теория графов:задача о Кенигсбергских мостах. Интересные факты • Первые русские академики-математики (С. К. Котельников) и астрономы (С. Я. Румовский) были учениками Эйлера. • Маркиз Кондорсе сообщает, что вскоре после переезда в Берлин Эйлера пригласили на придворный бал. На вопрос королевы-матери, отчего он так немногословен, Эйлер ответил: «Прошу меня простить, но я только что из страны, где за лишнее слово могут повесить».

№ слайда 49
Описание слайда:

№ слайда 50 Задача Задача В урне 2 белых и 4 черных шара. Один азартный человек держит пари
Описание слайда:

Задача Задача В урне 2 белых и 4 черных шара. Один азартный человек держит пари с другим, что среди вынутых 3-ех шаров будет ров­но 1 белый. В каком отношении находятся шансы спорящих? Решение (традиционное). Испытание - вынимание трех шаров. Событие «А»- достать ровно один белый и два черных шара. Число всех исходов Один белый шар можно достать в С21 случаях , а два черных - С42 , тогда по основному правилу комбинаторики Отсюда Р(А)= следовательно Р( ) = 1 - Р( А) = 1 - Ответ: отношение шансов спорящих равно 3:2.

№ слайда 51 Решение (наглядное) Решение (наглядное) «А»- появление одного белого и двух черн
Описание слайда:

Решение (наглядное) Решение (наглядное) «А»- появление одного белого и двух черных шаров. Р (А)= . Р( ) = 1 - Р( А) = 1- . Ответ: 3:2.

№ слайда 52 Задача Задача Слово «МАТЕМАТИКА» разделено на отдельные буквы, из них произвольн
Описание слайда:

Задача Задача Слово «МАТЕМАТИКА» разделено на отдельные буквы, из них произвольным образом отбираются и выкладываются по порядку четыре буквы. Какова вероятность получения слова «МАМА»? Решение. Составим вероятностное дерево исходов. Корневая вершина-начало испытания. Вес ребра - вероятность появления следующей буквы «А»- вероятность получения слова «МАМА».

№ слайда 53
Описание слайда:

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

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