Cтраница 2
Каркасом или остовом неориентированного графа называется его суграф в виде дерева. [16]
Второе неравенство следует из того, что покрывающий суграф имеет в каждой вершине хотя бы одно ребро. Предполагается, что G не является суммой однократных петель. [17]
Теорема 18.2.2. Любой покрывающий суграф содержит минимальный покрывающий суграф. [18]
Второе неравенство следует из того, что покрывающий суграф имеет в каждой вершине хотя бы одно ребро. Предполагается, что G не является суммой однократных петель. [19]
Будем говорить, что часть Н является покрывающим суграфом графа G ( или покрывает вершины графа G), если любая вершина графа G является концом по крайней мере одного ребра из Я. [20]
Теорема 13.2.2. Любой покрывающий су граф содержит минимальный покрывающий суграф. [21]
Теорема 13.2.3. Для того чтобы граф G имел такой покрывающий суграф II, что его дополнение П также является покрывающим суграфом, необходимо и достаточно, чтобы G не имел концевых ребер и никакая его связная компонента не состояла из одного простого цикла нечетной длины. [22]
Берж [23], А. А. Зыков [183], используют три понятия: суграф, подграф и часть графа. [23]
Достаточно показать, что любой связный граф G имеет минимальный покрывающий суграф. [24]
С), удовлетворяют условиям ( 7.5 8), имеет однородный суграф первой степени. [25]
Кроме того, для смешанных графов можно ввести понятие множества подграфов и множества суграфов данного графа и обобщить результаты, полученные для графов Бержа. [26]
Таким образом, теорема 7.4.3 дает необходимое и достаточное условие для того, чтобы G имел такой суграф. [27]
Причем ребра ГЦ не принадлежат ни G0, ни G0, хотя их можно отнести к любому из суграфов. [28]
Теорема 13.2.3. Для того чтобы граф G имел такой покрывающий суграф II, что его дополнение П также является покрывающим суграфом, необходимо и достаточно, чтобы G не имел концевых ребер и никакая его связная компонента не состояла из одного простого цикла нечетной длины. [29]
Теорема 7.5.3. Почти однородный граф G, в котором отклонения, определяемые в (7.5.6), удовлетворяют условиям (7.5.8), имеет однородный суграф первой степени. [30]