Ваганова Елена Вячеславовна, 102-491-543 «Содержание и методика организации факультативного курса - umotnas.ru o_O
Главная
Поиск по ключевым словам:
Похожие работы
Название работы Кол-во страниц Размер
Программа курса «Методология и методика научного исследования» 1 44.3kb.
Н. Г. Чернышевского На правах рукописи власова елена Вячеславовна... 7 2554.72kb.
Из истории развития студенческого самоуправления в России Бабаева... 1 69.84kb.
Методика обучения темам курса информатики, имеющим интеграцию с математикой 1 104.83kb.
Программа элективного курса «Микрокосмос» 1 236.77kb.
Программа факультативного курса для 10 11 классов 1 271.27kb.
Киселёвского городского округа 1 58.57kb.
Методика обучения темам курса информатики, связанным с информационными... 1 60.64kb.
Программа курса «Методика преподавания математики» делит его на две... 15 5255.78kb.
Учебно-методический комплекс по дисциплине «Теория организации» для... 2 480.42kb.
Семинар «Методика организации проектной исследовательской деятельности» 1 254.97kb.
Матрицы и алгебраические действия над ними с точки зрения информатики 2 335.82kb.
Викторина для любознательных: «Занимательная биология» 1 9.92kb.

Ваганова Елена Вячеславовна, 102-491-543 «Содержание и методика организации факультативного - страница №1/3

Ваганова Елена Вячеславовна, 102-491-543
« Содержание и методика организации факультативного курса «Деревья»
Оглавление.


Введение…………………………………………………………………………………

3


Глава I. Содержание факультативного курса «Деревья»




§1. Основные понятия и определения теории графов…………………..…………….

6

§2. Деревья……………………………………………………………………………….

14

§3. Остовные деревья……………………………………………………………….…..

18

§4. Задача об отыскании кратчайшего пути…………………………………………...

22

§5. «Сколько корней у дерева?»…………………………...…………………………...

26

§6. Деревья и комбинаторика……………………...……………………………………

29

§7. Деревья в теории вероятностей……………………...……………………………..

34


Глава II. Методика организации факультативного курса «Деревья»




§1. Анализ школьных учебников с точки зрения исследуемой проблемы………….

38

§2. Методические рекомендации по проведению факультативного курса…………

49

§3. Опытно-экспериментальная проверка разработанного факультативного курса….

56


Заключение………...……………………………………………………………………

60


Литература………………………………………………………...................................

61


Приложение 1 История возникновения теории графов……......………………….

65

Приложение 2 Дополнительные задания к факультативному курсу…..…………

69

Приложение 3 Проверочные работы……….……………………………..………..

78

Приложение 4 Инструкция по применению электронных материалов «Факультативный курс “Деревья”»……………………………………………..……...

81




Введение.

Наиболее динамичной областью знаний является дискретная математика. К ней относится: комбинаторика, теорияигр, математическая логика, теория алгебраических систем, теория графов и сетей и т.д.

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

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

Среди графов существует один простой и важный тип, это – деревья. Для них выполняются многие свойства, которые не всегда выполняются для графов в общем случае. Применительно к деревьям многие доказательства и рассуждения оказываются намного проще. Математики не уделяли должного внимания исследованию деревьев вплоть до конца XIX века, но древовидные графы использовались еще в глубокой древности (например, родственные отношения принято было изображать с помощью генеалогического древа) или классификацию, связанную с разбиением того или иного множества на классы, подклассы и так далее. Одно из наиболее часто употребляемых в средневековой метафизике деревьев – бинарное - ввел в своем комментарии к Аристотелю живший в III веке римский философ и противник христианства Порфирий.

В 1875 году английский математик А. Кэли примененил теории графов в органической химии. Он использовал понятие «висячая вершина» дерева для подсчета числа изомеров предельных (не имеющих цикла) углеводородов.

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

Деревья являются самым распространенным классом графов, применяемых в программировании, причем в самых разных ситуациях.

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

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

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

Таким образом, изучение деревьев в школе позволяет:

- шире познакомить учащихся с такими разделами математики, как комбинаторика и теория вероятностей;

- показать практическую значимость математики в реальных ситуациях;

- ускорить решение многих задач и упростить расчеты;

- отрабатывать умения действовать по алгоритму;

- решать различные головоломки, задачи олимпиадной направленности;

- познакомить учащихся с богатым историческим материалом.

Все вышесказанное определило актуальность данного исследования.

Объектом исследования является процесс организации учебной деятельности учащихся старших классов на факультативных занятиях.

Предметом исследования является методика проведения факультативных занятий по теме «Деревья».

Целью исследования является разработка содержания и методики организации факультативного курса «Деревья».

Гипотеза исследования - разработанный факультативный курс будет способствовать раскрытию индивидуальных возможностей учащихся, повышению уровня математической культуры.

Реализация поставленной цели потребовала решения ряда конкретных задач, а именно:



  1. Разработать содержание и методику проведения факультативного курса «Деревья».

  2. Провести анализ школьных учебников

  3. Провести опытно-экспериментальную проверку эффективности предложенной методики.

Решение поставленных задач потребовало привлечения следующих методов исследования:

- анализ работ по истории математики, школьных программ, учебников и учебных пособий;

- беседы с учащимися;

- проведение диагностирующих контрольных работ для проверки качества усвоения и доступности материала;

- проведение опытной проверки основных положений исследования.

Практическая значимость исследования определяется тем, что в нем разработаны и проверены:


  1. Учебный материал для преподавания курса «Деревья» для старшеклассников.

  2. Специальный набор упражнений и задач по указанной теме.

  3. Методические рекомендации для учителя по проведению факультатива.

Кроме того, отдельные материалы факультативного курса могут быть использованы преподавателями математики, а также информатики не только на внеклассных и факультативных занятиях, но и на уроках основного курса.

