Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 3 ] |
|
Автор | Сообщение | |
---|---|---|
AGN |
|
|
Имеется задача: установить, существует ли связный граф с [math]n \geqslant 2[/math] вершинами, для которого степени вершин образуют арифметическую прогрессию с [math]d = 1[/math]. Количество [math]m[/math] ребер в графе (простом, мультиграфы не рассматриваем) [math]n - 1 \leqslant m \leqslant \frac{ n\left( n - 1 \right) }{ 2 }[/math] (соответственно линейный и полный). Сумма всех степеней вершин равна [math]2m[/math]. С другой стороны (в предположении, что указанный граф существует), эта сумма не меньше чем [math]\frac{ n\left( n + 1 \right) }{ 2 }[/math]. Преобразования ничего не дали. Теорема Эрдёша-Галлаи? Не очень понимаю, как ее применить данному случаю. Как и тот факт, что количество вершин нечетной степени четно. Буду благодарен за подсказки - в каком направлении искать? Спасибо. |
||
Вернуться к началу | ||
swan |
|
|
Граф со степенями 1, 2 и 3 легко же реализуется
Или имеется в виду простой граф? Как-то это условие скрыто. Да нет, тоже слишком просто. Если n вершин, то максимальная степень n-1. Значит прогрессия с нуля и граф несвязен. |
||
Вернуться к началу | ||
За это сообщение пользователю swan "Спасибо" сказали: AGN |
||
AGN |
|
|
swan писал(а): Или имеется в виду простой граф? Как-то это условие скрыто. Да, скрыто. Но (мое предположение) граф простой по умолчанию. Для мультиграфа вроде проблем быть не должно. Цитата: Да нет, тоже слишком просто. Если n вершин, то максимальная степень n-1. Значит прогрессия с нуля и граф несвязен. Спасибо огромное. Такая простая вещь мне в голову не пришла. |
||
Вернуться к началу | ||
[ Сообщений: 3 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Дерево - связный граф без циклов, а не что-то другое
в форуме Начала анализа и Другие разделы школьной математики |
3 |
268 |
16 окт 2022, 16:24 |
|
Граф - куб | 2 |
165 |
07 дек 2020, 01:06 |
|
Граф | 2 |
423 |
26 авг 2015, 20:13 |
|
Неориентированный граф | 6 |
157 |
29 ноя 2020, 17:00 |
|
Граф и множества | 1 |
253 |
13 апр 2021, 23:35 |
|
Построить граф | 1 |
508 |
19 окт 2014, 14:02 |
|
Нарисовать граф | 4 |
607 |
19 окт 2014, 15:04 |
|
Доп.граф для мультиграфа | 0 |
199 |
24 мар 2016, 08:51 |
|
Построить граф | 3 |
104 |
12 окт 2019, 18:21 |
|
Случайный граф
в форуме Теория вероятностей |
21 |
953 |
07 окт 2017, 13:08 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 18 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |