2014 dxdy logo

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

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




 
 Утверждения о радиусе и диаметре графа
Сообщение23.06.2015, 20:09 
Предполагается, что граф связный

1.
Диаметр графа можно вычислить, как наибольший из эксцентриситетов вершин.
-- Верно. Диаметр графа $:=\max\limits_{u,v}d(u,v)$. Наибольший эксцентриситет $=\max\limits_{v}\max\limits_{u}d(u,v)$

2.
Если в графе G есть хоть одна вершина, то $diam(G)\leq|G|-1$, и бывают графы на $2015$ вершинах, на которых оценка достигается.
-- Верно, как пример просто цепочка из $2015$ вершин
Если в графе G есть хоть одна вершина, то $diam(G)\leq|G|$, и бывают графы на $2015$ вершинах, на которых оценка достигается.
-- Неверно, оценка не достигается.

4. Бывают графы на $2015$ вершинах, у которых радиус равен диаметру.
-- Верно. Например полный граф.

5.
Диаметр графа всегда строго больше радиуса.
-- Неверно, бывает равен
Диаметр графа всегда не меньше радиуса.
-- Верно, $\min\limits_{v}\max\limits_{u}d(u,v) \leq\max\limits_{v}\max\limits_{u}d(u,v)$

6.
Диаметр графа всегда не больше удвоенного радиуса. -- верно
Диаметр графа всегда не меньше удвоенного радиуса. -- неверно
Бывают графы, у которых диаметр строго больше удвоенного радиуса. -- неверно
Бывают графы, у которых диаметр строго меньше удвоенного радиуса. -- верно
Бывают графы, у которых диаметр равен удвоенному радиусу. -- верно

Где-то есть ошибка

 
 
 
 Re: Утверждения о радиусе и диаметре графа
Сообщение24.06.2015, 10:52 
Ошибок в классификации утверждений не вижу. Зато с форумом проблемы: первую формулу второго пункта отображает так же, как вторую, хотя они разные, что видно при наведении. Страницу перезагружал.
Изображение

 
 
 
 Re: Утверждения о радиусе и диаметре графа
Сообщение24.06.2015, 11:21 
NSKuber в сообщении #1030296 писал(а):
Зато с форумом проблемы:

Вот чуть что, - и сразу с форумом. Исправлено.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group