2014 dxdy logo

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

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




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


01/06/12
1016
Adelaide, Australia
Появилась интересная задачка которую не могу решить. Имеется граф у которого вершины обозначены цифрами. Граф считается счастливым если для каждой его вершины с цифрой n имеется n соседних вершин тоже с числом n; иначе граф считается несчастливым. Например квадрат можно сделать счастливым если обозначить его вершины 2. Сетку 3х3 можно сделать счастливой двумя способами:

Код:
221
221
110


или

Код:
222
202
222



Все графы которые я рассматривал я могу сделать счастливыми. Есть ли вообще несчастливые графы и как они выглядят?

 Профиль  
                  
 
 Re: Счастливые Графы
Сообщение02.04.2018, 01:25 


29/12/15
18
Было бы удивительно, если бы все графы были счастливые. Такой вроде как не счастливый:
Изображение

 Профиль  
                  
 
 Re: Счастливые Графы
Сообщение02.04.2018, 01:32 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Ribin, а доказать?

 Профиль  
                  
 
 Re: Счастливые Графы
Сообщение02.04.2018, 03:44 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Ribin, отличная находка! Вроде не сложно доказать что ваш граф не счастливый. Мы знаем что 2 не может быть, так как нет цикла. Значит все вершины 0 или 1. Начинаем писать цифры с черной вершины. Если она 1, значит соседняя тоже 1, но тогда нельзя заполнить другие две нижние вершины. Если черная вершина 0, значит соседняя 1 и ее сосед тоже 1. Остается два варианта и оба приводят к тупику.

Теперь новые вопросы:

1. Является ли этот граф самым маленьким из не счастливых (по количеству вершин) ?
2. Есть ли не счастливые графы с циклом ?
3. Самый главный вопрос: есть ли общая характеризация всех не счастливых графов ?
4. Сколько разных счастливых окрасок для сетки NxN ?

-- 02.04.2018, 10:09 --

1. Можно взять граф Ribin и убрать две нижние правые вершины. Граф останется не счастливым с 6 вершинами. Есть ли не счастливые графы на 5ти вершинах?

 Профиль  
                  
 
 Re: Счастливые Графы
Сообщение02.04.2018, 12:38 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
dimkadimon в сообщении #1301015 писал(а):
3. Самый главный вопрос: есть ли общая характеризация всех не счастливых графов ?
Гипотеза: кажый несчастливый граф должен иметь хотя бы одну вершину степени 1.

 Профиль  
                  
 
 Re: Счастливые Графы
Сообщение02.04.2018, 16:13 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Aritaborian в сообщении #1301061 писал(а):
Гипотеза: кажый несчастливый граф должен иметь хотя бы одну вершину степени 1.

Кажется нашел контра пример. Возьмем два квадрата и соединим их одним ребром, тогда получится несчастливый граф у которого все вершины имеют степень больше 1. Кстати этот пример решает мой второй вопрос про циклы.

 Профиль  
                  
 
 Re: Счастливые Графы
Сообщение02.04.2018, 16:47 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
Ну, моя гипотеза базировалась исключительно на рукомашестве каких-то интуитивных соображениях :facepalm:
dimkadimon в сообщении #1301135 писал(а):
Кажется нашел контра пример.
Позвольте снова позанудстовать: это ещё доказать надо. Этот пример мне не удалось пометить так, чтоб вышел счастливый, но это лишь значит, что я плохо старался.

(Ещё больше занудства богу занудства)

dimkadimon в сообщении #1301135 писал(а):
контра пример
Контрпример.

 Профиль  
                  
 
 Re: Счастливые Графы
Сообщение02.04.2018, 17:05 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Aritaborian в сообщении #1301158 писал(а):
Позвольте снова позанудстовать: это ещё доказать надо.
Квадраты $ABCD$ и $EFGH$, вершины $A$ и $E$ соединены. Если в $C$ пишем $0$, то в $B$ и $D$ пишем $1$, и в $A$ непонятно что. Если в $C$ пишем $1$, то в $B$ (или в $D$, неважно) пишем $1$, в $D$ пишем $0$, в $A$ непонятно что. Если в $C$ пишем $2$, то в $ABD$ тоже пишем $2$, и получаем всё то же самое с квадратом $EFGH$, только в $E$ написать $2$ уже нельзя.

 Профиль  
                  
 
 Re: Счастливые Графы
Сообщение02.04.2018, 17:09 


21/05/16
4292
Аделаида
mihaild в сообщении #1301167 писал(а):
в $A$ непонятно что
(второе повторение)
В $A$ пишем 1.

 Профиль  
                  
 
 Re: Счастливые Графы
Сообщение02.04.2018, 17:10 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
kotenok gav в сообщении #1301171 писал(а):
В $A$ пишем 1.
Нельзя: в $B$ написано $1$, и в двух соседях ($A$ и $C$) тоже $1$.

 Профиль  
                  
 
 Re: Счастливые Графы
