Вершина - степень
Cтраница 2
Можно предположить, что V 4 и что граф G не имеет вершин степени 2, поскольку если V 4 или в G имеется вершина степени 2, то вопрос о трехсвязности решается немедленно. В статье ( Хопкрофт, Тарьян [ 1971 А ]) описан метод разбиения графа на 2-связные компоненты за 0 ( V, E) действий. [16]
 |
Гомоморфные образы простой цепи Р4. [17] |
Теорема 12.26. Если G - связный п-хроматический граф, содержащий точно одну вершину степени больше п - 1, то G является п-реберно-критическим. [18]
Пусть корневое дерево с п ( п 2) висячими вершинами не имеет вершин степени 2, отличных от корня. [19]
Во-вторых, предположим, что ( связный) граф G ф К3 содержит вершину степени 2, а граф G получается из G сжатием двух ребер графа G, инцидентных этой вершине. [20]
В этих системах осуществляется связывание металл - металл, локализованное на ребрах, поскольку вершины степени 2 треугольника из атомов металла соответствуют 2 внутренним орбиталям, поставляемым каждым из 3 аномальных атомов металла, расположенных в вершинах. [21]
Тогда граф G - и - v либо кубический, либо имеет только по одной вершине степени 2 в каждом цветном классе. По предположению индукции, граф G - и - v содержит не менее 2 ( 4 / 3) - 2 совершенных паросочетаний. [22]
Ясно, что введение термина гомеоморфны удобно только с технической точки зрения - включение или удаление вершин степени 2 не имеет никакого отношения к планар-ности. [23]
Однако S не может содержать одновременно и 0, и п - 1, в противном случае, вершина степени п - 1 соединена со всеми остальными вершинами графа. В частности и с той, которая имеет степень 0, что невозможно. Рассмотрим функцию /: V - S, сопоставляющую каждой вершине графа G ее степень. Поскольку V п, то имеет место неравенство: V S. [24]
Наименьшим блоком с негамильтоновым реберным графом является тэта-граф с 8 вершинами, в котором расстояние между любой парой вершин степени 3 равно трем. [25]
Гра ф является плоским тогда и только тогда, когда он не содержит подграфа, изоморфного с точностью до вершин степени 2 одному из подграфов Понтрягина - Куратовского. [26]
Для определения числа несвязывающих тг - МО правила: 1) величина N0 не изменяется при из графа АУ вершины степени 1 и связанных с ней ребер; 2) N0 не изменится при замене в графе АУ цепи из четырех атомов одним ребром; 3) величина N0 не изменяется при удалении двух ребер и двух вершин из четырехчленного цикла, находящегося на периферийной части графа. [27]
Доказать, что если G - простой граф с максимальной степенью k и каждый цикл в нем проходит через вершину степени не выше k - 1, то граф G реберно - раскрашиваемый. Мы думаем, что в этом упражнении достаточно ограничиться нечетными циклами. [28]
 |
Пример не гамильтонова графа. [29] |
Но тогда ребра je и gd никак не могут принадлежать циклу С, поскольку в противном случае в нем появятся вершины степени три. Это вынуждает нас включить в цикл ребро ed, что приводит нас к противоречию: ребра, которые мы были вынуждены выбрать, образуют два несвязных цикла, а не один, существование которого мы предполагали. Вывод: граф, изображенный на рис. 7.10, не является гамильтоновым. [30]
Страницы: 1 2 3 4