Разбить граф на два полных

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

0

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

Кто-то гарантирует, что такое разбиение существует?

0

Сообщение от Shamil1 Кто-то гарантирует, что такое разбиение существует?

Пардон, задание не до конца озвучил.

... либо вывести сообщение о том, что такое разбиение невозможно.

0

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

0

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

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

0

Была похожая задача в контексте Яндекса, там в графе с n вершинами нужно было проверить можно ли его разбить на два полных подграф без общих вершин, используя при этом все вершины начального. Я написал что-то такое. Создаём два множества, ищем две точки у которых нет ребра, то есть они в разных подграфах и пушим в эти два множества(это будущие полные подграфы). Затем для каждой точки графа смотрим можем ли мы ее докинуть в какое-то множество, то есть нам надо проверить содержится ли одно множетсво в множестве инцедентных вершин этой точки(тип для полного графа все дела тыр пыр). Если точку можно докинуть в два графа одновременно, то закинем ее в какую-то очередь например, пока мы не рассмотрим все простые точки вот. Ок, все точки рассмлтрены, выфигачиваем точку из очереди и если она все ещё добавляема в два графа то кидаем ее в эти два графа, когда появляется точка которая протеворечит данной точке (которая лежит в двух множествах) то мы просто выпиливаем протеворечивую точки из множества, в которую мы не можем запихнуть текущую точку и спокойно ее туда пихаем. Собственно вроде все. А ну да, если протеворечивая точка не содержится в двух множествах одновременно, то все, гг.
Это все что я смог придумать на контексте, я закодил, но поймал TL на 5 тесте. Я конечно реализовывал коряво, а времени не оставалось, просто я хз как по другому(если мой вариант конечно правильный)
Могу кинуть код потом

0