Выберите рисунок на котором изображено дерево к данному графу

Обновлено: 18.09.2024

Рассмотри знаки, изображённые на рисунках. Как ты думаешь, что объединяет все эти знаки?

Какое правило отражает каждый из этих знаков? Напиши эти правила.

Пояснение . Правильный ответ должен содержать следующие элементы:

1) ответ на вопрос: все эти знаки можно встретить на улице ИЛИ это знаки дорожного движения; (Ответ на вопрос может быть дан в иной, близкой по смыслу формулировке.)

1 – Здесь следует переходить дорогу по пешеходному переходу.

2 – Осторожно! Здесь дорогу могут перебегать дети.

3 – Здесь расположена велодорожка.

(Правила могут быть приведены в иных, близких по смыслу формулировках. В качестве верного ответа могут быть приняты не только строгая формулировка правила, но и любое объяснение, свидетельствующее о том, что обучающийся понимает соответствующее правило)

Верно сформулированы три правила2

Верно сформулированы только два любых правила1

Верно сформулировано только одно любое правило.
ИЛИ Не сформулировано верно ни одного правила 0

На фотографиях изображены предметы, с которыми работают представители одной из профессий.

Что это за профессия? Какую работу выполняют люди этой профессии? Чем работа людей этой профессии полезна обществу?

Пояснение . На фотографиях изображены предметы, с которыми работают представители одной из профессий. Очевидно, что

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

Если профессия в явном виде не определена / определена неправильно и по критерию К1 выставлен 0 баллов, то по всем остальным позициям оценивания выставляется 0 баллов

Источник: Демонстрационная версия ВПР по окружающему миру 4 класс 2018 год., Демонстрационная версия ВПР по окружающему миру 4 класс 2019–2022., Демонстрационная версия ВПР по окружающему миру 4 класс 2021−2022 года.

Внимательно изучи по таблице прогноз погоды на трое суток.

Прочитай утверждения о погоде, которая ожидается в указанные сутки. Выбери верные утверждения, запиши их номера в специально отведённую строку.

1) Самая высокая влажность воздуха ожидается в четверг утром.

2) Самое прохладное утро будет в четверг.

3) Во вторник утром без зонта не обойтись.

4) Северо-западный ветер будет преобладать во все указанные дни недели.

Пояснение . Для выбора правильного ответа анализируем каждое предложение.

1) Самая высокая влажность воздуха ожидается в четверг утром.

Вывод: предложение верное.

2) Самое прохладное утро будет в четверг.

Вывод: предложение верное.

3) Во вторник утром без зонта не обойтись.

Вывод: предложение неверное.

4) Северо-западный ветер будет преобладать во все указанные дни недели.

Вывод: предложение неверное.

Рассмотри карту мира. На ней буквами А и Б отмечены два материка.

Запиши название каждого материка в отведённое для этого поле.

Название материка А

Название материка Б

Пояснение . Ответ: А — Южная Америка, Б — Африка.

Источник: Статград: Всероссийская проверочная работа по окружающему миру 4 класс 2016 год. Вариант 24.

Рассмотри карту мира. На ней буквами А и Б отмечены два материка.

Запиши название каждого материка в отведённое для этого поле.

Название материка А

Название материка Б

Пояснение . Ответ: А — Южная Америка, Б — Австралия.

Источник: Статград: Всероссийская проверочная работа по окружающему миру 4 класс 2016 год. Вариант 26.

Рассмотри карту мира. На ней буквами А и Б отмечены два материка.

Запиши название каждого материка в отведённое для этого поле.

Название материка А

Название материка Б

Пояснение . Посмотрим внимательно на карту и определим, какие материки обозначены на ней: А — Южная Америка, Б — Евразия.

Ответ: А — Южная Америка, Б — Евразия.

Источник: Статград: Всероссийская проверочная работа по окружающему миру 4 класс 2016 год. Вариант 27.

