"Записки научных семинаров ПОМИ"
Том 497, стр. 80-99
О реконструкции графов связности 2
Д. В. Карпов
St.Petersburg Department of the Steklov Mathematical Institute;
St.Petersburg State University
dvk0@yandex.ru
- Аннотация:
{\em Колодой} графа $G$ называется набор графов $G-v$ для всех вершин $v$ графа $G$.
Обозначим колоду графа $G$ через ${\mathcal D}(G)$. Мы докажем,
что не более чем два графа связности~2 и минимальной степени хотя бы 3
могут иметь одинаковую колоду. Статья содержит алгоритм восстановления по колоде
${\mathcal D}(G)$ двусвязного графа $G$ минимальной степени хотя бы 3
двух таких графов $G_1,G_2$, что $G\in \{G_1,G_2\}$.
Библ. -- 12 назв.
- Ключевые слова: восстановление графа, двусвязный граф
[graph reconstruction, 2-connected graphs]
Полный текст(.pdf)