2 задачи по дискретной математике

1. Районной администрацией принято
решение о газификации одного из небольших сел района, имеющего 12
жилых домов. Расположение домов
указано на рисунке. Числа в кружках
обозначают условный номер дома.
Узел 13 является газопонижающей
станцией. На рисунке показано также
возможное расположение трубопроводов и длины участков (первое число).
Разработать такой план газификации
села, чтобы общая длина трубопровода была наименьшей.
2.Решите задачу о назначениях, если
задана а) матрица стоимости выполнения работ; б) матрица производительности труда: