Графы | Степень вершины | Лемма о рукопожатиях | Компоненты связности

• В видео обсуждается теория графов, которая возникла из задачи о переводе задач в графы и изучении их характеристик.  

• Вершины и ребра графа определяются как объекты и связи между ними соответственно.  

• Степень вершины графа показывает, сколько ребер выходит из данной вершины.  

• Лемма рукопожатия утверждает, что сумма степеней вершин графа делится на два.  

• Следствием этой леммы является то, что если сумма степеней графа нечетное число, то граф не существует.  

• Граф называется связанным, если из любой вершины можно дойти до любой другой по ребрам.  

• Теорема утверждает, что если у графа n вершин и степень каждой вершины хотя бы минус один пополам, то граф будет связанным.  

• Доказательство этой теоремы проводится методом от противного.