Теперь Кью работает в режиме чтения

Мы сохранили весь контент, но добавить что-то новое уже нельзя

Загадка: Есть 2 круга, 2 квадрата, 2 треугольника, нужно соединить их линиями, так что бы ни одна лини не пересекалась с фигурами и с другими линиями, как?

ЗагадкиГрафикаЗадачки
Eric Muradyan
  · 2,2 K
нерегулярный игрок в чгк  · 14 июн 2017

Если я правильно понял, то загадка не имеет решения.
Напоминает граф "домики и колодцы", для которого  еще в 1930 году доказали, что нарисовать его по подобным условиям нельзя (wikipedia.org).  Соответствующего плоского (планарного) графа не существует и тут.

И все аналогично. Обозначим число всех наших объектов вместе взятых (вершин графа)  B, число соединяющих их линий - ребер- Р, а число "кусков"(граней), на которые они делят плоскость (включая бесконечный "кусок" плоскости), Г.
Тогда верна формула Эйлера B-Р+Г=2.
Здесь предполагается, что ребра пересекаются только в вершинах, что нам и требуется.
Будем рассуждать от противного. Предположим, такой граф существует.
Тогда В = 6.
Каждая вершина соединяется с каждой, кроме "одинаковой"(квадрат нельзя соединять с квадратом, но квадрат соединяется со всеми кругами и треугольниками, так?), поэтому для каждой отдельной вершины число ребер, сходящихся в ней, будет 5.
Всего вершин 6, каждому соответствует 5 входящих в него ребер, получаем 30. Но тут - важный момент - каждое ребро мы посчитали дважды (для обеих вершин- концов), поэтому в итоге Р = 30/2 = 15.
Из формулы Эйлера Г = 11.
Однако можно еще заметить, что Г не бывает больше, чем Р/2 = 7,5 (каждому ребру соответствует две грани, которые по нему граничат), поэтому получаем противоречие, и значит это сделать нельзя.
Так что тег "математика" тут тоже бы пригодился..