Вопрос из теории графов.

[C0rWin]

Могу ли я сказать, что если есть два изоморфных графа и один из них связанный, то второй тоже обязательно связанный? Если да то как это можно доказать и если нет, то хотелось бы знать почему нет.

[Руст]

Что понимаете под изоморфизмом?
Если возможность взаимно однозначного соответствия рёбер и вершин, так чтобы сохранялось принадлежность вершин рёбрам (думаю именно такое определение имеется в виду), то это очевидное следствие изоморфности. Было бы странно, если это не так.

[Brukvalub]

Про изоморфизм графов можно прочесть, например, здесь: http://it.kgsu.ru/TI_11/tgr_002.html .

[Macavity]

C0rWin писал(а):

Могу ли я сказать, что если есть два изоморфных графа и один из них связанный, то второй тоже обязательно связанный? Если да то как это можно доказать и если нет, то хотелось бы знать почему нет.

Можете. Если в исходном графе есть путь между двумя некоторыми вершинами, то в изоморфном графе это путь из вершин-образов исходного пути... (это и есть доказательство, следует из определения изоморфизма).