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

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

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

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




Начать новую тему Ответить на тему  [ Сообщений: 3 ] 
Автор Сообщение
 Заголовок сообщения: Связный граф
СообщениеДобавлено: 30 апр 2019, 17:31 
Не в сети
Оракул
Зарегистрирован:
10 окт 2018, 22:06
Сообщений: 830
Cпасибо сказано: 209
Спасибо получено:
245 раз в 225 сообщениях
Очков репутации: 38

Добавить очки репутацииУменьшить очки репутации
Добрый день.
Имеется задача: установить, существует ли связный граф с [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].
Преобразования ничего не дали. Теорема Эрдёша-Галлаи? Не очень понимаю, как ее применить данному случаю. Как и тот факт, что количество вершин нечетной степени четно.
Буду благодарен за подсказки - в каком направлении искать?
Спасибо.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Связный граф
СообщениеДобавлено: 30 апр 2019, 17:50 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Граф со степенями 1, 2 и 3 легко же реализуется

Или имеется в виду простой граф? Как-то это условие скрыто.

Да нет, тоже слишком просто. Если n вершин, то максимальная степень n-1. Значит прогрессия с нуля и граф несвязен.

Вернуться к началу
 Профиль  
Cпасибо сказано 
За это сообщение пользователю swan "Спасибо" сказали:
AGN
 Заголовок сообщения: Re: Связный граф
СообщениеДобавлено: 30 апр 2019, 20:16 
Не в сети
Оракул
Зарегистрирован:
10 окт 2018, 22:06
Сообщений: 830
Cпасибо сказано: 209
Спасибо получено:
245 раз в 225 сообщениях
Очков репутации: 38

Добавить очки репутацииУменьшить очки репутации
swan писал(а):

Или имеется в виду простой граф? Как-то это условие скрыто.


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

Цитата:
Да нет, тоже слишком просто. Если n вершин, то максимальная степень n-1. Значит прогрессия с нуля и граф несвязен.


Спасибо огромное. Такая простая вещь мне в голову не пришла.

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

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

в форуме Начала анализа и Другие разделы школьной математики

Fyodor272000

3

268

16 окт 2022, 16:24

Граф - куб

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

lolliker228

2

165

07 дек 2020, 01:06

Граф

в форуме Задачи со школьных и студенческих олимпиад

boroda33

2

423

26 авг 2015, 20:13

Неориентированный граф

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

lolliker228

6

157

29 ноя 2020, 17:00

Граф и множества

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

Victoria888

1

253

13 апр 2021, 23:35

Построить граф

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

dddd

1

508

19 окт 2014, 14:02

Нарисовать граф

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

Alexx74

4

607

19 окт 2014, 15:04

Доп.граф для мультиграфа

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

rfgbnfkbyf

0

199

24 мар 2016, 08:51

Построить граф

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

SDOX

3

104

12 окт 2019, 18:21

Случайный граф

в форуме Теория вероятностей

wormeer2017

21

953

07 окт 2017, 13:08


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



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

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


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

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

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

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