Произвольный граф

Cтраница 2

Пусть G - произвольный граф, двудольный или нет, v ( G) - реберное число независимости ( или, в иной терминологии, число паро-сочетания) графа G, т ( С) - число вершинного покрытия, a ( G) - вершинное число независимости и p ( G) - число реберного покрытия. [16]

Если G - произвольный граф ( отличный от К -) и G1 получается из G подразбиением ребра двумя вершинами, то граф G является 1-расширяемым тогда и только тогда, когда граф G 1-расширяемый. [17]

Пусть G - произвольный граф, содержащий или не содержащий совершенное паросочетание. Старое понятие, которое нам здесь пригодится, было введено в разд. Таким образом, множество A ( G) в декомпозиции Галлаи - Эдмондса графа G всегда является барьером. [18]

Пусть G - произвольный граф и пусть матрица В ( х) определена так, как описано выше. Граф G имеет совершенное паросочетание тогда и только тогда, когда det B ( x) не равен тождественно нулю. [19]

Построение пфаффовой ориентации. [20]

Пусть G - произвольный граф и G - какой-либо орграф, построенный из G путем некоторой ориентации его ребер. [21]

Часто необходимо отображать произвольный граф G в решетку G, таким образом, чтобы любые вершины х, у графа G размещались в узлах t, / решетки. В этом случае расстояние между вершинами х, у графа G принято определять по (1.19) как расстояние между соответственными узлами t, / решетки. [22]

Проблема нахождения рода произвольного графа, как и его толщины, весьма далека от своего решения. [23]

О хроматическом числе произвольного графа мало что можно сказать. Значительного прогресса можно добиться, если известна степень каждой вершины графа. [24]

Гипотеза Улама для произвольных графов остается еще не решенной. [25]

Операцию разности двух произвольных графов определим теперь следующим образом. [26]

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

О числе пересечений ребер произвольного графа, Вычислительные системы, Новосибирск, 1971, вып. [28]

Игра Шеннона происходит на произвольном графе с двумя выделенными вершинами. [29]

Сеть to и соответствующий ей граф Т. [30]

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