Счастливые Графы

[dimkadimon]

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

221
221
110

или

222
202
222

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

[Ribin]

Было бы удивительно, если бы все графы были счастливые. Такой вроде как не счастливый:

[Aritaborian]

Ribin, а доказать?

[dimkadimon]

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

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

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

-- 02.04.2018, 10:09 --

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

[Aritaborian]

dimkadimon в сообщении #1301015 писал(а):

3. Самый главный вопрос: есть ли общая характеризация всех не счастливых графов ?

Гипотеза: кажый несчастливый граф должен иметь хотя бы одну вершину степени 1.

[dimkadimon]

Aritaborian в сообщении #1301061 писал(а):

Гипотеза: кажый несчастливый граф должен иметь хотя бы одну вершину степени 1.

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

[Aritaborian]

Ну, моя гипотеза базировалась исключительно на рукомашестве каких-то интуитивных соображениях

dimkadimon в сообщении #1301135 писал(а):

Кажется нашел контра пример.

Позвольте снова позанудстовать: это ещё доказать надо. Этот пример мне не удалось пометить так, чтоб вышел счастливый, но это лишь значит, что я плохо старался.

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

dimkadimon в сообщении #1301135 писал(а):

контра пример

Контрпример.

[mihaild]

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$ уже нельзя.

[kotenok gav]

mihaild в сообщении #1301167 писал(а):

в $A$ непонятно что

(второе повторение)
В $A$ пишем 1.

[mihaild]

kotenok gav в сообщении #1301171 писал(а):

В $A$ пишем 1.

Нельзя: в $B$ написано $1$, и в двух соседях ($A$ и $C$) тоже $1$.

[Aritaborian]

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

[dimkadimon]

Вот счастливые графы на 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

[sqribner48]

dimkadimon

dimkadimon в сообщении #1301015 писал(а):

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

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

[waxtep]

sqribner48 в сообщении #1301714 писал(а):

Самый маленький по числу вершин несчастливый граф --- это 4-х вершинный граф звезда, имеющий одну вершину степени 3 и три вершины степени 1.

Но ведь можно поместить единицы в "центральную" вершину и одну из трех других, а в оставшиеся две - нули (?)

[mihaild]

Давайте и правда пока посмотрим на (корневые) деревья.
Можно использовать только $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$ вершинами счастливые.