2014 dxdy logo

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

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




 
 Задача по теории графов (глубинный остов, построенный обходо
Сообщение21.06.2009, 00:27 
Помогите пожалуйста решить следующую задачу по дискретной математике:
Пусть $D=(V,T)$ - это глубинный остов, построенный алгоритмом обхода "в глубину" для неориентированного графа $G=(V,E)$. Докажите что для каждого обратного ребра $(U,V)\in E\T$ либо $U$ является предком $V$ в $D$, либо $V$ является предком $U$ в $D$.

 
 
 
 Re: Помогите доказать
Сообщение21.06.2009, 01:26 
Это следует из правила проведения обхода в глубину.
Если предположить противное, то существует вершина $V$, что она соединена ребром с родителем $P$ и ребром с некоторым своим другим предком $U$, который является также и предком $P$, причём оба эти ребра лежат в дереве обхода. Вопрос: как могло получиться, что в вершину $V$ в ходе алгоритма мы попали из $P$, если есть ребро $(U,V)$?

 
 
 [ Сообщений: 2 ] 


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