Cтраница 4
Пусть нам дан ориентированный граф. Скажем, что ориентированное ребро графа исходит из вершины ( 3 ( входит в вершину ( 3), если ( 3 - начало ( конец) данного ребра. Скажем, что ребро инцидентно вершине, если эта вершина является одним из концов данного ребра. [46]
Мультиграф и псевдограф.| Орграфы с тремя вершинами и тремя дугами. [47] |
Ориентированный граф, или орграф, D состоит из конечного непустого множества V вершин и заданного набора X упорядоченных пар различных вершин. Элементы из X называются ориентированными ребрами, или дугами. [48]
Граф, на каждом ребре которого определено направление, называется ориентированным. Ребра этого графа называются ориентированными ребрами, или дугами. [49]
Шерман [197, 198] и Шимамото [192] занимаются подсчетом некоторых графов, встречающихся в теоретической физике. Пересчитывая графы с взвешенными элементами и ориентированными ребрами, появляющиеся в задаче синхронизации двоичных сообщений, Гилберт [12] использует производящие функции комплексного аргумента. Задачи на подсчет графов фигурируют также в работе Хомского и Миллера [60] по математической лингвистике. [50]
Для ориентированного графа G можно построить ориентированный граф G, вершинами которого являются листовые множества G. Два листовых множества L и L2 соединяются ориентированным ребром ( L (, L2) в G есдп имеются ориентированные ребра от L к L % в G, Этот граф называется листовой композицией графа G. G является ациклическим графом, так как любой ориентированный цикл в нем дал бы ориентированный цикл в G, проходящий через несколько листов. [51]
Точкам цепи соответствуют некоторые узлы на сети. Проведенной цепи ставится в соответствие дерево с ориентированными ребрами, причем направление ориентации от источника к стоку. Дерево строится по звеньям, и производится последовательное присоединение очередного стока к построенному фрагменту дерева. [52]
Для ориентированного графа G можно построить ориентированный граф G, вершинами которого являются листовые множества G. Два листовых множества LI и Z-2 соединяются ориентированным ребром ( L4, L2) в G, если имеются ориентированные ребра от Lt к L, в G. Этот граф называется листовой композицией графа G. G является ациклическим графом, так как любой ориентированный цикл в нем дал бы ориентированный цикл в G, проходящий через несколько листов. [53]