[специалистам по всему] дискретная математика

1) поиск в глубину, делов то.

1. задача о кенигсбергских мостах. решена Эйлером в 1736 году

2. задача о трех домах и трех колодцах. решена Куратовским в 1930 году

1. Там какое-то условие существования решения было. Не помню, правда, какое.

2. В двумерном пространстве решена?

1) Препод - провокатор. Решения нет, это классика теории графов.
http://ru.wikipedia.org/wiki/%D0%A1%D0%B5%D0%BC%D1%8C_%D0%BC%D0%BE%D1%81%D1%8...

2. В двумерном пространстве решена?

там граф не плоский задается(или доказывается что не плоский, вот этого не помню)

А ну да. Соббсно, вот:

>Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно).

>На упрощённой схеме части города (графе) мостам соответствуют линии (рёбра графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам: Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа всегда чётно. Невозможно начертить граф, который имел бы нечётное число нечётных вершин. Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине. Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

> http://ru.wikipedia.org/wiki/%D0%A1%D0%B5%D0%BC%D1%8C_%D0%BC%D0%BE%D1%81%D1%8.. .

Смотрел, знаю что нет.

> самолет находится на бесконечной конвеерной ленте, которая ускоряется с тем же ускорением, что сообщают самолету его двигатели, сможет ли самолет взлететь?

Боян. На LOR'e обсуждалось.

> там граф не плоский задается(или доказывается что не плоский, вот этого не помню)

Граф таки плоский. То-есть на листе бумаги.

1) http://img238.imageshack.us/img238/6979/31063354gy5.png
   http://img444.imageshack.us/img444/549/77652332hz3.png

2) http://img151.imageshack.us/img151/2865/53633035wq1.png

ничего особо не доказывается, но может быть пригодится для общего развития.

> там граф не плоский задается(или доказывается что не плоский, вот этого не помню)

Мсье имел в виду "планарный"?

Плохо гуглил: http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg

Классическая задачка по теории графов. В любом учебнике. Вторая тоже.

А препод наверное имеет ввиду решение того, что нужно доказать что решить невозможно.

> А препод наверное имеет ввиду решение того, что нужно доказать что решить невозможно.

Нам пока не известно, что он употребляет.)) Но скоро будим знать.

какой унылый боянъ...

>Гуглил-гуглил, решения, говорит, нет. Препод сказал есть. Думаем вместе!

конечно нет. есть доказательство того, что так сделать нельзя. что и требует препод. хинт: чтобы попасть в вершину графа(клочок суши) по одному мосту нужно зайти, а подругому - выйти

>Ну и дома тут такие же стоят.

ну ты понял. хинт: если взять два дома и три колодца то граф _всегда_ можно привести к виду:
  /-+-\
 /     \
*---+---*
 \     /
  \-+-/

Говорят, что какой-то еврейский торгаш первую задачку таки да решил. Правда не в Кенигсберге, а в Варшаве, чтобы с тачкой товарной бегать поменьше и денюжку зарабатывать быстрее.

2) http://en.wikipedia.org/wiki/Planar_graph искать слово K3,3

>пройдя по ВСЕМ мостам (М1, М2,..., М7) всего ОДИН раз

>Решения нет, это классика теории графов.

Решение есть в третьем измерении: когда мосты пройдены по одному разу, надо использовать "летающую корову" для перелёта в исходную точку :)

Мать-те-матеги хреновы.

+-----------+
|           |
| +---+   +---+   +---+
| |   |   |   |   |   |---+
| | К |-+ | К |-+ | К |   |
| |   | | |   | | |   |-+ |
| +---+ | +---+ | +---+ | |
|  | |  |    |  |    |  | |
|  | |  |    |  |    |  | |
|  | |  +--+ |  |    |  | |
|  | |     | |  +--+ |  | |
|  | +--+  | |     | |  | |
|  |    |  | |     | |  | |
|  |    |  | |     | |  | |
|  |    |  | |     | |  | |
| +---+ | +---+   +---+ | |
| |   | | |   |   |   | | |
+-| Д | | | Д |   | Д | | |
  |   | +-+---+---|   | | |
  +---+   +---+   +---+ | |
    |       |           | |
    |       +-----------+ |
    |                     |
    +---------------------+