Глава I. Содержание и методика организации

факультативного курса «Деревья».
§1. Основные понятия и определения теории графов.

Разберем задачи, подводящие, учащихся к понятию графа,



Задача 1.1.

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



Решение

Сделаем рисунок к условию задачи. При этом листы бумаги будем обозначать кружками: кружки, соответствующие разрезанным листам, закрасим; остальные оставим не закрашенными.




K=1

K=2

K=3

Рисунок 1

Рисунок помогает увидеть, что при разрезании появляются три новых листика вместо одного. Таким образом,получилось 1+2·1=3 листка;

если разрезали два листа, то получилось 1+2·2=5 листков; если три, то - 1+2·3=7 и т.д. Если же было разрезано k листов, то образовалось 1+2·k листиков.

При решении задачи, мы получили схемы, похожие на ветку дерева с листьями..

Рисунки этой задачи оставить на доске.

Задача 1.2.

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



Решение.

Представим данные задачи на чертеже. Обозначим участников соревнования точками так, что Кириллу будет соответствовать точка К, Денису – точка Д и т.д. Если двое участников уже сыграли между собой, то соединим изображающие их точки отрезками.

Получили некоторую схему, из которой видно, что число игр, проведенных к настоящему моменту, равно Рисунок 2. количеству изображенных на ней отрезков, то есть семь.

Чтобы найти число игр, которые осталось провести, соединим пунктирной линией еще не игравших друг с другом участников.

Таких «пунктирных» отрезков получилось восемь, то есть нужно провести еще восемь игр. Кирилл должен сыграть с Ольгой и Полиной, Денис – с Ольгой, Полиной и Андреем и т.д.

Рисунок 3. Рисунок также остается на доске.

Есть ли что-нибудь общее у полученных схем? Да. Они все состоят из точек (кружков) и линий (прямых или кривых), соединяющих пары точек. Эти схемы являются представителями так называемых графов.

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

Обозначать граф будем буквой Г. Вершины графа будем обозначать прописными буквами русского (латинского) алфавита или числами (например, А, Б, В,…,A, B, C, D,…,1, 2,…); ребра – парами вершин, принадлежащих данным ребрам или строчными буквами русского (латинского) алфавита (например, (А,Б), (N,F), (3,4), а, б, в, k, l, m). Иногда будем изображать граф, не обозначая его ребра и вершины.

В некоторых случаях каждому ребру графа присваивают некоторое число. Это число называется весом данного ребра.

Пример 1.1 Граф с вершинами A, B, C, D, E,

ребрами (A, B), (B, D), (C, E), (E, D).

20 – вес ребра (А, В),

15 – вес ребра (С, Е) и т.д.

Рисунок 4.

Вершины графа обычно изображают «жирными» точками, кружками или квадратиками, так как ребра графа иногда пересекаются на чертеже, но точка пересечения при этом не является вершиной.



Пример 1.2.


В данном графе точка пересечения диагоналей четырехугольника не является вершиной графа.




А в этом графе точка пересечения диагоналей четырехугольника является Рисунок 5. вершиной графа.

Не всегда все вершины графа соединены друг с другом. Иногда вершина не соединена ни с одной из вершин графа.

Определение 1.2. Вершина графа, не принадлежащая ни одному ребру, называется изолированной.

Пример 1.3.

Вершина 5 является

изолированной.

Задание 1.1. (Устно) Рисунок 6.

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



Решение.

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



Определение 1.3. Вершина А графа Г, принадлежащая одному ребру, называется висячей.

Пример 1.4. Вершины А и Б - висячие.

Рисунок 8.


Задание 1.2.

Укажите висячие вершины. Объясните ответ.

Есть ли здесь изолированные вершины? Объясните

ответ. Рисунок 9.

Ответ: 1, 4, 5 – висячие вершины по определению. Изолированных вершин нет по определению.

Задание 1.3. Начертите граф, содержащий 4 висячих и две изолированные вершины.

Задание 1.4. Начертите граф, содержащий шесть висячих и две изолированные вершины.

Определение 1.4. Степенью вершины А графа Г называется количество ребер графа Г, которым данная вершина принадлежит.

Обозначают степень вершины А: d(A).

В случае изолированной вершины d(A)=0; для висячей вершины d(A)=1.

Пример 1.5.

М и N – изолированные вершины.


Рисунок 10.



Задание 1.5. В следующих графах найдите степени каждой из вершин.

Рисунок 11.

Ответ: а) 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.

Установим связь между степенями вершин графа и числом его ребер.

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

А) Ответ: Р=4, С=1+2+3+2=8.

Рисунок 12.


Б) Ответ: Р=5, С=2+3+2+3=10.

Рисунок 13.

В) Ответ: Р=1, С=1+1+0=2.


Рисунок 14.


Г) Ответ: Р=7, С=4+3+2+2+3=14.


Рисунок 15.

Заметим, что в каждом случае сумма всех степеней вершин графа в два раза больше, чем число его ребер.



Теорема 1.1. Сумма степеней вершин графа Г равна удвоенному числу ребер, то есть , где r – число ребер.

Определение 1.5. Пусть дан граф Г с вершинами , , …, . Путем в графе Г называется последовательность ребер , , …, . Причем вершина называется началом пути, а вершина – концом пути.

Из определения следует, что каждые два соседних ребра пути имеют общую вершину и никакое ребро не встречается более одного раза.


Пример 1.6.

(M, B), (B, D), (D, E), (E, C), (C, N) – путь в данном графе из вершины М в вершину N.

M – начало пути; N – конец пути.
Рисунок 16.

Задание 1.7. (Устно.)

Являются ли путями из вершины 1 в вершину 5 следующие последовательности ребер:

