2014 dxdy logo

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

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




 
 Мощность подграфа
Сообщение01.05.2014, 23:27 
Есть связный граф $G$ в котором степень каждой вершины не больше $n$.
В нем есть непустой подграф $H$ такой что для любого $h \in H$ среди
соседей $h$ не менее $c\cdot n$ элементов из $H$, где $c$ положительная константа.
Как можно оценить мощность $H$ через мощность $G$?
Правда, что их отношение может стремиться к нулю?

 
 
 
 Re: Мощность подграфа
Сообщение01.05.2014, 23:31 
Аватара пользователя
rkrkrk в сообщении #857867 писал(а):
для любого $h \in H$ среди
соседей $h$ не менее $c\cdot h$ элементов из $H$

Так что же такое $h$ - элемент или число?

 
 
 
 Re: Мощность подграфа
Сообщение01.05.2014, 23:51 
Исправил: $h$ - элемент.

 
 
 
 Re: Мощность подграфа
Сообщение01.05.2014, 23:59 
Аватара пользователя
Условие только для элементов $H$ требует, чтобы у них было сколько-то соседей из $H$. Обеспечьте это условие, а потом добавьте к $H$ «периферию» из стольких элементов не-$H$, сколько захотите.

 
 
 
 Re: Мощность подграфа
Сообщение02.05.2014, 00:05 
блин, точно))
Спасибо!

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


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