Подграф

Cтраница 3

Подграф G не содержит циклов, каждая его вершина принадлежит некоторому пути, направленному на оа. [31]

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

Подграф Za, состоящий из всех ребер, инцидентных вершине а. Для графов без петель степень s ( а) вершины а есть число ребер в звезде Za. Очевидно, что сумма степеней всех вершин графа без петель равна удвоенному числу ребер. [33]

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

Подграф G ( R R), состоящий из ребер, соединяющих R и R, не имеет дефицита. [35]

Подграф SN с двумя стоками представлен в виде vlvmVn, где vi - источник, a vn иит - стоки подграфа. [36]

Максимальный двудольный подграф Н определяет в исходном графе G суграф Я, содержащий максимальное число непересекающихся ребер. [37]

Подграф уграфа G называется интервалом [18], если имеет единственную начальную вершину и она принадлежит каждой зоне уграфа G, содержащейся в этом подграфе. G), для любого уграфа G определен однозначно так называемый фактор-уграф I ( G) уграфа G относительно /, который получается из G стягиванием подграфов из 7 в уграфе G в вершины. Более точно, пусть Р - множество подграфов уграфа G с единственными начальными вершинами ( такие подграфы называются альтами [4]), образующее разбиение G. Множество вершин уграфа Gl - это множество начальных вершин подграфов из J3; а пара вершин р и q образует его дугу ( р, q) тогда и только тогда, когда в G существует дуга ( pt, q), где PI - вершина того подграфа из р, у которого р - начальная вершина. Начальной вершиной у Gt является р0, а конечными - начальные вершины подграфов из р, содержащие вершины из У. [38]

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

Подграфы сжатий графа С являются сжатиями подграфов графа О. [40]

Подграф сжатия графа О называется минором графа С. Таким образом, всякое сжатие графа О является минором этого графа и, с точностью до вершинного изоморфизма, всякий подграф графа С является минором графа О. [41]

Подграф второго прямого пути ( рис. 2.26, в) имеет два простых контура с передаточными функциями: WQI - Wi2Wi4 и WQS W32W34W35 - Эти контуры являются несоприкасающимися. [42]

Подграфом называют часть графа. [43]

Максимальным подграфом с ограниченными степенями считается подграф, имеющий наибольшее число ребер. [44]

Механическая цепь ( а и ее граф, представленный в двух конфигурациях ( б и в. [45]

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