Графовые структуры и отношения над ними
Ключевые понятия:графовая структура, связка инцидентности, ребро, вершина.
Графовая структура (граф) – реляционная структура, в которой все сигнатурные отношения являются бинарными (ориентированными либо неориентированными) отношениями смежности (см. подраздел 1.2). Связки этих отношений называют рёбрами графа. Первичные элементы графа называют вершинами. Приведём пример графовой структуры неориентированного графа в традиционном представлении:
При представлении графа на языке SCBкаждое неориентированное ребро графа представляется неориентированной бинарной связкой, а каждое ориентированное – ориентированной связкой.
SCBg-текст 3.4.4..Представление вышеприведённого графа на языкеSCB:
Введём в графическую модификацию языка SCBизображение связки отношения инцидентности:
-
v g;
Используя связки отношения инцидентности, можно рассматриваемую нами графовую структуру представить и таким образом:
Над графовыми структурами, так же как и над реляционными структурами, определены отношения гомоморфизма, изоморфизма и автоморфизма.
Существует типология графовых структур (графов):
ориентированные графы,
неориентированные графы,
смешанные графы;
связные графы,
несвязные графы;
цикличные графы,
ацикличные графы
деревья
бинарные деревья,
тернарные деревья
и т.п.
Выводы к разделу 3
Завершая раздел 3, подчеркнем, что на языке SCBвозможно эффективное представление не только классических, но и неклассических математических структур – не только канторовских множеств, но и мультимножеств (множеств с повторениями), не только классических кортежей, но и кортежей неклассического вида с произвольным характером распределения атрибутов между компонентами кортежа, не только классических отношений, каждое из которых представляет собой множество классических кортежей одинаковой мощности и с одинаковыми атрибутами, но и отношений неклассического вида, не только классических реляционных структур (алгебраических систем), но и реляционных структур неклассического вида.
Особо отметим неограниченные возможности языка SCBдля представления всевозможных метаструктур – метамножеств (множеств, элементами которых являются множества), метакортежей (кортежей, компонентами которых являются кортежи), метаотношений (отношений, в область определения которых входят отношения), реляционных метаструктур (реляционных структур, первичными и/или вторичными элементами которых являются знаки реляционных структур).