Линейный мограф

Cтраница 1

Линейные мографы являются мографами поддеревьев дерева и, как следует из теоремы 5.6, сжимаемыми к тривиальному мографу. Однако не все мографы поддеревьев дерева являются линейными. [1]

Процесс построения линейного f - графа.| Результирующий линейный / - граф. [2]

Наряду с линейными мографами много исследовались и циклические мографы, представляющие ( как и линейные) не только информационно-поисковый, но и генетический интерес. Существует простая связь между линейными и циклическими мографами. [3]

Теорема 5.9 характеризует линейные мографы двумя запрещенными фигурами. [4]

Мограф W ( X, ЗЯ ( а, V - расширение мографа Ч б и свертка мографа Ч 1 ( в. [5]

Как нетрудно убедиться, для линейных мографов операция сжатия и отношение подчинения RI удовлетворяют принципу локальности. Однако существуют и более жесткие отношения подчинения, удовлетворяющие принципу локальности для линейных мографов. [6]

Это свойство играет большую роль в характеризации линейных мографов. [7]

Мограф, получившийся в результате элементарного сжатия линейного мографа, линеен. Для любого х Х, а следовательно, и для поглощаемого элемента мограф У ( Х - х, ЗЯ [) ( Х - х) У линейный, так как его представление получается из представления Ч удалением х и, если х-не висячая вершина-соединением смежных с ней вершин. [8]

Отметим, что множество мографов с PD-организацией включает в себя множество линейных мографов. [9]

Наиболее изученным классом из всех рассматриваемых классов допустимых мографов является класс линейных мографов. Это объясняется тем, что еще раньше они нашли применение в генетике. Говорят, что двоичная матрица обладает свойством последовательных единиц, если существует такая перестановка ее столбцов, при которой единицы в каждой строке расположены последовательно. [10]

Из того, что отношение подчинения R2 удовлетворяет принципу локальности, следует, что линейные мографы могут быть охарактеризованы списком запрещенных фигур. [11]

Мограф W ( X, ЗЯ ( а, V - расширение мографа Ч б и свертка мографа Ч 1 ( в. [12]

Проиллюстрируем понятия расширения и свертки на примере, приведенном на рис. 5.14. Покажем, что отношение подчинения R2 удовлетворяет принципу локальности для линейных мографов и, более того, для всех классов допустимых мографов. [13]

Наиболее общим классом из рассматриваемых ранее является класс ациклических мографов. Действительно, линейные мографы являются ациклическими, поскольку линейные / - графы ацикличны. [14]

Из выделенных модельных преобразований наиболее важными являются преобразования мографов в линейные и ациклические. Первое - вследствие того, что в характеризуемой линейными мографами физической организации объекты хранятся в последовательных областях памяти. [15]

Страницы: 1 2