Информационные модели на графах. Пути в графах. Автор работы : уч. информатики Неклеса О. О.

ГРАФ – это средство наглядного представления элементов объекта связей между ними. Граф состоит из вершин (или узлов), связанных дугами или отрезками – ребрами. Две вершины, соединенные дугой или ребром, называются смежными. Каждому ребру или дуге соотносится какое- нибудь число. Число может обозначать расстояние между населёнными пунктами, время перехода от одной вершины к другой.

Граф может быть представлен в виде списка дуг (АВ; 7), графически или с помощью таблицы. АB C E Списки дугГрафическая форма Табличная форма (АВ; 7), (BC; 4) (CD; 8) АВС А3 В4 С34

Путь в графе - это конечная последовательность вершин графа, где каждая из вершин соединена со следующей в последовательности вершиной как минимум одним ребром (дугой).

Неравенство треугольника - если длина любой стороны треугольника не превосходит сумму длин двух его других сторон. АВ < АС + ВС АС < АВ + СВ ВС < АС + АВ Теорема: А С В

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

Сколько путей ?

Задача 2. Красная Шапочка пошла к бабушке пирожки отнести. Тропинок несколько. Сколько путей она может выбрать?

Сколько путей ?

С « Ё » « Ё » - колючий, С « У » « У » - ползучий : Задача 3. Сколько всего путей может быть?

С буквой буквой « Н », « Н », мои мои друзья, Ничего Ничего не не значу значу я,я,я,я, « Н » « Н » на на « С » « С » перемените перемените – Смело Смело в суп суп меня меня кладите. Не Не берите берите с буквой буквой « М » « М » - Я пальто пальто у вас вас проем. Задача 4. Сколько всего путей может быть?

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

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

Задача 7. Четыре мышонка решили соединить свои норки подземными ходами. Для этого они обозначили каждую нору и дом Катуси числом букв в имени хозяина. Соедини все пары норок, у которых сумма номеров – нечетное число Вершин : 5 Рёбер : 6

Соединить все пары норок у которых произведение номеров не больше 20. Задача 8. Вершин : 4 Рёбер :

Задача 9. Соединить все пары норок, у которых разность номеров равна 1 (из большего номера вычитается меньший) Вершин : 5 Рёбер :4

Задача 10. Соединить все пары норок, у которых сумма номеров меньше 9. Вершин: 3 Рёбер: 2

Самостоятельная работа по теме: «Графы» Вопрос 1 Вопрос 2 Вопрос 3 Вопрос 4 Вопрос 5 Вопрос 6 Вопрос 7 Д/ЗД/З

Вопрос 1 Вася, Маша, Даша и Катя пришли утром в школу и обменялись приветствиями каждый с каждым. Сколько всего было приветствий ? 4106

Нет ПОПРОБУЙТЕ ЕЩЁ РАЗ!

Правильно

Маша пришла в зоопарк и хочет увидеть как можно больше зверей. По какой тропинке ей надо идти? По краснойПо желтойПо зеленой Вопрос 2

Вопрос 3 Сколько всего путей, может быть в данном зоопарке? 5129

Вопрос 4 Петя может выбрать красный или зеленый карандаш и нарисовать или мяч, или воздушный шарик, или флажок. Сколькими способами он может это сделать?

Вопрос 5 Вопрос 5 Животные в зоопарке дружат друг с другом и часто ходят в гости. Сколько тропинок они протоптали между своими домиками ? 456

Вопрос 6 Пять футбольных команд А, Б, В, Г, Д должны сыграть в матчи друг с другом. Уже сыграли А с Б, В, Г ; Б с А, В, Д. Сколько матчей уже сыграно ? 546 А В БГ Д

Вопрос 7 Вопрос 7 Сколько матчей осталось сыграть ? 1085 А В БГ Д

Домашнее задание Задача: Соединить все пары норок, у которых произведение номеров делится на 7. Вершин : 5 Рёбер :4