Графы. Теория

Графы и не только конечные - мощнейшая математическая абстракция. А применений их (особенно помеченных) несть числа.

Есть два вида графов - ориентированные и неориентированные и одно мощное расширение - помеченные графы.

Мы тут начнём формализацию и аксиоматизацию теории графов.

Встречающиеся определения графа

см. отдельный гу-док здесь.

Неориетнированные графы (норграфы)

Пусть V и E - два произвольных множества: вершин (V) и рёбер (E), а inc (E V) - бинарное отношение между ними. Если inc обладает тем свойством, что каждое ребро находится в отношении inc либо только с одной либо только с двум вершинами, то тройка V, E, inc называется норграфом, а inc - отношением инцидентности. При этом говорится что ребро инцидентно либо не инцидентно той или иной вершине.

Что чему инцидентно?

В [GNA] «v is incident with e». В [ГСиА] на с.12 первый абзац читаем «ребро инцидентно своим концевым вершинам» И в [СТТГ] тоже. Но в его английской версии опять имеем «vertex is incident to both the edge that...». Возможно "у англичан" вершина инцидентна ребру, а "у русских" - ребро инцидентно вершине;-) впрочем в [GRAPP] допустимо говорить и то и другое (Инцидентность).

Считаем, что в формальной теории есть только inc(e v)! То есть объявляется/декларируется, что у предиката inc сорт первого аргумента - "E", а второго - "V".

А вот говорить можно всяко:

inc(e v) - читается/говорится:

- «v is incident with e»,

- “ребро e инцидентно вершине v”,

- “ребро касается вершины”,

- “вершина v есть концевая вершина ребра e”,

- “вершина v инцидентна ребру e”.

Замечание. Конечно можно ввести ещё один inc - inc(v e); синтаксически или как "перегрузку", но стоит ли огород городить?

Замечание для КРЯ. Вот и первая задачка тем кто будет транслировать предложения КРЯ контекста теории графов - всё вышеперечисленное транслируется в inc:-)

Вторая задачка может быть формализовать основное содержание отчёта о ГКВ!!! Ну там конечно помеченный орграф, но выразить формально основные результаты это 5!

Варианты формализации

Вар-1 две основы

Норграф есть двуосновная (V, E) алгебраическая система /АС/ с одним отношением inc(E V) и без операций:

<V,E; inc(E V)>, на которой выполнена аксиома инцидентности /АИ/ (см. далее).

В формальной двусортной (e,v) теории норграфов предикат inc(e v) - единственный первичный предикат и нет первичных функций.

Вар-2 одна основа

Норграф есть одноосновная (U) алгебраическая система с тремя отношениями: два унарных: V, E и одно бинарное - inc; и без операций:

<U;V(U), E(U), inc(U U)>, на которой выполнена аксиома инцидентности (см. далее).

В формальной односортной теории норгафов в этом случае три первичных предиката: V, E, inc и нет первичных функций.

Нам понадобятся дополнительные аксиомы, т.к. мы имеем представление основ(;-) унарными отношениями а естественные свойства основ: они не пересекаются, а объединение даёт "универсум" ("аксиома сортов"): ∀x:U V(x) xor E(x).

или так как в односортных языках сорт принято не писать а подразумевать:

∀x V(x) xor E(x).

Кроме того нужна запись "сигнатурных" свойств inc: всякий первый аргумент inc из E, а второй из V ("сигнатурные аксиомы"):

∀x (∃y inc(x y)) → E(x).

∀y (∃x inc(x y)) → V(y).

Замечание. в случае норграфов свойство вершин и рёбер не пересекаться можно попробовать и ослабить: представление о том что ребро может быть одновременно и вершиной может быть даже плодотворным;-) - будящим воображение!

Вар-2.1 одна основа и E, V определены через inc.

интересно рассмотреть ситуацию когда V и E определяются как унарные предикаты.

Тогда мы имеем АС: <U; inc(U U)> и в соответствующем формальном языке будет один первичный бинарный предикат - inc.

В результате мы оказываемся в логике бинарных отношений (R) и можем и в ней формулировать АТ норграфов - соответствующие формулировки даются после обозначения =Rel. В языке R-логики бинарные предикаты принято записывать инфиксно, например "e1 inc v1" и говорить про эту запись что e1 встретилось слева от inc, а v1 - справа.

