Я сталкивался с этим вопросом: предположим, что дан простой и неориентированный граф G, и пусть t (G) будет числом его остовных деревьев. Если H - граф, полученный из G путем замены каждого ребра в G на путь длины 2, то как мы можем найти число остовных деревьев в H, обозначенное как t (H)?
Для любого графа Gостовное дерево является подграфом G, который содержит все вершины G и является деревом. Есть несколько способов найти число связующих деревьев данного графа, например теорема о матричном дереве Кирхиффа (https://en.wikipedia.org/wiki/Kirchhoff%27s_theorem).). В этом вопросе я думаю, что для любого остовного дерева в G должно быть некоторое число остовныхдеревья для H, но я не могу найти ответ. Подобная проблема была бы, если бы мы заменили каждое ребро парой параллельных ребер, тогда ясно, что если G имеет порядок n, то t (G) .2 ^ (n-1) связующие деревья для H, потому что у любого остовного дерева есть n-1 ребер, и для каждого ребра есть две возможности. Но в этом вопросе каждое ребро заменяется путем длины 2, что означает, что число вершин H равно m +n, где n - число вершин в G, а m - количество ребер в G. Таким образом, структура H отличается от G.