Граф есть

Cтраница 1

Граф есть совокупность непустого множества V, изолированного от него множества Е ( возможно пустого) и отображения Ф множества Е на V& V. Элементы множеств V и Е называются вершинами и ребрами графа соответственно, а Ф называется отображением ищиден-ции графа. [1]

Обход графа есть наименьшая из длин его простых циклов; окружение - наибольшая из таких длин. [2]

В получившемся графе есть путь из / во все вершины. [3]

Теорема 8.5. Граф есть реберный граф дерева тогда и только тогда, когда он является связным графом блоков, каждая точка сочленения которого принадлежит в точности двум блокам. [4]

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

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

Заметим, что контурно-связный граф есть 2-кон-турно - связный. Граф называется KLC-графом, если найдется такое k, что граф является / с-контурно-связным. [7]

Другими словами, производный граф есть фактор-граф, но относительно интервалов, а не бнкомпонент. [8]

Полный набор изоморфов молекулярного графа с тремя трехфунк-циональными узлами. [9]

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

Сумма степеней всех вершин графа есть четное число, равное удвоенному числу ребер. [11]

Сумма двух четных подграфов любого графа есть также четный подграф, так как степень s ( a) вершины а в подграфе Hl-Hz равна s s - 2s12, где % и s2 - степени этой вершины в подграфах Нг и Я2 соответственно, a s12 - степень вершины а в пересечении Нг П Нг. Поэтому четные подграфы образуют подпространство в пространстве всех подграфов, очевидно, совпадающее с подпространством, натянутым на все элементарные циклы. [12]

Бержа о том, что дополнение совершенного графа есть совершенный граф, верна. [13]

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

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

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