Докажите, что подграф представляет собой остовное дерево

Question

Пусть T и T '- 2 связующих дерева связного графа G. Предположим, что дуга x находится в T, но не в T'. Докажите, что существует дуга у в ' таким образом, что (Т {х}) ∪ {у} и (Т' T - {у}) ∪ {х} являются остовных деревьев в G.

Любой идеи, как я могу это доказать? Существует ли формальный способ доказать, что подграф является связующим деревом?

Answer 1

Да и да.

Вы доказываете подграф является остов, доказав, что:

1. подграф затрагивает все узлы в графе; и
2. Подграф - это дерево.
   • Существует ровно один путь между любыми двумя узлами.

С T и T' оба остовных деревьев, вы знаете, что есть ровно один путь между любыми двумя узлами в T или T' и что оба T и T' прикосновением каждый узел в G.

Если вы удалите arc x от T, вы получите два дерева. Назовем их T0 и T1. Так как T' касается каждого узла, то в T' должен существовать arc y, так что одна конечная точка находится в T0, а другая находится в T1.

Оба arc x и arc y - это дуги, которые соединяют T0 с T1. Поскольку соединение двух деревьев дает дерево, а T0 и T1 охватывают все узлы в G, (T-{x})∪{y} и (T'-{y})∪{x} - это остовные деревья.

Как вы, возможно, заметили, я не вдавался в подробности о фактическом доказательстве и просто дал обзор. Вам нужно будет доказать:

1. Удаление arc x из T производит два дерева, T0 и T1, что доля не узлов и нет дуг;
2. Должно существовать arc y в T', который подключает T0 к T1;
3. Удаление arc y от T' создает два дерева, которые покрывают те же узлы, что и T0 и T1; и
4. Соединение двух деревьев с дугой создает дерево.

плюс некоторые другие мелкие вещи, чтобы приклеить все это вместе в один последовательный ответ, но эти 4 вещи являются основными элементами, которые необходимо показать. Остальные вещи легко понять, как только вы доказали это.

Удачи в том, что я предполагаю, что это часть домашней работы.