Сообщение02.04.2018, 17:31 
Аватара пользователя


11/06/12
10390
стихия.вздох.мюсли
mihaild, спасибо. Я пытался плясать от вершин (в ваших обозначениях) $A$ и $E$, доказательства не получилось.

 Профиль  
                  
 
 Re: Счастливые Графы
Сообщение03.04.2018, 03:40 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Вот счастливые графы на 4x4:

Код:
1101
0221
1220
1011

0110
1221
1221
0110

2222
2112
2222
0110

2222
2112
2202
0222

2220
2022
2202
0222

2220
2021
2221
0110

 Профиль  
                  
 
 Re: Счастливые Графы
Сообщение04.04.2018, 23:36 


13/05/14
476
dimkadimon
dimkadimon в сообщении #1301015 писал(а):
1. Является ли этот граф самым маленьким из не счастливых (по количеству вершин) ?
2. Есть ли не счастливые графы с циклом ?
3. Самый главный вопрос: есть ли общая характеризация всех не счастливых графов ?

Любое $n$-вершинное $(n \geq 3)$ дерево является несчастливым графом.
Если дерево большое по числу вершин, то после добавления одного или нескольких ребер может получиться несчастливый граф с циклом(циклами).
Самый маленький по числу вершин несчастливый граф --- это 4-х вершинный граф звезда, имеющий одну вершину степени 3 и три вершины степени 1.

 Профиль  
                  
 
 Re: Счастливые Графы
Сообщение05.04.2018, 01:01 
Аватара пользователя


07/01/16
1426
Аязьма
sqribner48 в сообщении #1301714 писал(а):
Самый маленький по числу вершин несчастливый граф --- это 4-х вершинный граф звезда, имеющий одну вершину степени 3 и три вершины степени 1.
Но ведь можно поместить единицы в "центральную" вершину и одну из трех других, а в оставшиеся две - нули (?)

 Профиль  
                  
 
 Re: Счастливые Графы
Сообщение05.04.2018, 01:53 
Заслуженный участник
Аватара пользователя


16/07/14
8355
Цюрих
Давайте и правда пока посмотрим на (корневые) деревья.
Можно использовать только $0$ и $1$ (т.к. по двойкам и большим числам можно найти цикл).
Назовем дерево веселым, если можно в нем расставить числа так, чтобы в корне стоял $0$, и радостным, если его можно раскрасить так, чтобы в корне стояла $1$. Счастливое дерево - либо веселое, либо радостное (либо и то и то).
Назовем дерево псевдорадостным, если все потомки корня веселые.
Вершину в дереве назовем веселой/радостной/псевдорадостной, если начинающееся в ней поддерево веселое/радостное/псевдорадостное.
Дерево веселое тогда и только тогда, когда все потомки корня радостные.
Дерево радостное тогда и только тогда, когда у корня есть псевдорадостный потомок, а все остальные потомки корня - веселые.

Дерево из одной вершине веселое и псевдорадостное.
Дерево из двух вершин радостное и псевдорадостное.
Деревья из трех вершин бывают радостными и веселыми, либо радостными и псевдорадостными.
Не-псевдорадостное деревье из четырех вершин либо радостное, либо радостное и веселое.

Рассмотрим минимальное (по числу вершин) не счастливое дерево.
Раз оно минимальное - то все потомки корня либо веселые, либо радостные. Раз оно не веселое - то у корня есть не радостный потомок. Раз оно не радостное - то у корня либо 1) нет псевдорадостного потомка, либо 2) есть потомок $A$ - псевдорадостный, потомок $B$ - не веселый, и одно из 2.1) есть еще один не веселый потомок $C$ 2.2) $A$ - не веселый 2.3) $B$ - не псевдорадостный.
1) У корня есть не радостный потомок, и нет псевдорадостных. Все не-радостные деревья из не более чем $4$ вершин псевдорадостные, так что у корня есть потомок хотя бы из $5$ вершин и в дереве хотя бы $6$ вершин
2.1) минимальное не-веселое дерево состоит из $2$ вершин, так что у корня есть потомок $A$ и два хотя бы двухэлементных поддерева $B$ и $C$ - так что в дереве не меньше $6$ вершин
2.2) минимальное не-веселое псевдорадостное поддерево состоит из $3$ вершин, так что в $A$ хотя бы $3$ вершины, в $B$ хотя бы $2$ - и во всем дереве хотя бы $6$
2.3) минимальное не-веселое не-псевдорадостное поддерево состоит из $4$ вершин, так что в $B$ хотя бы $4$ вершины, в $A$ хотя бы одна - и во всем дереве хотя бы $6$

Так что все деревья менее чем c $6$ вершинами счастливые.

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

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



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

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


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

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