2014 dxdy logo

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

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




 
 Число вершин графа
Сообщение10.11.2015, 14:28 
Степень каждой вершины графа равна 22. Никакие три вершины не образуют цикл. Для любых двух не смежных вершин А и В существуют ровно шесть вершин, смежных как с А, так и с В. Сколько вершин у графа?

Я пытался двумя способами подсчитать число рёбер. С одной стороны, оно равно числу вершин, умноженному на 11. Не получается выразить число рёбер через число вершин вторым способом.

 
 
 
 Re: Число вершин графа
Сообщение10.11.2015, 16:28 
Начните с малых степеней вершин.
Например, подсчитайте сколько нужно вершин степени 1, 2, 3 и т.д. для удовлетворения условий задачи.

 
 
 
 Re: Число вершин графа
Сообщение11.11.2015, 11:22 
Начать со степеней 1, 2, 3 не получится, так как степени любых двух не смежных вершин не менее 6.

Я построил граф, у которого степень каждой вершины равна 6 (а не 22) и который удовлетворяет остальным условиям задачи, но его созерцание пока не приближает меня к нужному рассуждению.

 
 
 
 Re: Число вершин графа
Сообщение11.11.2015, 12:32 
Аватара пользователя
Ambivalent
Будет ли ваш граф регулярным?
И если да, то чему равен его параметр $k$ и будет ли он (граф) сильно регулярным?
И если ответ на последний вопрос тоже "да", то чему равны его парметры $\lambda,\mu?$

 
 
 
 Re: Число вершин графа
Сообщение11.11.2015, 14:20 
whitefox
Огромное спасибо, всё понятно.

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


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