|
У нас есть граф G. Мы построили его реберный граф L(G). Может ли образ L(G) не быть изоморфным G? задан 2 Июн 19:35 
webeseit |
Здравствуйте
Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.
Присоединяйтесь!
отмечен:
задан
2 Июн 19:35
показан
164 раза
обновлен
4 Июн 18:57
Связанные вопросы
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Что подразумевается под образом рёберного графа? Он сам, конечно, может от G сильно отличаться.
Под образом L(G) я имею в виду граф G, реберный граф которого изомофрмен L(G). Иными словами, могут ли неизоморфные между собой графы иметь одинаковые реберные графы?
@webeseit: если задана функция f, то f(x) называется образом элемента x. Соответственно, если y=f(x), то x по отношению к y называется прообразом.
Если L(G)==L(H), то G и H могут не быть изоморфны. Пример: треугольник и "трилистник", когда 3 ребра выходят из одной вершины. Но это, по сути, единственное исключение. Это доказывается в теореме Уитни.