Кодирование графов для тех, кому нечего делать

[arseniiv]

Здесь нет единственного ответа, но вам может доставить удовольствие найти любой или в некотором смысле минимальный.

Придумайте способ кодирования $c$ ориентированных графов с вершинами, помеченными натуральными числами, с помощью неориентированных графов без пометки вершин. Этот способ должен быть таким, что:
(1) Коды разных графов разные, то есть $c$ инъективная (ну, это очевидно из слова «кодирование»).
(2) Есть некоторое число $s$, что для любых графов $G_1, G_2$, если они отличаются одним ребром, степень отличия графов $c(G_1), c(G_2)$ ограничена $s$. (Степень отличия двух графов можно определить как наименьшее число удалений и добавлений вершин и рёбер в них, делающих оба графа изоморфными.)
(3) Аналогично, есть некоторое число $s$, что если мы получили из графа $G_1$ граф $G_2$ добавлением изолированной вершины с меткой $n$, степень отличия $c(G_1), c(G_2)$ меньше $ns$.
(4) Есть некоторая функция $c^*$ оттуда же и туда же, что и $c$, что в $c(G_1)$ столько же подграфов, изоморфных $c^*(G_2)$, сколько в $G_1$ подграфов, изоморфных $G_2$. То есть кодирование достаточно аккуратное.

А ещё можно подумать о допущении петель, более чем одного ребра между каждой парой вершин (мультиграфы), пометке рёбер (подкорректировать условие 2 под 3) и т. д.. Наоборот, можно начать с кодирования графов без помеченных вершин (новое — только ориентация рёбер). Можно позариться на кодирование гиперграфов (опять же подкорректировать условие 2, учитывая кратность гиперребра).

[kotenok gav]

arseniiv в сообщении #1417205 писал(а):

без пометки вершин

Т.е. с точностью до их перестановки?

[arseniiv]

Да, перестановка любого множества непомеченных вершин даёт тот же граф. Это заставит нас кодировать разные пометки с помощью каких-то неизоморфных подграфов; неориентированность рёбер заставит кодировать ориентированные тоже какими-то более сложными чем одно ребро штуками.

[mihaild]

Заводим в $G_2$ несколько вспомогательных вершин:
-$d$ для задания направления
-$x$, $y$ и $t_1, \ldots, t_n$ для задания пометок
Соединим $x$ со всеми $t_i$ (чтобы не перепутать их с остальными вершинами), соединим $t_i$ цепью $t_1, t_2, \ldots, t_n$, соединим $t_1$ с $y$ для выделения начала

Для каждой вершины $v_i$ в $G_1$ заведем в $G_2$ вершину $v'_i$, для ребра $e_j$ - пару вершин $e'_j, e''_j$. Если было ребро $e_j: v_i \to v_j$, то соединим вершины $v'_i, e'_j$, $e'_j, e''_j$ и $e''_j, v_j$. Соединим $e'_j$ и $d$ для задания направления.
Соединим $v'_i$ с $t_i$ для задания нумерации.

Вроде бы этого достаточно. При добавлении ребра достаточно добавить две вершины и три ребра, при добавлении вершины - две вершины и три ребра. Автоморфизмы $G_1$ и $G_2$ соответствуют друг другу взаимно однозначно.

Граф растет в несколько раз. Самое сложное - аккуратно пометить $d$, $x$ и $y$, чтобы не спутать их с остальными. Можно например так: в нашем построенном графе нет листов, сосед которых имеет степень $2$ (если размер графа хотя бы $2$; для графа из одной вершины придумаем что-то отдельно). Соответственно можно подвесить к $d$ цепочку длины $2$, к $x$ - длины $3$ и к $y$ - длины $4$, это их однозначно задаст.

[arseniiv]

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

Самое сложное - аккуратно пометить $d$, $x$ и $y$, чтобы не спутать их с остальными.

Да, как раз читая на полпути решил спросить, будут ли они защищены. Интересная конструкция, такого типа мне искать в голову не приходило.

Я предполагал найти несколько графов $A, B, C, D$, не являющихся подграфами друг друга, и потом соединять $A$ с произвольным количеством $B$ для помеченной вершины, $C$ с $D$ как начало и конец ребра, и соединять их между собой каким-то аккуратным способом и надеяться, что можно подобрать $A, B, C, D$ и способы соединения, чтобы всё прошло.

Ещё мне наверно стоило задать условия более однородным и близким к тому, откуда родилась задача, образом: пусть есть правила переписывания графов $G\to G'$, задаваемые двумя графами, в которых каждая вершина дополнительно помечена именем, и применение правила заменяет произвольный изоморфный $G$ подграф на $G'$ так, что вершины $G$ с именами, которые не встречаются в $G'$, удаляются, вершины с именами, имеющимися и там, и там, остаются связанными с остальной частью графа так как были, а рёбра, соединяющие их между собой меняются на те, которые между ними есть в $G'$, и вершины с именами, уникальными для $G'$, добавляются. Тогда условие на кодирование простое: надо чтобы любое правило $R$ для помеченных орграфов можно было транслировать в правило $R'$ для их кодов, чтобы выполнялось $R'(c(G)) = \{ c(G') \mid G'\in R(G) \}$, где $R(G)$ — множество всех возможных результатов применения $R$ к $G$.