"Сборник бихевиорационализма" - читать интересную книгу автора (Елизаров Роман)
Аксиома о сложении ребер в орграфах.
61.
Эта аксиома тесно связана с понятием ориентированных графов или как их называют для краткости, орграфов.
62.
Изложу несколько общеизвестных положений об орграфах. Итак, в некоторых задачах инцидентные ребру вершины неравноправны, они рассматриваются в определенном порядке. Тогда каждому ребру можно приписать направление от первой из инцидентных вершин ко второй. Направленные ребра часто называют дугами, а содержащий их граф ориентированным графом (граф, определяемый ранее называется неориентированным). Первая по порядку вершина, инцидентная ребру ориентированного графа, называется его началом, вторая – его концом. Говорят еще, что ребро ориентированного графа «выходит из начала и входит в конец».
Относительно путей в теории графов сложилась следующая терминология. Цитирую по Татту:
«Невырожденным путем в орграфе Г называется произвольная последовательность Р=(D1, D2,… Dn) где n больше или равно 1 и Dj – дуги орграфа Г, не обязательно различные, удовлетворяющие условию, что конец дуги Dj является началом дуги Dj+1, где j больше либо равно 1 и меньше или равно n. Начало дуги Dj называется j-й вершиной пути Р. Конец дуги Dn называется последней или (n+1)-й вершиной пути Р. Первая и последняя вершины пути Р, т. е. начало дуги D1 и конец дуги Dn, называют соответственно началом (истоком) и концом (стоком) пути Р. Число n называется длиной пути Р и обозначается через s(P)».
Из Адельсона-Вельского и Кузнецова:
«Путь Z называется ориентированным циклом (или просто циклом, когда ясно, что рассматриваются только ориентированные циклы), если он состоит более чем из одного элемента и его начало совпадает с его концом. Граф, не содержащий циклов, называется ациклическим.»
«Вершина графа называется начальной, если в нее не входит ни одно ребро, и конечной – если из нее не выходит ни одно ребро. Во всяком конечном ациклическом графе G есть хотя бы одна начальная и хотя бы одна конечная вершина. Действительно, все пути G конечны и имеют длину, не превосходящую числа его вершин, так как в путях ациклического графа вершины не могут повторяться. Поэтому существует максимальный путь (быть может, не единственный), который нельзя удлинить ни в начале, ни в конце. Его начало будет начальной вершиной G, а конец – конечной вершиной. Максимальным рангом R(v) вершины v ориентированного графа G назывыается максимальная из длин путей этого графа с концом в v. «…» Минимальным рангом r(v) вершины v ориентированного графа G называется минимум длин путей L (v0,…, v) с началом в какой-либо начальной вершине v0 графа G и с концом в рассматриваемой вершине v.»
Напрашивающийся пример циклического графа – системы с обратной связью.
63.
Итак, рассматриваемая мною аксиома связана с идеей ориентированного графа. Его пример: я говорю кучеру трогайся, кучер погоняет лошадь, я говорю это с целью погонять лошадь. Собственно ребро «я погоняю лошадь» может отсутствовать и вы его не мыслите. Фактически есть путь: я говорю кучеру трогаться за чем автоматически следует шаг, что тот погоняет лошадь. Аксиома о сложении раскрашенных ребер гласит, что ребро «я погоняю лошадь» равно сумме ребер «я говорю кучеру трогайся» и «кучер погоняет лошадь».