Элементы комбинаторики (графы)

Элементы комбинаторики

7 класс

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

• Введем обозначение:
• P n – количество перестановок
• В нашем случае n=6, т.к. у нас 6 человек и 6 стульев.
• Р 6 =6*5*4*3*2*1=720

• Десять разных писем раскладывают по одному в десять конвертов. Сколько существует способов такого раскладывания? Предложенная ситуация отличается от предыдущей тем, что там были люди и стулья, а здесь письма и конверты. Однако и здесь, и там требуется узнать, сколькими способами можно разместить n предметов на n местах.

• Повторяя предыдущее решение, получаем, что всего имеется
• 10· 9· 8· 7· 6· 5· 4· 3· 2· 1 = способов раскладывания писем по конвертам. Более 3,5 миллионов!!!

• Как мы видим, условия задач разные, а решения одинаковы.
• Поэтому удобно ввести одинаковые обозначения для таких решений.
• Определение: Произведение первых подряд идущих n натуральных чисел называют факториалом и обозначают n!
• n! = 1· 2· 3· …· (n-2)(n-1)n

• число всевозможных перестановок из n элементов вычисляется по формуле Рn = n!
• Несколько первых значений для n!
• 0!=1
• 1! = 1
• 2! = 1·2 = 2
• 3! = 1· 2· 3 = 6
• 4! = 1· 2· 3· 4 = 24
• 5! = 4! · 5 = 120
• 6! = 5!· 6 = 720 

В 7 классе в среду 5 уроков: алгебра, геометрия, физкультура, русский язык, английский язык. Сколько можно составить вариантов расписания на этот день?

• n=5
• P5=5!=120

Бросают две игральные кости. Сколько различных пар очков может появиться?

Кол-во очков

1

1

1 1

2

2

3

2 1

1 2

3

4

2 2

1 3

4

3 1

4 1

5

2 3

5

3 2

1 4

2 4

6

1 5

3 3

5 1

6

4 2

4 3

2 5

6 1

5 2

3 4

1 6

4 4

5 3

6 2

2 6

3 5

4 5

6 3

5 4

3 6

5 5

4 6

6 4

6 5

5 6

6 6

Таблица вариантов

Итого 36 вариантов

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

• Вершины – это элементы некоторого множества
• Ребра – связи между этими элементами

Практическое применение графов

Виды графов

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

• Задача о семи кёнигсбергских мостах

• Из города А в город В ведут две дороги, из города В в город С – три дороги, из города С до пристани – две дороги. Туристы хотят проехать из города А через города В и С к пристани. Сколькими способами они могут выбрать маршрут ?

С1

С2

В1

С3

А

С1

С2

В2

С3

№ 716

б

щ

п

р

г

г

п

р

ч

ч

к

к

ч

к

к

ч

к

ч

к

ч

№ 727

• У нас 6 цифр, значит, n=6
• Р 6 =6!=720
• МЕТРО – 5 букв
• Р 5 =5!=120
• Р 8 =8!=8*7*6!
• Р 8 =56*720=40320

• Р3+Р4=3!+4!=3*2+4*3*2=6+24=30

№ 713 решим задачу с помощью графов

• 1.

• 3.

• 2.

Т.к. каждый отдал 2 карточки, то всего 6

Здесь из каждой вершины выходит 4 отрезка, вершин 5, ответ 20

Здесь каждый отдает 3. значит, всего 12

№ 730

7

7

77

8

8

9

9

78

87

97

79

88

89

98

99

№ 733 (1)

• В данном случае речь идет о сочетаниях
• Значит, порядок роли не играет:
• 3!/2=6/2=3
• У нас три варианта:
• АВ, АГ, ВГ

№ 731

7

8

9

9

8

9

7

8

7

9

7

9

8

8

7

Домашнее задание

• № 701, 702, 712