А) (1,2),(3,4),(4,5) – нет, т.к. ребра (1,2) и (3,4) – соседние, но не имеют общей вершины;

Рисунок 17.

Б) (1,2),(2,3),(3,4) – нет, т.к. эта последовательность не ведет в вершину 5;

В) (1,2),(2,4),(4,3),(3,2),(2,4),(4,5) – нет, т.к. ребро (2,4) повторяется.

Найдите путь от вершины 1 к вершине 5 в графе, изображенном на рисунке.

Ответ: (1,2),(2,3),(3,4),(4,5) или (1,2),(2,4),(4,5).

Сравним два полученных в задаче пути. Очевидно, второй из них короче. Значит можно говорить о длине пути в графе.

Определение 1.6. Длиной пути в графе Г называется количество входящих в этот путь ребер.

Пример 1.7.

(M, B), (B, D), (D, E), (E, C), (C, N) – путь в данном графе из вершины М в вершину N.

Длина пути равна пяти.
Рисунок 18.

Задание 1.8. (Устно.)


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

Рисунок 19.

Ответ: (1,4) и (1,2),(2,3),(3,4). Существует восемь путей длины два.



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

Пример 1.8.

(M, B), (B, D), (D, E), (E, C), (C, N), (N, M) – цикл в данном графе.

(A, B), (B, D), (D, A) – цикл в данном графе.

Рисунок 20.



Задание 1.9.

Является ли циклом следующая последовательность ребер:

А) (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);

Рисунок 21. Г) (B,E),(D,C),(C,B)?

Ответ:

А) нет, т.к. ребро (А,В) повторяется дважды, а значит последовательность – не путь.



Б) нет, т.к. начальная и конечная вершины не совпадают.

В) да, т.к. все условия определения цикла выполнены.

Г) нет, т.к. соседние ребра (B,E) и (D,C) не имеют общей вершины

(пропущено ребро (E,D)), а значит последовательность – не путь.



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

Задание 1.10.

Для каждого из изображенных на рисунке графов назвать все содержащиеся в них циклы и выбрать наибольший и наименьший по длине цикл.



Рисунок 22.

Ответ:

а) (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 на рисунке б)? Да. А на рисунке в)? Нет.



Определение 1.9. Граф называется связным, если между любыми двумя его вершинами существует путь. В противном случае граф называется несвязным.

Пример 1.9.

а) б) в)



Рисунок 23.

Две вершины А и В графа называются связными, если в графе существует путь с концами А и В; если не существует ни одного пути, связывающего их, то вершины называются несвязными.

Из определения следует, что граф является связным, если каждые две его вершины связны, и граф является несвязным, если хотя бы две его вершины несвязны.

Таким образом, чтобы доказать, что граф связный, нужно доказать, что каждые две его вершины являются связными. А чтобы доказать, что граф несвязный – нужно указать в нем две несвязные вершины.

Задание 1.11.

Какие из графов являются связными? Почему?



Рисунок 24.

Ответ: связными являются графы г) и д).

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

Пример 1.10.

Рисунок 25.



Задание 1.17.

Выделите в графе, изображенном на рисунке, ребра, которые являются мостами.

Ответ:

Рисунок 26. Рисунок 27.



Теорема 1.2. Ребро (А, В) является мостом в том и только том случае, если (А, В) – единственный путь, соединяющий вершины А и В.

Рисунок 28.



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


Рисунок 29.



Теорема 1.4. Ребро (А, В) является мостом в том и только том случае, если оно не принадлежит ни одному циклу.

Дополнительные задачи к §1см.приложение1



§2. Деревья.

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



Задание 2.1.

Нарисуйте

А) граф с семью вершинами и шестью ребрами, не имеющий циклов,

Б) связный граф с семью вершинами и шестью ребрами,

В) граф с семью вершинами, в котором для любых двух вершин существует один и только один связывающий их путь,

Г) связный граф с семью вершинами, каждое ребро которого – мост.

Возможные решения:

Рисунок 30.

Посмотрим внимательно на графы, полученные при решении задания 2.1. Что характерно для каждого из них? Во-первых, они связные; во-вторых, они не содержат циклов. Такие графы выделяют в отдельный класс.

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

При этом удобно считать, что граф, состоящий из одной изолированной вершины, тоже является деревом.

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

Задание 2.2.

Выберите из приведенных ниже графов те, которые являются деревьями. В выбранных деревьях отметьте висячие вершины.



Рисунок 31.



Замечание. Для решения этой задачи на доске можно нарисовать следующую таблицу:




1

2

3

4

5

6

Связность

Да

Да

Да

Нет

Нет

Да

Отсутствие циклов

Да

Нет

Да

Нет

Да

Да

Дерево

Да

Нет

Да

Нет

Нет

Да

Посчитаем теперь степени каждой из вершин найденных деревьев. Все они больше или равны единице. Действительно, по определению дерево – связный граф, а значит, оно не содержит изолированных вершин. Таким образом, верно утверждение: если дерево состоит более чем из одной вершины, то степень любой из его вершин d(A)1.

Задание 2.3.

Докажите, что для каждой пары вершин дерева существует единственный соединяющий их путь.



Замечание. Следует пояснить учащимся, что решение данной задачи сводится к доказательству двух утверждений:

1) доказать, что для каждой пары вершин дерева существует соединяющий их путь;

2) доказать, что путь, соединяющий любые две вершины дерева, - единственный.

Доказательство.

1) Дерево – связный граф. Из определения связности следует существование пути.

2) Предположим, что существует пара вершин данного дерева, у которых есть два соединяющих их пути. Тогда этот граф содержит цикл, то есть не является деревом. Получили противоречие, следовательно, наше предположение было неверным, и путь, соединяющий любые две вершины дерева, - единственный.

