Граф есть

Cтраница 3

Связный граф G называется А-угольно-критическим, если в нем нет совершенных 2-паросочетаний, не содержащих А - угольников, но для каждой вершины v 6 V ( G) граф G - v имеет совершенное 2-паросочетание, не содержащее А - угольников. Очевидно, что Z - угольно-критические графы являются факторно-критическими. Одновершинный граф есть 0-угольно-критический и других 0-уголь-но - критических графов не существует. [31]

Применяемый способ выбора системы независимых контуров и сечений основан на построении фундаментального дерева в графе схемы. Используется полюсный граф, повторяющий структуру эквивалентной схемы. Фундаментальное дерево связного графа есть связный подграф, включающий р - 1 ребро и не имеющий циклов. Контуром & - й хорды называют подмножество ребер графа ( ветвей схемы), входящих в замкнутый контур, образуемый при подключении & - й хорды к дереву. Сечения образуются следующим образом: отделим часть вершин графа от остальных с помощью замкнутой линии сечения, проведя ее так, чтобы ни одно ребро не пересекалось более одного раза и при этом пересекалась одна и только одна ветвь дерева. Следовательно, каждому сечению соответствует определенная ветвь дерева. На рис. 4.10, а для примера приведена некоторая схема, а на рис. 4.10 6 - ее граф с выделенным жирными линиями фундаментальным деревом. Штрихом показаны линии сечения. [32]

Плоский граф - конечное множество простых топологически замкнутых линий, называемых ребрами, на 2-сфере, таких, что любая точка пересечения двух различных элементов этого множества является концом каждого из этих элементов. Ясно, что всякое подмножество плоского графа есть плоский граф. [33]

Структура наглядно изображает, как устроена система - из каких частей она состоит и как эти части связаны друг с другом. Математической, а в этом смысле наиболее абстрактной и универсальной, формой изображения структуры является граф. Граф есть совокупность вершин и дуг ( ребер), представляющих однонаправленные ( соответственно двунаправленные) связи между вершинами. Вершины графа отождествляются с элементами ( минимальными частями) системы, а дуги и ребра графа - - со связями между соответствующими элементами. [34]

Назовем маршрутом М ( х) величины х путь в управляющем графе операторной схемы из оператора S, вырабатывающего величину х, в оператор 5 (, воспринимающий величину х, причем ни один из промежуточных операторов маршрута не вырабатывает величину х в целом. Для фиксированных операторов S и St ( начального и конечного) в управляющем графе в общем случае существует множество маршрутов. Так как понятие маршрута включает в себя не только путь в управляющем графе, но и информационную связь, которую этот путь реализует, то каждому множеству маршрутов некоторой величины с фиксированными началом и концом соответствует дуга информационного графа / ( G) операторной схемы. Информационный граф есть ориентированный двудольный граф, состоящий из нескольких компонент ( односторонней) связности. Каждая такая компонента есть совокупность маршрутов одной и той же величины и носит название области действия этой величины. Две области действия несовместимы, если в каждой из них найдется информационная связь, причем начальный оператор некоторого маршрута одной связи окажется начальным или внутренним оператором некторого маршрута другой связи. [35]

Несколько совершенных графов. [36]

Несколько упомянутых ранее результатов могут быть сформулированы в терминах совершенства определенных графов. Двудольные графы, как легко видеть, совершенны. Из теоремы Кенига о хроматическом индексе двудольных графов ( см. теорему 1.4.15) следует, что реберные графы двудольных графов являются совершенными. Из минимаксной теоремы Кенига ( теорема 1.1.1) вытекает, что дополнение реберного графа для двудольного графа есть совершенный граф. [37]

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

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