Dims писал(а):
Появилось ещё ряд вопросов, в связи с чем переименовал тему.
1)
Из каждого тождественного графа можно получить ещё один тождественный граф, заменив в матрице смежности 0 на 1 и наоборот. Если каждая такая замена будет давать неизоморфный исходному граф, то количество тождественных графов должно быть всегда чётно. Так ли это? Может ли быть, чтобы такой граф (назовём его инвертированным) совпал с исходным (с точностью до изоморфизма)?
2)
Рассмотрев 8 тождественных графов из 6 вершин, я обратил внимание, что один из них (первый) является подграфом всех остальных (и вообще, все можно получить из первого добавлением рёбер).
Вопрос: все ли тождественные графы таковы? Существуют ли тождественные графы с количеством вершин Н, для которых ни один из тождественных графов с количеством вершин М<Н не является подграфом?
Я не очень интересуюсь задачами относительно графов и не специалист. Тем не менее, второй вопрос тривиальный (решается за пару секунд).
В любом тождественном графе имеется некоторый минимальный тождественный подграф похожий на первый. Однако при n>6 минимальные тождественные графы выглядят иначе, точнее имеется один узел имеющий 3 ребра, исходящих из узла и три длины хвостов k<l<m. При этом k+l+m=n-1.
