|
Название: Пятиминутка теории графов. Отправлено: Sirion от Январь 03, 2012, 08:43:00 1. Верно ли, что вершинам любого графа можно приписать числовые значения так, чтобы для каждой вершины сумма чисел у её соседей равнялась единице?
2. Верно ли, что вершинам любого графа можно приписать числовые значения так, чтобы для каждой вершины сумма чисел у неё и её соседей равнялась единице? 3. Дан связный граф из n вершин. Какое минимальное количество рёбер понадобится пройти в худшем случае, чтобы обойти все вершины и вернуться в исходную? Название: Re: Пятиминутка теории графов. Отправлено: moonlight от Январь 03, 2012, 09:35:02 1 и 2 - нет
Показать скрытый текст Название: Re: Пятиминутка теории графов. Отправлено: iPhonograph от Январь 03, 2012, 09:44:45 Название: Re: Пятиминутка теории графов. Отправлено: moonlight от Январь 03, 2012, 09:46:46 Название: Re: Пятиминутка теории графов. Отправлено: Sirion от Январь 03, 2012, 09:47:14 всё верно
4. А верно ли, что если в 3. граф - не дерево, то это обязательно нам поможет? Название: Re: Пятиминутка теории графов. Отправлено: iPhonograph от Январь 03, 2012, 09:48:23 moonlight, твоя мельница во 2 задаче решаема - основание каждой лопасти (точка, откуда она растёт) делаем 1, все остальные 0
Название: Re: Пятиминутка теории графов. Отправлено: Sirion от Январь 03, 2012, 09:51:27 гм... проглядел
у меня была какая-то более простая конструкция для 2. особо не вдумываясь, решил, что эта тоже сойдёт Название: Re: Пятиминутка теории графов. Отправлено: iPhonograph от Январь 03, 2012, 09:52:33 4. А верно ли, что если в 3. граф - не дерево, то это обязательно нам поможет? да, рисуем цикл и дополняем его оставшимися деревьямиНазвание: Re: Пятиминутка теории графов. Отправлено: iPhonograph от Январь 03, 2012, 09:53:18 я сомневаюсь, что во 2 задаче ответ "нет"
Название: Re: Пятиминутка теории графов. Отправлено: moonlight от Январь 03, 2012, 10:15:42 moonlight, твоя мельница во 2 задаче решаема - основание каждой лопасти (точка, откуда она растёт) делаем 1, все остальные 0 агаНазвание: Re: Пятиминутка теории графов. Отправлено: Sirion от Январь 03, 2012, 10:39:48 В 2. ответ "нет", я перепроверил свою конструкцию три раза.
Название: Re: Пятиминутка теории графов. Отправлено: moonlight от Январь 03, 2012, 22:40:23 Название: Re: Пятиминутка теории графов. Отправлено: Sirion от Январь 03, 2012, 22:42:47 да, именно
|