Грэхема

Cтраница 4

Мы придем к противоречию, показав, что алгоритм Грэхема для R не может завершиться успешно. В частности, мы покажем, что принадлежащие множеству X вершины никогда не будут удалены. X содержится как в некотором ребре из Rb так и в некотором ребре из R2, а потому не является терминальной. Мы покажем, что при редукции это свойство сохраняется. [46]

Доказательство леммы 13.2. Согласно предложению 13.2, редуктивный алгоритм Грэхема сохраняет ацикличность. Если в процессе редукции ациклического гиперграфа Я, выполняемой с помощью этого алгоритма, на каком-либо шаге окажется, что промежуточный гиперграф нередуцирован, то к нему можно применить правило УР. Если же этот промежуточный гиперграф редуцирован, то либо мы уже достигли гиперграфа с единственным ребром, либо выполняется предложение 13.4, и мы можем использовать правило УВ для удаления некоторой терминальной вершины. Поскольку при применении правил редукции в алгоритме Грэхема общее количество ребер и вершин уменьшается, то этот алгоритм постепенно редуцирует Я до пустого гиперграфа. С другой стороны, алгоритм редукции не может завершиться успешно в случае циклического гиперграфа Я. Действительно, такой гиперграф должен иметь по крайней мере три ребра. Если бы редукция Я завершалась успешно, то одним из ее промежуточных результатов оказался бы гиперграф, обладающий в точности двумя ребрами и тем самым ациклический. [47]

Мы придем к противоречию, показав, что алгоритм Грэхема для R не может завершиться успешно. В частности, мы покажем, что принадлежащие множеству X вершины никогда не будут удалены. X содержится как в некотором ребре из RJ, так и в некотором ребре из R2, а потому не является терминальной. Мы покажем, что при редукции это свойство сохраняется. [48]

Изучая деление U235 на медленных нейтронах, Тоде и Грэхем [246] обнаружили аномальные выходы Кг89, Хе133 и Хе134, значительно превышающие выходы, получаемые интерполяцией по гладкой кривой. Позже, по мере совершенствования радиохимических и спектрометрических методов, это явление было обнаружено и при других делительных процессах. [49]

Бостона 29-летний преподаватель школы для глухих по имени Александр Грэхем Белл осуществил первую в мире успешную передачу речи при помощи электричества. [50]

Левая и правая крайние точки определяют разбиение множества на два подмножества. [51]

Несмотря на то что, как было показано, алгоритм Грэхема является оптимальным, по-прежнему имеется много причин для продолжения исследования задачи о выпуклой оболочке. [52]

Прежде чем закончить этот раздел, отметим, что метод Грэхема явным образом использует сортировку. [53]

Если исходные данные уже упорядочены, то, используя метод Грэхема, можно найти нижнюю оболочку за линейное время. [54]

Rp - ациклическая схема базы данных, то редуктивный алгоритм Грэхема для R завершается успешно. [55]

Заметим, что на всех шагах редукции R по алгоритму Грэхема связность сохраняется. Дерево соединений G для R строится следующим образом. Обозначим через REMj ( Rt) то, что осталось от Rt перед / - м шагом редукции. [56]

Страницы: 1 2 3 4