Cтраница 4
Для вершин орграфа существуют параметры, называемые полустепенью исхода, полу-степенью захода и степенью вершины. Полустепеныо исхода р вершины х называется число исходящих из нее ребер. Полустепеныо захода q вершины х называется число входящих в нее ребер. [46]
Подграф G удовлетворяет трем неравенствам, определяющим вершинный, реберный и локальный топологический ( степень вершины) ресурсы. Jlpn уточнении неравенств, определяющих ресурсы графа G, данная оценка хроматического числа может быть использована для произвольного графа. [47]
Пусть О ( X, А) - реберно-взвешенный неориентированный граф, а - степень вершины гг; в графе О. [48]
Если появление петель в графе недопустимо, то реализация множества целых чисел в качестве степеней вершин некоторого графа, вообще говоря, невозможна. Необходимо наложить более сильные требования на заданное множество целых чисел. Татт получил необходимые и достаточные условия, при которых данный граф содержит подграф, у которого вершины имеют заданные степени. [49]
Очевидно, что затрачиваемая работа зависит как от размера графа, так и от степеней вершин. [50]