Никакое ребро

Cтраница 4

Если маршрут имеет начальную вершину, по не имеет конечной вершины пли если он имеет конечную вершину, но по имеет начальной, то он называется односторонне-бесконечным. Если маршрут не имеет пи начальной, ни конечной вершины, то он называется двусторопне-бссконечны. Маршрут назовем нетривиальным, если он содержит хотя бы одно ребро; для систематичности рассуждений вводится еще нуль-маршрут, не содержащий, никаких ребер. [46]

Связный граф G. [47]

Несложно доказать, что в любом связном графе найдется подграф, являющийся деревом. Подграф в G, являющийся деревом и включающий в себя все вершины G, называется остовным деревом. Остовное дерево в графе G строится просто: выбираем произвольное его ребро и последовательно добавляем другие ребра, не создавая при этом циклов, до тех пор, пока нельзя будет добавить никакого ребра, не получив при этом цикла. Благодаря примеру 7.7, мы знаем, что для построения остовного дерева в графе из п вершин необходимо выбрать ровно п - 1 ребро. [48]

Каждое ребро может быть ориентированным редставляющим путь от одной вершины к другой в заданном направлении) л ибо неориентированным, что соответствует возможному пути от одной вершины к другой в обоих направлениях. Ребро, соединяющее вершину с ней самой, называется петлей. Возможно произвольное число ребер, соединяющих две фиксированные вершины; в то же время любому ребру соответствуют две вершины. Вершины, которым не соответствует никакое ребро, называются изолированными, голыми. Такие Г изображаются плоским чертежом, на котором вершины изображены точками, ребра - линиями, соединяющими эти точки. Ориентированные ребра ( иначе дуги) изображаются линиями со стрелочками, показывающими направление ориентации. [49]

Сначала допустим, что G обладает свойством Кенига. Тогда для каждого наибольшего паросочетания М графа G каждое ребро этого паросочетания инцидентно одной вершине в Т и наоборот. Поэтому множество D ( G) не может стягивать никаких ребер. Значит, граф G [ C ( G) ] также обладает свойством Кенига. [50]

Предположим сначала, что G имеет базисный граф В. Никакое ребро в B ( L ] не может быть излишним, так как иначе оно приводило бы к уменьшению В. В В существует только одно ребро, соединяющее пару листовых множеств L и L % в G ( и в В ], так как если одно такое ребро содержится в В, то другие, очевидно, являются излишними. Ребра из В образуют порождающий граф для G, и никакие ребра из В не могут бып. [51]

Тарелка, названная Юнифлакс, образована из S-образных элементов ( фиг. Элементы соединяются с помощью торцовых пластинок. Штамповка придает элементам такую жесткость, что при сборке колонн диаметром до 3 м никаких ребер не требуется; при диаметрах до 6 м по диаметру колонны перпендикулярно элементам ставится всего одно ребро. Кроме чисто конструктивных достоинств, на таких тарелках пар, выходящий из-под колпачков только с одной стороны, содействует направленному движению жидкости, благодаря чему снижается необходимый градиент жидкости и работа тарелки становится более стабильной. [52]

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

Поскольку множество М П E ( G - А) является наибольшим паросочетанием графа G - А, то немедленно получаем, что М Л Е ( Н) - совершенное паросочетание в Н, а. Из равенства (3.2.2) вытекает, что М П E ( G - А) М - А и, следовательно, М не содержит ребер, стягиваемых множеством А. Так как М покрывает все вершины множества А, то оно паросочета-ет А с G - А. Далее, очевидно, что ни одна вершина множества А не соединяется никаким ребром из М ни с одной вершиной множества C ( G) и что в А не найдется двух вершин, принадлежащих одной и той же компоненте G. Тем самым утверждение ( d) доказано. [54]

Множество ребер графа разбито на три непересекающиеся подмножества: R, Klt Ka. Ребрам каждого из этих подмножеств приписаны символы из У, х, у следующим образом. Каждому ребру из R приписан символ из У, всем ребрам из R приписаны различные символы, и все символы из У приписаны ребрам из R. Каждому ребру множества KI ( соответственно К2) приписаны символы из х ( соответственно у) так, что каждый символ может быть приписан нескольким ребрам, нек-рые символы могут быть не приписаны никаким ребрам. Если множество У пусто, то пусто и множество Кг. [55]

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