Если правильно подобрать к началу каждой фразы из первого столбца продолжение фразы из второго столбца, то получится правило, помогающее человеку сохранить здоровье и жизнь. Составь два правила из приведённых частей фраз: для этого к каждой позиции первого столбца подбери соответствующую позицию из второго столбца.

А) При поездке в транспорте общего пользования разрешается

Б) При поездке в транспорте общего пользования не разрешается

1) пользоваться острыми предметами.

2) пользоваться мобильным телефоном.

3) пользоваться мобильным телефоном во время остановки.

Запишите в ответ цифры, расположив их в порядке, соответствующем буквам:

Пояснение . Для успешного выполнения данного задания нужно попробовать соединять начало и конец фразы А с 1 и 2 и с 3; затем Б с 1 и 2 и с 3; найти верно сформулированные правила.

А) При поездке в транспорте общего пользования разрешается —2) пользоваться мобильным телефоном.

Б) При поездке в транспорте общего пользования не разрешается — 1) пользоваться острыми предметами.

Артём проводил наблюдения за появлением плесени на плодах вишни, которые он собрал на своей даче. Чтобы выяснить, как влияет предварительная обработка ягод на скорость появления плесени, он взял два десятка свежесобранных плодов вишни, половину из которых аккуратно помыл и высушил. В одно блюдце Артём положил немытые плоды, а в другое — предварительно обработанные, то есть вымытые и высушенные. Оба блюдца он поместил в шкаф и стал наблюдать. Через некоторое время Артём обнаружил, что сначала плесень появилась на немытых плодах и лишь спустя ещё некоторое время – на предварительно обработанных.

Сравни условия нахождения плодов в двух разных блюдцах в описанном эксперименте. Подчеркни в каждой строке одно из выделенных слов.

Плоды в блюдцах: одинаковые / различные

Подготовка плодов перед хранением: одинаковая / различная

Плоды

Подготовка

Пояснение . Сравним условия нахождения плодов в двух разных блюдцах в описанном эксперименте.

Плоды в блюдцах: одинаковые.

Подготовка плодов перед хранением: различная.

Ответ: плоды — одинаковые, подготовка — различная.

Источник: Статград: Всероссийская проверочная работа по окружающему миру 4 класс 2016 год. Вариант 37.

Ученики 4-го класса хотели выяснить, все ли вещества растворимы в воде. Ребята взяли две стеклянные колбы, в одну колбу насыпали столовую ложку сахарного песка, а в другую — столовую ложку песка с берега моря. В обе колбы они налили одинаковое количество холодной воды из-под крана, а затем взболтали содержимое колб.

Если бы ученики захотели выяснить, влияет ли температура воды на растворимость морского песка, с помощью какого эксперимента они могли бы это сделать? Опиши этот эксперимент.

Пояснение . В две одинаковые колбы насыпать одинаковое количество морского песка. В одну колбу налить холодную воду, а в другую — горячую. Взболтать содержимое. Наблюдать, растворяется ли вещество в колбах или нет. Сравнить результаты.

Внимание! Все тесты в этом разделе разработаны пользователями сайта для собственного использования. Администрация сайта не проверяет возможные ошибки, которые могут встретиться в тестах.

Список вопросов теста

Вопрос 1

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж и К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Вопрос 2

Выберите один из 4 вариантов ответа:

графическое изображение, которое отображает зависимость одной величины от другой, динамику какого-либо процесса в течение какого-либо периода.
графическое отображение состава и структуры сложной системы.
графическое изображение, которое даёт наглядное представление о соотношении каких-либо величин или нескольких значений одной величины, об изменении их значений.
условное графическое изображение предмета с точным соотношением его размеров, получаемое методом моделирования.

Вопрос 3

Для более наглядного представления информации в графических моделях могут быть использованы.

Выберите несколько из 5 вариантов ответа:

символы.
графические изображения.
числа.
муззыка.
текст

Вопрос 4

Выберите один из 4 вариантов ответа:

