2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Счастливые Графы
Сообщение06.04.2018, 15:22 
Аватара пользователя


01/06/12
905
Adelaide, Australia
waxtep в сообщении #1301738 писал(а):
Но ведь можно поместить единицы в "центральную" вершину и одну из трех других, а в оставшиеся две - нули (?)

Это верно.

-- 06.04.2018, 21:13 --

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

-- 06.04.2018, 21:23 --

Теперь допустим в минимальном не счастливом графе цикл из трех вершин (треугольник). Мы можем добавить одну или две вершины (до 5 вершин). Если новые вершины не соединены тогда граф можно осчастливить поставив 2 в треугольник и 0 в добавочные вершины, если они соединены тогда 2 в треугольник и 1 в добавочные вершины. Если же в минимальном не счастливом графе цикл из четырех вершин (и нет треугольника) тогда можно записать 2 в этот цикл и 0 в добавочную вершину. Если цикл из 5 вершин то везде ставим 2. Вроде других вариантов нет? В таком случае можно уверено сказать что минимальный не счастливый граф имеет 6 вершин.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 16 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group