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

@tikhonvova · Регистрация: 20.11.2012

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

Вершина степени 0 называется изолиррванной.определить число графов с n вершинами,в которых данные k вершин являются изолированными.помогите!

Добавлено через 1 час 7 минут
ну Help!

Байт · 27.12.2012, 09:10

2^x, где x = C²_n-k

Байт · 28.12.2012, 18:19

Отвечаю мистеру Х на его "Почему", посланному мне в личку. (Вот видите, мистер Х, как это неудобно, мой ответ повисает в воздухе, только мы с вами с вами знаем о чем идет речь, а вся остальная просвещенная публика пребывает в недоумении).
Я взял ровно ту постановку, задачи, которую предложил ТС. k вершин - изолированы. О других - ничего не сказано. Они могут быть быть как изолированы, так и нет. Нет слов "ровно k вершин изолировано". Поэтому у меня остается любой граф на n-k вершинах (отмеченных, заметьте!). И вот - мое предложение, это и есть стандартная формула перечисления графов.
Есть замечания? Возражения? Трактовки? - в студию!

@Mysterious Light · 29.12.2012, 02:32

Деанонимизирую себя )

n(n-1)/2 — число всевозможно-допустимых ребер на графе с n вершинами.
$https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{C_n^2}$ — количество всевозможных графов с n вершинами. Среди этих графов также есть и полностью несвязный, когда нет ни одного ребра, и имеющий изолированные точки.

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

ТС не требовал, чтобы в графе было ровно k изолированных вершин, допускается и большее количество, что означает правильность Вашей формулы. Спасибо за её пояснение. Действительно, всё очевидно, а я задал глупый вопрос.

Не по теме:

Поскольку ни ТС, ни все остальные не отписались с возражениями, всех интересующих вполне устраивает Ваш ответ.
Значит, мои возгласы «я жестко туплю и не понимаю, откуда эта формула взялась и почему она работает» являются в общей теме неуместными.
Значит, мой вопрос «почему» касается только меня и, может быть, ещё того, кто знает ответ.
Значит, ЛС — тут без вариантов. Заметьте, я не настаивал на ответе.
А так приходится себя полнейшим нубом выставлять привселюдно

Байт · 29.12.2012, 12:12

Mysterious Light, Вполне понимаю и даже разделяю ваше легкое недоумение. Постановка задачи - сырая. Ее можно понимать в разных смыслах. Я взял простейший, с расчетом на то, что ТС уточнит постановку, и тогда будет над чем подумать. Но видимо, ТС потерял к этой задаче интерес. То ли сдал зачет-экзамен, то ли наоборот - не сдал. Хотя в других постановках задача любопытна и не проста, как и многие задачи из ТГ. Если изолировано ровно k, она сводится к перечислению отмеченных графов без изолированных вершин. К сожалению все свои книжки по теории графов я свез на дачу, и до весны не имею возможности их пролистать.

@tikhonvova 0 / 0 / 0 Регистрация: 20.11.2012 Сообщений: 23
		1
	определить число графов 26.12.2012, 10:11. Показов 8461. Ответов 4 Метки нет (Все метки) Вершина степени 0 называется изолиррванной.определить число графов с n вершинами,в которых данные k вершин являются изолированными.помогите! Добавлено через 1 час 7 минут ну Help! 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	27.12.2012, 09:10	2
	2^x, где x = C²_n-k 0

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	28.12.2012, 18:19	3
	Отвечаю мистеру Х на его "Почему", посланному мне в личку. (Вот видите, мистер Х, как это неудобно, мой ответ повисает в воздухе, только мы с вами с вами знаем о чем идет речь, а вся остальная просвещенная публика пребывает в недоумении). Я взял ровно ту постановку, задачи, которую предложил ТС. k вершин - изолированы. О других - ничего не сказано. Они могут быть быть как изолированы, так и нет. Нет слов "ровно k вершин изолировано". Поэтому у меня остается любой граф на n-k вершинах (отмеченных, заметьте!). И вот - мое предложение, это и есть стандартная формула перечисления графов. Есть замечания? Возражения? Трактовки? - в студию! 0

@Mysterious Light $Эксперт по математике/физике$ 4300 / 2091 / 431 Регистрация: 19.07.2009 Сообщений: 3,163 Записей в блоге: 24
	29.12.2012, 02:32	4
	Деанонимизирую себя ) n(n-1)/2 — число всевозможно-допустимых ребер на графе с n вершинами. $https://www.cyberforum.ru/cgi-bin/latex.cgi?2^{C_n^2}$ — количество всевозможных графов с n вершинами. Среди этих графов также есть и полностью несвязный, когда нет ни одного ребра, и имеющий изолированные точки. Вы полагаете, что k вершин изолированы, выкидываете их, рассматриваете число всевозможных графов, которые остались, получаете Вашу формулу. Но среди этих графов есть и те, которые содержат хотя бы одну изолированную точку. Тогда суммарно будет больше k изолированных точек. ТС не требовал, чтобы в графе было ровно k изолированных вершин, допускается и большее количество, что означает правильность Вашей формулы. Спасибо за её пояснение. Действительно, всё очевидно, а я задал глупый вопрос. Не по теме: Поскольку ни ТС, ни все остальные не отписались с возражениями, всех интересующих вполне устраивает Ваш ответ. Значит, мои возгласы «я жестко туплю и не понимаю, откуда эта формула взялась и почему она работает» являются в общей теме неуместными. Значит, мой вопрос «почему» касается только меня и, может быть, ещё того, кто знает ответ. Значит, ЛС — тут без вариантов. Заметьте, я не настаивал на ответе. А так приходится себя полнейшим нубом выставлять привселюдно 2

Байт Диссидент 27709 / 17325 / 3811 Регистрация: 24.12.2010 Сообщений: 38,979
	29.12.2012, 12:12	5
	Mysterious Light, Вполне понимаю и даже разделяю ваше легкое недоумение. Постановка задачи - сырая. Ее можно понимать в разных смыслах. Я взял простейший, с расчетом на то, что ТС уточнит постановку, и тогда будет над чем подумать. Но видимо, ТС потерял к этой задаче интерес. То ли сдал зачет-экзамен, то ли наоборот - не сдал. Хотя в других постановках задача любопытна и не проста, как и многие задачи из ТГ. Если изолировано ровно k, она сводится к перечислению отмеченных графов без изолированных вершин. К сожалению все свои книжки по теории графов я свез на дачу, и до весны не имею возможности их пролистать. 0