2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Оценка диаметра графа
Сообщение06.04.2015, 19:53 
Заслуженный участник
Аватара пользователя


22/01/11
2641
СПб
Помогите старику, всё забыл, а не гуглится.
Где можно посмотреть оценки (сверху) диаметра связного графа через наименьшую степень вершин и их количество?

 Профиль  
                  
 
 Re: Оценка диаметра графа
Сообщение07.04.2015, 12:01 


14/01/11
2916
Пусть имеется граф $G$ с количеством вершин $n$, степень каждой из которых не менее $\delta$, а диаметр графа равен $D$.
Возьмём какую-нибудь вершину $A$ и обозначим $c(r)$ количество вершин графа $G$, расстояние от каждой из которых до $A$ составляет ровно $r$. Рассмотрим вершины, расстояние от которых до $A$ равно $r$, где $0 < r < D$. Обозначим их множество $S_r$. В соответствии с ранее введёнными обозначениями $|S_r|=c(r)$. Каждая вершина из $S_r$ может быть смежна только с вершинами из $S_r$, $S_{r-1}$ и $S_{r+1}$, исключая её саму.
Таким образом, $c(r)+c(r-1)+c(r+1)-1 \geqslant \delta$.
Запишем $D-1$ таких неравенств для всех $r$ от $1$ до $D-1$:
$c(0)+c(1)+c(2)-1 \geqslant \delta$
$c(1)+c(2)+c(3)-1 \geqslant \delta$

$\cdots$

$c(D-2)+c(D-1)+c(D)-1 \geqslant \delta$
Просуммируем их с учётом того, что $\sum\limits_{r=0}^Dc(r)=n$:
$3n-2(c(0)+c(D))-(c(1)+c(D-1))-(D-1) \geqslant (D-1) \delta$
$c(0)=1$ (Это наша вершина $A$). $c(D)$ при $D>1$ тоже можно сделать равным $1$ без уменьшения диаметра графа - просто перенесём лишние вершины в середину графа, соединив их, к примеру, со всеми вершинами из $S_1$. Точно так же при необходимости мы можем уменьшить $c(1)$ и $c(D-1)$ до $\delta$ при $D>3$.
Тогда
$3n-4-2\delta \geqslant (D-1)(\delta+1)$
$D \leqslant 1+\frac{3n-4-2\delta }{\delta+1}$
Эту оценку можно незначительно улучшить, если увидеть, что $c(0)+c(1)+c(2) \geqslant \delta+2$ ($c(0)=1$, $c(1) \geqslant \delta$, $c(2) \geqslant 1$), аналогично
$c(1)+c(2)+c(3) \geqslant \delta+2,$
$c(D-3)+c(D-2)+c(D-1) \geqslant \delta+2,$
$c(D-2)+c(D-1)+c(D) \geqslant \delta+2.$
Тогда
$$D \leqslant 3\frac{n-2}{\delta+1}-1 \eqno{(1)}$$
Эта оценка достигается на некоторых графах. Рассмотрим такой граф диаметра $D=3k-1$, $k>1$, что $$c(r)= \left\{\begin{matrix}
\delta-1, r \equiv 1(\mod 3) \wedge r \notin \{1,D-1\},
\\ 
\delta, \; \; \; r \in \{1,D-1\},

\\ 
1, r \not\equiv 1(\mod 3) \wedge r \notin \{1,D-1\},
\end{matrix}\right.$$
где при всех $r$ все вершины из $S_r$ соединены между собой, со всеми вершинами из $S_{r-1}$, если $r>0$, и со всеми вершинами из $S_{r+1}$, если $r<D$. Очевидно, степень каждой вершины такого графа не менее $\delta$, а общее количество его вершин составит $n=k(\delta+1)+2,$ что в точности соответствует оценке $(1)$.

 Профиль  
                  
 
 Re: Оценка диаметра графа
Сообщение29.12.2015, 00:44 


13/05/14
476
alcoholist
У меня есть статья Wayne Goddard and Ortrud R. Oellermann «Distance in Graphs», непонятно где напечатанная, может это отрывок из книги или из лекции. Там есть много чего о диаметре.
Если укажете эл. адрес куда ее послать то вышлю по эл. почте.
Пока привожу отрывок из статьи, может вам пригодится.
Цитата:
We look next at upper bounds involving the minimum or maximum degree.
Theorem 1. For a graph $G$ of order $n$:
1. $diam(G) \leqslant (n - \Delta(G) + 1)$.
2. [71] $rad(G) \leqslant  (n - \Delta(G))/2 + 1$.
3. If $\delta(G) \geqslant n/2$, then $diam(G) \leqslant 2$.
and these bounds are sharp.

(Оффтоп)

P.S. Что-то рано Вы себя в старики записали :-)

 Профиль  
                  
 
 Re: Оценка диаметра графа
Сообщение29.12.2015, 09:35 


14/01/11
2916
Перечитал свои рассуждения, всё-таки обозначать всё на свете одной буквой было не лучшей идеей. Поправил.

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

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group