Степени на насочени графи
В насочената графа има такива понятия катостепени на изходящи и входящи.
Извънстепенната степен m'(x) е броят на дъгите, излизащи от върха x. Входна полустепен m "(x) - броят на дъгите, влизащи във върха x. Примките се броят веднъж във всяка от полустепените.
Аналог на множеството неориентирани ръбове m(xi,xj) в насочен граф са две множества: m'(xi, xj) е броят на дъгите, насочени от xi към xj, m"(xi,xj) е броят на дъгите, насочени от xj към xi.
Броят на дъгите, излизащи от върха xi, се определя от сумата
а броят на дъгите, включени във върха хi е равен на
Следователно общият брой дъги на графиката:
Ако всички полустепени m'(x) и m"(x) са равни за всички x О X, тогава ориентираната графа G(X) се наричахомогенна графа от степен mn.
Ориз. 3.28. Хомогенни насочени графи
За такъв граф m = mn x n, където n е броят на върховете на графа G(X). Примери за хомогенни насочени графи са показани на фиг. 3.28.
| следваща лекция ==> | ||
| Степени на неориентирани графи | Характеристики на разстоянията в графики |
Не намерихте това, което търсихте? Google да ви помогне!