Question

Плата 100 баллов, математика дискретная. Задание 7 Последовательность [1,1,....,1,2,3,...,2020] графическая? Ответ обоснуйте. Задание 8 Пусть G - связный граф. Докажите, что λ (G) не превосходит степени любой из вершин графа.​

Answer 1

Задание 7

Последовательность  [1,1,1,1,....,1,1,1,1,1,2,3,...,2020]  

___________________|_(2018 раз)_|__________  

графическая? Ответ обоснуйте.

Если последовательность графическая, то сумма ее членов четна.  

$\sum\limits_{i}x_i=(\sum\limits_{i=1}^{2018}1)+2+3+...+2020=2018*1+\dfrac{2+2020}{2}*(2020-1)=2018+1011*2019$

- число нечетное. А значит последовательность не графическая

Задание 8

Пусть G - связный граф. Докажите, что λ (G) не превосходит степени  

любой из вершин графа.

По определению, реберная связность λ (G) - минимальное число ребер, удаление которых из графа G превращает его в несвязный или тривиальный граф.

Понятно, что если удалить все ребра, инцидентные какой-либо вершине, граф станет несвязным или тривиальным (появится хотя бы одна новая компонента связности - эта вершина). Значит, если удалить все ребра, инцидентные вершине наименьшей степени, граф также станет несвязным или тривиальным. А значит минимальное число ребер, удаление которых из графа G превращает его в несвязный или тривиальный граф, не превосходит этого минимума - а значит и степени любой из вершин.

Answer 2

Задание 7: Да, данная последовательность является графической. Графическая последовательность - это последовательность неотрицательных целых чисел, которую можно представить в виде графа, где числа представляют степени вершин. Для того чтобы определить, является ли данная последовательность графической, можно воспользоваться следующим алгоритмом:

1. Упорядочить последовательность по убыванию.
2. Начать с самого большого числа и уменьшать его значение на 1, а также уменьшать значения следующих чисел на 1, пока не получится набор нулей или отрицательных чисел.
3. Если после этого все числа в последовательности стали нулями или отрицательными, то последовательность является графической.

Применяя этот алгоритм к данной последовательности [1, 1, ..., 1, 2, 3, ..., 2020], можно видеть, что она может быть преобразована в следующую последовательность: [0, 0, ..., 0, 1, 2, ..., 2019]. Это означает, что данная последовательность действительно является графической.

Задание 8: Для доказательства данного утверждения, что спектральный радиус (λ) связного графа G не превосходит степени (максимальной степени вершины), можно воспользоваться следующим рассуждением:

Пусть v - вершина графа G с максимальной степенью d. Рассмотрим собственный вектор x, соответствующий собственному значению λ. По определению собственного значения и вектора для матрицы смежности графа, имеем:

A * x = λ * x,

где A - матрица смежности графа G.

Заметим, что вектор x будет иметь компоненты x_i для каждой вершины i. Рассмотрим компоненту x_v, соответствующую вершине v. Тогда умножение матрицы A на вектор x дает нам следующее:

(A * x)_v = λ * x_v.

Так как v имеет максимальную степень d, то сумма x_i для всех вершин, смежных с v, не меньше d (по определению степени вершины). Поскольку вектор x является собственным вектором, сумма x_i для всех смежных вершин также равна λ * x_v. Следовательно, λ * x_v не меньше d.

Таким образом, мы получаем, что λ (спектральный радиус) не меньше d (максимальной степени вершины), что можно записать как λ (G) ≤ d. Это и доказывает утверждение о том, что спектральный радиус не превосходит степени любой из вершин графа G.