Степень - вершина
Cтраница 2
Имеется 5 допустимых наборов степеней вершин. [16]
Для любого графа сумма степеней вершин равна удвоенному числу ребер. В конечном графе число нечетных вершин четно. [17]
Рассмотрим теперь графы со степенями вершин, не превышающими /, где t - фиксированное число. Первым барьером является выделение решающих свойств групп. [18]
Во всякой графе, все степени вершин которого равны четырем, найдется подграф, все степени вершин которого равны трем. [19]
Осталось рассмотреть случай, когда степень вершины v равна пяти и для вершин графа G, смежных с вершиной У, используются все пять цветов. Без ограничения общности можно считать граф G плоским, так что мы можем говорить о циклической упорядоченности смежных с v вершин. [20]
Осталось заметить, что и подсчет степени вершины, и проверка связности графа могут быть выполнены за полиномиальное время. [21]
Впоследствии были исследованы случайные графы с ограниченной степенью вершин. Однако при этом столкнулись с трудностями, когда, как было показано, свойства, связанные с циклической структурой модели, и физическая система оказываются несовместимыми ( [5], разд. В настоящее время рассматриваются модели, основанные на теории графов; в этих моделях исходят из графа G, имеющего структуру, близкую к структуре физической системы на конечной стадии некоторого процесса развития. [22]
Лемма об эстафете утверждает, что сумма степеней вершин произвольного графа G - ( V, Е) равна удвоенному числу его ребер. [23]
Работа Рида [ 187J посвящена подсчету графов, степени вершин которых делятся на заданное число, и связных графов. Риордан [188] каждому отображению множества п элементов в себя относит направленный граф и выводит рекуррентную формулу для количеств графов такого типа, имеющих заданное число компонент связности. К комбинаторным приложениям теории графов относится результат Харари [139] о взаимно однозначном соответствии между множеством неэквивалентных задач на перестановки с ограниченным положением ( см. [52], глава 7) и множеством неизоморфных графов с вершинами двух цветов; так как задача подсчета элементов второго множества ранее уже была решена им же [134] ( при помощи метода Пойя), то и задача пересчета первого множества, казавшаяся очень трудной, тем самым оказывается решенной. [24]
Лемма 3.2. Если в графе Gn, n степень белой вершины & не меньше m ( m n), а степени остальных белых вершин, равны п, то Gn, п имеет т-фактор. [25]
 |
Пример графа. w. W есть пара элементов и, v 6 V. [26] |
Число ребер, инцидентных с вершиной, называется степенью вершины. [27]
В § § 6 - 15 строится комплекс В локальных степеней вершин и определяется вершина, помещаемая в 1 - ю позицию. [28]
 |
Два двудольных графа. [29] |
Следующая теорема дает формулу для числа 2-раскрашенных графов со специальными степенями вершин. [30]
Страницы: 1 2 3 4