2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 связные помеченные графы
Сообщение09.04.2010, 12:22 
Аватара пользователя
Пусть $B_{n,k}$ - количество связных помеченных графов с $n$ вершинами и $k$ ребрами.
Существуют ли какие-нибудь утверждения о монотонности по $n$ и $k$ для этих чисел?
Всегда ли, например, $B_{n+1,k}<B_{n,k-1}$ или что-то подобное?

 
 
 
 Re: связные пмеченные графы
Сообщение12.04.2010, 23:19 
Аватара пользователя
Неравенство все же Вы имели в виду в другую сторону, так?

Ну как бы каждому помеченному графу на $n\ge 2$ вершинах с $k-1$ ребрами отвечают как минимум $n$ помеченных на $n+1$ вершине с $k$ ребрами -- тот, где $n+1$-я вершина соединена с 1, тот, где $n+1$-я вершина соединена с 2... Так?
То есть даже так, что ли: $B_{n+1,k}\ge n B_{n,k-1}$.

 
 
 
 Re: связные пмеченные графы
Сообщение13.04.2010, 20:56 
Аватара пользователя
Хорхе в сообщении #308884 писал(а):
Неравенство все же Вы имели в виду в другую сторону, так?

Ну как бы каждому помеченному графу на $n\ge 2$ вершинах с $k-1$ ребрами отвечают как минимум $n$ помеченных на $n+1$ вершине с $k$ ребрами -- тот, где $n+1$-я вершина соединена с 1, тот, где $n+1$-я вершина соединена с 2... Так?
То есть даже так, что ли: $B_{n+1,k}\ge n B_{n,k-1}$.


ну да, вроде так... что же меня смутило тогда? :))) вроде полученные графы каждый раз разные, и два разных $n$-вершинных графа порождают разные $n+1$-вершинные.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group