Задание 2.4.

Какое максимальное число висячих вершин может иметь дерево, построенное на 9 вершинах? Какое минимальное число висячих вершин оно может иметь?

Сделайте рисунки таких деревьев.

Ответ: 8 вершин и

2 вершины соответственно. Рисунок 32.

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

При этом удобно считать, что граф, состоящий из одного дерева, тоже является лесом.



Задание 2.5.

Выберите из данных графов те, которые являются лесом.



Рисунок 33.

Ответ: 1) да, 2) да, 3) нет, 4) да.

Теорема 2.1. Дерево – это минимальный связный граф.

Задание 2.6.

Постройте какие-нибудь деревья с 3, 4, 5, 6 вершинами и посчитайте число ребер в полученных графах.

Возможные варианты ответов:

Рисунок 34.

Обратим внимание, что в любом дереве с 3 вершинами 2 ребра, с 4 вершинами – 3, с 5 вершинами – 4, с 6 вершинами – 5, то есть во всех случаях количество ребер на единицу меньше количества вершин дерева.

Теорема 2.2. Число ребер дерева на n вершинах равно n-1.

Следствие. Связный граф на n вершинах имеет не менее чем n-1 ребро.

(Число ребер дерева на n вершинах равно n-1, а дерево – это минимальный связный граф по теореме 2.1.)



Задание 2.7.

Докажите, что дерево, имеющее не менее двух вершин, содержит, по крайней мере, две висячие вершины.



Доказательство.

Пусть дано дерево D, имеющее n (n≥2) вершин и r ребер. Дерево – связный граф, следовательно, для любой его вершины . Предположим, что для n-1 вершины их степени строго больше 1, а лишь у одной вершины степень больше или равна 1. Тогда

По теореме 1.1 сумма степеней всех вершин графа равна 2r, то есть ++…+=2r. Но из теоремы 2.2 следует, что r=n-1. Значит, =2n-2.

Таким образом, 2n-2>2n-1. Получили противоречие. Значит, по крайней мере две вершины должны иметь степень, равную 1 (по определению они и есть висячие).



Теорема 2.3. Последовательность целых чисел , , …, является последовательностью степеней вершин некоторого дерева на n вершинах (n≥2) тогда и только тогда, когда:

1) каждое 1, I =1, 2, …, n и 2) =2n-2



Задание 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, Б) нет, т.к. нет ни одной висячей вершины, В) да, т.к. выполняются условия теоремы, Г) да, т.к. выполняются условия теоремы.


§3. Остовные деревья.

Задача 3.1. Лена дружит с Викой, Олей и Сережей, Сережа, кроме того, – с Машей и Петей, а Глеб – с Димой и Машей. Изобразите с помощью графа отношение «дружить».

В полученном графе выделите те вершины и ребра, которые изображают отношение «Маша дружит с …»

Вопрос к учащимся:

- Является ли выделенный набор вершин и ребер графом? Почему?

Ответ: да, состоит из множества точек и множества соединяющих их линий.

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

Пример 3.1.
Задание 3.1. (устно) Рисунок 35.

В приведенных ниже графах назовите несколько подграфов.



Рисунок 36.



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

Пример 3.2.

Задание 3.2. Рисунок 37.

В графах задания 3.1 назовите несколько остовных подграфов.

Ответы детей учитель сохраняет на доске.

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

Пример 3.3.

Рисунок 38.

Вопрос к учащимся:

- У всякого ли графа можно выделить остовное дерево?

Ответ: несвязный граф не имеет остовного дерева, связный граф может иметь много остовных деревьев.

Задание 3.3.

А) Приведите пример графа, из которого нельзя выделить остов.

Б) Приведите пример графа и нескольких его остовных деревьев.

Возможные

ответы:
Рисунок 39.

Определение 3.4. Минимальным остовным деревом называется остовное дерево с минимальным общим весом его ребер

Задание 3.4.

В приведенном графе выделите минимальное остовное дерево.



Рисунок 40.



Задание 3.5.

Из графа Г удалите часть ребер так, чтобы новый граф Гбыл остовным деревом.



Решение. Рисунок 41.

Для того чтобы новый граф Г был остовным деревом, он должен быть остовным подграфом и быть деревом.

Данный граф Г имеет 7 вершин, значит 7 вершин должно быть и в графе Г.

По теореме 2.2 граф Г должен иметь 6 ребер. Поскольку в исходном графе 12 ребер, то удалить нужно 12-6=6 ребер так, чтобы при этом выполнялось определение дерева.



Задание 3.6.

Сколько ребер надо удалить из связного графа, имеющего r ребер и n вершин (r≥n), чтобы получить остов?



Решение.

Остов будет являться деревом на n вершинах. По теореме 2.2 дерево с n вершинами имеет n-1 ребро. Чтобы из данных r ребер графа получить n-1 ребро, нужно удалить

r-(n-1) или r-n+1 ребро. Ответ: r-n+1.

Практическую значимость остовных деревьев (остовов) дает популярная форма задачи А. Кэли. Необходимо соединить n городов железнодорожными линиями так, чтобы не строить лишних дорог. Известна стоимость строительства для каждой пары городов. Какова должна быть сеть дорог, соединяющая все города и имеющая минимальную возможную стоимость? Аналогичные вопросы могут возникать при проектировании линий электропередач, сетей ЭВМ и др.

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

Правило построения минимального остовного дерева:


  1. Выбрать произвольно вершину Х и отметить ее.

  2. Среди ребер, выходящих из отмеченной вершины Х, выбрать ребро (Х, Y) c наименьшим весом и включить его в дерево Го.

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

  4. Процесс включения ребер продолжить до тех пор, пока все вершины исходного графа Г не будут включены в дерево Го.

Построенное дерево будет минимальным остовным.

