Доказать, что в каждом связном графе есть остовное дерево

[KappaGolden]

Доказать, что в каждом связном графе есть остовное дерево.

Я решал так: пусть множество всех ациклических связных графов с операцией включения - ч.у.м. Назовем его X. Тогда, по лемме Цорна у X есть максимальный элемент, т.к. у любой цепи есть максимальный элемент (например, объединение всех цепей). Также можно доказать, что этот элемент будет действительно максимальным, т.к если добавить еще одно ребро, то граф станет либо циклическим, либо получим противоречие с максимальностью.

Подскажите, где ошибка в рассуждениях.

[Lia]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Карантин»
по следующим причинам:


- отсутствуют собственные содержательные попытки решения задач(и). Например, можно почитать учебник.

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.

[Lia]

Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»

[Someone]

KappaGolden в сообщении #1444763 писал(а):

Тогда, по лемме Цорна

Вы рассматриваете графы с бесконечным множеством вершин? Если множество вершин конечно, то лемма Цорна не при делах, и остовное дерево строится с помощью простого правила.

[KappaGolden]

Я понимаю, как построить остовное дерево для конечного графа, но мне как раз и нужно доказать и для бесконечного тоже.

[svv]

KappaGolden в сообщении #1444763 писал(а):

у любой цепи есть максимальный элемент (например, объединение всех цепей)

Имелось в виду объединение всех элементов этой цепи как графов.

-- Сб мар 14, 2020 13:57:20 --

Ищу, где бы придраться.

Рассмотрим квадрат $ABCD$ как циклический граф.
Возьмём два его подграфа. Один состоит из ребра $AB$, а второй из рёбер $AB$ и $BC$. Множество из этих двух подграфов является цепью и имеет максимальный элемент (второй подграф). Но мы можем добавить к последнему ещё одно ребро, и он не станет циклическим.
Стало быть, не все цепи надо рассматривать.

[Someone]

KappaGolden в сообщении #1444803 писал(а):

мне как раз и нужно доказать и для бесконечного

Понятно. Кстати, обратите внимание на замечание svv по поводу терминологии, оно существенно.
План доказательства может быть следующим.
1) Рассматриваем множество всех поддеревьев данного графа. Оно частично упорядочено отношением включения.
2) В этом множестве рассматриваем всевозможные цепи, то есть, линейно упорядоченные подмножества (не путать с путями в графе). Доказываем, что каждая цепь имеет верхнюю грань, в качестве каковой можно взять объединение всех поддеревьев, принадлежащих цепи. Фактически требуемое доказательство состоит в доказательстве того, что это объединение является поддеревом, то есть, оно связно и не содержит циклов. При этом не ссылаясь на "очевидность".
3) Сославшись на лемму Цорна, делаем вывод, что существует максимальная цепь, то есть, такая, которая не содержится ни в какой другой цепи.
4) Доказываем, что объединение всех элементов максимальной цепи есть остовное поддерево. Что оно поддерево, было доказано во втором пункте, а здесь надо доказать, что оно содержит все вершины. Например, методом "от противного".

Детали, естественно, за Вами.

[KappaGolden]

Так, попытаюсь доказать.

Рассмотрим связный граф. Рассмотрим множество всех поддеревьев этого графа. Вполне упорядочим его отношением включения. Рассмотрим все возможные цепи, и каждой есть верхняя грань ( например, объединяя все поддеревья цепи). Оно будет являться поддеревом, т.к. выполняется связность, потому что содержит в себе самое большое поддерево, которое будет связно, т.к является поддеревом связного графа. А ацикличность будет выполнена аналогично. По лемме Цорна существует максимальный элемент во множестве всех поддеревьев нашего графа. Допустим он не содержит все вершины, тогда проведем в эти вершины ребра, но тогда получим противоречие с максимальностью нашего элемента.

Вот, получилось примерно так, где я мог ошибиться?

[Someone]

KappaGolden в сообщении #1444858 писал(а):

Вот, получилось примерно так, где я мог ошибиться?

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