Danila44 |
Путь в графе 08.03.2010, 10:50 |
|
02/03/10 3
|
Существует в графе "каркас куба" путь, проходящий через одну из вершин 25 раз, а через остальные - по 30?
|
|
|
|
|
maxal |
Re: Путь в графе 09.03.2010, 17:12 |
|
Модератор |
|
11/01/06 5710
|
С каждым ребром ассоциируйте неизвестную, равную количеству прохождений пути через это ребро, а для каждой вершины запишите уравнение вида: сумма неизвестных соответствующих инцидентным ребрам равна удвоенному числу посещений вершины (для замкнутого пути или неконцевой вершины незамкнутого пути) или ему же уменьшенному на 1 (для концевой вершины незамкнутого пути). Если получившаяся система имеет решение - путь существует, а нет - так нет.
|
|
|
|
|
sergey1 |
Re: Путь в графе 09.03.2010, 17:38 |
|
14/02/06 285
|
Можно разбить вершины куба на две четверки попарно несоседних вершин и заметить, что суммы прохождений по вершинам четверок различаются не более чем на 1.
|
|
|
|
|
Danila44 |
Re: Путь в графе 09.03.2010, 22:05 |
|
02/03/10 3
|
Спасибо всем ответившим! Второй вариант особенно понравился - и как я сам не смог сообразить...
|
|
|
|
|
DrGonzo |
Re: Путь в графе 07.03.2011, 22:05 |
|
07/03/11 2
|
Добрый день. Сейчас пытаюсь решить эту же задачу. Логика была примерно такая же, как у maxal.
Составил систему линейный уравнений, обозначив за неизвестные количество проходов по рёбрам. А в качестве столбца свободных членов взял посещения вершин, домноженные на 2 (т.е. 60 и один член 50).
Для существования пути система должна быть совместной.
Проверил - получилось. Вроде бы всё, но что-то терзают меня смутные сомнения...
|
|
|
|
|
|
Страница 1 из 1
|
[ Сообщений: 5 ] |
|
Модераторы: Модераторы Математики, Супермодераторы