E, V будут иметь определения:

E(x) =def ∃y inc(x y). --дуга это то что чему-то инцидентно =Rel встречается слева от inc.

V(x) =def ¬E(x). --не дуга и ( =Rel не встречается слева от inc).

Вершины раделяются на два вида: пусть x - какая-то вершина

• ∃y inc(y x) --"задействованная" вершина это то чему что-то инцидентно =Rel встречается справа от inc,

• ∀x ¬inc(x y) --изолированная вершина это то чему ничто не инцидентно =Rel не встречается справа от inc.

Замечание о V. первое требование к V пересекается с аксиомой сортов и его интересно ослабить.

=Rel Об изолированной вершине. она не участвует в отношении inc ни слева ни справа, но находится в основе U.

по-простому мы должны оставить аксиому сортов и сигнатурные аксиомы (см. выше), но возможно это теоремы либо их можно упростить;-)

И ещё нужна аксиома инцидентности (см. далее), которая скорее всего упростится.

Конец описания вариантов

Далее как рабочий используется Вар-1.

Замечание о конечности. Обычно на практике V, E, inc конечны.

Замечание о пересечении V и E. Обычно на практике V и E есть два не пересекающихся множества и их естественно представлять разными сортами.

аксиома инцидентности

Мы строим теорию с равенством. По-научному - эгалитарную теорию. Соответственно предикат равенства "=" имеется и аксиомы оного тоже.

Аксиома инцидентности. У ребра одна инцидентная вершина есть всегда, может быть две, третьей быть не может.

Вариант: “у каждого ребра концевых вершин должно быть одна либо две”

∀e:E |inc(e *)|=1 or |inc(e *)|=2

В первом порядке:

(АИ-1) для каждого ребра существует инцидентный ему узел.

∀e:E ∃v:V inc(e v)

(АИ-2) у каждого ребра не больше двух инцидентных узлов:

∀e:E,v1,v2,v3:V inc(e v1) & inc(e v2) & inc(e v3) → v3=v1 or v3=v2

т.е. если три узла инцидентны ребру, то любой из них равен какому-то из остальных двух!

Через # - квантор количества:

