Дружелюбный Русский Алгоритмический язык, Который Обеспечивает Наглядность/Надёжность
Здесь показаны различия между двумя версиями данной страницы.
uporjadochenie_marshrutov_-_chem_pravee_tem..._pridumaj_sam [2012/04/07 13:27] Владислав Жаринов создано |
uporjadochenie_marshrutov_-_chem_pravee_tem..._pridumaj_sam [2012/04/10 08:31] (текущий) Владислав Жаринов [Варианты использования: разводим и сводим маршруты] - формат, уточнение определения |
||
---|---|---|---|
Строка 77: | Строка 77: | ||
===== Варианты использования: разводим и сводим маршруты ===== | ===== Варианты использования: разводим и сводим маршруты ===== | ||
- | Дракон-схема, как и БС, математически есть т.н. //**сводимый граф**//. Это значит, что у неё один конец, куда должны сойтись все маршруты, ведущие к нужному результату. Поэтому нужны и вершины-соединители маршрутов; пока на них останавливаться не будем. | + | Дракон-схема, как и БС, математически есть т.н. //**сводимый граф**//. Это значит, что у неё один конец, куда должны сойтись все маршруты, ведущие к нужному результату. Поэтому нужны и вершины-соединители маршрутов; на них мы останавливались [[http://drakon.su/vershiny_i_linii_sxem_-_smysl_v_grafike_i_tekste#razvetviteli_i_soediniteli_v_grebjonkax|здесь]]. |
+ | |||
+ | Разумеется, строгое определение графа как математического объекта не может исходить из смысла слова, которым его назвали - тем более обыденного... ;-) Поэтому укажем ещё на существенное именно для данного класса графов свойство: | ||
+ | |||
+ | //"Класс графов называется в теории графов аранжируемыми (в одной аксиоматике), сводимыми (в другой аксиоматике, у новосибирцев - [[http://drakon.su/biblioteka/start#knigi|Евстигнеева-Касьянова]]) и устремлёнными уже назван мной, с третьей стороны (по-третьему были введены; уже потом выяснилась эквивалентность этих классов). | ||
+ | |||
+ | Проще всего объяснить так: направленный граф с выделенной начальной вершиной, в котором разрешаются только такие циклы, при которых каждая дуга может быть классифицирована либо как прямая, либо как обратная (обратная дуга при этом идёт в доминатор той вершины, из которой выходит). | ||
+ | |||
+ | Совсем неформально можно сказать, что запрещается вход в середину цикла."// И. Е. Ермаков, [[http://forum.oberoncore.ru/viewtopic.php?p=44132#p44132|веб-сообщение]] | ||
Заметим, что можно и не сводить маршруты. Тогда схема нелинейного алгопроцесса будет деревом, у которого и главный, и каждый побочный маршруты имеют отдельный конец. Также и все цепочки, общие для разных маршрутов, дублируются. Циклы же разворачиваются — т.е. путь в цикле повторяется подряд столько раз, сколько итераций цикла (проходов по нему) будет при исполнении. Обычно заранее можно предсказать только максимальное и минимальное число итераций — так что и при описании развёрнутого цикла без РБНФ не обойтись. | Заметим, что можно и не сводить маршруты. Тогда схема нелинейного алгопроцесса будет деревом, у которого и главный, и каждый побочный маршруты имеют отдельный конец. Также и все цепочки, общие для разных маршрутов, дублируются. Циклы же разворачиваются — т.е. путь в цикле повторяется подряд столько раз, сколько итераций цикла (проходов по нему) будет при исполнении. Обычно заранее можно предсказать только максимальное и минимальное число итераций — так что и при описании развёрнутого цикла без РБНФ не обойтись. |