Почему в графах важна четность степеней вершин?

Чётность степеней вершин в графах важна по нескольким причинам:

• Определение общего количества связей в графе. education.yandex.ru Существует лемма о рукопожатиях, которая утверждает, что сумма степеней всех вершин графа всегда равна удвоенному числу его рёбер. education.yandex.ru Это позволяет быстро определить общее количество связей в графе по количеству связей каждого элемента. education.yandex.ru
• Сравнение графов. videouroki.net Часто можно доказать, что два графа не являются одинаковыми, подсчитывая степени вершин. videouroki.net Например, графы с одинаковым количеством вершин и рёбер, но с разными степенями вершин, не будут одинаковыми. videouroki.net
• Начертание графа. snq-teacher.ru Если все вершины графа чётные, то можно одним росчерком начертить граф, при этом движение можно начать с любой вершины и окончить в той же вершине. snq-teacher.ru Граф с двумя нечётными вершинами тоже можно начертить одним росчерком, но движение нужно начинать от любой нечётной вершины и заканчивать на другой нечётной вершине. snq-teacher.ru Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком. snq-teacher.ru

Пользователь

Время добавления