Графы. Задачка. Забыл как доказать, не напомните?

← →
OW © (2011-04-22 16:32) [0]

Три дома и три колодца.
Д Д Д
К К К
От каждого дома тропинка к каждому колодцу.

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

В задаче "Сколько максимально дорог можно проложить без пересечений".

← →
han_malign (2011-04-22 16:47) [1]

да на теорию графов вроде не похоже...

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

← →
iZEN (2011-04-22 17:01) [2]

2^3 == 8
8 < 9
Доказано!

← →
xayam © (2011-04-22 18:12) [3]

> что не возможно проложить все 9

в 3d очень даже можно :)

← →
Pavia © (2011-04-22 18:31) [4]

Мимо пробегал.
http://ru.wikipedia.org/wiki/Планарный_граф

← →
palva © (2011-04-22 20:18) [5]

Посмотреть в учебнике теорему Понтрягина-Куратовского.

← →
ов (дом) (2011-04-22 22:03) [6]

точно, спасибо!

Нынче в школе первый класс вроде института..
Задача, в исходном виде, предложена в учебнике математики за второй класс :)
Именно, как видоизмененная немного Задача о трех колодцах.
вот что-то где-то помню, а что.. где..

← →
palva © (2011-04-22 22:35) [7]

Доказательство доступное делфимастеру есть здесь:
http://reslib.com/book/Vvedenie_v_teoriyu_grafov/76
последний абзац на странице.
Только как это объяснить второкласснику, сказать затрудняюсь. Нужно хорошо представлять, что им рассказывали на уроках и что они считают очевидным.

← →
KilkennyCat © (2011-04-23 03:12) [8]

дома объединить в трехэтажный, и прямо внутре сверлить артезиан. имеем точку, тропинки не нужны.

← →
Inovet © (2011-04-23 09:05) [9]

> [8] KilkennyCat © (23.04.11 03:12)

Построить дома на глубине грунтовых вод, имеем ничего, тропинки не нужны

← →
oldman © (2011-04-25 08:40) [10]

> Доказать, что не возможно проложить все 9,

Возможно, к сожалению...

← →
OW © (2011-04-25 08:46) [11]

> oldman © (25.04.11 08:40) [10]

ну ка

← →
oldman © (2011-04-25 08:48) [12]

> OW © (25.04.11 08:46) [11]

выйди из плоскости...

от одного колодца ко всем трем домам по земле,
от второго под землей, от третьего над землей.

← →
OW © (2011-04-25 08:53) [13]

> выйди из плоскости...

хех, а если в четвертом измерении продавить, то колодец получится аккурат в доме :)

← →
oldman © (2011-04-25 08:59) [14]

На плоскости, ессно, нельзя...

http://levvol.ru/answer_euler.php

← →
Inovet © (2011-04-25 13:07) [15]

Нет, тропинка - это по поверхности земли, над поверхностью будет мост, под поверхностью - тунель. Иначе хоть сколько прокладывай в разных измерениях, их количество ведь явно не задано. А вообще меня всегда задачи в учебниках с недоговорками, неточными условиями, разночтениями заставляют задуматься - я дурак и не вижу чего-то, или авторы задачи дураки, или надо несколько решений привести.

Вот недавно была задача у сына. Что-то вроде: катер сначала по течению прошёл, потом назад, оба времени и скорости даны, какое он прошёл расстояние? Вот и думай какое расстоянме.

← →
oldman © (2011-04-25 13:09) [16]

> катер сначала по течению прошёл, потом назад, оба времени
> и скорости даны, какое он прошёл расстояние? Вот и думай
> какое расстоянме.

А в чем проблема?

← →
Inovet © (2011-04-25 13:31) [17]

> [16] oldman © (25.04.11 13:09)
> А в чем проблема?

Так какое надо расстояние - то, что на неком катерном одометре, или между пунктами отправления и прибытия, или между первым и вторым пунктом. Ладно скорости там заданы числом, п то ещё бы были непонятности. Оно, конечно, вроде же очевидно что по беоегу надо мерять, но это математика а не урок труда, и мышление должно прививаться вот на таких "мелочах" тоже.

ну да

кстати,

> оба времени и скорости даны

а зачем тогда обе? :) Пункты А и Б раздвинули пока назад шел?

Пункты А и Б раздвинули пока назад шел?

Вот видишь - и здесь гадание, но это из условия понятно - пункты там получаются А Б и С.

> Inovet © (25.04.11 13:31) [17]

Из А по течению в В. Из В против течения в С.

АС = расстояние.
АВ + ВС = путь.

Нормальная задача.

> [20] oldman © (25.04.11 15:17)
> АС = расстояние.
> АВ + ВС = путь.

Ладно, с терминами пусть так, но там даже и не так было, искать надо, а ещё есть вода и берега. В любом случае или трчно надо условие давать или ещё лучше для понимания несколько разных вопросов задать. Составители учебников, видимо, не понимают этого.

> а ещё есть вода и берега.

и пьяный капитан, ведущий судно не по прямой, а по синусоиде...
:)))

С пьяным капитаном уже повышенной сложности.

расчитать резонансную частоту колебаний катера при движении по течению и против при употреблении капитаном алкоголя :)

Графы. Задачка. Забыл как доказать, не напомните? Найти похожие ветки