ПОИСК Статьи Чертежи Таблицы Некоторые комбииаториые свойства графов из "Особенности процессов многократного рассеяния " Настоящая глава, в которой формализм доведен до предела, может произвести неприятное впечатление. Читателю рекомендуется бегло с ней ознакомиться (например, просмотрев рисунки), с тем чтобы возвращаться к ней по мере надобности. [c.27] Выражаясь математически, можно сказать, что все эти понятия, вероятно, найдут свое место в стандартных рамках категории графов в соответствии с этим в п. 0.2.1 вводится определение гомоморфизма графов, — но дальше по этому пути я не продвинулся. [c.27] В дальнейшем нам будет удобно представлять себе граф как множество путей, снабл енное ассоциативной операцией, которая не всюду определена композиция с с двух путей с н с определена тогда и только тогда, когда конец пути с совпадает с началом пути с. Определен путь с , обратный к пути с (это путь, пробегаемый в обратном направлении ). Композиции с с и сс всегда определены их можно отождествить соответственно с началом и концом пути с. Такая точка зрения интересна потому, что нет нужды вводить множество вершин, которое выступает здесь как множество путей специального вида ( нулевых путей ). [c.28] Читатель может пропустить следующий параграф, который посвящен формализации этой идеи. Тем не менее необходимо остановиться на одном обозначении запись i е v (соответственно е а) обозначает, что линия i имеет вершину v своим началом (соответственно концом). [c.28] В последовательности аь аг,. .., а-п О композиция любых двух последовательных элементов определена, то существует единственный элемент а й2. .. йп О, являющийся композицией всех аи с произвольным расположением скобок. [c.29] Единица. Элемент се О называется единицей, если еа = а (соответственно ае = а) всякий раз, когда еа (соответственно ае) определено. [c.29] Обратный элемент. Говорят, что а является обратным к элементу а (или а является обратным к элементу а ), если аа и а а определены и являются единицами. Единственность обратного элемента (если он существует) очевидна, так как если а и а два обратных к а элемента, то композиция а аа определена и равна одновременно а и а (используем ассоциативность и определение единицы). [c.29] Определение группоида ). Группоидом называется множество О, снабженное ассоциативной (не всюду определенной) операцией, такой, что для всякого элемента а е О имеется обратный, обозначаемый а . [c.29] Действительно, если е — единица, то элемент (ее )е определен и равен одновременно е (так как ее есть единица) и е (так как е — единица). [c.29] Классы эквивалентности, определенные отношением 11), называются вершинами. Принадлежность элемента о к классу о (обозначается а е о) выражается словами о является началом а или концо.ч а К Из этого соглашения вытекает, что аЬ определен тогда и только тогда, когда конец элемента Ь совпадает с началом элемента а. [c.30] Если аа определен, т. е. начало и конец элемента а совпадают, то мы будем говорить, что а является петлей. [c.30] Вершина содержит единицу действительно, если а ео, то V содержит единицу а а, так как (а а)а определен. Она содержит только одну единицу если бы V содержала две единицы е и е, то е е- был бы определен. Но, согласно ), = е. Следовательно, е е определен и равен одновременно е и е. [c.30] На основании свойства у) мы условимся отождествлять множество вершин с множеством единиц группоида. [c.30] Очевидным следствием свойства 1) является тот факт, что отображение ф преобразует петли в петли. С другой стороны, ф сохраняет отношение эквивалентности 1) и, следовательно, преобразует вершины в вершины. [c.31] Элементы множества I — это линии графа. Элементы группоида О, порожденного множеством /, являются путями графа. [c.31] Петлей (ср. 0.1.2) называется путь, начало и конец которого совпадают. [c.31] Путь с является направленны.ч, если его можно представить в виде Аг г... 1р, где 4 принадлежат / (но не / ). [c.31] Циклы и законы сохранения для указанного выше графа. [c.33] Вернуться к основной статье