Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 2 из 5 |
[ Сообщений: 47 ] | На страницу Пред. 1, 2, 3, 4, 5 След. |
|
Автор | Сообщение | |
---|---|---|
mathe |
|
|
|
||
Вернуться к началу | ||
Slon |
|
|
Так что утверждение доказывается по индукции по n, но для перехода эти 2 пункта понадобятся
|
||
Вернуться к началу | ||
mathe |
|
|
никак не пойму как математически формализуется наличие нашей фигуры в графе, почему вообще важно найти вершину с не более n ребер.
|
||
Вернуться к началу | ||
Slon |
|
|
Есть 2 объяснения:
1) нам это нужно для применения индукции, знаете, что это? https://ru.wikipedia.org/wiki/%D0%9C%D0 ... 0%B8%D1%8F 2) а можно без индукции, просто сказать, что делаем что-то пока не получим эти 2 треугольника: вот было 2n вершин и [math]n^2+1[/math] ребер, забираем 2 вершины и [math]2n-1[/math] ребро, затем еще 2 вершины и [math]2n-3[/math] ребра затем еще 2 вершины и [math]2n-5[/math] ребер и т. д. проделываем это n-2 раза пока не останется 4 вершины с 5 ребрами, а это то что нужно. Но чтобы сделать один шаг (а их n-2) нужно еще доказать, что это можно сделать. Понимаете? Если да, то Вам как больше нравится через индукцию или вторым способом? |
||
Вернуться к началу | ||
mathe |
|
|
Slon писал(а): Да, но с Вашем участием: 1) докажите, что найдется вершина из которой выходит не более n ребер 2) докажите, что после того как удалили вершину из которой исходило [math]x\leqslant n[/math] ребер в полученном графе можно будет найти вершину с числом выходящих из нее ребер не более чем [math]2n-1-x[/math] 1)если в графе из каждой вершины выходит [math](n+1)[/math] ребер, то общее кол-во ребер в графе будет [math]2n(n+1) \,\colon 2 = n^2 + n[/math], след-о найдется вершина из которой выходит не более n ребер |
||
Вернуться к началу | ||
mathe |
|
|
Slon писал(а): Есть 2 объяснения: 1) нам это нужно для применения индукции, знаете, что это? https://ru.wikipedia.org/wiki/%D0%9C%D0 ... 0%B8%D1%8F 2) а можно без индукции, просто сказать, что делаем что-то пока не получим эти 2 треугольника: вот было 2n вершин и [math]n^2+1[/math] ребер, забираем 2 вершины и [math]2n-1[/math] ребро, затем еще 2 вершины и [math]2n-3[/math] ребра затем еще 2 вершины и [math]2n-5[/math] ребер и т. д. проделываем это n-2 раза пока не останется 4 вершины с 5 ребрами, а это то что нужно. Но чтобы сделать один шаг (а их n-2) нужно еще доказать, что это можно сделать. Понимаете? Если да, то Вам как больше нравится через индукцию или вторым способом? Вообще оба интересны, но мне кажется поняв второй, можно будет индукцию быстро применить. |
||
Вернуться к началу | ||
mathe |
|
|
во втором объяснении самое главное не понятно вот что мне
если мы забираем 2n вершин и [math]n^2+1[/math] ребер, то как сделать так чтобы мы случайно не забрали ребро или вершину из наших двух треугольников |
||
Вернуться к началу | ||
mathe |
|
|
ой, кажется понял, даже если мы заберем, то это не важно, т.к в конце все равно два треугольника с общим ребром будут
|
||
Вернуться к началу | ||
Slon |
|
|
Вот если Вам все понятно, то теперь остается просто показать 2)
На индукцию я не настаиваю, она просто идеальна в самом формальном плане, но рассуждать проще вторым способом, то есть проделав n-2 шага |
||
Вернуться к началу | ||
mathe |
|
|
вот мне как раз формальное док-во и нужно, т.е. индукция как раз подошла бы.
Допустим, что условие выполняется при n, тогда при (n+1) мы будем иметь на 2 вершины и 2n+1 ребер больше. Насколько я понимаю, нужно показать, что при удалении двух вершин граф (n+1) будет идентичен графу n. Но как? Или я ошибаюсь? |
||
Вернуться к началу | ||
На страницу Пред. 1, 2, 3, 4, 5 След. | [ Сообщений: 47 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Доказать, что среди ребят найдутся 3, решавших одну задачу
в форуме Алгебра |
3 |
601 |
10 апр 2014, 11:25 |
|
Доказать,что возможно найти крат. путь в графе за O(|V|+|E|) | 0 |
284 |
27 окт 2015, 14:18 |
|
Множество задать общим свойством | 1 |
229 |
18 сен 2016, 10:50 |
|
Куб с ребром 1 повернуто на 45 градусов вокруг оси, соединяю
в форуме Геометрия |
1 |
240 |
16 июн 2018, 17:04 |
|
Угол между ребром и гранью тетраэдра
в форуме Геометрия |
3 |
237 |
17 ноя 2019, 16:04 |
|
Угол между ребром и диагональю пирамиды
в форуме Геометрия |
7 |
523 |
28 май 2015, 19:05 |
|
Куб с ребром 2 повернуто на 90 градусов вокруг диагонали одн
в форуме Геометрия |
1 |
201 |
16 июн 2018, 17:02 |
|
Нахождение угла между ребром и гранью пирамиды | 5 |
643 |
08 янв 2017, 15:19 |
|
Доказать свойство треугольника Паскаля
в форуме Алгебра |
1 |
280 |
22 ноя 2017, 23:47 |
|
Доказать выполнимость аксиомы треугольника для кв. метрики
в форуме Функциональный анализ, Топология и Дифференциальная геометрия |
1 |
558 |
07 фев 2020, 20:02 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |