Приложение 3. Теоретико-графовая интерпретация ступеней

Класс графов

Графом называется конечное множество точек, произвольно расположенных на неметризованной плоскости, называемых «вершинами», соединенных между собой отрезками линий (не обязательно прямых), называемых «дугами».

Графы различаются по мощности множества вершин, по мощности множества дуг и по топологии вершин (отношению «соседства» между вершинами, определяемого соединяющими их дугами).

Виды графов по топологии:

• 
  по связности: от полностью несвязанных до полностью связанных;
  
• 
  по наличию циклов (замкнутых последовательностей дуг): не имеющие циклов (графы типа «цепи», «дерева»); имеющие циклы (от «сетей» и «лесов» до «кольца»);
  
• 
  по кратности вершин (число дуг у одной вершины): однократные (изолированные) вершины, двукратные (у вершин две дуги), …, многократные (типа «звезды»);
  
• 
  по кратности дуг (число дуг, соединяющих пару вершин): однократные (называется «граф»), многократные (называется «мультиграф»).
  

• 
  с фиксированной кратностью дуг;
  
• 
  с различной кратностью дуг,
  

• 
  у которых дуги не ориентированы;
  
• 
  у которых некоторые дуги ориентированы;
  
• 
  у которых все дуги ориентированы;
  

• 
  у которых дуги не метризованы;
  
• 
  у которых некоторые дуги метризованы;
  
• 
  у которых все дуги метризованы.
  

Понятие «ориентированный граф»

Ориентированным графом называется граф, одной, нескольким или всем дугам которого приписаны направления. Дуга называется «ориентированной», если ей приписано направление.

Виды ориентированных графов

Если ориентация дуг единая для всего графа, то такой граф называется «правильно ориентированным».

Если ориентация дуг такова, что к вершине направлены две дуги, а от вершины дуг нет, то граф называется «противоречивым».

Неориентированная дуга в ориентированном графе означает, что следование ее вершин не определено. Такой путь называется «частично ориентированным».

Класс метризованных графов

Понятие «метризованный граф»

Граф называется «метризованным», если только вершинам, или только дугам, или вершинам и дугам приписаны числа (как правило, из множества натуральных чисел).

Класс комбинированных графов

Понятие «комбинированный граф»

Комбинированным графом называется граф, составленный из нескольких графов одного класса графов или нескольких классов графов.

Графы, составленные из нескольких графов одного класса, называются гомографами. Графы, составленные из нескольких графов разных классов, называются гетерографами.

Графы, вершины которых представляют графы, называются гиперграфами. Графы, которые в гиперграфе представлены его вершинами, называются миниграфами.

Вершины миниграфа, в свою очередь, могут представлять граф. Такое раскрытие вершин может производиться многократно. Соответственно, гиперграф с единичным раскрытием своих вершин называется «гиперграфом первого порядка», с двукратным раскрытием — «гиперграфом второго порядка» и т.д.

Булеан двухместного декартиана множества Х представляет все подмножества декартиана. Среди них часть имеет теоретико-графовую интерпретацию. Аксиомы, выделяющие эти подмножества, не приводятся из-за их очевидности.

Полезность эта возникает по двум причинам. Первая состоит в легко возникающем зрительном образе, становящемся инструментом мышления, в частности, средством эвристики. Вторая заключается в том, что возникающим образам легко давать имена, разумеется, при расширении теории графов. Ниже приводятся варианты расширения теории графов.

D-графы	DB-графы	DB-графы
D2-графы	DB2-графы	D2B-графы
…	…	…
Dn-графы	DBn-графы	DnB-графы

DB-графы	DBD-графы	DBD-графы
D2B2-графы	D2BD-графы	DB2D-графы
…	…	…
DnBn-графы	DnBD-графы	DBnD-графы

DBD-графы	DBD-графы	DBD-графы
DBD2-графы	D2BD2-графы	D2B2D2-графы
…	…	…
DBDn-графы	DnBDn-графы	DnBnDn-графы

Граф, Гиперграф-1, Гиперграф-2, …, Гиперграф-n

Гиперграф-1: вершины являются графами.

Гтперграф-2: вершины являются гиперграфами-1.

Гиперграф-3: вершины являются гиперграфами-2.

……………………………………………………….

Гиперграф-n: вершины являются гиперграфами-n–1.

Вариант теоретико-множественных обозначений для случая двух типов Рассела в абстрактной теории ступеней

Обозначения для ступеней	Обозначения для метатеории ступеней
Х	Х
х  Х	х  Х
Y  X	Y  X
DX	DX
BX	BX
BDX	BDX
DBX	DBX

Для различения в тексте множеств разных типов можно использовать термины: