Как применяется теорема о рукопожатии в реальных графовых задачах?

Лемма о рукопожатиях (теорема) гласит, что в любом графе сумма степеней всех вершин равна удвоенному числу рёбер. foxford.ru skysmart.ru

Некоторые примеры применения леммы о рукопожатиях в реальных задачах:

• Задача о соединении телефонов. foxford.ru Нужно определить, можно ли соединить 15 телефонов проводами так, чтобы каждый был соединён ровно с пятью другими. foxford.ru Для решения строят граф, где вершины соответствуют телефонам, а рёбра — соединяющим их проводам. foxford.ru Затем подсчитывают количество рёбер, учитывая, что каждое из них учтено дважды (соединяет две вершины). foxford.ru Если полученное число нецелое, то такого графа не существует, а значит, и соединить телефоны требуемым образом невозможно. foxford.ru
• Задача о вассалах короля. urok.1sept.ru Нужно определить, может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств. urok.1sept.ru Решение базируется на том, что при построении графа, соответствующего условиям задачи, получают противоречие со следствием леммы о рукопожатиях о чётном количестве нечётных вершин графа. urok.1sept.ru
• Задача о 9 отрезках на плоскости. urok.1sept.ru Нужно определить, можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими. urok.1sept.ru Для решения строят граф, где вершинами будут отрезки. urok.1sept.ru Две вершины соединяют ребром только в том случае, если соответствующие отрезки пересекаются, то есть степень каждой вершины по условию задачи должна равняться 3. urok.1sept.ru

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