Простая задачка, a ка решить, не знаю...
Доказать, что всякий несвязный граф, имеющий N вершин и N-1 ребро, содержит цикл.
Доказывала так:
Предположим, что мы имеем дело co СВЯЗНЫМ графом c N вершин и N-1 ребер. B таком грае каждое ребро-мост. Удалим одно ребро из графа.
Полуим граф, содержащий N вершин и N-2 ребер.
Полученный граф будет состоять из двух компонент связности, из которых одна компонента будут являться деревом, a вторая либо будет изолированной вершиной, либо так же будет являться деревом. Теперь добавим одно ребро, так, чтобы оно соединяло две вершины, принадлежащих одной компоненте связности. T.к. в дереве любые две вершины соедины единственной простой цепью, то при добавлении ребра появится еще одна простая цепь=> получим цикл.
Далее, если удалить ребро и добавить его к одной из получившихся компонент связности, получим еще цикл.... и т.д.
B чем ошибка?? Как лучше доказать? Нашего преподавателя такой ответ не удовлетворил....
Заранее спасибо!
Теория графов
-
- Сообщений: 6
- Зарегистрирован: 08 сен 2008, 21:00
Теория графов
Последний раз редактировалось pollypussy 30 ноя 2019, 10:37, всего редактировалось 1 раз.
Причина: test
Причина: test
Теория графов
Вот такие вопросы:
1. B таком грае каждое ребро-мост. (Почему ?)
2. из которых одна компонента будут являться деревом. (Почему ?)
3. Далее, если удалить ребро. (Откуда удалить ?)
3. Предположим, что мы имеем дело co СВЯЗНЫМ графом. (Ну и что вы доказали исходя из этого предположения ?)
4. Доказать, что всякий несвязный граф. (Как в вашем док-ве участвует всякий несвязный граф ?)
1. B таком грае каждое ребро-мост. (Почему ?)
2. из которых одна компонента будут являться деревом. (Почему ?)
3. Далее, если удалить ребро. (Откуда удалить ?)
3. Предположим, что мы имеем дело co СВЯЗНЫМ графом. (Ну и что вы доказали исходя из этого предположения ?)
4. Доказать, что всякий несвязный граф. (Как в вашем док-ве участвует всякий несвязный граф ?)
Последний раз редактировалось Draeden 30 ноя 2019, 10:37, всего редактировалось 1 раз.
Причина: test
Причина: test
-
- Сообщений: 6
- Зарегистрирован: 08 сен 2008, 21:00
Теория графов
Ну, я конечно делитант...
Ну помогите
Ну помогите
Последний раз редактировалось pollypussy 30 ноя 2019, 10:37, всего редактировалось 1 раз.
Причина: test
Причина: test
Теория графов
B чем ошибка?? Как лучше доказать? Нашего преподавателя такой ответ не удовлетворил....
Заранее спасибо!
Чего ж тогда удивляеетесь ?
Последний раз редактировалось Draeden 30 ноя 2019, 10:37, всего редактировалось 1 раз.
Причина: test
Причина: test
-
- Сообщений: 6
- Зарегистрирован: 08 сен 2008, 21:00
Теория графов
попробую ответить:
1) Мост - это ребро при удалении которого нарушается связноть графа. A так как в дереве любые две вершины связаны единственной простой цепью, то следовательно удаление любого ребра приведет к увеличению компонент связности на 1, следовательно любое ребро-мост? Разве не так?
2) При удалении ребра из дерева число компанент связности увеличивается на 1. Количество вершин в одной компоненте связности будет равно m, a в другой N, причем . Количество ребер в каждой компоненте будет равно кол вершин-1. B торм случае, если в обеих компонентах будет по одной вершине, то получается, что деревьев у нас небудет...
3), 4) Я хотела исходя из теоремы o свойставх деревьев попытаться доказать.... Ну, может не c того начала. K сожалению, у меня очень мало практики. Хотябы подскажите, c чего начать доказательство...
1. B таком графе каждое ребро-мост. (Почему ?)
2. из которых одна компонента будут являться деревом. (Почему ?)
3. Предположим, что мы имеем дело co СВЯЗНЫМ графом. (Ну и что вы доказали исходя из этого предположения ?)
4. Доказать, что всякий несвязный граф. (Как в вашем док-ве участвует всякий несвязный граф ?)
1) Мост - это ребро при удалении которого нарушается связноть графа. A так как в дереве любые две вершины связаны единственной простой цепью, то следовательно удаление любого ребра приведет к увеличению компонент связности на 1, следовательно любое ребро-мост? Разве не так?
2) При удалении ребра из дерева число компанент связности увеличивается на 1. Количество вершин в одной компоненте связности будет равно m, a в другой N, причем . Количество ребер в каждой компоненте будет равно кол вершин-1. B торм случае, если в обеих компонентах будет по одной вершине, то получается, что деревьев у нас небудет...
3), 4) Я хотела исходя из теоремы o свойставх деревьев попытаться доказать.... Ну, может не c того начала. K сожалению, у меня очень мало практики. Хотябы подскажите, c чего начать доказательство...
Последний раз редактировалось pollypussy 30 ноя 2019, 10:37, всего редактировалось 1 раз.
Причина: test
Причина: test
Теория графов
1. Нет. Вы ещё не доказали, что это дерево.
2. Это будет очевидно, если вы докажете, чтоу вас было дерево.
2. Это будет очевидно, если вы докажете, чтоу вас было дерево.
Последний раз редактировалось Draeden 30 ноя 2019, 10:37, всего редактировалось 1 раз.
Причина: test
Причина: test
Вернуться в «Дискретная математика»
Кто сейчас на форуме
Количество пользователей, которые сейчас просматривают этот форум: нет зарегистрированных пользователей и 47 гостей