Математическое моделирование

№45. Матрицы смежности и инцидентности
Ответ.
Матрицы смежности и инцидентности используются в теории графов для непосредственного задания графа. Матрицы смежности подразделяются на матрицы смежности вершин и матрицы смежности дуг.
Матрица смежности вершин – это квадратная матрица А, каждый ij-ый элемент которой численно равен количеству дуг, идущих из вершины E_i в вершину E_j. В случае неориентированного графа матрица смежности вершин будет принимать симметрический вид, так как (E_i,E_j ) и (E_j,E_i ) существуют одновременно.
Вообще говоря, любая симметрическая матрица смежности с целыми неотрицательными элементами может быть интерпретирована как граф.
Матрица смежности дуг графа – это квадратная матрица А, каждый ij-ый элемент который равен 1, если конечная вершина дуги e_i является начальной вершиной дуги e_j (то есть если ребра имеют общую вершину), и нулю во всех остальных случаях...

№ 232. На заданной сети указаны пропускные способности ребер. Предполагается, что пропускные способности в обоих направлениях одинаковы. Необходимо:
– сформировать поток максимальной мощности, направленный из истока в сток;
– выписать ребра, образующие на сети разрез минимальной пропускной способности...