За да разберем входящата и изходящата степен на връх, първо трябва да научим за понятието степен на връх. След това можем лесно да разберем входящата и изходящата степен на даден връх. Трябва да знаем, че входящата и изходящата степен могат да бъдат определени само в насочената графика. Можем да изчислим степента на връх с помощта на неориентиран граф. В неориентираната графа не можем да изчислим степента навътре и навън на даден връх.
Степен на върха
Ако искаме да намерим степента на всеки връх в графика, в този случай трябва да преброим броя на връзките, установени от даден връх с другия връх. С други думи, можем да определим степента на даден връх с помощта на изчисляване на броя на ръбовете, свързващи се с този връх. Степента на върха се обозначава с помощта на deg(v). Ако има проста графа, която съдържа n на брой върхове, в този случай степента на всеки връх ще бъде:
Deg(v) = n-1 ∀ v ∈ G
Един връх има способността да образува ребро с всички други върхове в графика, освен със себе си. Така че в една проста графика, степента на върха ще се открие по броя на върховете в графиката минус 1. Тук 1 се използва за самия връх, защото той не прави цикъл сам по себе си. Ако графиката съдържа върховете, които имат самообръщение, тогава този тип графика няма да бъде проста графика.
Пример:
В този пример имаме график, който има 6 върха, т.е. a, b, c, d, e и f. Върхът „a“ има степен 5, а всички останали върхове имат степен 1. Ако някой връх има степен 1, тогава този тип връх ще бъде известен като „краен връх“.
Има два случая на графики, в които можем да разгледаме степента на върха, които са описани по следния начин:
- Неориентирана графа
- Насочена графа
Сега ще научим подробно степента на върха в ориентиран граф и степента на върха в неориентиран граф.
Степен на връх в неориентиран граф
Ако има неориентиран граф, тогава в този тип графики няма да има насочен ръб. Примерите за определяне на степента на връх в неориентиран граф са описани, както следва:
Пример 1: В този пример ще разгледаме неориентирана графа. Сега ще открием степента на всеки връх в тази графика.
Решение: В горния неориентиран график има общо 5 броя върхове, т.е. a, b, c, d и e. Степента на всеки връх се описва, както следва:
- Горната графика съдържа 2 ребра, които се срещат във връх 'a'. Следователно Deg(a) = 2
- Тази графика съдържа 3 ребра, които се срещат във връх 'b'. Следователно Deg(b) = 3
- Горната графика съдържа 1 ребро, което се среща във връх 'c'. Следователно Deg(c) = 1. Върхът c е известен също като висящ връх.
- Горната графика съдържа 2 ребра, които се срещат във връх 'd'. Следователно Deg(d) = 2.
- Горната графика съдържа 0 ребра, които се срещат във връх 'e'. Следователно Deg(a) = 0. Върхът e може също да се нарече изолиран връх.
Пример 2: В този пример ще разгледаме неориентирана графа. Сега ще открием степента на всеки връх в тази графика.
Решение: В горния неориентиран график има общо 5 броя върхове, т.е. a, b, c, d и e. Степента на всеки връх се описва, както следва:
Степен на върха a = deg(a) = 2
Степен на върха b = deg(b) = 2
Степен на върха c = deg(c) = 2
java произволно число
Степен на върха d = deg(d) = 2
Степен на върха e = deg(e) = 0
В тази графика няма висящ връх, а връх 'e' е изолиран връх.
Степен на върха в насочен граф
Ако графът е насочен граф, тогава в този график всеки връх трябва да има входяща и изходяща степен. Да предположим, че има насочен граф. В тази графика можем да използваме следните стъпки, за да открием степента на входа, степента на излизане и степента на даден връх.
Степен на връх
Вътрешната степен на връх може да бъде описана като брой ръбове с v, където v се използва за обозначаване на крайния връх. С други думи, можем да го опишем като редица ръбове, идващи към върха. С помощта на синтаксиса deg-(v), можем да напишем степента на връх на връх. Ако искаме да определим степента на връх на върха, за това трябва да преброим броя на ръбовете, които завършват на върха.
Външна степен на връх
Изходящата степен на връх може да се опише като брой ръбове с v, където v се използва за обозначаване на началния връх. С други думи, можем да го опишем като редица ръбове, излизащи от върха. С помощта на синтаксиса deg+(v), можем да запишем изходящата степен на връх. Ако искаме да определим външната степен на връх, за това трябва да преброим броя на ръбовете, които започват от върха.
Степен на върха
Степента на връх се посочва с помощта на deg(v), което е равно на добавянето на входяща степен на връх и изходяща степен на връх. Символното представяне на степен на връх се описва, както следва:
Deg(v) = deg-(v) + deg+(v)
Пример 1: В този пример имаме график и трябва да определим степента на всеки връх.
Решение: За целта първо ще намерим степента на върха, степента на входа на върха и след това степента на излизане на върха.
Както можем да видим, че горната графика съдържа общо 6 върха, т.е. v1, v2, v3, v4, v5 и v6.
В степен:
Степен на връх v1 = deg(v1) = 1
Степен на връх v2 = deg(v2) = 1
Степен на връх v3 = deg(v3) = 1
Степен на връх v4 = deg(v4) = 5
Степен на връх v5 = deg(v5) = 1
Степен на връх v6 = deg(v6) = 0
Извън степен:
Изходяща степен на връх v1 = deg(v1) = 2
Изходяща степен на връх v2 = deg(v2) = 3
Изходяща степен на връх v3 = deg(v3) = 2
Изходяща степен на връх v4 = deg(v4) = 0
машинопис тип дата
Изходяща степен на връх v5 = deg(v5) = 2
Изходяща степен на връх v6 = deg(v6) = 0
Степен на върха
С помощта на дефиницията, описана по-горе, знаем, че степента на връх Deg(v) = deg-(v) + ти+(v). Сега ще го изчислим с помощта на тази формула, както следва:
Степен на връх v1 = deg(v1) = 1+2 = 3
Степен на връх v2 = deg(v2) = 1+3 = 4
Степен на връх v3 = deg(v3) = 1+2 = 3
Степен на връх v4 = deg(v4) = 5+0 = 5
Степен на връх v5 = deg(v5) = 1+2 = 3
Степен на връх v6 = deg(v6) = 0+0 = 0
Пример 2:
В този пример имаме насочен граф със 7 върха. Върхът 'a' съдържа 2 ребра, т.е. 'ad' и 'ab', които вървят навън. Следователно, връх 'a' съдържа изходящата степен, която е 2. По подобен начин, връх 'a' също има ребро 'ga', което идва към този връх 'a'. Следователно върхът 'a' съдържа входящата степен, която е 1.
Решение: Входящата и изходящата степен на всички горни върхове са описани, както следва:
В степен:
Степен на връх a = deg(a) = 1
Степен на връх b = deg(b) = 2
Степен на връх c = deg(c) = 2
Степен на връх d = deg(d) = 1
Степен на връх e = deg(e) = 1
Степен на връх f = deg(f) = 1
Степен на връх g = deg(g) = 0
Извън степен:
Изходяща степен на връх a = deg(a) = 2
Изходяща степен на връх b = deg(b) = 0
Изходяща степен на връх c = deg(c) = 1
Изходяща степен на връх d = deg(d) = 1
Изходяща степен на връх e = deg(e) = 1
Изходяща степен на връх f = deg(f) = 1
Изходяща степен на връх g = deg(g) = 2
Степен на всеки връх:
Знаем, че степента на връх Deg(v) = deg-(v) + ти+(v). Сега ще го изчислим с помощта на тази формула, както следва:
Степен на връх a = deg(a) = 1+2 = 3
Степен на връх b = deg(b) = 2+0 = 2
Степен на връх c = deg(c) = 2+1 = 3
Степен на връх d = deg(d) = 1+1 = 2
Степен на връх e = deg(e) = 1+1 = 2
Степен на връх f = deg(f) = 1+1 = 2
Степен на връх g = deg(g) = 0+2 = 2
Пример 3: В този пример имаме насочен граф с 5 върха. Върхът 'a' съдържа 1 ребро, т.е. 'ae', които вървят навън. Следователно, връх 'a' съдържа изходяща степен, която е 1. По подобен начин, връх 'a' също има ребро 'ba', което идва към този връх 'a'. Следователно върхът 'a' съдържа входящата степен, която е 1.
Решение: Входящата и изходящата степен на всички горни върхове са описани, както следва:
В степен
Степен на връх a = deg(a) = 1
Степен на връх b = deg(b) = 0
Степен на връх c = deg(c) = 2
Степен на връх d = deg(d) = 1
Степен на връх e = deg(e) = 1
Извън степен:
Изходяща степен на връх a = deg(a) = 1
Изходяща степен на връх b = deg(b) = 2
Изходяща степен на връх c = deg(c) = 0
конвертиране от char в int java
Изходяща степен на връх d = deg(d) = 1
Изходяща степен на връх e = deg(e) = 1
Степен на всеки връх:
Знаем, че степента на връх Deg(v) = deg-(v) + ти+(v). Сега ще го изчислим с помощта на тази формула, както следва:
Степен на връх a = deg(a) = 1+1 = 2
Степен на връх b = deg(b) = 0+2 = 2
Степен на връх c = deg(c) = 2+0 = 2
Степен на връх d = deg(d) = 1+1 = 2
Степен на връх e = deg(e) = 1+1 = 2
Пример 4: В този пример имаме график и трябва да определим степента, степента на входа и степента навън на всеки връх.
Решение: За целта първо ще открием степента на входа на върха и след това степента на излизане на върха.
Както можем да видим, че горната графика съдържа общо 8 върха, т.е. 0, 1, 2, 3, 4, 5 и 6.
В степен:
Степен на връх 0 = deg(0) = 1
Степен на връх 1 = deg(1) = 2
Степен на връх 2 = deg(2) = 2
Степен на връх 3 = deg(3) = 2
Степен на връх 4 = deg(4) = 2
Степен на връх 5 = deg(5) = 2
Степен на връх 6 = deg(6) = 2
Извън степен:
Изходяща степен на връх 0 = deg(0) = 2
Изходяща степен на връх 1 = deg(1) = 1
Изходяща степен на връх 2 = deg(2) = 3
Изходяща степен на връх 3 = deg(3) = 2
дълъг към низ java
Изходяща степен на връх 4 = deg(4) = 2
Изходна степен на връх 5 = deg(5) = 2
Външна степен на връх 6 = deg(6) = 1
Степен на всеки връх:
Знаем, че степента на връх Deg(v) = deg-(v) + ти+(v). Сега ще го изчислим с помощта на тази формула, както следва:
Степен на връх 0 = deg(0) = 1+2 = 3
Степен на връх 1 = deg(1) = 2+1 = 3
Степен на връх 2 = deg(2) = 2+3 = 5
Степен на връх 3 = deg(3) = 2+2 = 4
Степен на връх 4 = deg(4) = 2+2 = 4
Степен на връх 5 = deg(5) = 2+2 = 4
Степен на връх 6 = deg(5) = 2+1 = 3
Степенева последователност на графика
За да определим степенната последователност на графа, първо трябва да определим степента на всеки връх в графа. След това ще напишем тези степени във възходящ ред. Този ред/последователност може да се нарече степенна последователност на графика.
Например: В този пример имаме три графики, които имат 3, 4 и 5 върха, а степенната последователност на всички графики е 3.
В горната графика има 3 върха. Степента на последователност от тази графика е описана по следния начин:
В горната графика има 4 върха. Последователността на степените на тази графика е описана по следния начин:
В горната графика има 5 върха. Последователността на степените на тази графика е описана по следния начин: