7. ЭЙЛЕРОВЫ ЦЕПИ И ЦИКЛЫ
Рассматриваемая в этой главе задача является одной из самых старейших в теории графов. В городе Кенигсберге (ныне Калининград) имелось семь мостов, соединяющих два берега реки Преголь, и два основа на ней друг с другом (рис. 7.1а). Требуется, начав путешествие из одной точки города пройти по всем мостам по одному разу и вернуться в исходную точку.
Если поставить в соответствие мостам ребра, а участкам суши — вершины, то получится граф (точнее псевдограф), в котором надо найти простой цикл, проходящий через все ребра. В общем виде эта задача была решена Эйлером в 1736 г.
Определение 7.1. Эйлеровой цепью в неориентированном графе G называется простая цепь, содержащая все ребра графа G . Эйлеровым циклом называется замкнутая Эйлерова цепь. Аналогично, эйлеров путь в орграфе G — это простой путь, содержащий все дуги графа G . Эйлеров контур в орграфе G — это замкнутый эйлеров путь. Граф, в котором существует эйлеров цикл, называется эйлеровым .
Простой критерий существования эйлерова цикла в связном графе дается следующей теоремой.
Теорема 7.1. (Эйлер) Эйлеров цикл в связном неориентированном графе G ( X , E ) существует только тогда, когда все его вершины имеют четную степень.
Доказательство. Необходимость. Пусть μ — эйлеров цикл в связном графе G , x — произвольная вершина этого графа. Через вершину x эйлеров цикл проходит некоторое количество k ( k ≥ 1) раз, причем каждое прохождение, очевидно, включает два ребра, и степень этой вершины равна 2 k , т.е. четна, так как x выбрана произвольно, то все вершины в графе G имеют четную степень.
Достаточность. Воспользуемся индукцией по числу m ребер графа. Эйлеровы циклы для обычных (не псевдо) графов можно построить начиная с m =3.Легко проверить, что единственный граф с m =3, имеющий все вершины с четными степенями, есть граф K 3 (рис. 7.2). Существование эйлерова цикла в нем очевидно. Таким образом, для m =3 достаточность условий доказываемой теоремы имеет место. Пусть теперь граф G имеет m >3 ребер, и пусть утверждение справедливо для всех связных графов, имеющих меньше, чем m ребер. Зафиксируем произвольную вершину a графа
G и будем искать простой цикл, иду-
щий из a в a . Пусть μ ( a , x ) — простая
цепь, идущая из a в некоторую верши-
ну x . Если x ≠ a , то цепь μ можно про-
должить из вершины x в некотором на-
правлении. Через некоторое число та-
ких продолжений мы придем в верши-
ну z X , из которой нельзя продлить
полученную простую цепь. Легко ви-
деть, что z = a так как из всех остальных вершин цепь может выйти (четные степени!); a в a она начиналась. Таким образом, нами построен цикл μ , идущий из a в a . Предположим, что построенный простой цикл не содержит всех ребер графа G . Удалим ребра, входящие в цикл μ , из графа G и рассмотрим полученный граф G ′ ( X , E ′ ) . В графе G ′ все вершины имеют
четные степени. Пусть G 1 ′ , G 2 ′ . G k ′ — компоненты связности графа G ′ , содержащие хотя бы по одному ребру. Согласно предположению индукции все эти компоненты обладают эйлеровыми циклами μ 1 , μ 1 , …, μ k соответственно. Так как граф G связан, то цепь μ встречает каждую из компонент G 1 ′ , G 2 ′ . G k ′ . Пусть первые встречи цикла μ с компонентами
G 1 ′ , G 2 ′ . G k ′ происходят соответственно в вершинах x 1 , x 2 , …, x k . Тогда простая цепь
ν ( a , a )= μ ( a , x 1 ) U μ 1 ( x 1 , x 1 ) U μ ( x 1 , x 2 ) U … U μ k ( x k , x k ) U μ ( x k , a )
является эйлеровым циклом в графе G . Теорема доказана.
Замечание. Очевидно, что приведенное доказательство будет верно и для псевдографов, содержащих петли и кратные ребра (см. рис. 7.1,а).
Таким образом, задача о кенигсбергских мостах не имеет решения, так как соответствующий граф (см. рис. 7.1,б) не имеет эйлерова цикла из-за нечетности степеней все вершин.
Отметим, что из существования эйле-
рова цикла в неориентированном гра-
фе G не следует связность этого графа.
Например, неориентированный граф
G на рис. 7. 3 обладает эйлеровым циклом и вместе с тем несвязен. Совершенно также, как теорема 7.1, могут быть доказаны следующие
Теорема 7.2. Связный неориентированный граф G обладает эйлеровой цепью тогда и только тогда, когда число вершин нечетной степени в нем равно 0 или 2, причем если это число равно нулю, то эйлерова цепь будет являться и циклом.
Теорема 7.3. Сильно связный орграф G ( X , E ) обладает эйлеровым контуром тогда и только тогда, когда для любой вершины x X выполняется
Можно также обобщить задачу, которую решал Эйлер следующим образом. Будем говорить что множество не пересекающихся по ребрам про-
стых цепей < μ i , i = 1, m >( μ i Iμ j = , i ≠ j ) графа G покрывает его, если
все ребра графа G включены в цепи μ i . Нужно найти наименьшее количество таких цепей, которыми можно покрыть заданный граф G .
Если граф G — эйлеров, то очевидно, что это число равно 1. Пусть теперь G не является эйлеровым графом. Обозначим через k число его вершин нечетной степени. По теореме … k четно. Очевидно, что каждая вершина нечетной степени должна быть концом хотя бы одной из покрывающих G цепей μ i . Следовательно, таких цепей будет не менее чем k /2. С другой стороны, таким количеством цепей граф G покрыть можно. Чтобы убедиться в этом, расширим G до нового графа G ′ , добавив k /2 ребер E ′ , соединяющих различные пары вершин нечетной степени. Тогда G ′ оказывается эйлеровым графом и имеет эйлеров цикл μ′ . После удаления из μ′ ребер E ′ граф разложится на k /2 цепей, покрывающих G . Таким образом, доказана
Теорема 7.4. Пусть G — связный граф с k >0 вершинами нечетной степени. Тогда минимальное число непересекающихся по ребрам простых цепей, покрывающих G , равно k /2.
Алгоритм построения эйлерова цикла
Для начала отметим, что теорема 7.1 также дает метод построения эйлерова цикла. Здесь мы рассмотрим несколько иной алгоритм.
Пусть G ( X , E ) — связный неорентированный граф, не имеющий вершин нечетной степени. Назовем мостом такое ребро, удаление которого из связного графа разбивает этот граф на две компоненты связности, имеющие хотя бы по одному ребру.
1 ° . Пусть a — произвольная вершина графа G . Возьмем любое ребро e 1 =( a , x 1 ) , инцидентное вершине a, и положим μ = < e 1 >.
2 ° . Рассмотрим подграф G 1 ( X , E\ μ 1 ). Возьмем в качестве e 2 ребро, инцидентное вершине x 1 и неинцидентное вершине a , которое также не является мостом в подграфе G 1 (если такое ребро e 2 существует!). Получим про-
3 ° . Пусть e 2 = ( x 1 , x 2 ), x ≠ a . Рассмотрим подграф G 2 ( X , E\ μ 2 ) и удалим из него все изолированные вершины. В полученном подграфе G 2 ′ выберем
ребро e 3 E\ μ 2 , инцидентное вершине a , которое не является мостом в подграфе G 2 ′ (если такое ребро e 3 существует!). Получим простую цепь
Продолжая указанный процесс, мы через конечное число шагов получим эйлеров цикл μ = < e 1 , e 2 , …, e n >, где n — число ребер графа G ( X , E ).
Обоснование алгоритма
Предположим, что уже построена простая цепь μ k -1 = < e 1 , e 2 , …, e k -1 >для
k ≥ 2 методом, указанным в алгоритме. Пусть e k -1 = ( x k -2 , x k -1 ) и x k -1 ≠ a . Рассмотрим подграф G k ′ − 1 , который получается из подграфа G k -1 ( X , E\ μ k -1 )
удалением всех изолированных вершин. Вершина x k -1 в этом подграфе G k ′ − 1 имеет нечетную степень, поэтому существует по крайней мере одно
ребро e k E\ μ k -1 , инцидентное x k -1 . Если это ребро единственное, то оно не является мостом в графе G k ′ − 1 . В противном случае вершина a будет свя-
зана с некоторой вершиной y G k ′ − 1 единственной цепью, содержащей
ребро e k , что противоречит существованию эйлерова цикла в графе G . Поскольку e k — не мост, то процесс можно продолжать, взяв μ k =μ k − 1 U < e k >.
Если ребро e k не единственное инцидентное вершине x k -1 , то среди этих ребер есть по крайней мере одно, не являющееся мостом. В противном случае один из этих мостов e k ′ можно выбросить так, что вершины x k -1 и a
попадут в разные компоненты связности графа G k ′ − 1 . Если x k -1 принадле-
жит компоненте M , то в этой компоненте все вершины имеют четную степень, поэтому существует эйлеров цикл в M , проходящий через x k -1 . Этот цикл содержит все ребра, инцидентные x k -1 и принадлежащие
( E \ μ k − 1 ) \ < e k ′ >, являющиеся одновременно мостами. Получено противо-
речие, так как ребра из эйлерова цикла мостами быть не могут. Итак, в рассмотренном случае существует ребро e k , инцидентное вершине x k -1 и не являющееся мостом. Значит, и в этом случае процесс можно продолжать, взяв
Из предыдущего следует, что процесс нельзя продолжать тогда и только тогда, когда мы попадем в вершину a , причем степень вершины a относительно непройденных ребер равна нулю. Докажем, что в этом случае построенный цикл μ — простой цикл. Покажем, что μ содержит все ребра графа G . Если не все ребра графа G принадлежат μ , то не принадлежащие μ ребра порождают компоненты связности C 1 , …, C m ( m ≥ 1) в подграфе G ′ ( X , E \ μ ). Пусть компонента C i , 1 ≤ i ≤ m соединяется с циклом μ в вер-
шине y i . Если существует ребро e μ , такое, что e =( y i , a ), то при построении цикла μ было нарушено правило выбора ребра e , что невозможно. Если часть цикла μ , соединяющая y i и a , состоит более чем из одного ребра, то первое ребро этой части e ′ = ( y i , y i + 1 ) было мостом, и поэтому было нарушено правило выбора e ′ , что невозможно. Итак, непройденных ребер быть не может, поэтому μ — эйлеров цикл.
8.НАХОЖДЕНИЕ КРАТЧАЙШИХ ПУТЕЙ В ГРАФЕ
В этом параграфе рассматриваются ориентированные графы G ( X , E ) каждой дуге e E которого ставится в соответствие вещественное число l ( e ). Т.е. на множестве Е создана функция l : E → R . Такой граф принято называть нагруженным . Само число l называется весом дуги.
Можно увидеть аналогию между, например, картой автомобильных или железных дорог. Тогда множество вершин Х будет соответствовать городам, множество дуг – магистралям, соединяющим города, а веса – расстояниям. (На практике, при этом, фактически получится неориентированный граф).
В связи с изложенной аналогией будем называть веса дуг расстояниями.
Определение 8.1. Пусть имеется последовательность вершин x 0 , x 1 , …, x n , которая определяет путь в нагруженном графе G ( X , E ), тогда длина этого
пути определяется как ∑ l ( x i − 1 , x i ) .
Естественный интерес представляет нахождение кратчайшего пути между двумя заданными вершинами x и y.
Алгоритм Форда отыскания кратчайшего пути.
Будем предполагать, что все расстояния в графе положительны. (Если это не так, то ко всем весам можно всегда добавить такую константу, что все эти веса станут положительными).
Пусть мы ищем путь от вершины x 0 к вершине x n . Будем каждой вершине x i ставить в соответствие некоторое число λ i по следующим правилам. 1 ° Положим λ 0 = 0, λ i = ∞ (достаточно большое число) для i > 0.
Вариант 8: задания 1,2,3,4,5,9,10,11,12,13,14,15. Доказать тожества, используя только определения операций над множествами
Доказать тожества, используя только определения операций над множествами.
(=>) Пусть. это выполняется тогда и только тогда, тогда. А это значит, что x не лежит ни в A, ни в B, т.к. если бы он лежал хотя бы в одном множестве, то он лежал бы и в объединении этих множеств.
Получается, что. и. или, по-другому. и. По определению это.
( [0, 1) по следующему правилу:
f(x)=x, для всех x не равных (1/2)n
f(x)=x/2, для всех x равных (1/2)n
Тогда мы получаем взаимно-однозначное отображение, причём в образе этого отображения не будет единицы (1=(1/2)0).
Теперь сделаем отображение g:[0, 1] -> (0, 1] по правилу g(x)=1-f(x) — оно взаимно-однозначно.
Доказать методом мат.индукции.
10. База индукции. =.
20. Шаг индукции: n=>n+1.
Пусть выполнено. для n. Проверим что выполняется следующее равенство.
Заменим первые n слагаемых по предположению индукции.
Последнее утверждение истинно, значит истинно и то, что мы собирались доказать.
Изобразить P1, P2 графически. Найти. Проверить с помощью матрицы [P2] является ли отношение P2 рефлексивным, симметричным, антисимметричным, транзитивным.
Из вида матрицы [P2] можно заключить, что отношение P2 является рефлексивным (на диагонали матрицы стоят единицы), симметричным (матрица симметрична), транзитивным (т.к. [P2?P2]=[P2]), не является антисимметричным (есть элементы вне диагонали для симметричной матрицы). Таким образом, отношение P2 является отношением эквивалентности (рефлексивность, симметричность, транзитивность).
Найти область определения, область значений отношения P. Является ли отношение рефлексивным, симметричным, транзитивным?
Область определения, значений.
Рефлексивность: проверим. Т.е. это неверно, значит отношение не является рефлексивным.
Симметричность: пусть. тогда. Проверим, будет ли выполняться. Очевидно, что нет, например при y=2, x=0. Следовательно, отношение не является симметричным.
Транзитивность: Пусть. и. Тогда, по определению. и. Отсюда следует, что. и уж тем более. То есть отношение является транзитивным.
Даны графы G1 и G2. Найти. Для графа. найти матрицы смежности, инцидентности, сильных компонент, маршрутов длины 2 и все маршруты длины 2, исходящие из вершины 1.
Найдём для графа. матрицу смежности:
матрицу инцидентности (занумеруем дуги так e1=(1,1), e2=(1,2), e3=(1,3), e4=(1,4), e5=(2,2), e6=(2,3), e7=(3,2), e8=(3,4), e9=(4,1), e10=(4,3)):
Матрица сильных компонент S, находим через матрицу достижимости C:
Матрица маршрутов длины 2:
Количество всех маршрутов длины 2, исходящих из вершины 1: 10.
Найти матрицы фундаментальных циклов, фундаментальных разрезов, радиус и диаметр, минимальное множество покрывающих цепей графа G. Является ли граф Эйлеровым? Является ли он планарным?
Сразу заметим, что граф планарен. Т.к. его можно изобразить без пересечений:
Кроме того, он не является Эйлеровым, т.к. есть нечётные вершины.
Цикломатическое число. =12-8+1=5.
u1. u7 — ветви остова, v1. v5 — хорды остова.
Матрица фундаментальных циклов:
Матрица фундаментальных разрезов (получаем транспонированием подматрицы в С):
Найдём эксцентриситеты вершин: e(1)=3, e(2)=2, e(3)=3, e(4)=3, e(5)=3, e(6)=3, e(7)=2, e(8)=3
Найдём минимальное множество покрывающих цепей графа.
По теореме 4.7.2 минимальное число покрывающих цепей равно 2:
1-я цепь: u2, u3, u4, u5, v3, v2
2-я цепь: v1, u6, u7, v5, u1, v4.
Составить таблицы истинности формул.
0 0 0 1 0 0 0 1 0
0 0 1 1 0 1 0 1 1
0 1 0 0 1 1 0 1 1
1 0 0 1 0 0 0 1 0
0 1 1 0 1 1 0 1 1
1 0 1 1 0 1 0 1 1
1 1 0 0 0 0 1 0 1
1 1 1 0 0 1 1 0 0
Проверить эквивалентность формул:
а) таблицами истинности;
б) эквивалентными преобразованиями.
0 0 0 1 1 0 0 1
0 0 1 1 1 0 1 1
0 1 0 0 0 1 0 0
0 1 1 1 1 1 1 1
1 0 0 1 1 1 1 1
1 0 1 1 1 1 1 1
1 1 0 0 1 1 1 1
1 1 1 1 1 1 1 1
Эквивалентными преобразованиями привести формулу. к ДНФ, КНФ, СДНФ, СКНФ, полином Жегалкина.
Найти сокращённую, все тупиковые и минимальные ДНФ функции f(x, y, z)
а) методом Квайна.
000 001 011 100 110
Классы Поста: не сохраняет единицу ( f(1, 1, 1)=0), не сохраняет ноль (f(0, 0, 0)=1).
не самодвойственна ( f(0, 0, 1)=1. (1, 1, 0)=0), нелинейна (. )
не монотонная (т.к. не сохраняет единицу и не тождественно ложна).
Найти сокращённую, все тупиковые и минимальные ДНФ, КНФ функции
x1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1
x2 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
x3 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
x4 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
f 1 0 1 1 1 0 1 1 1 1 0 0 1 1 1 1
Нарисуем карты Карно:
здесь «максимальными» импликантами будут. и. Остальные точки покроем разными способами:
Связь максимального паросочетания и минимального вершинного покрытия в двудольных графах
Пусть в [math]G[/math] построено максимальное паросочетание. Ориентируем ребра паросочетания, чтобы они шли из правой доли в левую, ребра не из паросочетания — так, чтобы они шли из левой доли в правую. Запустим обход в глубину из всех не насыщенных паросочетанием вершин левой доли. Разобьем вершины каждой доли графа на два множества: те, которые были посещены в процессе обхода, и те, которые не были посещены в процессе обхода. Тогда [math]L = L^+ \cup L^-[/math] , [math]R = R^+ \cup R^-[/math] , где [math]L, R[/math] — правая и левая доли соответственно, [math]L^+, R^+[/math] — вершины правой и левой доли, посещенные обходом, [math]L^-, R^-[/math] — не посещенные обходом вершины. Тогда в [math]G[/math] могут быть следующие ребра:
- Из вершин [math]L^+[/math] в вершины [math]R^+[/math] и из вершин [math]R^+[/math] в вершины [math]L^+[/math] .
- Из вершин [math]L^-[/math] в вершины [math]R^-[/math] и из вершин [math]R^-[/math] в вершины [math]L^-[/math] .
- Из вершин [math]L^-[/math] в вершины [math]R^+[/math] .
Очевидно, что ребер из [math]L^+[/math] в [math]R^-[/math] и из [math]R^+[/math] в [math]L^-[/math] быть не может. Ребер из [math]R^-[/math] в [math]L^+[/math] быть не может, т.к. если такое ребро [math]uv[/math] существует, то оно — ребро паросочетания. Тогда вершина [math]v[/math] насыщена паросочетанием. Но т.к. [math]v \in L^+[/math] , то в нее можно дойти из какой-то ненасыщенной вершины левой доли. Значит, существует ребро [math]wv, w \in R^+[/math] . Но тогда [math]v[/math] инцидентны два ребра из паросочетания. Противоречие.
Заметим, что минимальным вершинным покрытием [math]G[/math] является либо [math]L[/math] , либо [math]R[/math] , либо [math]L^- \cup R^+[/math] . В [math]R^+[/math] не насыщенных паросочетанием вершин быть не может, т.к. иначе в [math]G[/math] существует дополняющая цепь, что противоречит максимальности построенного паросочетания. В [math]L^-[/math] свободных вершин быть не может, т.к. все они должны находиться в [math]L^+[/math] . Тогда т.к. ребер из паросочетания между [math]R^+[/math] и [math]L^-[/math] нет, то каждому ребру максимального паросочетания инцидентна ровно одна вершина из [math]L^- \cup R^+[/math] .
Алгоритм построения минимального вершинного покрытия
Из доказательства предыдущей теоремы следует алгоритм поиска минимального вершинного покрытия графа:
Алгоритм поиска наименьшего по мощности покрытия конечного множества его подмножествами
Разбирая старые бумаги наткнулся на изрядно потрёпанную тетрадь, в которой обнаружил наброски алгоритма поиска покрытия. Автор алгоритма Виктор Анатольевич Щербанов — мой учитель, под руководством которого я работал в девяностые годы прошлого столетия. Моё скромное участие в основном заключалось в том, что я предлагал в большинстве случаев неверные (а порой и просто бредовые) варианты. Что в общем-то не помешало Шефу (так мы его называли между собой) таки довести работу над алгоритмом до логического завершения. Где-то в двухтысячных годах алгоритм был опубликован в одном из институтских изданий Томска. Но думаю, что не лишним будет вспомнить его ещё раз. Собственно в память о Шефе я и решил написать этот пост. Может быть алгоритм покажется кому-то интересным или подтолкнёт на какие-то новые идеи по реализации алгоритма.
Сам алгоритм зиждется на двух утверждениях и двух теоремах, доказательства которых здесь не приводятся, из-за их довольно большого объёма.
Для начала определимся с тем, что мы, собственно, ищем.
Пусть задано конечное множество и семейство его подмножеств .
Найти подсемейство (если оно существует) такое, что и мощность подсемейства S* (покрытия множества V) наименьшая из всех возможных.
Следующие утверждения определяют понятия минимального и наименьшего покрытия.
Утверждение 1.
Для того чтобы подсемейство , было покрытием множества , необходимо и достаточно, чтобы выполнялось условие
Покрытие S’ называется минимальным, если не существует покрытия S» такого, что .
Покрытие S* называется наименьшим, если для любого минимального покрытия S’ выполняется условие
Утверждение 2.
Покрытие минимально тогда и только тогда, когда для любого , выполняется условие
И, самое основное.
Пусть задано конечное множество и семейство его подмножеств .
Построим полный нагруженный граф , в котором множеству вершин графа взаимно однозначно сопоставлено семейство подмножеств ,
а каждому ребру — подмножество .
Обозначим множество всех рёбер инцидентных вершине , а — множество всех вершин, инцидентных рёбрам из множества .
Теорема 1.
Минимальное по мощности подмножество ребер, инцидентных произвольной вершине в графе G, при выполнении условий
определяет минимальное покрытие , однозначно соответствующее множеству вершин, если , или множеству вершин, если .
Теорема 2.
Минимальное по мощности подмножество ребер, инцидентных произвольной вершине ребра в графе G, при выполнении условий
для всех
определяет наименьшее покрытие , однозначно соответствующее множеству вершин, если , или множеству вершин, если .
На основании теорем предлагается следующий алгоритм поиска наименьшего покрытия.
1. Множеству и семейству его подмножеств , сопоставить семейство подмножеств . Если для некоторого окажется , то существует тривиальное покрытие . Конец алгоритма.
Иначе перейти на п.2.
2. Построить полный нагруженный граф , где .
Вершину нагрузить множеством
Ребро нагрузить множеством .
3. Проверить существование покрытия: для произвольной вершины определить подмножество
,
где — множество рёбер, инцидентных вершине в графе .
Если , то покрытия не существует. Конец алгоритма.
Если , то покрытие существует. Перейти к процедуре поиска наименьшего покрытия (п. 4).
4. Положить t:=0.
5. В полном нагруженном графе найти ребро для которого выполняется условие .
Если , то перейти на п. 6,
иначе — на процедуру построения множества D вершин, определяющих наименьшее покрытие (п. 7).
6. Построить полный нагруженный граф , полагая , — множество рёбер, инцидентных вершине в графе .
Положить для всех .
Положить t:=t+1 и перейти на п. 5.
7. Начало построения множества D вершин, определяющих наименьшее покрытие .
Положить .
8. Если t=0, то перейти на п. 11, иначе — положить t:=t-1.
9. В графе определить подмножество
10. Если в графе выполняется условие , то положить , иначе — D:=D. Перейти на п. 8.
11. Семейство подмножеств определяет наименьшее покрытие множеств .
Конец алгоритма.
Попробуем оценить сложность алгоритма.
Вся, так сказать, суть алгоритма (с точки зрения оценки сложности) заключена в фразе «построим полный нагруженный граф».
Нам требуется выполнить n действий для вычисления нагрузки в n вершинах графа и (n-1)n/2 вычислений (по количеству рёбер полного графа) для нагрузки рёбер графа. И всё это, если рассматривать наихудший случай, когда подмножества взаимно не пересекаются, выполняется n-2 раза. Таким образом грубая оценка O(n) = n 3 + n 2 .
И в заключение. Не уверен, что пост заслуживает инвайта, потому как моя причастность к алгоритму более чем сомнительная. Но опубликования, как мне кажется, стоит. Надеюсь модераторы разберутся.
Как там греки говорили? — Fais se que dois adviegne que peut (делай, что должно, и будь, что будет).
(или это были римляне?)
