Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 47 ]  На страницу Пред.  1, 2, 3, 4, 5  След.
Автор Сообщение
 Заголовок сообщения: Re: Доказать, что в графе найдутся 2 треугольника с общим ребром
СообщениеДобавлено: 12 мар 2018, 19:56 
Не в сети
Начинающий
Зарегистрирован:
09 мар 2018, 16:31
Сообщений: 24
Cпасибо сказано: 4
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
а как это вообще на 2 треугольника с общим ребром завязывается?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Доказать, что в графе найдутся 2 треугольника с общим ребром
СообщениеДобавлено: 12 мар 2018, 19:58 
Не в сети
Оракул
Зарегистрирован:
14 дек 2017, 17:48
Сообщений: 870
Cпасибо сказано: 33
Спасибо получено:
206 раз в 187 сообщениях
Очков репутации: 31

Добавить очки репутацииУменьшить очки репутации
Так что утверждение доказывается по индукции по n, но для перехода эти 2 пункта понадобятся

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Доказать, что в графе найдутся 2 треугольника с общим ребром
СообщениеДобавлено: 12 мар 2018, 20:15 
Не в сети
Начинающий
Зарегистрирован:
09 мар 2018, 16:31
Сообщений: 24
Cпасибо сказано: 4
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
никак не пойму как математически формализуется наличие нашей фигуры в графе, почему вообще важно найти вершину с не более n ребер.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Доказать, что в графе найдутся 2 треугольника с общим ребром
СообщениеДобавлено: 12 мар 2018, 21:14 
Не в сети
Оракул
Зарегистрирован:
14 дек 2017, 17:48
Сообщений: 870
Cпасибо сказано: 33
Спасибо получено:
206 раз в 187 сообщениях
Очков репутации: 31

Добавить очки репутацииУменьшить очки репутации
Есть 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) нужно еще доказать, что это можно сделать.
Понимаете?
Если да, то Вам как больше нравится через индукцию или вторым способом?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Доказать, что в графе найдутся 2 треугольника с общим ребром
СообщениеДобавлено: 12 мар 2018, 21:21 
Не в сети
Начинающий
Зарегистрирован:
09 мар 2018, 16:31
Сообщений: 24
Cпасибо сказано: 4
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
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 ребер

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Доказать, что в графе найдутся 2 треугольника с общим ребром
СообщениеДобавлено: 12 мар 2018, 21:31 
Не в сети
Начинающий
Зарегистрирован:
09 мар 2018, 16:31
Сообщений: 24
Cпасибо сказано: 4
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
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) нужно еще доказать, что это можно сделать.
Понимаете?
Если да, то Вам как больше нравится через индукцию или вторым способом?


Вообще оба интересны, но мне кажется поняв второй, можно будет индукцию быстро применить.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Доказать, что в графе найдутся 2 треугольника с общим ребром
СообщениеДобавлено: 12 мар 2018, 21:43 
Не в сети
Начинающий
Зарегистрирован:
09 мар 2018, 16:31
Сообщений: 24
Cпасибо сказано: 4
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
во втором объяснении самое главное не понятно вот что мне
если мы забираем 2n вершин и [math]n^2+1[/math] ребер, то как сделать так чтобы мы случайно не забрали ребро или вершину из наших двух треугольников

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Доказать, что в графе найдутся 2 треугольника с общим ребром
СообщениеДобавлено: 12 мар 2018, 21:47 
Не в сети
Начинающий
Зарегистрирован:
09 мар 2018, 16:31
Сообщений: 24
Cпасибо сказано: 4
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
ой, кажется понял, даже если мы заберем, то это не важно, т.к в конце все равно два треугольника с общим ребром будут

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Доказать, что в графе найдутся 2 треугольника с общим ребром
СообщениеДобавлено: 12 мар 2018, 23:09 
Не в сети
Оракул
Зарегистрирован:
14 дек 2017, 17:48
Сообщений: 870
Cпасибо сказано: 33
Спасибо получено:
206 раз в 187 сообщениях
Очков репутации: 31

Добавить очки репутацииУменьшить очки репутации
Вот если Вам все понятно, то теперь остается просто показать 2)
На индукцию я не настаиваю, она просто идеальна в самом формальном плане, но рассуждать проще вторым способом, то есть проделав n-2 шага

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Доказать, что в графе найдутся 2 треугольника с общим ребром
СообщениеДобавлено: 12 мар 2018, 23:27 
Не в сети
Начинающий
Зарегистрирован:
09 мар 2018, 16:31
Сообщений: 24
Cпасибо сказано: 4
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
вот мне как раз формальное док-во и нужно, т.е. индукция как раз подошла бы.

Допустим, что условие выполняется при n, тогда при (n+1) мы будем иметь на 2 вершины и 2n+1 ребер больше. Насколько я понимаю, нужно показать, что при удалении двух вершин граф (n+1) будет идентичен графу n. Но как? Или я ошибаюсь?

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему    На страницу Пред.  1, 2, 3, 4, 5  След.  Страница 2 из 5 [ Сообщений: 47 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Доказать, что среди ребят найдутся 3, решавших одну задачу

в форуме Алгебра

oksi

3

601

10 апр 2014, 11:25

Доказать,что возможно найти крат. путь в графе за O(|V|+|E|)

в форуме Дискретная математика, Теория множеств и Логика

duducai007

0

284

27 окт 2015, 14:18

Множество задать общим свойством

в форуме Дискретная математика, Теория множеств и Логика

lolopop12

1

229

18 сен 2016, 10:50

Куб с ребром 1 повернуто на 45 градусов вокруг оси, соединяю

в форуме Геометрия

IvanSavkiv

1

240

16 июн 2018, 17:04

Угол между ребром и гранью тетраэдра

в форуме Геометрия

jj1247

3

237

17 ноя 2019, 16:04

Угол между ребром и диагональю пирамиды

в форуме Геометрия

Ilitan

7

523

28 май 2015, 19:05

Куб с ребром 2 повернуто на 90 градусов вокруг диагонали одн

в форуме Геометрия

IvanSavkiv

1

201

16 июн 2018, 17:02

Нахождение угла между ребром и гранью пирамиды

в форуме Аналитическая геометрия и Векторная алгебра

Oleg2017

5

643

08 янв 2017, 15:19

Доказать свойство треугольника Паскаля

в форуме Алгебра

argus

1

280

22 ноя 2017, 23:47

Доказать выполнимость аксиомы треугольника для кв. метрики

в форуме Функциональный анализ, Топология и Дифференциальная геометрия

Vvn3012

1

558

07 фев 2020, 20:02


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved