Свойство - граф
Cтраница 3
Рассмотрим алгоритм построения графа ранжировки уровней ребер линейной модели графа. Для выявления планарных свойств ЛМ графа необходимо построить граф ранжировки ее плоского чертежа. [31]
Схематически автономный конечный автомат может быть изображен в виде помеченного ориентированного графа G, вершинами которого являются элементы множества Q ( внутренние состояния), а дугами ( направленными ребрами) - пары ( g, g ( q)) - Каждая вершина помечена знаком у / ( д), который вырабатывается при выходе из вершины. При изучении интересующих нас свойств графа G метки никакого значения не имеют, поэтому мы далее их рассматривать не будем. [32]
В предыдущих главах наряду с другими представлениями графа в чисто иллюстративных целях часто использовались его изображения на плоскости. Это и понятно - исследование свойств графа с помощью рисунка удобно и наглядно. В данной главе представления графа на плоскости будут играть уже принципиальную роль, причем интересовать нас будут не любые изображения графа на плоскости, а вполне определенные. [33]
Для представления графов мы пользовались диаграммами, на которых точки или кружки изображали вершины, а прямолинейные отрезки или дуги кривых - ребра. Такие диаграммы очень удобны при исследовании свойств отдельных графов. Естественно поэтому спросить, что это на самом деле означает - представить граф с помощью диаграммы, и всякий ли граф может быть представлен таким образом. Читателю, которому нравится рисовать картинки и которого нисколько не беспокоит обоснование этого занятия, достаточно будет узнать, что он все делает правильно. [34]
Изложенные рассуждения показывают, что на современном этапе поисков доказательства гипотезы о восстановлении нет также оснований рассчитывать, что такое доказательство даст, кроме того, хороший алгоритм. Поэтому в следующих разделах будут рассмотрены такие свойства графов, которые являются восстанавливаемыми, но, по всей вероятности, не выявляются с помощью хороших алгоритмов. [35]
Может возникнуть вопрос: почему мы не называем такие графы 1-критическими. Дело в том, что их свойства, оказывается, близки свойствам бикритических графов. Например, 2-бикритический граф всегда содержит совершенное 2-паросочетание. [36]
Для задачи ПАСС стационарность разметки обеспечивается непрерывностью функции разметки, интерпретирующей схему анализа. Однако, как уже подчеркивалось, задачи анализа на верхней и нижней полуструктурах свойств графа программы принципиально различны. [37]
По условию задачи требуется раскрасить карту или неориентированный граф в минимальное число цветов так, чтобы никаких два соседних региона ( никакие две смежные вершины) не были одного цвета. Хотя в данный момент не требуется точно специфицировать формат исходной и выводимой информации, а также внутреннее представление данных, можно сообразить, какие свойства графа будут существенны для любой программы. Очевидно, нужно знать число вершин графа, уметь регулярным образом обращаться к вершинам, уметь раскрашивать вершины и узнавать их цвет, определять, являются ли две вершины смежными, и, наконец, нужно уметь порождать много различных цветов. Вопрос о конкретном способе определения смежности вершин целесообразно отложить. [38]
Увы, необходимо сформулировать ряд определений, чтобы в дальнейшем иметь возможность использовать основные понятия и терминологию теории графов. После этого мы дадим краткое введение в учение о полных подграфах, в теорию экстремальных графов ( которая изучает графы с запрещенными подграфами), в исследование свойств графов пересечений ( в которых вершинами являются множества, а непустые пересечения представляют смежность); будут определены также полезные операции на графах. [39]
 |
Сигнальный граф двух последовательно соединенных подсистем ХТС. [40] |
Если ХТС, по существу, является последовательной комбинацией двух более простых подсистем, сигнальный граф может отметить указанную эквивалентность и в тех случаях, когда это не отмечается системой совместных уравнений. Если сложному графу придается форма, которую можно разделить линией так, что все отрезки, пересекаемые ею, направлены слева направо, то ХТС может рассматриваться как последовательная комбинация двух более простых подсистем: одна слева от упомянутой линии, другая - справа. Это свойство графа, изображенного на рис. IV-62, называется декомпозицией сигнального графа. [41]
Число Ро ( 0) относится к структурным свойствам графа О. Это вытекает из замечаний об изоморфизме, приведенных в конце разд. В действительности большинство из свойств графов, рассматриваемых в этой книге, являются структурными и допускают определение с использованием лишь отношения инцидентности. [42]
Свойство Р графа G называется наследственным, если каждый подграф графа G также обладает этим свойством. Примерами наследственных свойств служат такие свойства графа, как вполне несвязность, ацикличность, двудольность. [43]
Остается много открытых вопросов, касающихся эволюции случайных графов. Результаты параграфа 2.1 показывают, что тонкие свойства докритических графов можно изучать простым и естественным путем, в том числе, и некоторые свойства таких графов вблизи критической точки. [44]
При изготовлении электромеханических систем их звеньям присущи производственный погрешности, которые в условиях массового производства носят случайный характер. В общем случае оценка влияния производственных погрешностей на показатели точности систем производится при помощи метода статистических испытаний. Во млогих случаях наряду с этим методом может быть использован и так называемый метод деревьев логических возможч ностей, основанный на свойствах графов. [45]
Страницы: 1 2 3 4