Здравствуйте, помогите доказать, что если у графа есть 2 различных остовных деревьев, обязательно найдется 3е/4 отличное от 2х предыдущих

задан 8 Фев 21:51

Желательно записать условие по-русски, то есть словами.

(8 Фев 22:37) falcao

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

(8 Фев 22:42) Иван123421

@Иван123421: в таком виде понятно, но что значило 3e/4?

(8 Фев 22:54) falcao

Имелось ввиду, можно ли найти еще 3е(-еще одно), 4(-еще 2 отличных), но сейчас нарисовал пример, где абсолютно не факт что если у графа есть 3 оставных дерева различных, то существует еще одно отличное

(8 Фев 22:57) Иван123421

А вот как доказать что если у графа есть 2 различных остовных дерева, то граф будет иметь еще одно отличное от двух предыдущих, примеры рисую - всё сходится, но формально доказать не получается

(8 Фев 22:58) Иван123421

@Иван123421: граф с весами, или обычный?

(9 Фев 0:08) falcao

@falcao обычный

(9 Фев 0:36) Иван123421

@Иван123421: граф считаем простым (в противном случае утверждение неверно). Он не является деревом => есть цикл длиной n>=3. Удаляем из цикла дно ребро n способами. Получившийся подграф без циклов дополняем до максимального с этим же свойством. Это будет остовное дерево. Все n таких деревьев -- разные.

(9 Фев 1:57) falcao
показано 5 из 8 показать еще 3
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,357
×522

задан
8 Фев 21:51

показан
36 раз

обновлен
9 Фев 1:57

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru