Графы Комбинаторика. Планеты Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: - презентация

1 Графы Комбинаторика

2 Планеты Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?

3 Телефоны В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими ?

4 Города В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой.

5 Дороги В государстве 100 городов к из каждого города выходит 4 дороги. Сколько всего дорог в государстве.

6 Сколько дорог? В государстве 100 городов, из каждого выходит 2 дороги, кроме столицы, откуда выходит 5 дорог и города Горный, откуда выходит одна единственная дорога. Сколько всего дорог в государстве?

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

8 Алгоритм Флойда Построим матрицу D 0 размерности |V| x |V|, элементы которой определяются по правилу: d ii 0 = 0; d ij 0 = Weight(v i, v j ), где ij, если в графе существует ребро (дуга) (v i, v j ); d ij 0 = бесконечность, где ij, если нет ребра (дуги) (v i, v j ). m=0

9 Пример V1V1 V2V2 V3V3 V4V4 V5V5 V1V1 0х332 V2V2 50ххх V3V3 х20х3 V4V4 хх20х V5V5 ххх10 V1 V2 V3 V4 V

10 Основная часть алгоритма 1. Построим матрицу D m+1 по D m, вычисляя ее элементы следующим образом: d ij m+1 =min{d ij m, d i(m+1) m + d (m+1)j m }, где ij; d ii m+1 =0 (*). 2. m:=m+1; если m

11 Пример m=0 V1V1 V2V2 V3V3 V4V4 V5V5 V1V1 0х332 V2V2 50ххх V3V3 х20х3 V4V4 хх20х V5V5 ххх10 V1V1 V2V2 V3V3 V4V4 V5V5 V1V1 0х332 V2V хх V3V3 х20х3 V4V4 хх20х V5V5 ххх10 V1 V2 V3 V4 V

12 Пример m=1 V1V1 V2V2 V3V3 V4V4 V5V5 V1V1 0х332 V2V V3V3 х20х3 V4V4 хх20х V5V5 ххх10 V1V1 V2V2 V3V3 V4V4 V5V5 V1V1 0х332 V2V V3V х3 V4V4 хх20х V5V5 ххх10 V1 V2 V3 V4 V

13 Пример m=2 V1V1 V2V2 V3V3 V4V4 V5V5 V1V1 0х332 V2V V3V V4V4 хх20х V5V5 ххх10 V1V1 V2V2 V3V3 V4V4 V5V5 V1V V2V V3V V4V4 хх20х V5V5 ххх10 V1 V2 V3 V4 V

14 Пример m=3 V1V1 V2V2 V3V3 V4V4 V5V5 V1V V2V V3V V4V V5V5 ххх10 V1V1 V2V2 V3V3 V4V4 V5V5 V1V V2V V3V V4V V5V хх10 V1 V2 V3 V4 V

15 Пример m=4 V1V1 V2V2 V3V3 V4V4 V5V5 V1V V2V V3V V4V V5V V1V1 V2V2 V3V3 V4V4 V5V5 V1V V2V V3V V4V V5V V1 V2 V3 V4 V

16 Пример m=5 V1V1 V2V2 V3V3 V4V4 V5V5 V1V V2V V3V V4V V5V

17 Пример V1V1 V2V2 V3V3 V4V4 V5V5 V1V V2V V3V V4V V5V φ 1 =13 Ψ 1 =31 Q 1 =44 φ 2 =28 Ψ 2 =16 Q 2 =44 φ 3 =16 Ψ 3 =16 Q 3 =32 φ 4 =20 Ψ 4 =16 Q 4 =36 φ 5 =19 Ψ 5 =17 Q 5 =36 Q 3 – медиана.

18 Найти медиану графа

19

20 Любимые мультфильмы Жила-была одна дружная семья: мама, папа и сын. Они все любили делать вместе. Но вот мультфильмы любили разные: «Ну, погоди!», «Покемоны», «Том и Джерри». Определите, какой мультфильм любит каждый из них, если мама, папа и любитель мультфильма «Покемоны» никогда не унывают, а папа и любитель мультфильма «Том и Джерри» делают зарядку по утрам?

21 Марки и конверты Имеется 5 видов конвертов и 4 вида марок. Сколькими способами можно выбрать конверт с маркой?

22 Словари Сколько словарей нужно издать, чтобы переводить с любого из 5 языков на любой другой?

23 Шахматный турнир В шахматном турнире участвуют 16 человек. Сколько партий должно быть сыграно в турнире, если между любыми участниками должна быть сыграна одна партия?

24 Жеребьевка Порядок выступления 7 участников конкурса определяется жребием. Сколько различных вариантов жеребьевки при этом возможно?

25 Студенты Сколькими способами можно разбить группу из 25 студентов на три подгруппы по 6, 9 и 10 человек в каждой группе?

26 Семизначные числа Сколько существует семизначных чисел, состоящих из цифр 4,5 и 6, в которых цифра 4 повторяется 3 раза, а цифры 5 и 6 - по 2 раза?

27 Все для чая В магазине «Все для чая» есть 5 разных чашек и 3 разных блюдца. Сколькими способами можно купить чашку с блюдцем?

28 Города В Стране Чудес есть четыре города: А, Б и В и Г. Из города А в город Б ведет 6 дорог, а из города Б в город В – 4 дороги, из города А в город Г – две дороги, и из города Г в город В – тоже две дороги. Сколькими способами можно проехать от А до В?

29 Флаг Сколькими способами можно сделать трехцветный флаг с горизонтальными полосами одинаковой ширины, если имеется материя шести различных цветов?

30 Авиалинии В стране 20 городов, каждые два из которых соединены авиалинией. Сколько авиалиний в этой стране?