графическое изображение, которое отображает зависимость одной величины от другой, динамику какого-либо процесса в течение какого-либо периода.
графическое изображение, которое даёт наглядное представление о соотношении каких-либо величин или нескольких значений одной величины, об изменении их значений.
графическое отображение состава и структуры сложной системы.
условное графическое изображение предмета с точным соотношением его размеров, получаемое методом моделирования.

Вопрос 5

Выберите один из 4 вариантов ответа:

условное графическое изображение предмета с точным соотношением его размеров, получаемое методом моделирования.
графическое изображение, которое отображает зависимость одной величины от другой, динамику какого-либо процесса в течение какого-либо периода.
графическое отображение состава и структуры сложной системы.
графическое изображение, которое даёт наглядное представление о соотношении каких-либо величин или нескольких значений одной величины, об изменении их значений.

Вопрос 6

Выберите один из 4 вариантов ответа:

совокупность объектов со связями между ними.
граф с циклом.
граф, в котором нет циклов, то есть в нём нельзя из некоторой вершины пройти по различным рёбрам и вернуться в ту же вершину.
информационная модель, имеющая вид графа, вершинам которого соответствуют определённые объекты, а рёбра задают отношения между ними.

Вопрос 7

Дайте определение понятию "Граф".

Выберите один из 3 вариантов ответа:

Граф – это условное графическое изображение предмета с точными соотношениями его размеров, получаемое методом моделирования.
Граф – это совокупность объектов со связями между ними.
Граф – это графическое отображение состава и структуры сложной системы.

Вопрос 8

Взвешенный граф – это.

Выберите один из 4 вариантов ответа:

граф, в котором нет циклов.
путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза.
граф, в котором вершины или рёбра характеризуются некоторой дополнительной информацией.
граф с циклом.

Вопрос 9

Какой тип графа изображён на рисунке?

Изображение:

Выберите один из 4 вариантов ответа:

Цепь.
Взвешенный граф.
Семантическая сеть.
Цикл.

Вопрос 10

Семантическая сеть – это.

Выберите один из 4 вариантов ответа:

цепь, в которой начальная и конечная вершины совпадают.
совокупность объектов со связями между ними.
граф с циклом.
информационная модель, имеющая вид графа, вершинам которого соответствуют определённые объекты, а рёбра задают отношения между ними.

Вопрос 11

Выберите один из 4 вариантов ответа:

путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза.
граф, в котором вершины или рёбра характеризуются некоторой дополнительной информацией.
граф, в котором нет циклов
граф с циклом.

Вопрос 12

Какой тип графа изображён на рисунке, если при рисовании данного графа нельзя отрывать ручку от бумаги?

Изображение:

Выберите один из 4 вариантов ответа:

Цепь.
Взвешенный граф.
Семантическая сеть.
Цикл.

Вопрос 13

Выберите один из 4 вариантов ответа:

граф с циклом.
цепь, в которой начальная и конечная вершины совпадают.
граф, в котором вершины или рёбра характеризуются некоторой дополнительной информацией.
информационная модель, имеющая вид графа, вершинам которого соответствуют определённые объекты, а рёбра задают отношения между ними.

Вопрос 14

Выберите один из 4 вариантов ответа:

граф, в котором вершины или рёбра характеризуются некоторой дополнительной информацией.
цепь, в которой начальная и конечная вершины совпадают.
информационная модель, имеющая вид графа, вершинам которого соответствуют определённые объекты, а рёбра задают отношения между ними.
путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза.

Вопрос 15

Вопрос 16

Вопрос 17

Вопрос 18

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Вопрос 19

На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, К. На рисунке изображена схема соединений, связывающих пункты А, В, С, D, Е, F, G, Н. По каждому соединению можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт Н?

Вопрос 20

На рисунке изображена схема соединений, связывающих пункты А, В, С, D, Е, F, G, Н. По каждому соединению можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из пункта А в пункт Н?

Вопрос 21

На рисунке — схема дорог, связывающих города A, B, C, D, E, F, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город G?

Вопрос 22

