СПРОСИ ПРОФИ
👍
−1
👎 -14

Теория графов, план этажа

Для следующего плана этажа в здании был задан вопрос: можно ли войти через дверь А и выйти через дверь Б, пройдя ровно один раз (!) через каждую (!) дверь на этом этаже в направлении ее открытия?


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

Может кто помочь разобраться с этой задачей?

👍
0
👎 0

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

👍
0
👎 0
  #3   17 фев 2022 17:02   Ответить
👍
0
👎 0

Так?

  #4   17 фев 2022 17:02   Ответить
👍
0
👎 0

Этого недостаточно, направление тоже важно

Задайте свой вопрос по высшей математике
профессионалам

Сейчас онлайн 75 репетиторов по высшей математике
Получите ответ профи быстро и бесплатно

Другие вопросы на эту тему:

👍
+2
👎 23

Задача про граф   3 ответа

В графе 100 черных вершин, 50 белых и есть еще зеленые. Каждая зеленая вершина смежна ровно с одной черно-белой парой, то есть ровно с одной черной вершиной и ровно с одной белой. Никакие три зеленые вершины не смежны с одной и той же черно-белой парой. Какое наибольшее количество зеленых вершин может быть в этом графе?

Я вроде придумала максимизирующую конструкцию, но не получается доказать ее максимальность...
  28 фев 2017 14:56  
👍
0
👎 03

Теория Графов   3 ответа

В классе у каждого ученика есть 1 враг и 1 друг.На уроке враги дерутся,а друзья болтают
Доказать что:
-в классе чётное количество учеников
-класс можно разделить на 2 группы,в которых все будут вести себя спокойно
Прошу подсказку,спасибо!
ASK.PROFI.RU © 2020-2023