Две вершины, являющиеся концевыми для некоторого ребра, называются смежными вершинами. Два ребра, инцидентные одной и той же вершине, называются смежными ребрами. На рис. 11.1 / , pt—смежные вершины, а а1( a4—смежные ребра. , [c.258]
Далее введем представление неисправной системы."Отказ" вершины графа может быть интерпретирован известной в теории графов операцией замыкания вершины. При этом вершина удаляется из графа, а инцидентные ей ребра (дуги) определенным образом отождествляются. Тем самым предполагается, что информационные каналы не отказывают. Возможна и другая интерпретация - отказ вершины рассматривается одновременно как и отказ всех ее ребер (дуг). На первый взгляд второй подход кажется более адекватным, однако это не так. Предлагаемая ниже методология "работает" с обеими моделями неисправностей, но с точки зрения применяемого математического аппарата и интерпретации к прикладным задачам первая модель позволяет найти более изящные и экономичные решения, чем вторая. Основной довод в пользу выбора первой модели неисправностей связан с тем, что информационные каналы не отказывают не из-за каких-то особых свойств вершин графа, представляющего систему, а благодаря свойству отказоустойчивости самих информационных каналов. Т.е. это свойство закладывается при проектировании и реализации самих каналов. Таким образом, неисправности физически могут возникать как собственно в каналах, так и из-за отказов в вершинах, но логически эти неисправности парируются благодаря свойству отказоустойчивости каналов. [c.239]
ВЕРШИНА ГРАФА [graph node] — элемент точка) графа, обозначающий объект любой природы, входящий в множество объектов, описываемое графом. То же узел, точка. Изолированная В. — та, которая не является концевой точкой какого-либо ребра. Степень В. — число ребер, для которых она является концом (инцидентных к ней). В. называется нечетной, если ее степень — нечетное число, и четной, если ее степень — четное число степень изолированной В. — нулевая. [c.47]
ГРАФ (graph) — непустое конечное мн-во узлов (вершин), а также ребер (дуг), соединяющих пары разл вершин Если ребро L соединяет вершины V, и V, то принято говорить, что V, и V2 инцидентны L, а сами вершины называются соседними Если каждому ребру приписано направление, то Г называется ориентированным или орграфом Г обычно представляют в наглядной форме, изображая вершины точками, а ребра — линиями Такое представление полезно по причине наглядности, но не пригодно для машин- ной обработки При обработке на ЭВМ наиболее удобно представление Г в виде матрицы инцидентности Г — удобная модель математическая разл процессов, протекающих в логистических системах, и имеет ряд практических приложений См [c.39]
Вершина и ребро называются инцидентными друг другу, если вершина является для этого ребра концевой точкой. На рис. 11.1 вершина ря и ребро а3 инцидентны друг другу. [c.258]
На рис. 11.9 граф G ие является эйлеровым, так как вершина ра инцидентна тальк одному ребру. Если путь [c.263]