На рисунке изображена схема дорог, связывающих города A, B, C, D, E, F, G. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город D?

Тест по информатике Информационные модели на графах для 6 класса с ответами. Тест включает в себя 2 варианта, в каждом варианте 10 заданий с выбором ответа.

1 вариант

1. Как называется форма информационной модели, которая представляет структуру и состав системы объектов?

1) граф
2) карта
3) план
4) все утверждения верны

2. Какую форму имеет граф?

1) круги, соединённые линиями
2) прямоугольники, соединённые стрелками
3) оба утверждения верны

3. Что обозначают вершины графа?

1) объекты системы
2) связи между объектами
3) процессы в системе
4) все утверждения не верны

4. Чем отличается дуга от ребра графа?

1) дуга и ребро — это одно и то же
2) дуга — направленная линия, ребро — ненаправленная линия
3) ребро — направленная линия, дуга — ненаправленная линия
4) все утверждения не верны

5. Какой граф называется неориентированным?

1) если его вершины не соединены линиями
2) если его вершины соединены дугами
3) если его вершины соединены рёбрами
4) все утверждения не верны

1) Аня-Вера-Галя
2) Аня-Вера-Галя-Аня
3) Даша-Галя-Аня-Галя-Вера
4) все утверждения верны

7. Как называется граф, если его вершины или рёбра дополнены информацией, такой как расстояние или код объекта?

1) взвешенным
2) ориентированным
3) сетью
4) семантической сетью

8. В каком отношении находятся элементы иерархической системы?

1) входят в состав
2) являются разновидностью
3) оба утверждения верны

9. Где у графа-дерева расположен корень?

1) наверху
2) внизу
3) возможны оба варианта

10. Что такое семантическая сеть?

1) граф, в котором вершинам дано подробное название
2) граф, в котором дугам дано описание действий
3) граф, в котором есть дуги, петли и циклы
4) все утверждения верны

2 вариант

1. Какая информационная модель представляет структуру и состав системы объектов?

1) схема
2) граф
3) карта
4) план

2. Как формируется граф?

1) объекты обозначаются кругами или прямоугольниками
2) отношения объектов обозначаются линиями или стрелками
3) выполняются оба утверждения

3. Что называют вершинами графа?

1) процессы в системе
2) объекты системы
3) связи между объектами
4) все утверждения верны

4. Как будут соединены объекты, если отношения симметричны?

1) дугой
2) ребром
3) оба утверждения верны

5. Какой граф называется ориентированным?

1) Аня-Вера-Галя
2) Аня-Вера-Галя-Аня
3) Аня-Вера-Галя-Даша
4) все утверждения не верны

7. Какой граф называется сетью?

1) взвешенный
2) ориентированный
3) в котором есть цепи
4) в котором есть циклы

1) иерархическая
2) подчинённая
3) сеть
4) все утверждения не верны

9. Какой вид графа отображает родственные связи между членами семьи?

1) сеть
2) дерево
3) взвешенный граф

10. Можно ли с помощью графа описать рассказ (событие)?

1) да, с помощью любого графа
2) да, с помощью семантической сети
3) нет, граф для этого не предназначен
4) все утверждения не верны

Понятие графа целесообразно вводить после того, как разобрано несколько задач, подобных задаче 1, решающее соображение в которых – графическое представление. Важно, чтобы ученики сразу осознали, что один и тот же граф может быть нарисован разными способами. Строгое определение графа, на мой взгляд, давать не нужно, т.к. оно слишком громоздко и это только затруднит обсуждение. На первых порах хватит и интуитивного понятия. При обсуждении понятия изоморфизма можно решить несколько упражнений на определение изоморфных и неизоморфных графов. Одно из центральных мест темы – теорема о четности числа нечетных вершин. Важно, чтобы ученики до конца разобрались в ее доказательстве и научились применять к решению задач. При разборе нескольких задач рекомендую не ссылаться на теорему, а фактически повторять ее доказательство. Чрезвычайно важно также понятие связности графа. Содержательным соображением здесь является рассмотрение компоненты связности, на это необходимо обратить особое внимание. Эйлеровы графы – тема почти игровая.

