I тур 1. Какой граф называется неполным? 2. Какой граф называется связным? 3. Какой граф называется плоским? 4. Какой граф называется нулевым? 5. Какой. - презентация

1

2 I тур

3 1. Какой граф называется неполным? 2. Какой граф называется связным? 3. Какой граф называется плоским? 4. Какой граф называется нулевым? 5. Какой граф называется несвязным?

4 1. Чему равно количество рёбер полного графа? 2. Что называют степенью вершины графа? 3. Какие графы называют изоморфными? 4. Что называют путем в графе? 5. Что называют циклом?

5 II тур

6 1. «Кто ходит в гости по утрам…» «Кто ходит в гости по утрам…» «Кто ходит в гости по утрам…» 2. Есть ли жизнь на марсе? Есть ли жизнь на марсе? Есть ли жизнь на марсе? 3. «Мы едем-едем-едем…» «Мы едем-едем-едем…» «Мы едем-едем-едем…» 4. Квартет. Квартет. 5. Какой следующий урок? Какой следующий урок? Какой следующий урок?

7 «Кто ходит в гости по утрам…» Винни-Пух решил навестить своих друзей: Пятачка, Кролика и ослика Иа. Ему обязательно было нужно побывать у каждого из своих друзей и вернуться домой. Если он к кому-то не зайдет, то его друг обидится. Но вы же знаете Винни - Пуха: он не любит длительных путешествий. Помогите ему выбрать кратчайший путь, если известно, как расположены домики друзей и на каком расстоянии они находятся друг от друга Ответ:

8 Самый короткий путь Винни-Пуха равен 165

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

10 Земля Меркурий Плутон Венера Уран Нептун Сатурн Юпитер Марс Невозможно

11 «Мы едем-едем-едем …» На рисунке изображены расстояния между пунктами А,B, C, D, E и Е. Двигаться по дорогам можно только в направлении, указанных стрелочками. Водитель едет из пункта А в пункт D. Каково минимальное расстояние, которое он может преодолеть? Ответ: A E F B D C

12 Минимальное расстояние, которое может преодолеть водитель равно 14. (Путь A-F-B-E-D)

13 Квартет «Проказница мартышка, осел, козёл да косолапый мишка затеяли сыграть квартет».мартышка расположилась на против медведя, а слева и справа от нее - осел и козел. «Ударили в смычки, дерут, а толку нет». Тогда осел и козел поменялись местами. «Расселись, начали квартет. Он все – таки на лад нейдет». Таким образом они перепробовали все возможные варианты. Медведь всегда оставался на своем месте. Сколько всего было вариантов расположения незадачливых музыкантов? Ответ:

14 Ответ: 6 вариантов

15 Какой урок? Необходимо составить фрагмент расписания для одного дня с учетом следующих обстоятельств: Учитель истории может дать либо первый, либо второй, либо третий уроки, но только один урок; Учитель истории может дать либо первый, либо второй, либо третий уроки, но только один урок; Учитель литературы может дать один, либо второй, либо третий урок; Учитель литературы может дать один, либо второй, либо третий урок; Математик готов дать либо только первый, либо только второй урок; Математик готов дать либо только первый, либо только второй урок; Преподаватель физкультуры согласен дать только последний урок. Преподаватель физкультуры согласен дать только последний урок. Сколько и каких вариантов расписания, удовлетворяющего всем вышеперечисленным условиям одновременно, может составить завуч школы? Ответ:

16 История Литература Математика 1 урок 2 урок 3 урок История 4 урок Возможны три варианта: 1.История, математика, литература, физкультура. 2.Математика, история, литература, физкультура. 3.Математика, литература, история, физкультура

17 III тур

18 1. Вопрос. Вопрос. 2. Задача. Задача. 3. Вопрос. Вопрос. 4. Задача. Задача. 5. Вопрос. Вопрос.

19 Вопрос Какой цикл называют Эйлеровой линией? Ответ:

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

21 Вопрос Что называется «деревом»? Ответ:

22 Задача В стране Древляндия 101 город, и некоторые из них соединены дорогами. При этом любые два города соединяет ровно один путь. Сколько в этой стране дорог? Ответ:

23 Вопрос Какая вершина в графе называется «висячей»? Ответ:

24 Путь, проложенный по сторонам любого многоугольника, начинающийся и заканчивающийся в одной и той же его вершине, является Эйлеровой линеей

25 Это не возможно т. к. при подсчитывании ребер в этом графе получается не целое число 15*5/2. Следовательно, такого графа не существует, я значит, соединить телефоны требуемым образом невозможно.

26 Деревом называется любой связный граф, не имеющий циклов. Считают «деревом» и всякий граф, состоящий из одной (изолированной) вершины

27 100 дорог. 100 дорог. Граф дорог Древляндии- дерево, у которого есть висячая вершина. Удалим ее вместе с ребром, которое из нее выходит. Оставшийся граф так же является деревом. Проделав эту операцию 100 раз, мы получим граф, состоящий из одной вершины. Граф дорог Древляндии- дерево, у которого есть висячая вершина. Удалим ее вместе с ребром, которое из нее выходит. Оставшийся граф так же является деревом. Проделав эту операцию 100 раз, мы получим граф, состоящий из одной вершины.

28 Вершина дерева, имеющая степень единицу, называется висячей вершиной.

29 Подведем итоги