Решим конкретную задачу, используя данное правило.



Задача 3.2.

Было решено соединить пять городов (Серпухов, Коломну, Каширу, Москву и Подольск) железнодорожными линиями так, чтобы не строить лишних дорог. Какова должна быть сеть дорог, соединяющая все города и имеющая минимальную возможную стоимость, если известно, что стоимость строительства дороги

от Серпухова до Коломны - 200, до Каширы –100, до Москвы– 75, до Подольска – 80;

от Коломны до Каширы – 150, до Москвы – 120, до Подольска – 140; от Каширы до Москвы -90, до Подольска – 105; от Москвы до Подольска – 60?



Решение. Построим граф по условию задачи. Для получения остова данного графа, во-первых, отметим произвольно одну из вершин, например, Серпухов (1). Во-вторых, среди исходящих из этой вершины ребер выберем ребро с наименьшим весом.

Это ребро Серпухов – Москва (4). В-третьих, из всех ребер, выходящих из вершин Серпухов и Москва, отметим ребро наименьшего веса. Это ребро Москва – Подольск (5). В-четвертых, из ребер, исходящих из трех уже отмеченных вершин (1, 4, 5), выберем ребро наименьшего веса так, чтобы свом вторым концом оно не попадало ни в одну помеченную вершину. Рисунок 42.

Это ребро Москва – Кашира (3). Аналогично среди ребер, исходящих из вершин 1, 3, 4 или 5, выберем ребро с наименьшим весом, входящее в последнюю не помеченную вершину 2 (Коломна). Полученное дерево и есть минимальный остов.

Затраты на строительство дорог при этом составят 75+60+90+120=345.



Замечание. После того, как задача решена, следует проверить, получится ли то же самое остовное дерево, если на первом шаге выбрать например, вершину 5.

Задача 3.3.

Задано множество аэродромов, нужно определить минимальный (по сумме расстояний) набор авиарейсов, позволяющий перелететь с любого аэродрома на любой другой.

Известно, что расстояние между аэродромом А и аэродромом Б равно 500 км, между А и В – 400 км, А и Г – 450 км, А и Д – 670 км, А и Е – 800 км; между аэродромом Б и В – 340 км, Б и Г – 460 км, Б и Д – 550 км, Б и Е – 900 км; между В и Г – 280 км, В и Д – 1100 км, В и Е – 870 км, между Г и Д – 630 км, Г и Е – 1200 км, между Д и Е – 1500 км.

Ответ:


Рисунок 43.



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

Рисунок 44.



§4. Задача об отыскании кратчайшего пути.

Задач4.1.

Мистер Х решил купить себе галстук. Для этого он отправился из дома в торговый центр. Схема района, в котором живет Мистер Х, изображена с помощью графа: вершины – дома, ребра – дороги. Передвигаться от дома к дому можно только в направлении стрелок, причем около каждого из домов он не

Рисунок 45. хочет бывать более одного раза.

Сколькими способами он может попасть из дома (пункт 1) в торговый центр (пункт 9)? У какого из этих путей наименьшая длина?

Обратите внимание, что граф не совсем обычный – его ребра изображены в виде стрелок.

Определение 4.1. Ребро графа, у которого указано направление, называется ориентированным.

Пример 4.1

Обозначать ориентированное ребро с началом в вершине А и концом в вершине Б будем <А,Б> . В этом случае говорят, что ориентированное ребро выходит из А и входит в Б.


Рисунок 46.

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

Пример 4.2.

Рисунок 47.

Иногда естественно рассматривать смешанные графы, имеющие как ориентированные, так и неориентированные ребра.

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



Задание 4.1.

Какие из графов являются

А) ориентированными, Б) неориентированными, В) смешанными?

Рисунок 48.

Ответ: б) – ориентированный; г) – неориентированный; а), в) – смешанные.

Вернемся к задаче 1. Ответить на поставленные в ней вопросы помогают деревья.

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

Правило построения дерева по исходному графу:


  1. Отметить вершину X – начало пути. Это корень дерева.

  2. Из отмеченной вершины Х провести столько ребер, сколько выходило в исходном графе.

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

  4. Повторять шаг 3. до тех пор, пока каждая из висячих вершин полученного дерева не будет совпадать с вершиной Y – концом пути.

Применив указанное правило к задаче 1, получим дерево:

Рисунок 49.

Число путей равно числу висячих вершин дерева, то есть 14. Длину пути помогает определить размещение каждой вершины дерева в соответствующем ярусе.

Наикратчайший путь заканчивается в меньшем «ярусе» висячей вершины дерева, длина кратчайшего пути (1,5); (5,9) равна двум. Самый длинный путь заканчивается в наибольшем «ярусе». Длина наиболее продолжительного пути равна 7. (Ярусы отмечаем на рисунке штриховыми линиями.)

Этот пример показывает, что понятие «длина пути» в теории графов не обязательно совпадает с понятием «длина пути» в геометрии или географии.

Рисунок дерева полезен не только тем, что позволяет подсчитать количество всех возможных путей, отыскать среди них наиболее протяженный или кратчайший. Он позволяет одновременно «увидеть» все пути и сравнить их.



Задача 4.2.

Движение из пункта 1 в пункт 8 разрешается только в направлении стрелок, указанных на рисунке.

В каждом пункте можно бывать не более одного раза.
Рисунок 50.

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

Рассмотрим теперь задачу 4.1, но с условием, что план местности строится с учетом возможного различия в расстояниях между пунктами. На рисунке эти расстояния записаны над ребрами.
Рисунок 51.

То есть теперь для каждого ребра задан его вес, показывающий расстояние между домами. А вопрос тот же: определить число возможных путей от дома мистера Х до торгового центра и длину наикратчайшего из них.

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

