Ми також можемо назвати теорію рукостискання теоремою суми ступенів або лемою рукостискання. Теорія рукостискання стверджує, що сума ступенів усіх вершин графа буде подвоєною кількістю ребер, які містяться в цьому графі. Символічне представлення теорії рукостискання описується наступним чином:
тут,
'd' використовується для позначення ступеня вершини.
'v' використовується для позначення вершини.
'e' використовується для позначення країв.
Теорема рукостискання:
У теоремі рукостискання є деякі висновки, які необхідно зробити, які описуються наступним чином:
У будь-якому графіку:
- Для суми ступенів усіх вершин повинні бути парні числа.
- Якщо для всіх вершин є непарні ступені, то сума ступенів цих вершин завжди повинна залишатися парною.
- Якщо є вершини, які мають непарний ступінь, то число цих вершин буде парним.
Приклади теорії рукостискання
Існують різні приклади теорії рукостискання, і деякі з них описані так:
приклад 1: Тут ми маємо граф, який має ступінь кожної вершини як 4 і 24 ребра. Зараз ми дізнаємося кількість вершин у цьому графі.
рішення: За допомогою наведеного вище графіка ми отримали такі деталі:
Степінь кожної вершини = 24
приховані програми
Кількість ребер = 24
Тепер припустимо, що кількість вершин = n
За допомогою теореми рукостискання ми маємо наступні речі:
Сума ступенів усіх вершин = 2 * Кількість ребер
Тепер ми помістимо дані значення у наведену вище формулу рукостискання:
n*4 = 2*24
n = 2*6
n = 12
Таким чином, у графі G кількість вершин = 12.
приклад 2: Тут ми маємо граф, який має 21 ребро, 3 вершини ступеня 4 і всі інші вершини ступеня 2. Тепер ми дізнаємося загальну кількість вершин у цьому графі.
найкраще авто в світі
рішення: За допомогою наведеного вище графіка ми отримали такі деталі:
Кількість вершин Ступеня 4 = 3
Кількість ребер = 21
Всі інші вершини мають ступінь 2
Тепер припустимо, що кількість вершин = n
За допомогою теореми рукостискання ми маємо наступні речі:
Сума ступенів усіх вершин = 2 * кількість ребер
Тепер ми помістимо дані значення у наведену вище формулу рукостискання:
3*4 + (n-3) * 2 = 2*21
12+2n-6 = 42
2n = 42 - 6
2n=36
n = 18
Таким чином, у графі G загальна кількість вершин = 18.
приклад 3: Тут ми маємо граф, який має 35 ребер, 4 вершини 5 ступеня, 5 вершин 4 ступеня і 4 вершини 3 ступеня. Тепер ми дізнаємося кількість вершин 2 ступеня в цьому графі.
рішення: За допомогою наведеного вище графіка ми отримали такі деталі:
Кількість ребер = 35
sdlc
Кількість вершин ступеня 5 = 4
Кількість вершин ступеня 4 = 5
Кількість вершин ступеня 3 = 4
Тепер припустимо, що кількість вершин ступеня 2 = n
За допомогою теореми рукостискання ми маємо наступні речі:
Сума ступенів усіх вершин = 2 * кількість ребер
Тепер ми помістимо дані значення у наведену вище формулу рукостискання:
4*5 + 5*4 + 4*3 + n*2 = 2*35
20 + 20 + 12 + 2n = 70
52+2n = 70
2n = 70-52
2n = 18
n = 9
назва міста в США
Таким чином, у графі G кількість вершин ступеня 2 = 9.
Приклад 4: Тут ми маємо граф, який має 24 ребра, а ступінь кожної вершини дорівнює k. Тепер ми дізнаємося можливу кількість вершин із наведених варіантів.
- п'ятнадцять
- двадцять
- 8
- 10
рішення: За допомогою наведеного вище графіка ми отримали такі деталі:
рядок додавання java
Кількість ребер = 24
Степінь кожної вершини = k
Тепер припустимо, що кількість вершин = n
За допомогою теореми рукостискання ми маємо наступні речі:
Сума ступенів усіх вершин = 2 * кількість ребер
Тепер ми помістимо дані значення у наведену вище формулу рукостискання:
N*k = 2*24
K = 48/прибл
Степінь будь-якої вершини обов'язково містить ціле число.
Тому ми можемо використовувати лише ті типи значень n у наведеному вище рівнянні, які дають нам ціле значення k.
Тепер ми перевіримо наведені вище параметри, поставивши їх на місце n один за одним таким чином:
- Для n = 15 ми отримаємо k = 3,2, що не є цілим числом.
- Для n = 20 ми отримаємо k = 2,4, що не є цілим числом.
- Для n = 8 ми отримаємо k = 6, що є цілим числом, і це допустимо.
- Для n = 10 ми отримаємо k = 4,8, що не є цілим числом.
Таким чином, правильний варіант - варіант С.