Cтраница 3
Как и в теореме 7.5.1, мы замечаем, что однородный ориентированный граф не имеет дефицита; следовательно, он имеет суграф первой степени. [31]
Рассмотрим свойства операций объединения, пересечения, дополнения по отображению и соединения графов и определим структуры, которые образуют по этим операциям множества подграфов и суграфов. Использование различных свойств операций позволяет выполнять эквивалентные преобразования графов, а знание структур позволяет переносить на графы все результаты, известные в алгебре для структур данного типа. [32]
Двойственным образом назовем семейство ребер D ( Ei) покрывающим семейством ребер, если оно имеет хотя бы одно ребро в каждой вершине. H JEt является покрывающим суграфом для вершин из G. [33]
Наш результат может быть также сформулирован так, что ребра графа можно разбить на два непересекающихся класса, причем каждый класс представлен в каждой вершине, только если выполняются условия теоремы 13.2.3. Другая формулировка следующая. Будем говорить, что граф Н есть собственный покрывающий суграф, если он покрывает вершины G, но не содержит всех его ребер в каждой из вершин. Тогда G имеет собственный покрывающий суграф только при ограничениях теоремы 13.2.3. Теорема 13.2.2 показывает, что в этом случае G имеет два непересекающихся по ребрам минимальных покрывающих суграфа. [34]
Наш результат может быть также сформулирован так, что ребра графа можно разбить на два непересекающихся класса, причем каждый класс представлен в каждой вершине, только если выполняются условия теоремы 13.2.3. Другая формулировка следующая. Будем говорить, что граф Я есть собственный покрывающий суграф, если он покрывает вершины G, но не содержит всех его ребер в каждой из вершин. Тогда G имеет собственный покрывающий суграф только при ограничениях теоремы 13.2.3. Теорема 13.2.2 показывает, что в этом случае G имеет два непересекающихся по ребрам минимальных покрывающих суграфа. [35]
В этой главе исследуются свойства теоретико-множественных операций объединения, пересечения, соединения и дополнения над графами Бержа с точки зрения абстрактной теории множеств. Показано, что множество подграфов произвольного непустого графа образует дистрибутивную структуру по операциям объединения и пересечения графов, а множество суграфов произвольного графа по операциям объединения, пересечения и дополнения над графами является булевой структурой или булевой алгеброй. Соответствующие операций и их свойства легко обобщаются на смешанные графы. В заключение определяются однозначные функции на графах и приводятся их основные свойства. Теоретико-множественные операции используются при изучении алгебраических операций над графами и при разложении графов по алгебраическим операциям, а методы разложения графов, в свою очередь, являются фундаментом, на котором основаны теоремы и алгоритмы декомпозиции абстрактных автоматов. [36]
Считаем, что граф G, используемый в дальнейших рассуждениях, получен этим методом. Заметим, что ребра графа G, которые не имеют пересечений, не учитываются при построении матрицы RQ, так как их можно расположить в любом из полученных плоских суграфов. В дальнейшем эти ребра не рассматриваются. [37]
Наш результат может быть также сформулирован так, что ребра графа можно разбить на два непересекающихся класса, причем каждый класс представлен в каждой вершине, только если выполняются условия теоремы 13.2.3. Другая формулировка следующая. Будем говорить, что граф Н есть собственный покрывающий суграф, если он покрывает вершины G, но не содержит всех его ребер в каждой из вершин. Тогда G имеет собственный покрывающий суграф только при ограничениях теоремы 13.2.3. Теорема 13.2.2 показывает, что в этом случае G имеет два непересекающихся по ребрам минимальных покрывающих суграфа. [38]
Наш результат может быть также сформулирован так, что ребра графа можно разбить на два непересекающихся класса, причем каждый класс представлен в каждой вершине, только если выполняются условия теоремы 13.2.3. Другая формулировка следующая. Будем говорить, что граф Я есть собственный покрывающий суграф, если он покрывает вершины G, но не содержит всех его ребер в каждой из вершин. Тогда G имеет собственный покрывающий суграф только при ограничениях теоремы 13.2.3. Теорема 13.2.2 показывает, что в этом случае G имеет два непересекающихся по ребрам минимальных покрывающих суграфа. [39]
Рассмотрим теперь выделение в графе пересечений максимальных двудольных подграфов. Это необходимо, так как, согласно критерию Бадера, граф G плоский, когда граф G двудольный. Если двудольным оказывается только подграф Н графа G, то соответственно плоским является суграф Н графа G. В результате получаем разложение графа G на плоские суграфы. [40]
Каждой ветви первичной сети PS ( X, V) ставится в соответствие некоторая вероятность удаления данной ветви из PS. Разыгрывается t вариантов удаления ветвей из PS согласно заданным вероятностям. PS уменьшается, а для ветвей, входящих в PSj с наихудшим значением целевой функции, она увеличивается. Процедура построения t случайных суграфов PS повторяется до тех пор, пока относительная погрешность не станет меньше заданной величины или процесс не стабилизируется. [41]