Теперь давайте обсудим некоторые важные параметры графов. В графах важно, что, как только мы свели задачу к графам, мы можем забыть все детали постановки задачи и изучать только графы. У графов есть важные параметры, анализ которых может помочь в решении нашей задачи. Давайте начнем с самых простых. Во-первых, у графа есть вершины и ребра, и есть два простых параметра: число вершин и число ребер. Они характеризуют размер графа: чем больше вершин, тем больше граф; чем больше ребер, тем больше у нас граф. А соотношение между этими величинами характеризует плотность графа: насколько много ребер на каждую вершину приходится в этом графе. У графа есть и другие важные параметры. Начнем с самых простых, и это степень вершины. Пусть v — это вершина графа, и степенью вершины v называется число ребер, входящих в эту вершину. Обозначается это через d от v. На этой картинке, на этом примере, например, степень вершины A — два, в A входят два ребра; степень вершины C — четыре, там четыре ребра; а степень вершины F — ноль. Такое тоже разрешается, в вершину могут не входить никакие ребра. Степень вершины — это важный параметр. Например, в социальных сетях она характеризует активность пользователя, насколько много у него друзей. А в транспортных сетях она характеризует загруженность узла, насколько много дорог входят в этот узел. Но есть ли связь степеней и вершин с другими параметрами графов? Оказывается, что есть. Оказывается, что сумма степеней всех вершин в графе равна в точности удвоенному числу ребер. Или можно написать это в виде формулы: сумма по всем вершинам степеней v — это удвоенное число ребер. Давайте это докажем. Для доказательства достаточно просто посмотреть на правильный параметр, на правильную величину. Эта величина — это количество концов ребер. Давайте посчитаем двумя способами одну и ту же величину — количество концов ребер в графе. С одной стороны, посчитать это легко: у каждого ребра два конца. Поэтому у нас есть: два умножить на количество ребер концов ребер. Хорошо. Но, с другой стороны, каждый конец ребра входит в какую-то вершину. Сколько концов ребер входит вершину v? В точности d от v, в точности степень вершины. И тогда общее количество концов ребер в графе — это сумма по всем вершинам степеней вершин. Таким образом, мы посчитали одну и ту же величину два раза, и результаты должны совпадать. Поэтому мы получаем, что сумма степеней вершин в графе — это удвоенное число ребер. Мы просто двумя способами посчитали количество концов ребер. Давайте сразу посмотрим на примере, как этим можно пользоваться. Давайте рассмотрим такую задачу. Пусть у нас есть граф на пяти вершинах, и сказано, что степени его вершин — 1, 2, 2, 3 и 3. Бывает ли такой граф? Давайте просто посчитаем сумму степеней вершин. Если такой граф есть, то сумма степеней его вершин — это в точности 11. Но, с другой стороны, это должно быть равно удвоенному числу ребер. И 11 не делится на два, удвоенное число ребер четно. Поэтому мы получили противоречие. В целом, мы доказали равенство, что сумма степеней вершин — это удвоенное число ребер. Из этого равенства сразу следует, что левая часть четная. Правая четная, значит, и левая должна быть четной. Или можно сказать это по-другому: в любом графе число вершин нечетной степени четно. Действительно, в графе есть вершины четной степени и нечетной. И вот в эту сумму степеней вершин вершины четной степени дают четный вклад, а вершины нечетной степени дают нечетный вклад. Чтобы сумма была четна, количество слагаемых, которые нечетны, должно быть тоже четно, иначе сумма кажется нечетной. Хорошо. Графы оказываются полезны в тех ситуациях, когда у нас есть объекты, связанные отношениями. Оказывается, что даже просто нарисовать картинку, нарисовать граф бывает полезно. Уже очень простые наблюдения могут помочь нам решить какие-то задачи. И в следующем уроке мы обсудим пути в графах.