Cтраница 2
Теорема 5.2.1. Конечный граф с четными локальными степенями не может иметь разделяющих ребер. [16]
Для локально конечного графа можно сформулировать аналогичный результат. [17]
Пусть G - конечный граф, полученный из G ( V) с помощью указанных преобразований. [18]
При таком определении конечный граф может иметь бесконечное число вершин, но все они. Однако обычно в конечном графе число вершин также конечно. [19]
Теорема 7.8.6. Локально конечный граф имеет максимальное паросочетание. [20]
Теорема 7.9.5. Локально конечный граф имеет конечно минимальные разделяющие множества S, и любое такое множество согласовано для некоторого максимального паросочетания. [21]
Если G - конечный граф, то существуют базисные графы, и они могут быть получены при последовательном удалении ребер, как это указано выше. Если G имеет ориентированный гамильтонов цикл, то он может быть взят в качестве базисного графа. Если существует базисный граф, он не обязательно единственный. На рис. 8.4.1 любое радиальное ребро и ориентированный многоугольный цикл определяют базисный граф. [22]
Пусть G - конечный граф с р вершинами, х - ег хроматически многочлен2, К - целое положительное число. Дается комбинаторная интерпр тация целых положительных чисел ( - 1) РХ ( -) в терминах ациклически. В частности, устанавливается, что ( - 1) РХ ( - 1) число ациклических ориентации графа G. В качестве приложения перечисля ются помеченные3 ациклические орграфы. Строится алгебра полного биноми-i ального типа в смысле Дубиле - Рота - Стенли, которая порождает произ -; водящие функции, возникающие в контексте. [23]
При таком определении конечный граф может иметь бесконечное число вершин, но все они, кроме конечного числа, изолированные. Однако обычно в конечном графе число вершин также конечно. [24]
Теорема 7.9.5. Локально конечный граф имеет конечно минимальные разделяющие множества S, и любое такое множество согласовано для некоторого максимального паросочетания. [25]
Если G - конечный граф, то существуют базисные графы, и они могут быть получены при последовательном удалении ребер, как это указано выше. Если G имеет ориентированный гампльтонов цикл, то он может быть взят в качестве базисного графа. Если существует базисный граф, он не обязательно единственный. На рис. 8.4.1 любое радиальное ребро и ориентированный многоугольный цикл определяют базисный граф. [26]
Граф G является конечным графом, не имеющим циклов и имеющим по меньшей мере одно ребро. [27]
Теорема 1.2.1. В конечном графе число вершин нечетной степени четно. [28]
Теорема 1.3. В конечном графе число вершин нечетной степени четно. [29]
Теорема 1.2.1. В конечном графе число вершин нечетной степени четно. [30]