Cтраница 3
Если графы G и Н, не имеющие петель и кратных ребер, изоморфны, то для каждого d 0 число вершин степени d в графах G и Н одинаково. [31]
Граф G имеет не более одной вершины нечетной степени; если такой вершины нет, то должна существовать по крайней мере одна вершина бесконечной степени. [32]
Граф G имеет по более одной вершины нечетной степени; если такой вершины нет, то должна существовать по крайней мере одна вершина бесконечной степени. [33]
Существование такого подграфа означает, что можно взять один из двух подграфов Понтрягина - Куратовского, разделить некоторые из его ребер, введя вершины степени 2, и получить граф, изоморфный рассматриваемому подграфу. Для этого следует выделить цепи, граничные вершины которых имеют степени больше 2, а все степени внутренних вершин равны 2, и считать эти цепи одним ребром. [34]
Можно предположить, что V 4 и что граф G не имеет вершин степени 2, поскольку если V 4 или в G имеется вершина степени 2, то вопрос о трехсвязности решается немедленно. В статье ( Хопкрофт, Тарьян [ 1971 А ]) описан метод разбиения графа на 2-связные компоненты за 0 ( V, E) действий. [35]
Пусть G - связный граф, удовлетворяющий условию YI - Обозначим через ао вершину нечетной степени, если она существует; в противном случае а0 - вершина бесконечной степени. [36]
Очевидно, что свойства плоскости графа не изменяются, если некоторое ребро разделить на два введением новой вершины степени 2 или если два ребра, инцидентные вершине степени 2, заменить на одно, удалив при этом данную вершину. Такие рассуждения приводят к следующему определению: графы G и G называются изоморфными с точностью до вершин степени 2, если они изоморфнц или если они могут быть превращены в изоморфные графы с помощью указанных выше преобразований. [37]
Граф ( мультиграф без петель) называется псевдорегулярным степени т, если степень каждой его вершины равна либо т, либо 1; ребро, инцидентное вершине степени 1, называется висячим. Достаточность доказывается путем построения требуемых графов. [38]
Пусть G - связный счетный граф, являющийся полуэйлеровым, но не эйлеровым; тогда ( i) G содержит либо не более одной вершины нечетной степени, либо не менее одной вершины бесконечной степени; ( и) для каждого конечного подграфа Н графа G бесконечный граф Я ( описанный ранее) содержит ровно одну бесконечную компоненту. [39]
Доказательство теоремы 8.1.7. Мы докажем следующее, несколько более общее, утверждение индукцией по п: если G - такой двудольный граф с 2п вершинами, что каждый его цветной класс содержит одну вершину степени 2 и п - 1 вершин степени 3, то граф G содержит не менее 2 ( 4 / 3) - 1 совершенных паросочетаний. Сначала убедимся, что это утверждение действительно влечет утверждение теоремы. Пусть G - кубический двудольный граф с 2гг вершинами и пусть ребра е, е и ез инцидентны одной вершине графа G. Тогда если сформулированное утверждение справедливо, то каждый из графов G - е; содержит по меньшей мере 2 ( 4 / 3) - 1 совершенных паросочетаний. Поскольку каждое совершенное паросочетание графа G учтено точно в двух графах G - е -, то граф G содержит не менее 3 ( 4 / 3) - 1 ( 4 / 3) совершенных паросочетаний. [40]
Доказательство теоремы 8.1.7. Мы докажем следующее, несколько более общее, утверждение индукцией по п: если G - такой двудольный граф с 2п вершинами, что каждый его цветной класс содержит одну вершину степени 2 и п - 1 вершин степени 3, то граф G содержит не менее 2 ( 4 / 3) - 1 совершенных паросочетаний. Сначала убедимся, что это утверждение действительно влечет утверждение теоремы. Пусть G - кубический двудольный граф с 2гг вершинами и пусть ребра е, е и ез инцидентны одной вершине графа G. Тогда если сформулированное утверждение справедливо, то каждый из графов G - е; содержит по меньшей мере 2 ( 4 / 3) - 1 совершенных паросочетаний. Поскольку каждое совершенное паросочетание графа G учтено точно в двух графах G - е -, то граф G содержит не менее 3 ( 4 / 3) - 1 ( 4 / 3) совершенных паросочетаний. [41]
Но тогда Я не может быть подграфом такого n - минимального графа G, для которого G Я, так как для каждой компоненты С графа G - Е ( Н) множество вершин N ( C G) содержит по меньшей мере две вершины степени п в Я. [42]
Схему можно также представлять в виде ориентированного ациклического графа, у которого вершины входной степени 0 ( входы) помечены исходными переменными; остальные вершины ( функциональные элементы) помечены функциями из базиса ( при этом входная степень вершины должна совпадать с количеством аргументов ее пометки); ребра помечены числами, указывающими номера аргументов; вершины выходной степени 0 ( выходы) помечены переменными, описывающими результат работы схемы. УЙ, из которых ведут ребра в данную вершину v, вершина v получает значение у fv ( yi, , ykv), где fv - базисная функция, которой помечена вершина. При переходе к графу схемы мы опускаем несущественные присваивания, которые ни разу не используются на пути к выходным вершинам, так что они никак не влияют на результат вычисления. [43]
Предположим, что в связном графе найдется гамильто-нов цикл. Вершины степени 2 входят в цикл вместе с обоими инцидентными с ними ребрами. [44]
Аналогично, два различных ребра графа G называются смежными, если они имеют по крайней мере одну общую вершину. Вершина степени 0 называется изолированной вершиной, вершина степени 1 называется висячей ( или концевой) вершиной. [45]