Решение задач по теме «ГРАФЫ» Миткевич Елена Юрьевна, учитель информатики МБОУ «Лицей» р. П. Степное. - презентация

1 Решение задач по теме «ГРАФЫ» Миткевич Елена Юрьевна, учитель информатики МБОУ «Лицей» р. П. Степное

2 Состав графа Граф состоит из вершин, связанных линиями. Направленная линия (со стрелкой) называется дугой. Линия ненаправленная (без стрелки) называется ребром. Линия, выходящая из некоторой вершины и входящая в неё же, называется петлей. А В С петля ребро дуга

3 Изображение вершин

4 Неориентированный граф - граф, вершины которого соединены ребрами. С помощью таких графов могут быть представлены схемы двухсторонних (симметричных) отношений. Маша Юра Аня Витя Коля

5 Граф отношения «переписываются» Цепь – путь по вершинам и ребрам, включающий любое ребро графа не более одного раза. Цикл – цепь, начальная и конечная вершины которой совпадают. Граф с циклом называют сетью. Маша Юра Аня Витя Коля

6 Ориентированный граф - граф, вершины которого соединены дугами. С помощью таких графов могут быть представлены схемы односторонних отношений. Маша Юра Аня Витя Коля

7 граф, у которого вершины или рёбра (дуги) несут дополнительную информацию (вес). Взвешенный граф - Москва, 1147 Переславль Залесский, 1152 Владимир,

8 Иерархия - это расположение частей или элементов целого в порядке от высшего к низшему. Директор Заместители директора Учителя Ученики Отношения подчиненности в школе

9 Классификация компьютеров Дерево – граф иерархической структуры. Между любыми двумя его вершинами существует единственный путь. Дерево не содержит циклов и петель. компьютер суперкомпьютер рабочая станция персональный компьютер настольный портативный карманный

10 Чемпион Финалисты Участники ½ финала Участники ¼ финала Первоначальные игроки Корень – главная вершина дерева. Предок – объект верхнего уровня. Потомок – объект нижнего уровня. Листья – вершины, не имеющие потомков. Олимпийская система спортивных соревнований

11 Файловая структура

12 Задача : В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в бутылке, сосуд с лимонадом стоит между кувшином и сосудом с квасом, в банке – не лимонад и не вода. Стакан стоит около банки и сосуда с молоком. Куда налита каждая жидкость? Молоко ЛимонадКвас Вода Бутылка Стакан Кувшин Банка Ответ: в кувшине-молоко, в банке-квас, в стакане-вода, в бутылке-лимонад.

13 Соединим пунктирными ребрами те вершины, которые не могут быть связаны друг с другом. бутылкастаканбанкакувшин молоко лимонад квас вода

14 бутылкастаканбанкакувшинмолоко лимонад квас вода Ответ: в кувшине-молоко, в банке-квас, в стакане-вода, в бутылке-лимонад.

15 На международном конгрессе встретились четверо ученых: физик, историк, биолог и математик. Национальности их различны и, хотя каждый из ученых владеет двумя языками их четырех (русский, английский, французский и итальянский), нет такого языка, на котором они могут разговаривать вчетвером. Есть язык, на котором они могут разговаривать сразу трое, – итальянский. Никто из ученых не владеет французским и русским языками одновременно. Хотя физик не говорит по-английски, но может быть переводчиком, если биолог и историк захотят поговорить друг с другом. Историк может говорить с математиком по-французски. Физик, биолог и математик не могут беседовать втроем на одном языке. Какими двумя языками владеет биолог (укажите названия языков в именительном падеже через пробел). Задача :

16 Рус.яз Анг.яз Фран.яз Итал.яз Физик ИсторикБиолог Математик Ответ: русский английский

17 Решение: Рус.яз Анг.яз Фран.яз Итал.яз Физик Историк Биолог Математик Ответ: русский английский