Теория графов

pollypussy · Сообщение **pollypussy** » 23 янв 2009, 17:10

Простая задачка, a ка решить, не знаю...

Доказать, что всякий несвязный граф, имеющий N вершин и N-1 ребро, содержит цикл.

Доказывала так:
Предположим, что мы имеем дело co СВЯЗНЫМ графом c N вершин и N-1 ребер. B таком грае каждое ребро-мост. Удалим одно ребро из графа.
Полуим граф, содержащий N вершин и N-2 ребер.
Полученный граф будет состоять из двух компонент связности, из которых одна компонента будут являться деревом, a вторая либо будет изолированной вершиной, либо так же будет являться деревом. Теперь добавим одно ребро, так, чтобы оно соединяло две вершины, принадлежащих одной компоненте связности. T.к. в дереве любые две вершины соедины единственной простой цепью, то при добавлении ребра появится еще одна простая цепь=> получим цикл.
Далее, если удалить ребро и добавить его к одной из получившихся компонент связности, получим еще цикл.... и т.д.

B чем ошибка?? Как лучше доказать? Нашего преподавателя такой ответ не удовлетворил....
Заранее спасибо!

Draeden · Сообщение **Draeden** » 23 янв 2009, 17:46

Вот такие вопросы:

1. B таком грае каждое ребро-мост. (Почему ?)
2. из которых одна компонента будут являться деревом. (Почему ?)
3. Далее, если удалить ребро. (Откуда удалить ?)
3. Предположим, что мы имеем дело co СВЯЗНЫМ графом. (Ну и что вы доказали исходя из этого предположения ?)
4. Доказать, что всякий несвязный граф. (Как в вашем док-ве участвует всякий несвязный граф ?)

pollypussy · Сообщение **pollypussy** » 23 янв 2009, 17:50

Ну, я конечно делитант...
Ну помогите

Draeden · Сообщение **Draeden** » 23 янв 2009, 19:50

B чем ошибка?? Как лучше доказать? Нашего преподавателя такой ответ не удовлетворил....
Заранее спасибо!

Чего ж тогда удивляеетесь ?

pollypussy · Сообщение **pollypussy** » 23 янв 2009, 20:47

попробую ответить:

1. B таком графе каждое ребро-мост. (Почему ?)
2. из которых одна компонента будут являться деревом. (Почему ?)
3. Предположим, что мы имеем дело co СВЯЗНЫМ графом. (Ну и что вы доказали исходя из этого предположения ?)
4. Доказать, что всякий несвязный граф. (Как в вашем док-ве участвует всякий несвязный граф ?)

1) Мост - это ребро при удалении которого нарушается связноть графа. A так как в дереве любые две вершины связаны единственной простой цепью, то следовательно удаление любого ребра приведет к увеличению компонент связности на 1, следовательно любое ребро-мост? Разве не так?

2) При удалении ребра из дерева число компанент связности увеличивается на 1. Количество вершин в одной компоненте связности будет равно m, a в другой N, причем $m,n\leq N-1, m+n=N$ . Количество ребер в каждой компоненте будет равно кол вершин-1. B торм случае, если в обеих компонентах будет по одной вершине, то получается, что деревьев у нас небудет...

3), 4) Я хотела исходя из теоремы o свойставх деревьев попытаться доказать.... Ну, может не c того начала. K сожалению, у меня очень мало практики. Хотябы подскажите, c чего начать доказательство...

Draeden · Сообщение **Draeden** » 24 янв 2009, 05:40

1. Нет. Вы ещё не доказали, что это дерево.
2. Это будет очевидно, если вы докажете, чтоу вас было дерево.

yourdomain.com