В графе на 100 вершинах, каждая из которых имеет степень 3, есть ровно 600 путей длины 3. Сколько в этом графе циклов длины 3?

задан 15 Окт '19 20:56

@Man: здесь под путями понимаются простые пути? То есть не замкнутые, а циклы считаются отдельно?

Желательно использовать более точную терминологию. Взять хотя бы понятие цикла. Это циклический подграф, или его контур? Скажем, если у нас есть граф C3 (треугольник), то это один цикл, или шесть? (По числу способов его "прочитать".)

(15 Окт '19 21:08) falcao

@falcao Да, под путями понимаются незамкнутые пути. С3 это один цикл(Один способ прочитать).

(15 Окт '19 21:37) Man
10|600 символов нужно символов осталось
0

Будем рассматривать все приведённые пути длины 3 в стандартном смысле этого слова, включая замкнутые. Приведённый путь не должен иметь вхождений вида ee^{-1}, то есть не должен проходить по тому же ребру туда-сюда друг за другом.

Такие пути имеют вид e1e2e3. Сначала выбираем среднее ребро e2. Оно определяется началом и концом. Начало -- любая вершина; способов выбрать 100. Конец -- любая из трёх соседних вершин. Итого 300 способов выбрать e2. Пусть оно идёт из вершины u в вершину v. Ребро e1 теперь выбирается 2 способами: оно идёт в u из любой соседней вершины, не считая v. Аналогично, 2 способа для e3. Итого 1200 способов выбора пути из трёх рёбер.

Если из них 600 простых, согласно условию, то остальные 600 -- это замкнутые приведённые пути. Поэтому циклов в смысле циклических подграфов С3 будет 100, так как любой такой подграф можно "прочитать" в виде замкнутого пути 6 способами.

Для примера: граф из условия может быть дизъюнктным объединением 25 тетраэдров (полных графов K4).

ссылка

отвечен 16 Окт '19 0:56

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×624
×40

задан
15 Окт '19 20:56

показан
2843 раза

обновлен
16 Окт '19 0:56

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru