помощь зала?

[hgr]

в тех модальных логиках пространства, где рассматривается топология (а не расстояния), всё построено на эквивалентности топологических понятий открытого и замкнутого множеств и, соответственно, понятий необходимости и возможности: т.к. в открытом множестве любая его точка -- внутренняя, то *необходимо* существует такая ее ε-окрестность, любая точка которой будет также принадлежать этому множетсву; если же множество замкнутое, то такая окрестность лишь *возможна*.

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

где здесь эквиваленты модальных "необходимо" и "возможно"? (я уверен, что они есть, но у меня плохо и с математикой, и с пространственным воображением). чтО здесь у нас будет вместо эпсилон-окрестности?

общий смысл мне понятен, но с формализмом торможу.

(а общий смысл такой:
для графа С(G) будет сохраняться различие между степенями для некоторых вершин (тех, к которым достраивались ребра). те, к которым что-то достраивалось, -- это, по-моему, внешние, т.е. дискретный аналог топологической границы. )

УПД кажется, разобрался. тут различаются "внутренние" и "внешние" ребра графа -- т.е. допустимые для данного пространства пути.

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

Comments

[kouzdra.livejournal.com]

Ну раз за это цепляться, можно наверное рассмотреть множества связные подграфы, образованные ребрами, сумма степеней концов которых >= n, как открытые - соответственно их дополнения, взять это в качестве базы топологии и посмотреть что получится.

Хотя imho сомнительно и непонятен смысл.

[hgr.livejournal.com]

смысл -- построить "топологическую" пространственную логику для пространства на графе.
для обычных и даже не очень обычных ("дистанционных") пространств она построена.
ее главные положения -- interior = square, closure = diamond operators of modal logic.
требуется достроить до графов. тут в литературе тоже кой-какие наметки недавно появились, но мне мало.

[losia.livejournal.com]

Я вот чего не поняла: при соединении двух вершин, степень каждой из них повысится на 1. Прии следующем соединении учитываем эту повысившуюся степень или старую?

[hgr.livejournal.com]

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

[losia.livejournal.com]

Вообще непонятно, на чем строится топология: на ребрах или на вершинах?
Если граф направленный, то первое, что приходит в голову: считать граничными точки, из которых нельзя уйти, или в которые нельзя прийти, т.е. "хвосты". А все остальное -внутреннее.
Окрестность - шаг вперед и шаг назад.

Приведенное же Вами понятие замыкания пока никаких топологических ассоциаций не вызвало. В топологическом смысле замыкание - это присоединение к множеству всех его граничных точек, которые ему еще не принадлежат.

[hgr.livejournal.com]

направленность не надо сюда вмешивать.

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

[losia.livejournal.com]

1. Привычно, что топология строится на множестве однотипных объектов :
либо это ребра, либо вершины, либо (под)графы. Видимо, третье.

2. Общее определение (топологического) замыкания множества - это множество, объединенное со всеми своими предельными точками (т.е. граничными и выколотыми).

2.1 Предельная точка множества-это такая, у которой для любого эпсилона в эпсилон окрестности существуют другие точки множества. И, вообще говоря, их д.б. бесконечное число, т.к. всегда можно можно взять епсилон меньший, чем растояние до каждой конкретной точки. Поэтому если речь идет о конечных множествах, то эпсилоны не для нас.

3.Есть понятие замыкания множества X по операции (или их множеству).
Это все возможные результаты применения этих операций к элементам множества X или предыдущим результатам.
Тут множество применений операций бесконечно, поэтому предельные точки есть. Но вот множество результатов операций может оказаться конечным.
Например, сложение по модулю N. Операцию можно применять бесконечно, а результаты всегда- 0,1,2,.., N

[hgr.livejournal.com]

1. в этом смысле -- вершины.

2. в графе такого определения дать нельзя, поэтому придумали то, какое придумали.

2.1. да, эпсилоны не для нас: внутри графа мера расстояния -- это количество вершин между теми вершинами, между которыми расстояние. т.е. оно будет 0, 1, 2 и т.д., в зависимости от пути.

3. да, понятно.

[hgr.livejournal.com]

напр., здесь http://pco.iis.nsk.su/grapp/WIN/sl_z.html
с ссылкой на эту книгу (ее тоже можно скачать в разных местах) http://lib.mexmat.ru/books/523 (я уже забыл, где скачивал, могу прислать).

из новых работ -- http://books.google.ru/books?id=jI_AmQsoslEC&printsec=frontcover&dq=linfan+mao&ei=JbMmS6nPHp7IzASF3fWfCw&cd=1#v=onepage&q=closure&f=false c
с. 66 (книга полностью есть на гиге).

пространство на графе -- это развивалось давно как графы, embedded в топологические пространства, но сейчас появляются всякие штуки без embedding'a (если ничего не путаю).

просто обычно топологическое пространство определяется на множестве неотрицательных действительных чисел, а тут то же самое определение, только на множестве натуральных чисел.

[hgr.livejournal.com]

далАсь Вам эта топология! я ведь сразу написал, что здесь не топология, а только аналогия с топологией.

в аналогии не может всё выполняться.

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

теперь другие цели, где графы еще больше напоминают пространства. вот и нужно продолжение банкета (аналогии)!

[hgr.livejournal.com]

а можно было бы построить "ослабленную" топологию, аналогичную "ослабленной" метрике дистанционных пространств (когда только первая аксиома обязательна), где из четырех аксиом Куратовского обязательны к выполнению только три?
это не нужно для той работы, которую я пишу сейчас. но, в принципе, это может быть нужно для формализации того, что называют перцепционным пространством.

[hgr.livejournal.com]

вот есть очень хорошая книга
http://www.informatik.uni-trier.de/~ley/db/reference/spatial/spatial2007.html (полностью бесплатно на гиге) плюс ряд чуть более ранних статей тех же аффтаров.
там про разные модальные логики разных пространств (включая такие пространства, где только первая из трех метрических аксиом выполняется).

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

[hgr.livejournal.com]

вот воистину приятно слышать!!!

[hgr.livejournal.com]

вот нашел про логику пространства на графах, со с. 7:

http://www.informatik.uni-bremen.de/~okutz/metric_tocl.pdf