Первая и главная цель, которую нужно преследовать при изучении графов, –научить школьников видеть граф в условии задачи и грамотно переводить условие на язык теории графов. Не стоят рассказывать обе всем на нескольких занятиях подряд. Лучше разнести занятия по времени на 2–3 учебных года. (Прилагается разработка занятия “Понятие графа. Применение графов к решению задач” в 6 классе).

2. Теоретический материал к теме “Графы”.

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

Рассмотрим две задачи.

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

Теперь сразу видно, что долететь с Земли до Марса нельзя.

Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки.

Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу ?

Решение: Занумеруем последовательно клетки доски:

А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен:

Мы рассмотрели две непохожие задачи. Однако решения этих двух задач объединяет общая идея – графическое представление решения. При этом и картинки, нарисованные для каждой задачи, оказались похожими: каждая картинка – это несколько точек, некоторые из которых соединены линиями.

Такие картинки и называются графами. Точки при этом называются вершинами, а линии – ребрами графа. Заметим, что не каждая картинка такого вида будет называться графом. Например. если вас попросят нарисовать в тетради пятиугольник, то такой рисунок графом не будет. Будем называть что рисунок такого вида, как в предыдущих задачах, графом, если есть какая-то конкретная задача для которой такой рисунок построен.

Другое замечание касается вида графа. Попробуйте проверить, что граф для одной и той же задачи можно нарисовать разными способами; и наоборот для разных задач можно нарисовать одинаковые по виду графы. Здесь важно лишь то, какие вершины соединены друг с другом, а какие – нет. Например, граф для задачи 1 можно нарисовать по-другому:

Такие одинаковые, но по-разному нарисованные графы, называются изоморфными.

Степени вершин и подсчет числа ребер графа

Запишем еще одно определение: Степенью вершины графа называется количество выходящих из нее ребер. В связи с этим, вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной.

С понятием степени вершины связана одна из основных теорем теории графов –теорема о честности числа нечетных вершин. Докажем ее мы немного позднее, а сначала для иллюстрации рассмотрим задачу.

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

Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным . Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.

Ответ. Соединить телефоны таким образом невозможно.

Теорема: Любой граф содержит четное число нечетных вершин.

Доказательство: Количество ребер графа равно половине суммы степеней его вершин. Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной. А это возможно только в том случае, если граф содержит четное число нечетных вершин.

Связность графа

Есть еще одно важное понятие, относящееся к графам – понятие связности.

Граф называется связным, если из любые две его вершины можно соединить путем, т.е. непрерывной последовательностью ребер. Существует целый ряд задач, решение которых основано на понятии связности графа.

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

Доказательство: Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:

Теперь явно видно, что мы получили не менее различных 16 городов, что противоречит условию задачи. Значит утверждение доказано от противного.

Если принять во внимание предыдущее определение, то утверждение задачи можно переформулировать и по-другому: “Доказать, что граф дорог страны Семерка связен.”

Теперь вы знаете, как выглядит связный граф. Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф. Пример несвязного графа вы видите на рисунке:

Каждый такой отдельный кусок называется компонентой связности графа. Каждая компонента связности представляет собой связный граф и для нее выполняются все утверждения, которые мы доказали для связных графов. Рассмотрим пример задачи, в которой используется компонента связности:

Задача 5. В Тридевятом царстве только один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов, – по 20. Докажите, что из столицы можно долететь в город Дальний.

Доказательство: Понятно, что если нарисовать граф ковролиний Царства, то он может быть несвязным. Рассмотрим компоненту связности, которая включает в себя столицу Царства. Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний – по 20, поэтому, чтобы выполнялся закон о четном числе нечетных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности. А так как компонента связности – связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать.

