Cтраница 2
Заметим, что несмотря на одинаковую запись структурных чисел матрицы и графа, переход от номеров структурных чисел к элементам определителей матрицы у них осуществляется по-разному. Если область определения отображения, порождаемого структурным числом матрицы, соответствует первым индексам элементов матрицы, а область значений - вторым индексам, то для структурного числа графа область определения - это множество вершин графа, откуда исходят дуги фактора ( пути), а область значений - множество вершин, куда входят эти дуги. В связи с этим члены определителя в случае использования структурных чисел матриц записываются непосредственно по соответствующим отображениям, а при использовании структурных чисел графов получаемые отображения служат для определения путей и факторов графа. Члены определителя получаются уже как сумма весов дуг, входящих в эти пути и факторы. [16]
Если алфавитное отображение ф удовлетворяет сформулированным выше четырем условиям автоматно-сти, то можно построить автоматы Мили и Мура ( вообще говоря, бесконечные), индуцирующие это отображение. В случае, когда область определения отображения ф конечна, эти автоматы также могут быть выбраны конечными. [17]
Рассмотрим случай, когда областью определения отображения Г является множество Т XX. Из условий нашей теоремы и теоремы 2.5.4 следует, что множество НГ ( Ж) не пусто. [18]
Область определения автоматного отображения удовлетворяет условию полноты, то есть, иначе говоря, вместе с любым содержащимся в ней словом содержит также все начальные отрезки этого слова. Пустое слово всегда входит в область определения отображения. [19]
Смысл ее заключается в следующем. Если р - некоторый начальный отрезок слова р из области определения отображения /, то полагаем f ( р) равным начальному отрезку слова f ( p), имеющему равную с отрезком р [ длину. В результате применения операции пополнения к отображению / получаем новое отображение f, область определения которого удовлетворяет условию полноты. Если отображение / - однозначное отображение, то очевидно, что оно удовлетворяет условиям автоматности и, таким образом, является искомым автоматным отображением. [20]
Пусть А и В - два множества и каждому элементу а е Л поставим в соответствие один единственный элемент b e В. Говорят, что / - отображение множества Л в множество В, и записывается это таким образом - f: A - B, или fB А. Множество Л называется областью определения отображения, а В - областью значений. [21]
На первом этапе мы покажем, что если для некоторого элемента ж () е Нг ( жо) существует множество & - ( х) - Т ( ( a) c: R), ц ( ( г)) 0, в каждой точке t которого множество T ( t, x ( t)) не выпукло, то ( существует m 0 такое, что) для любого е 0 ( и любого отрезка Тп [ 0, га ], пт) найдется элемент ж8 ( -) ellr-r ( ж0) Нг ( а: в), удовлетворяющий неравенству x ( t) - xt ( t) e, t & T ( t Tn), Первый этап. Рассмотрим сначала случай, когда областью определения отображения Г служит множество Т X XX. Очевидно, что В - компакт. Согласно лемме 1.1.1, оно является сильно измеримым отображением из Т в convX и, следовательно, ц-почти сепарабельнозначным. [22]
Вторая операция применяется только к выравненным алфавитным отображениям ф, то есть к таким отображениям, у которых длины входных и соответствующих им выходных слов равны между собой. Сущность этой операции, которую мы будем называть операцией пополнения отображения ф, заключается в распространении отображения ф на начальные отрезки слов. Операция пополнения имеет следующий вид: если s - произвольный начальный отрезок любого слова р из области определения отображения ф, то мы полагаем ф ( х) равным начальному отрезку слова ф ( /), имеющему равную с начальным отрезком s длину. [23]
Как было установлено в предыдущем параграфе, любое автоматное отображение ф может быть задано конечным множеством М событий во входном алфавите этого отображения. Конечное событие можно задать, перечислив все его элементы. Однако, как уже отмечалось выше, нашей основной целью является рассмотрение отображений с произвольными областями определения. Ясно, что в случае, когда область определения отображения ф бесконечна, хотя бы одно из событий множества М также будет бесконечным. [24]
Можно предполагать, что U содержит образ у. Обозначим через W окрестность точки р, являющуюся выпуклой нормальной окрестностью каждой своей точки. Положим q у ( / 0) и r - f ( Ч) - Тогда отображение Я expq - / expp1: W - M определено вблизи г и аналитично. Это отображение Я переводит геодезические, начинающиеся в г, в геодезические, исходящие из q, и сохраняет длины вдоль этих геодезических. В действительности Я совпадает с / - 1 вблизи г. Отображение Я не обязательно взаимно однозначно вследствие того, что таковым свойством обладает ехр. Поскольку область определения expq представляет собой объединение прямолинейных отрезков, начинающихся в начальной точке пространства TqM, то область определения V отображения Я должна быть некоторым подмножеством из W, представляющим собой объединение геодезических сегментов, исходящих из г. Отсюда следует, что множество V не может совпадать со всем W только в том случае, если ехр. V, содержащей точку г. Это означает, что V ф W. И мы приходим к противоречию. [25]