Итак, дерево путей в этом случае будет выглядеть так:



Рисунок 52.



Задача 4.3.

Движение из пункта 1 в пункт 8 разрешается только в направлении стрелок, указанных на рисунке. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 1 в пункт 8? Какой из этих путей кратчайший, какой самый длинный?


Рисунок 53.

Задача 4.4.

Движение из пункта 2 в пункт 6 разрешается только в направлении стрелок, указанных на рисунке. В каждом пункте можно бывать не более одного раза. Сколькими способами можно попасть из пункта 2 в пункт 6? Какой из этих путей кратчайший, какой самый длинный?

Рисунок 54.

§5. «Сколько корней у дерева?»

Рассмотрим деревья, изображенные на рисунках.



Рисунок 55.

Ясно, что «особое место» в дереве занимают не только висячие вершины. Выделяются в этих деревьях и вершины, отмеченные черным цветом. Такие вершины называются корневыми.

Задание 5.1. (устно)

Назовите корневые вершины, изображенные на рисунках:



Рисунок 56.

Ответ: корневыми являются вершины 1) А; 2) С; 3) Н.

Обратимся теперь к деревьям следующего вида:



Рисунок 57.

Вопрос к учащимся:

- Какие вершины считать корневыми в этих деревьях?

Естественно считать, что все эти три дерева имеют по две корневые вершины: 1) А и В; 2) С и D; 3) А и В.

Так можно ли дать точное определение корневой вершины дерева? И сколько корневых вершин может иметь одно дерево? Чтобы ответить на эти вопросы, познакомимся с еще тремя понятиями: расстоянием между двумя вершинами, радиусом и диаметром связного графа.



Определение 5.1. Расстоянием d(A,B) между вершинами А и В графа Г называется длина кратчайшего пути, соединяющего эти вершины.

Если граф – дерево, то путь, соединяющий вершины А и В, существует и единственный (см. задачу 2.3).


Пример 5.1.

1) d(A,B)=1, d(D,C)=2,

2) d(A,B)=1, d(A,E)=4.

Рисунок 58.



Задание 5.2.

Для графов, приведенных на рисунке, найдите расстояние между вершинами А и В.



Рисунок 59.

Ответ: 1) 2; 2) 2; 3) 3.

Подсчитаем для каждой вершины дерева, изображенного на рисунке 60, наибольшее из расстояний до всех остальных его вершин и запишем эти числа на рисунке около вершин:



Рисунок 60.



Определение 5.2. Наибольшее из расстояний от каждой вершины графа до всех остальных его вершин называется диаметром графа (в данном случае дерева), а наименьшее – радиусом графа.

На рисунке 60 диаметр графа равен 5, радиус - 3



Задание 5.3.

Для графов, приведенных на рисунке, найдите их диаметры и радиусы.



Рисунок 61.

Ответ: 1) 4, 2; 2) 5, 3.

Теперь можем дать определение корневой вершины дерева.



Определение 5.3. Вершины дерева, для которых максимальное из расстояний до других его вершин равно радиусу, называются корневыми.

Пример 5.2. На рисунке 60 корневыми являются вершины А и В.

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



Задание 5.4.

Посчитайте диаметр и радиус изображенных на рисунке 62графов.



Рисунок 62.

Ответ: 1) 1,1; 2) 5, 3; 3) 3, 2; 4) 2, 1.

Задание 5.5.

Нарисуйте дерево:

А) с одной корневой вершиной и радиусом 3,

Б) с одной корневой вершиной и радиусом 4,

В) с двумя корневыми вершинами и радиусом 4,

Г) с двумя корневыми вершинами и радиусом 5,

Д) диаметр которого равен 4.

Теорема 5.1. Любое дерево имеет либо одну, либо две корневые вершины. Корневые вершины – смежные.

Доказательство.

Это утверждение, как мы видели, справедливо для простейших деревьев:

При решении задач мы убедились, что

1) расстояние от данной вершины Х дерева до любой другой его Рисунок 86. вершины Y может достигать наибольшего значения только в том случае, когда Y – висячая вершина,

2) корневая вершина не может быть висячей.

Удалим теперь из дерева D, имеющего радиус r, все его висячие вершины. Тогда получим дерево , имеющее радиус длины r-1 и те же корневые вершины.

Ясно, что, продолжая этот процесс, придем, в конце концов, к дереву, изображенному на рисунке или на рисунке. Полученное дерево имеет ту же (те же) корневую вершину (корневые вершины), что и первоначальное дерево D.

§6. Деревья и комбинаторика.

«Десять друзей, решив отпраздновать окончание школы в ресторане, заспорили у стола о том, как усесться вокруг него:

- Давайте сядем в алфавитном порядке.

- Нет, сядем по возрасту!

- По успеваемости, может?.....

Подошел официант: «Вы еще не расселись? Молодые друзья мои, оставьте ваши пререкания. Сядьте за стол, как кому придется, и выслушайте меня.

Пусть один из вас запишет, в каком порядке вы сидите сейчас. Завтра вы снова явитесь сюда пообедать и разместитесь в ином порядке. Послезавтра сядете опять по-иному и т.д., пока не перепробуете все возможные размещения. Когда же придет время вновь сесть так, как высидите сейчас, тогда – обещаю торжественно – я начну ежедневно угощать вас всех бесплатно самыми изысканными обедами».

Друзья очень обрадовались такому предложению и согласились.

Однако им не пришлось дождаться того дня, когда они стали питаться бесплатно. И не потому, что официант не исполнил своего обещания, а потому, что число всех возможных размещений за столом чересчур велико. Оно равно ни мало, ни манного 3628800. Такое число дней составляет почти 10000 лет! Вам может показаться невозможным, что 10 человек могли разместиться таким большим числом способов. Проверьте расчет сами».