>Мать-те-матеги хреновы. +-----------+ | | | +---+ +---+ +---+ | | | | | | |---+ | | К |-+ | К |-+ | К | | | | | | | | | | |-+ | | +---+ | +---+ | +---+ | | | | | | | | | | | | | | | | | | | | | | | +--+ | | | | | | | | | | +--+ | | | | | +--+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +---+ | +---+ +---+ | | | | | | | | | | | | +-| Д | | | Д | | Д | | | | | +-+---+---| | | | +---+ +---+ +---+ | | | | | | | +-----------+ | | | +---------------------+

Так палевно, лучше так:

+-----------+ | | | +---+ +---+ +---+ | | | | | | |---+ | | К |-+ | К |-+ | К | | | | | | | | | | |-+ | | +---+ | +---+ | +---+ | | | | | | | | | | | | | | | | | | | | | | | +--+ | | | | | | | | | | +--+ | | | | | +--+ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | +---+ | +---+ +---+ | | | | | | | | | | | | +-| Д | | | Д | | Д | | | | | | | | | | | | +---+ +-+---+---+---+ | | | | | | | +-----------+ | | | +---------------------+

>Мать-те-матеги хреновы.
+-----------+
|           |
| +---+   +---+   +---+
| |   |   |   |   |   |---+
| | К |-+ | К |-+ | К |   |
| |   | | |   | | |   |-+ |
| +---+ | +---+ | +---+ | |
|  | |  |    |  |    |  | |
|  | |  |    |  |    |  | |
|  | |  +--+ |  |    |  | |
|  | |     | |  +--+ |  | |
|  | +--+  | |     | |  | |
|  |    |  | |     | |  | |
|  |    |  | |     | |  | |
|  |    |  | |     | |  | |
| +---+ | +---+   +---+ | |
| |   | | |   |   |   | | |
+-| Д | | | Д |   | Д | | |
  |   | +-+---+---|   | | |
  +---+   +---+   +---+ | |
    |       |           | |
    |       +-----------+ |
    |                     |
    +---------------------+

Так палевно, лучше так:

+-----------+
|           |
| +---+   +---+   +---+
| |   |   |   |   |   |---+
| | К |-+ | К |-+ | К |   |
| |   | | |   | | |   |-+ |
| +---+ | +---+ | +---+ | |
|  | |  |    |  |    |  | |
|  | |  |    |  |    |  | |
|  | |  +--+ |  |    |  | |
|  | |     | |  +--+ |  | |
|  | +--+  | |     | |  | |
|  |    |  | |     | |  | |
|  |    |  | |     | |  | |
|  |    |  | |     | |  | |
| +---+ | +---+   +---+ | |
| |   | | |   |   |   | | |
+-| Д | | | Д |   | Д | | |
  |   | | |   |   |   | | |
  +---+ +-+---+---+---+ | |
    |       |           | |
    |       +-----------+ |
    |                     |
    +---------------------+

блин с этим тексом

это ж читерство!

Ну да. Но где в задании сказано, что нельзя читерствовать?

Впервые вижу человека, реально пишущего на brainf*ck.

(Сорри, не удержался)

У нас в школе (я был тогда классе в 8-м или 9-м) была популярна
головоломка, аналогичная задаче о мостах. Рисуется вот такое окошко:

   +--+---+--+
   |  |   |  |
   +--+-+-+--+
   |    |    |
   |    |    |
   +----+----+

Нужно провести линию, пересекающую все границы между квадратиками
окошкама по одному разу. Народ кучу бумаги извёл, рисуя эти линии.
Я Эйлером не был и слова «граф» не знал, но быстро понял, что раз
так долго не могут решить перебором такой простой рисунок,
значит скорее всего решения просто нет. :) И почти сразу это доказал
(в данном случае у нас три нечётных вершины графа, то есть наша линия
должна иметь три конца минимум).

Никто мне не поверил и ещё месяца два изводили бумагу. :)

Мать-те-матеги!

У графа не может быть три нечётных вершины.

Прошу прощения, вместе с «внешней» — конечно четыре. :) Но достаточно того, что мы видим три, зачем искать четвёртую? :)

Вообще, чёрт побери, а ведь действительно! Прошло ещё пятнадцать лет, и я узнал что-то новое об этой головоломке. :) Хотя моё доказательство всё равно корректно: я ведь не говорил, что концов у линии должно быть ровно три, я просто показал три места, где они точно должны быть. Короче попрошу не критиковать! :)