∀e:E(#v:V inc(e v))<3

Реплика. А хорошо тут смотрятся внешние скобки!

С # естественно и объединение аксиом:

∀e:E 1≤(#v:V inc(e v))≤2

Cвойства теории. Непротиворечивость следует из наличия модели. А что с полнотой?

Начальные определения

#2do

маршрут walk

Немного терминологии и определений для этого параграфа

Петля - дуга с одной концевой вершиной.

Ребро - дуга с двумя концевыми вершинами.

Последовательность есть функция с отрезка натуральных чисел (обычно [1..k]) в какое либо множество (членов последовательности).

Основная идея маршрута - непрерывное перемещение от одной вершины к другой по дугам графа. Эта динамика проявляется в тексте теории например так "A walk is a trail if any edge is traversed at most once." [KR-2013], p.6.

Замечание. Иногда (см. [KR-2013], p.6) допускается и число шагов 0.

Замечание. Наглядно непрерывность перемещения можно понимать поместив граф подходящим образом в R3, т.е. сопоставив вершинам точки R3, петлям - окружности а рёбрам отрезки прямой и разместив всё хозяйство без лишних пересечений. При этом чтобы обозначить на этом "хозяйстве" один конкретный маршрут достаточно пометить дуги номером шага. Понятно что в общем случае дуга будет иметь несколько меток. Конечно такая разметка не может быть произвольна.

Классическое определение маршрута

(вар-1) Маршрут есть последовательность чередующихся вершин и дуг, начинающаяся и заканчивающаяся вершинами и такая что соседи каждой дуги есть все её концевые вершины. (см. wikip-eng)

Назовём требование к соседям дуги - локальный критерий маршрута:

(ЛКМ1) Совокупность вершин соседних дуге совпадает с составом концевых вершин дуги.

Ясно что если мы прошли по графу и записали трассу (Стартовал в v1. Прошёл по e2. Попал в v3...), то на трассе ЛКМ1 будет соблюдено (ведь проходя ребро мы войдём с одной вершины а выйдем в другую), тем самым ЛКМ1 является необходимым, обязательным свойством трассы. Рассмотрим маршрут вар-1 как задание. Причём задание с проверками: пройдя из очередной вершины v, имеющей номер i в маршруте, по дуге номер i+1 мы куда-то попадём и надо проверить что это вершина номер i+2 в маршруте.

Небольшое рассуждение показывает что ЛКМ1 обеспечивает выполнимость задания:

в1 инцидентно д1, а значит мы можем двинуться по д1. Если д1 - петля, то мы вернёмся в в1 и именно так будет в задании. Если д1 - ребро, то мы попадём в другую его концевую и именно так будет в задании. Таким образом в обоих случаях мы сможем сделать шаг по д1 и проверка будет выполнена. Если мы пришли в конечную вершину задания то мы его выполнили, иначе надо повторить рассуждение.

Это конечно скрытая индукция, но нас не интересует формализация данного рассуждения, оно лишь делает очевидным (в концепте непрерывных движений в пространстве норгарфа) что ЛКМ1 достаточное условие проходимости маршрута.

То что иногда встречаются непроходимые определения маршрута см. обзор;-)

Немного формализации

На практике в теории обычно (см. обзор) маршрут задают двумя согласованными последовательностями - вершин и дуг (следите за нумерацией!;-): начни с вершины v1, пройди от неё по дуге e1 и ты попадёшь в вершину v2, далее по дуге e2… Формально мы имеем

Модификация вар-1

(вар-1.1) Маршрут есть две последовательности: дуг длины n>0 и вершин длины n+1, таких что:

для каждого i:[1..n] вершины номер i, i+1 инцидентны дуге номер i и различны для ребра.

В этом случае мы идём из i-вершины по i-дуге в вершину i+1. Фраза "различны для ребра" обеспечивает выполнение ЛКМ1.

Довольно просто показать, что вар-1 и вар-1.1 эквивалентны.

Y!L

Итак E - сорт дуг, V - сорт вершин, пусть loop - предикат быть петлёй.

Declaration walk (Nat:E) (Nat:V) : TV --объявление предиката "быть маршрутом".

Definition walk(es vs) =def ∀x:Def(es) inc(vs(x) es(x)) and inc(vs(x+1) es(x)) and (not(loop(es(x))) → vs(x)≠vs(x+1)).

Важное замечание-1. В декларации walk не сказано что функции аргументы должны быть от отрезков натуральных чисел. Это некое ослабление (а возможно обобщение).

А именно: если мы возьмём состав нат-чисел из Def(es), то vs должна быть задана на нём, и на нём +1. Тогда walk вычислится (не даст no_value) и возможно даже даст True. Более того если vs задана за пределами Def(es)∩(Def(es)+1), то эти значения не скажутся на значении walk, что тоже "обобщение", а скорее "шум". Таким образом есть неформализованное требование к заданию маршрутов: Def(es) должен быть отрезком Nat, а Def(vs) должен быть Def(es)+1!

Рассмотрим задание маршрута на примере, где 101 - длина конкретного маршрута в дугах.

Этот маршрут задаётся:

- объявлением двух функций: es1 [1..101]:E и vs1[1..102]:V,

- их свойствами: Full es, Full vs.

И назначением им значений командами вида !es(1):e1000!

Итак в теории мы можем задать маршрут как

- последовательность чередующихся вершин и дуг (вар-1),

- пару последовательностей: одна вершин, другая дуг (вар-1.1),

- и даже как пару: вершина и последовательность дуг (вар-0) (см. обзор).

Естественно что дальнейшие определения на основе маршрута, обладающего дополнительными свойствами, будут по разному выражаться в разных формализациях.

Кроме того скорее всего в теории стоит ограничиться одним способом определения маршрута.

Дальнейшие определения

У маршрута есть начальная вершина и конечная, вместе они называются концевые или терминальные. Остальные вершины маршрута - внутренние.

Открытый маршрут - концевые вершины различны.

Замкнутый маршрут - концевые вершины совпадают.

Цепь (trail/лучше тропа) есть маршрут все дуги которого различны. [ГСиА], с.17.

Цепь открыта/замкнута как маршрут.

Путь (path/лучше цепь) есть открытая цепь и все узлы различны. [ГСиА], с.17.

[МОГЗ] “Путём (или цепью) в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.”

“Путь (или цикл) называют простым, если ребра в нём не повторяются; элементарным, если он простой и вершины в нём не повторяются.”

Непосредственно дуг в пути у них нет;-)