Действительно, число перестановок десяти элементов равно n!, то есть 1·2·3·4·5·6·7·8·9·10=3628800.

Комбинаторные задачи встречаются довольно часто. Конечно, такие задачи можно решать, используя соответствующие формулы, и для большого числа элементов это удобно (см. пример выше). Однако если элементов немного и к тому же нужно увидеть все возможные варианты, то помогут деревья.

С помощью леса можно представить перестановки из n элементов некоторого множества и подсчитать их число. Для n=4 такой лес изображен на рисунке.



Рисунок 63.

Всевозможные перестановки прочитываются по этой схеме от корневой до висячей вершины соответствующего дерева. Ярус показывает номер места, на котором расположен элемент. Число висячих вершин леса равно числу перестановок.

Задача 6.1.

Составьте всевозможные перестановки из букв слова «граф». Изобразите лес решения.



Задача6.2.

Даны цифры: 3, 5, 7. Составьте из них все возможные трехзначные числа, в которых данные цифры не повторяются. (Ответ: 6.)

С помощью леса можно также представить размещения из n элементов по k некоторого множества и подсчитать их число. Для n=4, k=2 такой лес изображен на рисунке.

Рисунок 64.

Всевозможные размещения прочитываются по этой схеме от корневой до висячей вершины соответствующего дерева. Ярус показывает номер места, на котором расположен элемент, количество ярусов равно числу k. Число висячих вершин леса равно числу размещений.

Задача6.3.

Даны цифры: 3, 5, 7. Составьте из них все возможные двузначные числа, в которых данные цифры не повторяются. (Ответ: 6.)



Задача 6.4.

Изобразите с помощью леса всевозможные размещения четырех элементов множества {a,b,c,d} по трем ячейкам и подсчитайте их число. (Ответ: 24.)



Задача 6.5.

От турбазы к горному озеру ведут четыре тропы. Сколькими способами туристы могут отправиться в поход к озеру, если они не хотят спуститься по той же тропе, что и поднимались? (Ответ: 12)



Задача 6.6.

Сколько различных обедов П.И.Чичиков мог насчитать из блюд, выставленных на столе у П.П.Петухова, если бы каждый обед состоял только из одного холодного блюда, одного первого, одного второго и одного третьего? На столе у П.П.Петухова на этот раз были выставлены: из холодных блюд - студень с хреном, свежая икра, свежепросольная белужина; из первых – уха из стерлядей, щи с грибами; из вторых – осетрина жареная, теленок, жареный на вертеле; из третьих–арбузы, груши.(Ответ: 24.)



Задача.6.7.

Продаются чайные чашки по 40 р., 50 р., 60 р., 70 р., 75 р. и блюдца по 32 р., 42 р., 58 р. Сколько различных наборов из одной чашки и одного блюдца можно составить? Какой набор будет самым дешевым (дорогим)? Могут ли оказаться два различных набора с одинаковой ценой? (Ответ: 15 наборов, самый дешевый набор - чашка за 40 р., блюдце за 32 р., самый дорогой - чашка за 75 р., блюдце за 58 р., с одинаковой ценой – 40+42 и 50+32, 50+42 и 60+32, 60+42 и 70+32.)



Указание. Для решения данной задачи необходимо составить дерево вариантов составления наборов, а затем посчитать их стоимости.

Задача 6.8. (О взвешивании монет.)

Известна целая серия задач о взвешивании монет. Рассмотрим одну из них.

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

Решение. Занумеруем мо­неты, и пусть монета 6 — настоящая. Обозначим через F(A) вес монет, принадлежащих множеству А. Процесс определения фальшивой монеты с помо­щью двух взвешиваний изображен на рисунке 65.

Рисунок 65.


Из рисунка видно, что в любом случае можно найти фальшивую монету за 2 действия (взвешивания).

Задача6.9. (О разбиении и композиции натуральных чисел.)

Задачи на разбиение натуральных чисел впервые решались еще в XVII веке Г.В.Лейбницем. Родственные им задачи и сейчас занимают важное место в современной комбинаторике.

Разбиение натурального числа – это его представление в виде суммы натуральных слагаемых.

Пример 6.1.

Разбиение числа 3: 3=3, 3=2+1, 3=1+1+1;

Разбиение числа 4: 4=4, 4=3+1, 4=2+2, 4=2+1+1, 4=1+1+1+1.

Композиция натурального числа – это его «разбиение» с учетом порядка расстановки слагаемых.

Так, число 5 может быть представлено в виде суммы 2+3 или 3+2. Обе эти записи обозначают одно и тоже разбиение, но две различные композиции. Ясно, что количество композиций для данного натурального числа больше количества его разбиений.

Пример 6.2.

Композиции числа 3: 3=3, 3=2+1, 3=1+2, 3=1+1+1;

Композиции числа 4: 4=4, 4=3+1, 4=1+3, 4=2+2, 4=2+1+1, 4=1+2+1, 4=1+1+2, 4=1+1+1+1.

Две композиции считаются равными только в том случае, если они состоят из одинакового числа соответственно равных слагаемых, расположенных в одинаковом порядке.

Всевозможные композиции любого натурального числа n можно представить с помощью дерева, способ построения которого ясен из рассмотрения рисунка 66, где изображено такое дерево для случая n=5.

Число, которое представляется набором композиций для каждого соответствующего яруса дерева, на рисунке выделяется с помощью кружочка. Например, в ярусе 3 находим, следуя по вертикали сверху вниз, всевозможные композиции числа 3 в определенной очередности: 1+1+1, 1+2 и т.д. Число композиций при переходе от яруса k к ярусу k+1, как это видно на рисунке, удваивается (в каждую вершину входит одно ребро, а выходит в следующий ярус два), а при k=1 оно равно единице. Поэтому число композиций для произвольного яруса k равно .


