У нас есть граф G. Мы построили его реберный граф L(G). Может ли образ L(G) не быть изоморфным G?

задан 2 Июн 19:35

Что подразумевается под образом рёберного графа? Он сам, конечно, может от G сильно отличаться.

(2 Июн 21:14) falcao

Под образом L(G) я имею в виду граф G, реберный граф которого изомофрмен L(G). Иными словами, могут ли неизоморфные между собой графы иметь одинаковые реберные графы?

(4 Июн 10:09) webeseit

@webeseit: если задана функция f, то f(x) называется образом элемента x. Соответственно, если y=f(x), то x по отношению к y называется прообразом.

Если L(G)==L(H), то G и H могут не быть изоморфны. Пример: треугольник и "трилистник", когда 3 ребра выходят из одной вершины. Но это, по сути, единственное исключение. Это доказывается в теореме Уитни.

(4 Июн 18:57) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×628
×136

задан
2 Июн 19:35

показан
164 раза

обновлен
4 Июн 18:57

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru