Можем също да наречем теорията за ръкостискане като теорема за сумата от степени или лема за ръкостискане. Теорията за ръкостискане гласи, че сборът от степените на всички върхове за една графа ще бъде удвоен от броя на ръбовете, съдържащи се в тази графа. Символното представяне на теорията за ръкостискане е описано по следния начин:
Тук,
'd' се използва за указване на степента на върха.
'v' се използва за обозначаване на върха.
„e“ се използва за обозначаване на краищата.
Теорема за ръкостискане:
Има някои заключения в теоремата за ръкостискане, които трябва да бъдат направени, които са описани, както следва:
Във всяка графика:
- Трябва да има четни числа за сумата от степени на всички върхове.
- Ако има нечетни степени за всички върхове, тогава сумата от степени на тези върхове винаги трябва да остане четна.
- Ако има върхове с нечетна степен, тогава броят на тези върхове ще бъде четен.
Примери за теория на ръкостискането
Има различни примери за теория на ръкостискането и някои от примерите са описани по следния начин:
Пример 1: Тук имаме графика, която има степента на всеки връх като 4 и 24 ребра. Сега ще разберем броя на върховете в тази графика.
Решение: С помощта на горната графика получихме следните подробности:
Степен на всеки връх = 24
Брой ръбове = 24
Сега ще приемем, че броят на върховете е = n
бързо сортиране на java
С помощта на теоремата за ръкостискане имаме следните неща:
Сума от степен на всички върхове = 2 * Брой ръбове
Сега ще поставим дадените стойности в горната формула за ръкостискане:
n*4 = 2*24
n = 2*6
n = 12
Така в графиката G броят на върховете е = 12.
Пример 2: Тук имаме графика, която има 21 ребра, 3 върха от степен 4 и всички други върхове от степен 2. Сега ще открием общия брой върхове в тази графика.
Решение: С помощта на горната графика получихме следните подробности:
Брой върхове от степен 4 = 3
Брой ръбове = 21
Всички останали върхове имат степен 2
Сега ще приемем, че броят на върховете е = n
низ int
С помощта на теоремата за ръкостискане имаме следните неща:
Сума от степени на всички върхове = 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
пример за java здравей свят
Брой върхове от степен 5 = 4
Брой върхове от степен 4 = 5
Брой върхове от степен 3 = 4
Сега ще приемем, че броят на върховете от степен 2 е = n
С помощта на теоремата за ръкостискане имаме следните неща:
Сума от степени на всички върхове = 2 * Брой ръбове
Сега ще поставим дадените стойности в горната формула за ръкостискане:
4*5 + 5*4 + 4*3 + n*2 = 2*35
сортиране на масив в java
20 + 20 + 12 + 2n = 70
52+2n = 70
2n = 70-52
2n = 18
n = 9
По този начин, в графика G, броят на върховете от степен 2 е = 9.
Пример 4: Тук имаме графика, която има 24 ребра и степента на всеки връх е k. Сега ще разберем възможния брой върхове от дадените опции.
- петнадесет
- двадесет
- 8
- 10
Решение: С помощта на горната графика получихме следните подробности:
Брой ръбове = 24
Степен на всеки връх = k
np подложка
Сега ще приемем, че броят на върховете е = 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, което не е цяло число.
Следователно правилната опция е опция C.