Вычисление общего количества связующих деревьев, содержащих определенный набор краев
Я попробовал следующий подход:
Сначала я действительно ограничиваю сокращение для всех краев в данном наборе краев для формирования измененного графика.
Затем я вычисляю общее количество связующих деревьев, с помощью матричной древовидной теоремы, от измененного графика.
Я хочу знать, корректен ли этот метод и если существуют некоторые другие лучшие методы.
2 ответа
Пусть G - граф, пусть e - ребро, и пусть G/e - тот же граф с сокращенным e. Тогда,
Предложение: Существует биекция между прямыми деревьями G, содержащими e, и прямыми деревьями G/e.
Это утверждение несложно доказать; вам лучше понять доказательство самому, а не спрашивать других людей, верно ли оно. Очевидно, что если у вас есть остовное дерево T из G, которое содержит e, то T/e является остовным деревом G/e. Нужно подумать о том, что можно идти и в обратном направлении.
И, как отмечает Адам, нужно быть осторожным, чтобы правильно обрабатывать графы с параллельными ребрами и графы с ребрами от вершины к самой себе.
Я не знаю, правильно это или нет, но вы должны быть осторожны с тем, что сужение ребра может привести к параллельным ребрам. Вы должны убедиться, что деревья, отличающиеся только тем, какое параллельное ребро используется, считаются различными.