Билет 30

Теорема (о поиске количества путей заданной длины с помощью матрицы смежности ориентированного графа):

Пусть — матрица смежности ориентированного графа без петель и ,

где . Тогда равно количеству путей длины .

Доказательство:

Утверждение очевидно при . Пусть , и утверждение верно для . Тогда , где

равно количеству путей длины . Следовательно,

равно числу путей длины , так как каждый такой маршрут состоит из путей длины и ребра,

ведущего из предпоследней вершины пути в его последнюю вершину .

Теорема:

Алгоритм поиска в ширину в невзвешенном графе находит длины кратчайших путей до всех достижимых вершин.

Доказательство:

Допустим, что это не так. Выберем из вершин, для которых кратчайшие пути от найдены некорректно, ту, настоящее

расстояние до которой минимально. Пусть это вершина , и она имеет своим предком в дереве обхода в ширину , а предок в

кратчайшем пути до — вершина .

Так как — предок в кратчайшем пути, то , и расстояние до w найдено

верно, . Значит, .

Так как — предок в дереве обхода в ширину, то .

Расстояние до найдено некорректно, поэтому . Подставляя сюда два последних равенства, получаем

, то есть, . Из ранее доказанной леммы следует, что в этом случае вершина

попала в очередь и была обработана раньше, чем . Но она соединена с , значит, не может быть предком в дереве

обхода в ширину, мы пришли к противоречию, следовательно, найденные расстояния до всех вершин являются кратчайшими.