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

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



Advertisements
Похожие презентации
Тема урока: «Решение комбинаторных задач с помощью графов»
Advertisements

Вопросы к уроку. Что такое комбинаторика? Что такое граф? Какие задачи относятся к комбинаторным? Как решаются комбинаторные задачи с помощью графов?
Повторение основных методов решения комбинаторных задач и формул комбинаторики.
Элементы комбинаторики. Задача 1. Три друга – Антон, Борис и Виктор – приобрели два билета на футбольный матч. Сколько существует различных вариантов.
Чем занимается комбинаторика ? Что такое граф ? Какие задачи относятся к комбинаторным ? Как решаются комбинаторные задачи с помощью графов ?
Урок 2 Цели: изучить комбинаторное правило умножения Усвоить способы решения комбинаторных задач Воспитывать самостоятельность и внимательность.
ГОУ средняя общеобразовательная школа 80 с углубленным изучением английского языка Петроградского административного района г. Санкт- Петербурга.
Введение в комбинаторику Введение в комбинаторику Комбинаторика является древнейшей и, возможно, ключевой ветвью математики.
Живаева Екатерина Ученица 11 класса. Выяснить особенности применения теории графов при решении задач и в практической деятельности.
2 Решение многих комбинаторных задач основывается на общем правиле умножения. Для того чтобы найти число всех возможных исходов независимого проведения.
К ОМБИНАТОРИКА. Решение задач. Орлова Л.В., Малышкина С.Ю.
ГРАФЫ … ГРАФЫ ??? ГРАФЫ ??? ГРАФЫ !!! ГРАФЫ !!!. Задача 1 Между девятью планетами Солнечной системы установлено космическое сообщение. Рейсовые ракеты.
Комбинаторные задачи Тема «Введение в вероятность». Учитель Козловская Т.В. МБОУ «Хову-Аксынская СОШ» Prezentacii.com.
Сочетания Задача 1. Три друга – Антон, Борис и Виктор – приобрели два билета на футбольный матч. Сколько существует различных вариантов посещения футбольного.
Алексеева Е.В., учитель информатики и ИКТ МОУ «Сланцевская СОШ 3» Введение в теорию графов 11 класс начать.
Различные комбинации из трех элементов. А-7. Три друга, Антон, Борис и Виктор, приобрели два билета на футбольный матч. Сколько существует различных вариантов.
Сочетания Выбор нескольких элементов. Выбор двух элементов из множества В чемпионате участвовали 7 команд. Каждая команда играла один матч с каждой. Сколько.
1 Графы Это - один из способов решения логических задач По условию задачи составляется схема, состоящая из линий(ребер) и точек (вершин).
Комбинаторные задачи. Комбинаторика. выбор расположение перестановки n!
Элементы статистики и вероятность. Алгебра. 7-9 класс. Автор: Рыженко Е.В. МОУ « СОШ 64» г. Астрахань.
Транксрипт:

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

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

Задача 2: Андрей, Борис, Виктор и Григорий обменялись фотографиями, причём каждый подарил каждому по одной фотографии. Сколько всего фотографий было подарено? ВГ Б 1 А Ответ: ? С помощью стрелок на рёбрах полного графа показан процесс обмена фотографиями.

Задача 3: Сколько диагоналей можно провести в выпуклом n-угольнике ? A1A1 A2A2 A3A3 AnAn n-угольник с диагоналями - это полный граф с n вершинами. Найдём число его рёбер: n * (n-1)/2.Тогда число диагоналей на n меньше и равно n * (n-1)/2-n = n * (n-3)/2 Ответ: n=n*(n-3)/2

Граф – дерево. Задача 4: В столовой на выбор предложено 3 первых, 2 вторых и 4 третьих блюда. Сколько различных обедов можно составить? 1-е блюдо2-е блюдо 3-е блюдо

1-е блюдо2-е блюдо3-е блюдо Дерево вариантов

Задача 5: Антон, Борис, и Василий купили 3 билета на футбол на 1-е, 2-е и 3-е места первого ряда. Сколькими способами они смогут занять свои места? А А В А В Б Б В Б Б А В В Б А Ответ: ?способов

Таким образом, графы представляют собой удобные схемы для изображения всех вариантов и определения их количества. Задачи для самостоятельного решения: 1.При встрече каждый из друзей пожал другому руку. Сколько рукопожатий было сделано, если друзей было: 1)трое; 2)четверо; 3)пятеро ? 2. Маше на день рождения подарили 3 букета цветов: розы, астры и гвоздики. В доме было 2 вазы: хрустальная и кера- мическая. Перечислить все возможные сочетания букета с вазой. 3. Сколько различных трёхзначных чисел можно записать с помощью цифр 5, 6, 7, 8, 9 при условии, что цифры в числе 1)могут повторяться; 2)должны быть различными?