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
9208
Цюрих
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
9208
Цюрих
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
1612
Аязьма
sqribner48 в сообщении #1301714 писал(а):
Самый маленький по числу вершин несчастливый граф --- это 4-х вершинный граф звезда, имеющий одну вершину степени 3 и три вершины степени 1.
Но ведь можно поместить единицы в "центральную" вершину и одну из трех других, а в оставшиеся две - нули (?)

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


16/07/14
9208
Цюрих
Давайте и правда пока посмотрим на (корневые) деревья.
Можно использовать только $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  След.

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



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

Сейчас этот форум просматривают: YandexBot [bot]


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

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