выделить подграф

@eXXXXXXXXXXX · Регистрация: 24.02.2011

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

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

@iama · 21.11.2011, 21:39

eXXXXXXXXXXX, первое, что пришло в голову - считаем степени всех вершин, и начинаем удалять все вершины, степени которых меньше искомого числа.

@eXXXXXXXXXXX · 21.11.2011, 22:11 **[ТС]**

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

eXXXXXXXXXXX, первое, что пришло в голову - считаем степени всех вершин, и начинаем удалять все вершины, степени которых меньше искомого числа.

т.е. жадный алгоритм, а он точно всегда будет давать правильный алгоритм?

@Хохол · 21.11.2011, 22:31

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

@iama · 22.11.2011, 00:04

Разве можно такой алгоритм назвать жадным?

@Хохол · 22.11.2011, 01:01

Еще как.

@turbanoff · 22.11.2011, 07:47

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

@Хохол · 22.11.2011, 08:05

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

@eXXXXXXXXXXX 32 / 32 / 6 Регистрация: 24.02.2011 Сообщений: 126
		1
	выделить подграф 21.11.2011, 21:30. Показов 3089. Ответов 7 Метки нет (Все метки) задан обычный граф, выделить из него подграф, в котором из любой вершины выходит не меньше k ребер, каким алгоритмом здесь можно воспользоваться? 0

@iama 1360 / 988 / 119 Регистрация: 30.07.2010 Сообщений: 5,297
	21.11.2011, 21:39	2
	eXXXXXXXXXXX, первое, что пришло в голову - считаем степени всех вершин, и начинаем удалять все вершины, степени которых меньше искомого числа. 1

@eXXXXXXXXXXX 32 / 32 / 6 Регистрация: 24.02.2011 Сообщений: 126
	21.11.2011, 22:11 [ТС]	3
	Сообщение от iama eXXXXXXXXXXX, первое, что пришло в голову - считаем степени всех вершин, и начинаем удалять все вершины, степени которых меньше искомого числа. т.е. жадный алгоритм, а он точно всегда будет давать правильный алгоритм? 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	21.11.2011, 22:31	4
	Ну смарите, если в исходном графе есть вершина степени меньше K, ее обязательно надо выкинуть - она нам никогда не подойдет. Рассматриваем получившийся граф - если в нем есть вершина степени меньше K, ее обязательно надо выкинуть - она нам никогда не подойдет. И так далее. Если на некотором этапе таких вершин не нашлось - нужный граф построен. 1

@iama 1360 / 988 / 119 Регистрация: 30.07.2010 Сообщений: 5,297
	22.11.2011, 00:04	5
	Разве можно такой алгоритм назвать жадным? 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	22.11.2011, 01:01	6
	Еще как. 0

@turbanoff 4092 / 3826 / 745 Регистрация: 18.05.2010 Сообщений: 9,331 Записей в блоге: 11
	22.11.2011, 07:47	7
	после отсеивания могут получиться несколько несвязных между собой подграфов (хотят тут вопрос терминологии что считать подграфом). Необходимо еще выделить один из них / найти подграф с макс. кол-вом вершин (исходя из задачи). 0

@Хохол 476 / 444 / 34 Регистрация: 20.11.2009 Сообщений: 1,293
	22.11.2011, 08:05	8
	Подграф - подмножество вершин исходного графа с подмножеством ребер исходного графа, инцидентных выбранным вершинам. Так что ничего плохого в несвязном графе не вижу. Даже если вдруг все-таки захотелось связности - выбрать из имеющихся компонент связности одну с максимальным количеством вершин несложно. 0