Вы наверняка сталкивались с задачами, в которых требуется нарисовать какую-либо фигуру не отрывая карандаш от бумаги и проводя каждую линию только один раз. Оказывается, что такая задача не всегда разрешима, т.е. существуют фигуры, которые указанным способом нарисовать нельзя. Вопрос разрешимости таких задач также входит в теорию графов. Впервые его исследовал в 1736 году великий немецкий математик Леонард Эйлер, решая задачу о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами.

Задача 6. Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз ?

Решение. Если мы будем рисовать граф так, как сказано в условии, то в каждую вершину, кроме начальной и конечной, мы войдем столько же раз, сколько выйдем из нее. То есть все вершины графа, кроме двух должны быть четными. В нашем же графе имеется три нечетные вершины, поэтому его нельзя нарисовать указанным в условии способом.

Сейчас мы доказали теорему об Эйлеровых графах:

Теорема: Эйлеров граф должен иметь не более двух нечетных вершин.

И в заключение – задача о Кенигсбергских мостах.

Задача 7. На рисунке изображена схема мостов города Кенигсберга.

Можно ли совершить прогулку так, чтобы пройти по каждому мосту ровно 1 раз?

3. Задачи к теме “Графы”

Понятие графа.

1. На квадратной доске 3x3 расставлены 4 коня так, как показано на рис.1. Можно ли сделав несколько ходов конями, переставить их в положение, показанное на рис.2?

Решение. Занумеруем клетки доски, как показано на рисунке:

Каждой клетке поставим в соответствие точку на плоскости и, если из одной клетки можно попасть в другую ходом шахматного коня, то соответствующие точки соединим линией. Исходная и требуемая расстановки коней показаны на рисунках:

При любой последовательности ходов конями порядок их следования, очевидно, измениться не может. Поэтому переставить коней требуемым образом невозможно.

2. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9 ?

Решение. Поставив в соответствие каждому городу точку и соединив точки линией, если сумма цифр делится на 3, получим граф, в котором цифры 3, 5, 9 связаны между собой, но не связаны с остальными. Значит долететь из города 1 в город 9 нельзя.

Степени вершин и подсчет числа ребер.

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

Решение. Подсчитаем общее количество выходящих городов дорог – 100 . 4 = 400. Однако при таком подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 200.

4. В классе 30 человек. Может ли быть так, что 9 человек имеют по 3 друга, 11 – по 4 друга, а 10 – по 5 друзей ?

Ответ. Нет (теорема о четности числа нечетных вершин).

5. У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей ?

Ответ. Нет, не может.

6. Может ли в государстве, в котором из каждого города выходит ровно 3 дороги, быть ровно 100 дорог?

Решение. Подсчитаем число городов. Число дорог равно числу городов х, умноженному на 3 (число выходящих из каждого города дорог) и разделенному на 2 (см. задачу 3). Тогда 100 = Зх/2 => Зх=200, чего не может быть при натуральном х. Значит 100 дорог в таком государстве быть не может.

7. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.

Доказательство непосредственно следует из теоремы о четности числа нечетных вершин графа.

Связность.

8. В стране из каждого города выходит 100 дорог и из каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь из любого города можно добраться до любого другого.

Доказательство. Рассмотрим компоненту связности, в которую входит один из городов, дорогу между которыми закрыли. По теореме о четности числа нечетных вершин в нее входит и второй город. А значит по-прежнему можно найти маршрут и добраться из одного из этих городов в другой.

Графы Эйлера.

9. Имеется группа островов, соединенных мостами так, что от каждого острова можно добраться до любого другого. Турист обошел все острова, пройдя по каждому мосту розно 1 раз. На острове Троекратном он побывал трижды. Сколько мостов ведет с Троекратного, если турист

а) не с него начал и не на нем закончил?
б) с него начал, но не на нем закончил?
в) с него начал и на нем закончил?

10. На рисунке изображен парк, разделенный на несколько частей заборами. Можно ли прогуляться по парку и его окрестностям так, чтобы перелезть через каждый забор розно 1 раз?

Читайте также: