0 / 0 / 0
Регистрация: 08.05.2016
Сообщений: 73
1

Показать, что для любого связного графа справедливо неравенство

16.01.2017, 20:11. Показов 2146. Ответов 1
Метки нет (Все метки)

Показать, что для любого связного графа G выполняется:
diam(G) <= n - delta(G) + 1, где delta(G) — максимальная степень вершины
Если там немного писать, то распишите подробно, пожалуйста. Если решение большое, то подскажите формулы или опишите на словах, как решать.
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
16.01.2017, 20:11
Ответы с готовыми решениями:

Доказать, что в упорядоченном поле справедливо неравенство
Доброго времени суток. Помогите пожалуйста. Доказать, что в упорядоченном поле справедливо...

Доказать индукцией, что при любом натуральном числе k справедливо неравенство
Дан ряд b1,b2,..., где b1=b2=1 и для любого натурального числа больше двух k : bK = bk-1 + bk-2....

Показать что для любого целого m выражение (m-1)*m*(m+1) делится на 3
Показать, что для всех m от 1 до N (N задаёт пользователь) (m-1)*m*(m+1)/3 - целое число Помогите,...

Для любого натурального числа А найти наименьшее натуральное число n, такое что выполняется неравенство 2^n > А
Которая для любого натурального числа а находит наименьшее натуральное число n, такое что...

1
Эксперт по математике/физике
3818 / 2828 / 855
Регистрация: 19.11.2012
Сообщений: 5,898
17.01.2017, 09:03 2
Лучший ответ Сообщение было отмечено Mysterious Light как решение

Решение

Цитата Сообщение от _amper Посмотреть сообщение
где delta(G) — максимальная степень вершины
А n - порядок графа. Коротко так. Пусть длина простого пути от х до у равна m=dim(G): x=x0,x1,...,xm=y и степень вершины z равна Δ(G).
Дальше надо разобрать несколько случаев.
Вот один из них. Если ни z, ни соседи z не лежат среди иксов, то
n=>dim(G)+1+Δ(G)+1. Получилось даже с запасом.
Вот другой. Если z среди иксов, то не более двух соседей z среди иксов (продумайте это). Тогда
n=>dim(G)+1+Δ(G)-2. Тоже получилось, но уже тика в тику.
Остальные случаи самостоятельно разберите.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
17.01.2017, 09:03

Вычислить произведение элементов массива, для которых справедливо неравенство
Создать массив с элементами {z{}_{k,n}}_{}=n*f(k)+sin(k)*f(n), где n,k = 1 … N, N– целое число,...

Вычислить произведение всех значений функции у, для которых справедливо неравенство
Используя функцию F, построить массив у с эл-тами у= F(k). Вычислить произведение всех значений...

Вычислить произведение всех значений функции у, для которых справедливо неравенство
Вычислить произведение всех значений функции у, для которых справедливо неравенство 1&lt;у&lt;3,1....

Определить сколько в последовательности пар чисел, для которых справедливо неравенство |X|<|Y|.
Написать задачу двумя способами, применив операторы повтора WHILE и REPEAT : Дана непустая...

Формула Эйлера для не связного графа
Как это можно доказать? Добавлено через 20 минут p-q+r=k+1 , где k - количество компонент...

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


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
2
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.