Цикл в изоморфных графов

@PDA · Регистрация: 21.12.2013

Author24 — интернет-сервис помощи студентам

Доказать,что если два графа изоморфны , то в них имеется одинаковое количество циклов одной и той же длины..

Помагите пожалуйста доказать это задание.

@Mysterious Light · 19.01.2014, 20:59

Пусть G и H — графы и f — изоморфизм между ними. Любые две вершины u и v смежны в G тогда и только тогда, когда f(u) и f(v) смежны в H.

Пусть есть некоторый цикл длины n в G. Тогда образ этого цикла относительно f будет тоже циклом в H.
Если в G есть ровно N циклов длины n, то циклов длины n в H будет не меньше N прото потому, что образы всех цилов из G являются циклами той же длины в H.

Далее говорим, что f обратимо и f^-1 является тоже изоморфизмом, из H в G.
Тогда циклов длины n в G будет не меньше, чем циклов длины n в H.

Сопоставляя эти суждения, получаем, что число циклов длины n в G и H совпадает.

Байт · 20.01.2014, 17:52

Сообщение от PDA

если два графа изоморфны

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

@PDA 2 / 2 / 1 Регистрация: 21.12.2013 Сообщений: 72
		1
	Цикл в изоморфных графов 19.01.2014, 19:40. Показов 852. Ответов 2 Метки нет (Все метки) Доказать,что если два графа изоморфны , то в них имеется одинаковое количество циклов одной и той же длины.. Помагите пожалуйста доказать это задание. 0

@Mysterious Light $Эксперт по математике/физике$ 4300 / 2091 / 431 Регистрация: 19.07.2009 Сообщений: 3,162 Записей в блоге: 24
	19.01.2014, 20:59	2
	Пусть G и H — графы и f — изоморфизм между ними. Любые две вершины u и v смежны в G тогда и только тогда, когда f(u) и f(v) смежны в H. Пусть есть некоторый цикл длины n в G. Тогда образ этого цикла относительно f будет тоже циклом в H. Если в G есть ровно N циклов длины n, то циклов длины n в H будет не меньше N прото потому, что образы всех цилов из G являются циклами той же длины в H. Далее говорим, что f обратимо и f^-1 является тоже изоморфизмом, из H в G. Тогда циклов длины n в G будет не меньше, чем циклов длины n в H. Сопоставляя эти суждения, получаем, что число циклов длины n в G и H совпадает. 2

Байт Диссидент 27706 / 17322 / 3812 Регистрация: 24.12.2010 Сообщений: 38,979
	20.01.2014, 17:52	3
	Сообщение от PDA если два графа изоморфны то очевидно, что у них совпадают все характеристики. Хотя... Если графы нарисовать на листе бумаги, то утверждения типа "левая нижняя вершина имеет степень 3" может быть для одного графа верным, а для другого нет. В связи с этим встает вопрос. Какие утверждения о графах инвариантны по отношению к изоморфизму? 0