Конечный граф

Cтраница 3

Теорема 2.5.4. В конечном графе G без петель и кратных ребер пусть / с есть длина длиннейшей простой цепи, а / о - максимальный индекс компонент по всем простым цепям. [31]

По теореме 1.6.1 локально конечный граф имеет порядок. [32]

По теореме 1.2.1 каждый конечный граф имеет четное число вершин нечетной степени. Так как это условие выполняется и для той компоненты G, которой принадлежит а0, то Ь0 должно принадлежать той же компоненте. Кроме того, легко видеть, что а0 и Ь0 должны остаться связанными в графе Н, полученном из G удалением части Н, в которой все локальные степени) четные. [33]

Сеть комплекса рассматривается как ориентированный конечный граф без контуров. [34]

Доказать, что для конечного графа с разделяющими ребрами существуют по крайней мере два листовых множества с одним соединяющим ребром. [35]

Теорема 6.6.3. Пусть в конечном графе все графы исключения с максимальным числом ребер сингулярны. [36]

Теорема 2.2.2. Если в конечном графе G ровно две вершины а0 и Ь0 имеют нечетную локальную степень, то они связаны. [37]

Граф для определения. [38]

Полное сопротивление схемы находится из конечного графа, который, кроме вершины-источника и вершины-стока, содержит в явном виде ветвь, для которой требуется определить обратную связь. Источник и сток изображают переменные напряжение и ток, отношением которых определяется искомое сопротивление. [39]

Алгоритм решения этой задачи для произвольного конечного графа дан в следующем параграфе. [40]

Теоремы о паросочетаниях для локально конечных графов зависят, как мы видели в предыдущей главе, от понятия дефицита множества, и это понятие также легко переносится на ориентированные графы. [41]

Гуйя-Ури [123] доказал, что всякий конечный граф, допускающий квазитранзитивную ориентацию, можно ориентировать транзитивно; проверка же квазитранзитивной ориентируемости данного графа G сводится к проверке того, является ли некоторый вспомогательный граф G, определяемый по графу G, бихро-матическим. [42]

Если после нескольких преобразований мы получим конечный граф, то можем воспользоваться следующей теоремой. [43]

Под термином мультиграф в дальнейшем понимается конечный граф, имеющий более одного ребра между, по крайней мере-одной парой смежных вершин, а под термином граф, когда это не вызывает недоразумений - конечный неориентированный граф ( или мультиграф), а также конечный направленный графг у которых отсутствуют петли. Химическую структуру, соответствующую такому графу, называют молекулярным графом, или химическим графом. [44]

Доказательство, По теореме 1.2.1 каждый конечный граф имеет четное число вершин нечетной степени. Так как это условие выполняется и для той компоненты G, которой принадлежит ао, то Ь0 должно принадлежать топ же компоненте. [45]

Страницы: 1 2 3 4