Двач, всем известна хохма на ОП-пике сверху. Невозможно, мол, провести сплошную линию через все ребра фигуры, не пересекая их более одного раза. Аргументируется это математически тем, что для этой фигуры не существует эйлерова пути по теореме:В графе G = (V, E) существует эйлеров путь тогда и только тогда, когда:1. Количество вершин с нечетной степенью меньше или равно двум.2. Все компоненты связности кроме, может быть одной, не содержат ребер.Но линия, которую мы ведем не обязана по условию быть путем, то есть идти по ребрам. Она может "перепрыгивать" при необходимости. Соответственно теорема неприменима к этой задаче.В качестве примера привожу более простой граф на ОП-пике снизус четырьмя вершинами нечетной степени (4>2, Эйлеров путь отсутствует), который преспокойно пересекается сплошной линией.Если я прав, то реквестирую у математиков ПРИМЕНИМЫЙ способ проверки решаемости задачи.
>>129661468 (OP)Можно представить, что каждый из прямоугольников (плюс внешняя область) - это вершина. Каждая граница - ребро. На картинке снизу у вершин, полученных из прямоугольников, степень 4. На картинке сверху у трех больших прямоугольников степень 5.
>>129662025На картинке сверху при твоем представлении у двух боковых прямоугольников степень не три, а два; у центрального нижнег - степень четыре, у двух верхних - степень три.Да и в целом твой вариант - в лучшем случае гипотеза, согласись.
>>129662419>у двух боковых прямоугольников степень не триНа самом деле - 5. Они имеют общую границу, 2 границы снизу, и две границы с внешней вершиной. Ну, это мультиграф получился, что не мешает решению.>у центрального нижнег - степень четыре5 по тому же принципу. Он соединен единичным ребром с внешней областью.
>>129662801Я, кажется, не совсем понимаю твоего способа представления... Можешь нарисовать эти два графа преобразованными по твоей системе?
А еще линия не обязана по условия находиться в одной плоскости. В таком случае решаемость задачи стопроцентная.
>>129663222>условию
>>129661468 (OP)
>>129663203
>>129663415И куда же ведут "ребра", направленные куда-то в пространство?
>>129663315>Я знаю, в чем суть задачи, но буду придираться к словам и требовать точных исходных данных.
>>129663602На оснавание чего такое преобразование графа можно считать допустиммым - можешь обосновать?
>>129663620В пространство вне фигуры. Просто судя по примеру ОПа нужно пересекать и ребра на границе фигуры, следовательно нужно выходить за пределы фигуры и это самое пространство вне тоже нужно считать.
>>129664022Не понимаю, о чем ты. Есть граф 1, и есть мультиграф 2. Для каждого пути на картинке 1 можно изобразить путь по ребрам мультиграфа 2.Как может получится недопустимое преобразование? Множество вершин ного графа заданы, мульти-отношение на них - тоже.
В /sci объяснил человек, вам тоже спасибо, ребята.ОП
>>129664767Для проверки: пикрелейтед можно пересечь?
>>129661468 (OP)Чувак, просто взять рандомные хуйни с пикчи и сказать, что это вот вершины и рёбра -- это то, что сделал ты, и что не имеет никакого смысла и отношения к этой задаче. Реально задача состоит в том, чтобы найти некоторый путь. Что называем путём? Без потери точности, путь в этой задаче -- последовательность различных перегородок между областями, такая, что любые две соседние принадлежат одной и той же области.Такая формулировка уже позволяет пересказать задачу в смысле графов, сделав области вершинами, перегородки между ними -- рёбрами. Тогда эйлеровы пути в таком графе действительно соответствуют путям, которые требует задача.
>невозможноКто сказал?
>>129668162Верхнюю и правую нижнюю пропустил.
>>129661468 (OP)В условии про непересечение линии самой с собой ничего не говорилось.
>>129661468 (OP)невозможно мой зад
>>129669257Центр-лево пропустил.
>>129669092Верхние два раза пересек.
>>129669618Каждый раз проигрываю с даунов.
>>129661468 (OP)>Но линия, которую мы ведем не обязана по условию быть путем, то есть идти по ребрам. Она может "перепрыгивать" при необходимости. что, правда?в какое многообразие у тебя вложен граф?что такое "перепрыгивать"какой задачи нужен способ проверки и что такое применимый?
>>129661468 (OP)Это было легко
>>129670871Только за этим сюда и зашел
>>129671256Это что ещё за хуйня? Слева сверху ты не то дважды зашёл, не то ни разу.
