Информационные модели на графах

Многообразие схем

Блок-схема

Графы Граф –это схема являющаяся наглядным представлением состава и структуры системы. Граф состоит из вершин, связанных линиями.

Неориентированный граф Связи между объектами взаимные. Вершины соединены рёбрами.

Ориентированный граф Связь между объектами односторонняя. Вершины соединены дугами (стрелками)

Взвешенный граф

Задача 1 Сколькими способами можно рассадить в ряд на три стула троих учеников?

Задача 2 Чтобы принести царю-батюшке молодильные яблоки, Иван-Царевич должен найти единственный верный путь к волшебному саду. На развилке трёх дорог старый ворон посоветовал Ивану: 1) иди сейчас по правой тропинке; 2) на следующей развилке не выбирай правую тропинку; 3) на третьей развилке не ходи по левой тропинке. Пролетавший мимо голубь шепнул Ивану, что только один совет ворона верный, и что на всех трёх развилках надо выбрать дороги разных направлений. Укажите верный маршрут.

Задача 3 Для составления цепочек используются бусины, помеченные буквами A, B, C, D, E. На первом месте в цепочке стоит одна из бусин A, C, E. На втором – любая гласная, если первая согласная, и любая согласная, если первая гласная. На третьем месте - одна из бусин C, D, E, не стоящая на первом месте. Сколько цепочек можно составить по этому правилу?

Задача 4 Между населёнными пунктами A, B, C, D, E построены дороги. Протяженность которых приведена в таблице: Определите кратчайший путь между дорогами A и D. ABCDE A246 B21 C4151 D53 E613

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