Cтраница 2
Прежде чем сформулировать принцип упрощения направленного графа с помощью вычислителя, целесообразно расширить понятие линейного графа, введенное в гл. Точнее, ам необходимо обобщить понятие соответствия между направленным графом и системой линейных алгебраических уравнений. С введением обобщенных графов топологические операции, выполнявшиеся нами с простыми графами, приобретают более широкое значение. [16]
В этом смысле взаимодействие между частицами и имеет обменный характер. Будем говорить, что частицы а, Ь, с, d являются участниками данного взаимодействия, а частица X - его переносчиком. Указанные процессы удобно изображать графически. Элементарные акты взаимодействия (46.44) и соответствующие ему простые графы на рис. 46.2, а служат своего рода кирпичиками, из которых по почти очевидным правилам можно построить любой сколь угодно сложный процесс, обусловленный данным взаимодействием. Фейнман, и все рисунки, подобные рис. 46.2, называются фейн-мановскими диаграммами. Однако, несмотря на всю красоту описанной обменной схемы взаимодействий, на первый взгляд может показаться, что она вообще не имеет права на существование. [17]
Более точно, графом G называется пара ( V ( G), E ( G)), где V ( G) - непустое конечное множество элементов, называемых вершинами, a E ( G) - конечное семейство неупорядоченных пар элементов из F ( G) ( не обязательно различных), называемых ребрами. Заметим, что употребление слова семейство говорит о том, что допускаются кратные ребра. О каждом ребре вида о, w говорят, что оно соединяет вершины v и w; значит, каждая петля v, v соединяет вершину v саму с собой. Хотя в этой книге нам придется иногда ограничиться простыми графами, всюду, где это возможно, мы будем доказывать наши результаты для общих графов. [18]
Нетривиальный граф G называется простым, если разложение GGlxG2 возможно лишь тогда, когда или GI, или G2 - тривиальный граф; граф G называется составным, если он не является простым. Сабидус-си [5] заметил, что декартово произведение графов коммутативно и ассоциативно. Так как он доказал, что каждый нетривиальный граф единственным образом можно представить в виде произведения простых графов, то ясно, что такое взаимно простые графы. [19]
Формулировка физической задачи в форме причина - следствие является в известном смысле произвольной. Можно выбрать переменные и составить формулировку по предварительной схеме, которая не изменяется при переходе от одной задачи к другой. Однако такие формальные методы приводят к очень сложному графу. В этой главе сначала выведем определенные формальные операции и затем, используя их в качестве основы, перейдем к другим формулировкам графов, которые часто дают более простые графы, более четко связанные с физическими задачами. [20]
На практике диаграммы ПЕРТ истолковываются несколько иначе, а именно дуги представляют этапы, а вершины изображают абстрактные события, указывающие начала или окончания этапов. С другой стороны, такое представление имеет важное преимущество перед первоначальным, поскольку приводит на практике к более простым диаграммам. Это происходит в силу того, что временная задержка с ц между началами этапов i и / является, вообще говоря, постоянной для данного i и совершенно не зависит от следующего этапа. В таких случаях подобное представление приводит на практике к более простым графам ( даже с учетом фиктивных вершин), в то время как представление, рассмотренное ранее, остается неизменным. [21]
На практике диаграммы ПЕРТ истолковываются несколько1 иначе, а именно дуги представляют этапы, а вершины изображают абстрактные события, указывающие начала или окончания этапов. С другой стороны, такое представление имеет важное преимущество перед первоначальным, поскольку приводит на практике к более простым диаграммам. Это происходит в силу Того, что временная задержка с ц между началами этапов г и / является, вообще говоря, постоянной для данного г и совершенно не зависит от следующего этапа. В таких случаях подобное представление приводит на практике к более простым графам ( даже с учетом фиктивных вершин), в то время как представление, рассмотренное ранее, остается неизменным. [22]
Химические связи в непредельном углеводороде определяют бинарное отношение на базисном множестве, состоящем из атомов углерода п атомов водорода. Это бинарное отношение описывается в терминах МГ. В графах такого типа степень вершины для ненасыщенного углеродного атома не больше трех, а степень каждой вершины, соответствующей водороду, равна единице. Кроме того, в соответствии с классической теорией химическое строение непредельных углеводородов может быть описано в терминах муль-тиграфов - структурных формул, которые содержат информацию о кратных связях. Если молекуле может быть сопоставлена хотя бы одна структурная формула со связями только между соседними атомами н без формальных зарядов, в которой каждая простая связь С-С инцидентна двум кратным или одной кратной связи и атому с неподелеппымн электронами, то такая молекула относится к классу сопряженных систем. Примеры сопряженных систем приведены на рис. 1.15. Обычно для описания сопряженных углеводородов используют более простые графы, которые определяют бинарное отношение только на множестве атомов углерода, участвующих в образовании сопряженной части молекулы. Наличие плоского фрагмента в сопряженном углеводороде дает возможность провести разбиение валентных АО углеродных атомов этого фрагмента на две группы. [23]
Поскольку орграф планарен тогда и только тогда, когда планарен соответствующий неориентированный граф, полученный игнорированием направления ребер, то достаточно рассматривать только неориентированные графы. Поскольку неориентированный граф планарен тогда и только тогда, когда все его связные компоненты планарны, достаточно рассматривать лишь связные неориентированные графы. Более того, легко видеть, что неориентированный граф планарен тогда и только тогда, когда все его двусвязные компоненты планарны. Поэтому, если неориентированный граф является разделимым, мы можем разложить его на двусвязные компоненты и рассматривать их отдельно. Наконец, поскольку параллельные ребра и петли всегда можно добавить к графу или удалить из него без нарушения свойства планарности, достаточно рассматривать только простые графы. [24]