2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Теория графов
Сообщение22.08.2011, 18:56 
Есть такая задачка.
Если $G$ -- граф, то пусть $B(G)$ -- его граф блоков (то есть вершины -- блоки, а ребро проводится, если соответствующие блоки имеют общую вершину), а $C(G)$ -- граф точек сочленения (вершины -- точки сочленения, рёбра проводятся, если соответствующие точки сочленения принадлежат одному блоку).
Так вот, если $G$ -- связный граф с хотя бы одной точкой сочленения, то надо доказать, что $B(B(G))$ изоморфен $C(G).$

Можно сначала рассмотреть граф $B(G),$ в котором (это нетрудно доказать) все блоки - клики. Как-то надо показать, что каждый такой блок в $B(G)$ в некотором смысле привязан к точке сочленения исходного графа... но как?

Вообще утверждение довольно понятное, но как-то доказать не получается... Подскажите, на что опираться?

 
 
 [ 1 сообщение ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group