|
Danila44 |
Путь в графе  08.03.2010, 10:50 |
|
02/03/10
3
|
|
Существует в графе "каркас куба" путь, проходящий через одну из вершин 25 раз, а через остальные - по 30?
|
|
|
|
 |
|
maxal |
Re: Путь в графе 09.03.2010, 17:12 |
|
| Модератор |
 |
11/01/06
5702
|
|
С каждым ребром ассоциируйте неизвестную, равную количеству прохождений пути через это ребро, а для каждой вершины запишите уравнение вида: сумма неизвестных соответствующих инцидентным ребрам равна удвоенному числу посещений вершины (для замкнутого пути или неконцевой вершины незамкнутого пути) или ему же уменьшенному на 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 ] |
|
Модераторы: Модераторы Математики, Супермодераторы
