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

@boyar · Регистрация: 13.11.2016

Студворк — интернет-сервис помощи студентам

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

@Shamil1 · 27.03.2018, 10:46

Сообщение от boyar

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

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

@boyar · 27.03.2018, 12:33 **[ТС]**

Сообщение от Shamil1

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

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

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

@salam · 30.03.2018, 11:30

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

@Shamil1 · 30.03.2018, 11:51

Сообщение от salam

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

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

@edwin_paco · 20.05.2018, 11:27

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

Новые блоги и статьи Все статьи Все блоги /
моя боль iceja 24.01.2026 Выложила интерполяцию кубическими сплайнами www. iceja. net REST сервисы временно не работают, только через Web. Написала за 56 рабочих часов этот сайт с нуля. При помощи perplexity. ai PRO , при. . .	Модель сукцессии микоризы anaschu 24.01.2026 Решили писать научную статью с неким РОманом	http://iceja.net/ математические сервисы iceja 20.01.2026 Обновила свой сайт http:/ / iceja. net/ , приделала Fast Fourier Transform экстраполяцию сигналов. Однако предсказывает далеко не каждый сигнал (см ограничения http:/ / iceja. net/ fourier/ docs ). Также. . .	http://iceja.net/ сервер решения полиномов iceja 18.01.2026 Выкатила http:/ / iceja. net/ сервер решения полиномов (находит действительные корни полиномов методом Штурма). На сайте документация по API, но скажу прямо VPS слабенький и 200 000 полиномов. . .
Расчёт переходных процессов в цепи постоянного тока igorrr37 16.01.2026 / * Дана цепь(не выше 3-го порядка) постоянного тока с элементами R, L, C, k(ключ), U, E, J. Программа находит переходные токи и напряжения на элементах схемы классическим методом(1 и 2 з-ны. . .	Восстановить юзерскрипты Greasemonkey из бэкапа браузера damix 15.01.2026 Если восстановить из бэкапа профиль Firefox после переустановки винды, то список юзерскриптов в Greasemonkey будет пустым. Но восстановить их можно так. Для этого понадобится консольная утилита. . .	Сукцессия микоризы: основная теория в виде двух уравнений. anaschu 11.01.2026 https:/ / rutube. ru/ video/ 7a537f578d808e67a3c6fd818a44a5c4/	WordPad для Windows 11 Jel 10.01.2026 WordPad для Windows 11 — это приложение, которое восстанавливает классический текстовый редактор WordPad в операционной системе Windows 11. После того как Microsoft исключила WordPad из. . .

@boyar 0 / 0 / 0 Регистрация: 13.11.2016 Сообщений: 2

	Разбить граф на два полных 26.03.2018, 23:29. Показов 4415. Ответов 5 Метки нет (Все метки) Требуется разбить неориентированный граф на два полных графа, то есть чтобы в результате получилось 2 графа, каждая вершина которого смежна с любой другой вершиной это графа. Ничего не приходит в голову, кроме как прямой перебор в лоб, но нужен алгоритм по-оптимальней. Подскажите, пожалуйста, в каком направлении копать. 0

@salam 194 / 174 / 30 Регистрация: 10.07.2012 Сообщений: 800
	30.03.2018, 11:30
	что-то вы, наверное, еще не досказали. если речь именно о разбиении на две части, каждая из которых - полный подграф, то исходный граф должен представлять собой две компоненты связности, и, соответственно, разбиение однозначно. 0

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