13. Понятие реляционной структуры. Типология элементов реляционной структуры. Представление реляционных структур на языке семантических сетей.
Объединение переменных классов математических структур назовем классической реляционной структурой.
В состав реляционной структуры общего вида входят:
знаки множества-носителя (множества первичных элементов) реляционной структуры;
знаки сигнатурных множеств реляционной структуры;
знаки сигнатурных отношений реляционной структуры;
знаки атрибутов, входящих в схемы отношений реляционной структуры;
те элементы сигнатурных множеств реляционной структуры, которые являются элементами универсума этой структуры;
знаки атрибутов, используемых для построения таких вторичных элементов реляционной структуры, которые являются элементами унарных отношений этой реляционной структуры;
те знаки связок сигнатурных отношений реляционной структуры, которые являются вторичными элементами универсума этой реляционной структуры;
промежуточные вторичные (!) элементы реляционной структуры – это элементы, которые не входят в число вышеперечисленных элементов реляционной структуры и являются элементами множеств, обозначаемых вышеуказанными вторичными элементами реляционной структуры (т.е. теми вторичными элементами универсума (!) реляционной структуры, которые являются элементами сигнатурных множеств и отношений этой реляционной структуры); при этом, если промежуточный вторичный элемент реляционной структуры одним из своих элементов имеет вторичный элемент универсума этой реляционной структуры, не попавший в вышеназванные классы элементов реляционной структуры, то этот вторичный элемент универсума приписывается к числу промежуточных вторичных элементов реляционной структуры;
знаки атрибутов, используемых для построения промежуточных вторичных элементов реляционной структуры.
Перейдем к строгому определению понятия реляционной структуры. Реляционная структура – это такая система множеств, для которой каждому ее элементу дополнительно приписывается некоторая его роль в рамках этой системы множеств. Для указания роли элементов реляционных структур используются следующие атрибуты:
первичный элемент_ (быть первичным элементом реляционной структуры);
атрибут_ (быть знаком атрибута, используемого в кортежах, знаки которых являются вторичными элементами реляционной структуры);
сигнатурное отношение_ (быть знаком сигнатурного отношения реляционной структуры);
сигнатурное множество_ (быть знаком сигнатурного множества реляционной структуры);
атрибут по умолчанию_ (атрибут, задаваемый по умолчанию и отмечающий вторичные элементы реляционной структуры).
14. Типология и свойства графовых структур.
Совокупность двух
множеств V(точек)
и Е(линий), между элементами которых
определено отношение инцидентности,
причём каждый элемент
инцедентен ровно двум элементамv’,
v``
V.
Элементы множества V
называются вершинами графа G,
элементы множества Е – его рёбрами.
Вершины и рёбра графа называют ещё его
элементами, т.е. v
G
и е
G.
Инцидентные ребру вершины неравноправны, они рассматриваются в определенном порядке. Тогда каждому ребру можно приписать направление от первой из инцидентных вершин ко второй. Направленные ребра часто называют дугами), а содержащий их граф—ориентированным (граф, определенный ранее, называется неориентированным). Первая по порядку вершина, инцидентная ребру ориентированного графа, называется его началом, вторая — его концом. Говорят еще, что ребро ориентированного графа выходит из начала и входит в конец.
На рис. 4.1, а—з изображены некоторые неориентированные графы.
Множество ребер Е может быть пустым (рис. 4.1, г). Если же множество вершин V пусто, то пусто и Е.
Такой граф называется пустым. Линии, изображающие ребра графа, могут пересекаться, но точки пересечения не являются вершинами (рис. 4.1, d); различные ребра могут быть инцидентны одной и той же паре вершин (рис. 4.1,е), в этом случае они называются кратными; граф, содержащий кратные ребра, часто называют мультиграфом. Ребро может соединять некоторую вершину саму с собой (рис. 4.1, ж), такое ребро называется петлей. На рис. 4.1,з изображен фрагмент бесконечного графа. Его вершины — это точки плоскости с целыми координатами (х, у), а ребра — соединяющие их горизонтальные и вертикальные отрезки длины 1.
Обычно рассматриваемые графы конечны, т, е. конечны множества их элементов (вершин и ребер). Поэтому конечность этих графов не будет специально оговариваться. Однако некоторые понятия и результаты, о которых будет идти речь, относятся к произвольным графам.
При изображении ориентированных графов (рис. 4.2, а—з) направления ребер отмечаются стрелками, примыкающими к их концам. Ориентированный граф также может иметь кратные ребра(рис. 4.2, е), петли (рис. 4.2,ж), а также соединяющие одни и те же вершины ребра, идущие в противоположных направлениях (рис. 4.2, з).
Каждому неориентированному графу можно поставить в соответствие ориентированный граф с тем же множеством вершин, в котором каждое ребро заменено двумя ориентированными ребрами, инцидентными тем же вершинам и имеющими противоположные направления. Такое соответствие будем называть каноническим.
Граф может быть представлен различными способами. Он может быть изображен на чертеже, задан матрицей инцидентности, списком ребер или матрицей смежности. граф считается полностью заданным, если нумерация его вершин зафиксирована; графы, отличающиеся только нумерацией вершин, называются изоморфными.
Пусть G — неориентированный граф. Количество p() ребер, инцидентных вершине G, называется ее локальной степенью или просто степенью.
Если степени всех вершин конечны, рассматриваемый граф G называется локально-конечным. В частности, любой конечный граф локально-конечен.
Граф называется однородным степени k, если степени всех его вершин равны k и тем самым равны между собой. Граф без кратных рёбер называется полным, если каждая пара вершин соединена ребром.
Пусть G — неориентированный граф. Маршрутом в G называется такая конечная или бесконечная последовательность ребер (...е0, е1 ..., en...), что каждые два соседние ребра еi=1=1 и еi имеют общую инцидентную вершину. Пусть маршрут М(е1, e2, ..., en) имеет начало 0 и конец n. Тогда его называют соединяющим вершины 0 и n. Число ребер маршрута называется его длиной. Если 0=n, маршрут называют циклическим. Отрезок (ei, ei+1, ,.., еj) конечного или бесконечного маршрута М сам является маршрутом. Он называется участком маршрута М.
Маршрут М называется цепью, если каждое ребро встречается в нем не более одного раза, и простой цепью, если любая вершина графа G инцидентна не более чем двум его ребрам. Циклический маршрут называют циклом, если он является цепью, и простым циклом, когда это простая цепь. Однако фактическим циклом (соответственно простым циклом) считают циклически упорядоченное множество ребер, в котором два соседних ребра имеют общую инцидентную вершину.
Вершины ', "G называются связанными, если существует маршрут М с началом ' и концом ". Легко видеть, что в этом случае существует также маршрут с началом ' и концом ". Граф может быть разложен в прямую сумму подграфов: G=UG(Vi). Граф G называется связным, если все его вершины связаны между собой. Поэтому все подграфы G(Vi) связны и называются связными компонентами рассматриваемого графа.
Эйлеров цикл можно считать следом пера, вычерчивающего этот граф, не отрываясь от бумаги. Таким образом, эйлеровы графы — это такие графы, которые можно изобразить одним росчерком пера, причем процесс такого изображения начинается и кончается в одной и той же точке.
Конечный неориентированный граф G эйлеров тогда и только тогда, когда он связен и степени всех его вершин четны. Чтобы в конечном ориентированном графе существовал эйлеров цикл, необходимо и достаточно равенство степеней вершин этого графа по входящим и выходящим ребрам.
Гамильтовым циклом называется простой цикл, проходящий через все вершины рассматриваемого графа.
Максимальным рангом R(v) вершины v ориентированного графа G называется максимальная из длин путей этого графа с концом в v. R(v) ==0, если и только если v — начальная вершина G.
Минимальным рангом r(v) вершины v ориентированного графа G называется минимум длин путей L{v0,.. ,v) с началом в какой-либо начальной вершине v0 графа G и с концом в рассматриваемой вершине v.