Есть ли у любых двух остовных деревьев простого графа общие ребра?

24

Я пробовал несколько случаев и обнаружил, что любые два остовных дерева простого графа имеют некоторые общие ребра. Я имею в виду, что до сих пор не нашел контрпример. Но я не мог ни доказать, ни опровергнуть это. Как доказать или опровергнуть эту гипотезу?

Мистер Сигма
источник

Ответы:

46

Нет, рассмотрим полный график :K4

У него есть следующие непересекающиеся остовные деревья: введите описание изображения здесь

Бьёрн Кьос-Хансен
источник
2
Вы можете сделать каждое дерево плоским, выбрав одно в форме а другое в формеВы можете сделать все это плоским, нарисовав ребро от верхней правой вершины до нижней левой вершины в виде кривой, выходящей за пределы квадрата. ZNZ
накопление
@kelalaka Нам не нужен полный график, нет (представьте, что вы делаете то же самое с - если я не пропустил свое предположение, у вас есть несколько неиспользуемых ребер, которые можно удалить, сделав их более неполными (потому что каждая вершина нуждается в 2-4 пересеченных ребрах, связанных с ней, и каждая вершина в имеет 5 доступных ребер, поэтому каждая вершина прикреплена как минимум к одному неиспользуемому ребру)). , вероятно, просто лучший пример - он хорошо известен, его легко визуализировать (сравнительно немного ребер) и он имеет очень простые охватывающие деревья. К 5 К 4K5K5K4
Фонд Моника иск
14

Для более заинтересованных читателей есть некоторые исследования по разложению графа в непересекающиеся остовные деревья .

Например, в классических работах по проблеме разложения графа на связных факторовn У. Т. Тутте и Edge-дизъюнктных остовных деревьев конечных графов С. St.JA Нэш-Уильямс дает характеристику графов, содержащую попарно ребро-дизъюнкт охватывающие деревья.k

Например, в статье Бициклические разложения полных графов на остовные деревья Далибор Фрончек показывает, как разложить полные графы на изоморфные остовные деревья.K4k+22k+1

Например, в статье « Факторизация полных графов в остовные деревья со всеми возможными максимальными степенями » Петра Коваржа и Михаэля Кубеса показано, как разложить на остовные деревья с заданной максимальной степенью.K2n

Вы можете искать больше. Например, поиск Google для разложения графа на связующие деревья .

Apass.Jack
источник
9

РЕДАКТИРОВАТЬ: Это неверно, как указано в комментариях. Как говорится в другом ответе, связующее дерево для может быть выполнено без совместного использования ребер.K4

Нет, это не правда, что любые два остовных дерева графа имеют общие ребра.

Рассмотрим колесный график:

введите описание изображения здесь

Вы можете создать остовное дерево с ребрами «внутри» цикла, а другое - из внешнего цикла.

Gokul
источник
3
но внешняя петля не достигает центрального узла
amI
Вы правы, я удалю этот ответ, так как другого достаточно.
Гокул
10
Вы можете изменить это, взяв цикл выхода минус некоторый «аккорд» плюс некоторый «радиус» и его дополнение.
Boboquack
Да. На самом деле я видел только так. @boboquack
Мистер Сигма.
3

Knn4
введите описание изображения здесь

2

Knn4n42

2

  1. 22
  2. Есть ли какой-либо граф, кроме колеса или колеса, поскольку его подграф имеет остовные деревья с несвязными краями?
Мистер Сигма
источник
На эти и другие вопросы были даны ответы в цитируемых мной работах. Если вы заинтересованы, вы можете посмотреть.
Apass.Jack
Спасибо @ Apass.Jack Я видел твой ответ. Посмотрим на это.
Мистер Сигма.
1

K2k

G1={(v2i,v2i+1),(v2i,v2i+2),,(v2k2,v2k1)},

G2={(v2i+1,v2i+2),(v2i,v2i),(v2(k1),v2(k1))}

0i<k

nn+1

Acccumulation
источник
0

Если у графа есть мост (т. Е. Ребро, удаление которого отключает граф), то это ребро должно принадлежать каждому остовному дереву. Интуитивно понятно, что мост является единственным ребром, соединяющим две его конечные точки, и поэтому обязательно принадлежит каждому связанному подграфу.

С другой стороны, если ребро графа принадлежит циклу, то существует остовное дерево, не содержащее этого ребра.

Таким образом, если каждое ребро графа принадлежит циклу, то ни одно ребро не является общим для всех остовных деревьев (т. Е. Пересечение множеств ребер остовных деревьев является пустым множеством).

mo2019
источник