Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия, Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки
Степень каждой вершины графа равна 22. Никакие три вершины не образуют цикл. Для любых двух не смежных вершин А и В существуют ровно шесть вершин, смежных как с А, так и с В. Сколько вершин у графа?
Я пытался двумя способами подсчитать число рёбер. С одной стороны, оно равно числу вершин, умноженному на 11. Не получается выразить число рёбер через число вершин вторым способом.
Skeptic
Re: Число вершин графа
10.11.2015, 16:28
Начните с малых степеней вершин. Например, подсчитайте сколько нужно вершин степени 1, 2, 3 и т.д. для удовлетворения условий задачи.
Ambivalent
Re: Число вершин графа
11.11.2015, 11:22
Начать со степеней 1, 2, 3 не получится, так как степени любых двух не смежных вершин не менее 6.
Я построил граф, у которого степень каждой вершины равна 6 (а не 22) и который удовлетворяет остальным условиям задачи, но его созерцание пока не приближает меня к нужному рассуждению.
whitefox
Re: Число вершин графа
11.11.2015, 12:32
Последний раз редактировалось whitefox 11.11.2015, 12:34, всего редактировалось 2 раз(а).
Ambivalent Будет ли ваш граф регулярным? И если да, то чему равен его параметр и будет ли он (граф) сильно регулярным? И если ответ на последний вопрос тоже "да", то чему равны его парметры