Рисунок 66.



§7. Деревья в теории вероятностей.

Еще в глубокой древности появились различные азартные игры. В Древней Греции и Риме широкое распространение получили игры в астрагалы, когда игроки бросали кости животных. Также пользовались популярностью игральные кости – кубики с нанесенными на гранях точками. Позднее азартные игры распространились и в средневековой Европе.

Эти игры подарили математикам массу интересных задач, которые потом легли в основу теории вероятностей.

Так, до середины XVII в. не было правильных методов решения задач «о дележе ставки» (как правило, играли на деньги: игроки делали ставки, а победитель забирал всю сумму; однако иногда игра прерывалась раньше финала, и возникал вопрос: «Как разделить деньги?»).

В 1654 г. между французскими математиками Блезом Паскалем и Пьером Ферма возникла переписка по поводу ряда комбинаторных задач, в том числе и задач «о дележе ставки». Оба ученых, хотя и несколько разными способами, пришли к верному решению, деля ставку пропорционально вероятности выигрыша всей суммы при продолжении игры. Нужно отметить, что до них никто из математиков вероятность событий не вычислял, в их переписке вероятность и комбинаторика впервые были научно обоснованы, и поэтому Паскаль и Ферма считаются основателями теории вероятностей.

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



Задача 7.1. (задача Гюйгенса).

В урне два белых и четыре черных шара. Один азартный человек держит пари с другим, что среди вынутых трех шаров будет ров­но один белый. В каком отношении находятся шансы спорящих?



Решение 1 (традиционное).

В данном случае испытание - вынимание трех шаров, а событие, благоприятствующее одному из спорящих, - достать ровно один белый шар (обозначим его А).

Поскольку порядок вынимания трех шаров не имеет значения, то число всех исходов можно найти как число сочетаний из 6 по 3, т. е. .

Один белый шар можно достать в случаях, а два черных - в , тогда по ос­новному правилу комбинаторики .

Отсюда Р(А)=, следовательно Р( ) = 1 - Р( А) = 1 - .

Следовательно, отношение шансов спорящих равно 3:2.

Э
то стандартный способ решения данной задачи. Однако существует другой, более наглядный, способ решения данной задачи, который основывается на построении вероятностного дерева.

Решение 2.

Рисунок 67.

Составим вероятностное дерево исходов, где корневая вершина – начало испытания, а каждому ребру ставится в соответствие число (вес) - вероятность появления белого (не закрашенного) или черного (закрашенного) шара (рисунок ).

Мы получили, что вероятность события Р(А) - появление одного белого и двух черных шаров, равна, следовательно Р( ) = 1 - Р( А) = 1-.

Ответ: 3:2.

Задача 7.2.

Какова вероятность, что при двукратном бросании игральной кости:

а) оба раза выпадет единица;

б) хотя бы один раз выпадет единица?



Решение.

Построим дерево согласно условию. Ярус дерева показывает номер соответствующего события: 1-й ярус – не бросалась ни одна кость, 2-й ярус – бросалась одна кость, 3-й ярус – две и т.д.


Рисунок 68.

а) Вес каждого ребра будет равен 1/6.

б) Вес каждого ребра будет равен 1/6. Вероятность того, что выпадет две единицы равна , 1 и 2 – , 1 и 3 – , и т.д. Таким образом, вероятность того, что хотя бы один раз выпадет единица, равна:



.

Задача 7.3.

В XVII в. жил во Франции страстный игрок в кости шевалье де Мерэ. Ему хотелось разбогатеть при помощи игры в кости, и для этого он придумывал различные усложненные правила игры. Однажды де Мерэ придумал следующее правило игры в кости: игральная кость бросается четыре раза; шевалье бился об заклад, что при этом хотя бы один раз выпадет шесть очков.



Решение.

Т. к. при каждом бросании игральной кости имеется шесть различных возможностей, то при четырех бросаниях кости число различных равновозможных случаев будет 6·6·6·6=1296. Но среди этих 1296 случаев будет 5·5·5·5=625 таких, когда шесть не появится ни разу, а в 1296-625=671 случае хотя бы один раз из четырех выпадет шестерка. Следовательно, вероятность выпадения хотя бы одной шестерки при четырех бросках равна , что больше . И чем больше шевалье де Мерэ играл, тем больше выигрывал.



Замечание. Попросить учащихся построить дерево исходов дома самостоятельно.

Задача 7.4.

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



Решение. Составим вероятностное дерево исходов, где корневая вершина соответствует началу испытания, а вес ребра - вероятность появления следующей буквы:

Рисунок 69.

Вероятность получения слова «мама» - .

Задача7.5.

Слово «СОЕДИНЕНИЕ» разделено на отдельные буквы, из них произвольным образом отбираются и выкладываются по порядку четыре буквы. Какова вероятность получения слова «НОС»? Ответ:



Задача 7.6.

Из пяти букв разрезной азбуки составлено слово «КНИГА». Неграмотный


мальчик перемешал буквы, а потом наугад их собрал. Какова вероятность того, что он
опять составил слово «КНИГА»? Ответ:

Задача 7.7.

Какова вероятность того, что при двух бросаниях монеты хотя бы один раз выпадет «орел»? Ответ:



Задача 7.8.

Два мальчика бросают монету 3 раза каждый. Выигрывает первый, если выпадет


два орла и одна решка, а второй - если три орла. У кого больше шансов выиграть?

Ответ: у первого.



Задача 7.9.

В пруду водится 4 окуня, 5 карасей и З щуки. Какова вероятность того, что среди


двух пойманных рыбаком рыб будет а) одна ­- щука, другая - окунь; б) обе – караси.

Ответ: а) ; б) .


следующая страница >>