Цикл (cycle) есть замкнутая цепь.

Узлы в цикле могут повторяться.

Простой цикл (circuit [GTaA] p.8) есть цикл у которого все вершины без последней различны.

ИЛИ ...не проходит дважды через одну вершину. [СТТГ]

Замечание. Термин "кольцо/ring" свободен в русской и en версии [СТТГ];-) Подстановка определений даёт: простой цикл есть маршрут все дуги которого различны и все вершины которого без последней различны и у которого первая и последняя вершины совпадают.

То что дуги различны, в купе с тем что дуги индуцируют вершины, делает очевидным что простой цикл можно задать одной последовательностью дуг.

Кольцо есть простой цикл но не петля. Оно интересно в онтологистике где связь с самим собой редка если вообще есть.

Об определениях кольца

Два важных случая наличия кольца это

- во-первых граф (целиком!) представляющий собой кольцо и

- во-вторых под-граф - кольцо некоего графа.

Критерии для графа быть кольцом (и только кольцом) указаны в таблице ТФК1 в колонке "граф". При этом чтобы проверить что граф есть кольцо нам надо будет найти некое упорядочение его дуг, либо убедиться что такого упорядочения нет. В случае под-графа - кольца, нам понадобится упорядочение некоторого подмножества дуг графа, содержащего кольцо.

Когда упорядочение задано будем называть кольцом простой цикл длины >1, т.е. не являющийся петлёй.

Ясно что для кольца должны быть требования только к совокупности дуг. В таблице ТФК1 эти требования выписаны в первой колонке. То что эти требования дают кольцо и только одно почти очевидно. См. идею доказательства после таблицы.

Мы рассмотрим три способа задания дуг кольца: последовательностью дуг, контуром дуг и унарным предикатом на дугах, чтобы посмотреть варианты их формализации и выбрать один.

Идея задания последовательностью. это классика, но у неё есть два варианта: а) совсем классический - отображение отрезка нат-чисел в дуги, б) инъекция дуг в отрезок нат-чисел, что может показаться более эстетичным, т.к. мы имеем как-бы разметку дуг числами, а не "чисел дугами";-)

Идея задания контуром. Последовательность задаёт кольцо "разрывая" его, представляя фактически как путь. Но то что в пути действительно есть: первая и последняя вершины пути, в кольце отсутствует - все вершины входят в кольцо одинаковым образом. Если мы введём на конечной совокупности дуг /Д1/ операцию next, задающую следующую, то для кольца это будет полная операция на Д1. Полная операция на Д1 может задать и несколько колец. Унарная операция задающая только одно кольцо называться контуром.

При оценке добавок в формализацию (например в Y!L;-) в случае применения контура (колонка "контур" ТФК1) указаны и добавки из определений Order и Contour [см].

Идея задания унарным предикатом. унарный предикат на дугах традиционным образом задаёт подмножество дуг, коего достаточно для подграфа кольца, т.к. в нём нет изолированных узлов, т.е. он дуго-порождаемый;-)

+?:как указать узлы кольца?

Таблица Формализация кольца /ТФК1/

Конец требований

Замечания

к б) граф Фраза"∃r:(E:E) Full(r) & Contour(r)" это синтаксически(!) конечно не первый и даже не второй порядок, утверждает, что существует такое зацикленное упорядочение дуг графа, что выполнено б).

к б) послед Последь зациклена "арифметически": следующий у последнего это первый. Это обеспечивается операцией % - остаток от деления.

к б) уна-преди тут довольно хитро, т.к. "следующего" нет. впрочем должно быть аналогично графу;-)

Идея доказательства единственности кольца

б) даёт связность, а в1) - только кольца, значит кольцо одно.