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

1

2

3

4

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

6 Мы знаем длину каждой дороги. Пропишем ее над соответствующей линией. Такие графы в математике называются взвешенными

7 Чтобы помочь принцу, нужно найти такой маршрут, по которому он сможет обойти все дома и найти Золушку:

8 или

9 или Видно, что существует много способов отыскать нужную дорогу ! Такую процедуру математики называют поиском в графе!!!

10 Очень хочется, чтобы принц сэкономил временя, а значит, побывал в каждом доме (то есть посетил каждую вершину) только один раз. Из рассмотренных нами случаев сюда можно отнести:

11 и Такой путь назвали гамильтоновым в честь великого математика Уильяма Роуана Гамильтона.

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

13

14

15 Из рассмотренных нами случаев, длина пути меньше всего у данного графа! Возможно, это и есть самый короткий путь!!!!!

16

17 Мы увидели, что математика может помочь нашему принцу поскорее найти Золушку. Вопросы, которые мы рассматривали уже давно известны в этой науке. Можно сделать вывод:

18