какую топологию я хочу
Apr. 20th, 2008 03:27 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
hgrделаю над собой страшное усилие -- пытаюсь перейти чиста канкретно на язык математики.
есть три стандартные аксиомы метрики, а я буду рядом писать, какие мне нужны вместо них:
1. d (x, y) = 0 iff x = y (вот эта единственная аксиома, которая мне подходит),
2. d (x, z) < или = d (x, y) + d (y, z) (вот это не подходит категорически: в этом неравенстве подходит только знак < , без "равно": т.к. пространство дискретно, то количество вершин графа является мерой расстояния само по себе; следовательно, если на одну вершину больше, то и расстояние больше),
3. d (x, y) = d (y, x) (это годится, но только для обычного случая; а может и не годиться: если граф направленный, то имеет смысл понятие расстояния только в одном направлении, а в обратном направлении просто не может быть никакого расстояния).
--------
я совсем не уверен, что на этом мои запросы к метрике кончаются, но, похоже, это главное или очень важное.
если думать о геометрической репрезентации таких графов, то, видимо, вместо точек в пространстве д.б. какие-то формулы, похожие на волновые функции Шредингера.
есть три стандартные аксиомы метрики, а я буду рядом писать, какие мне нужны вместо них:
1. d (x, y) = 0 iff x = y (вот эта единственная аксиома, которая мне подходит),
2. d (x, z) < или = d (x, y) + d (y, z) (вот это не подходит категорически: в этом неравенстве подходит только знак < , без "равно": т.к. пространство дискретно, то количество вершин графа является мерой расстояния само по себе; следовательно, если на одну вершину больше, то и расстояние больше),
3. d (x, y) = d (y, x) (это годится, но только для обычного случая; а может и не годиться: если граф направленный, то имеет смысл понятие расстояния только в одном направлении, а в обратном направлении просто не может быть никакого расстояния).
--------
я совсем не уверен, что на этом мои запросы к метрике кончаются, но, похоже, это главное или очень важное.
если думать о геометрической репрезентации таких графов, то, видимо, вместо точек в пространстве д.б. какие-то формулы, похожие на волновые функции Шредингера.
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2008-04-19 11:40 pm (UTC)По-моему, вполне справедливое требование.
За исключением, конечно, случая отсутствия пути - тогда d(y,z)=∞ или d(x,y)=∞.
Но и тут можно, в принципе, как-то играть, например, заявив, что отсутствие пути есть большая, но конечная величина (то есть, граф полностью связный).
(я любитель, не профессионал;)
no subject
Date: 2008-04-19 11:48 pm (UTC)да, м.б., надо ввести в метрику четвертую аксиому:
4. d (x, y) = 1 iff x, y суть соседние вершины графа.
no subject
Date: 2008-04-19 11:50 pm (UTC)no subject
Date: 2008-04-20 12:01 am (UTC)А граф, значит, у вас без весов на дугах. Понятно.
структуры на графах
Date: 2008-04-20 12:08 am (UTC)Мне кажется, Вы здесь слово "топология" используете в несколько нестандартном смысле. Поэтому я предлагаю изложить то, что Вам нужно, в какой-то другой форме, без привлечения этого слова.
Любой граф можно рассматривать как топологический объект, а можно этого и не делать. Описать граф можно не привлекая никакой геометрии -- в чисто комбинаторных терминах. Например, сказать, что вершины занумерованы числами, а рёбра соединяют вершины с такими-то номерами (и далее список).
Хотелось бы сделать ещё одно замечание (малосодержательное) по поводу условия 2. Когда Вы говорите, что знак равенства категорически не подходит, то непонятна причина. Равенство здесь лишь допускается. Если у Вас знак был бы всегда "строго меньше", то условие 2 всё равно выполнено.
Я сейчас на таком примере поясню. Возьмём высказывание "2 меньше либо равно 3". Оно истинно, потому что представляет собой сокращённую форму дизъюнкции двух высказываний, то есть: "2 меньше 3" или "2 равно 3". Первое из взятых в кавычки высказываний истинно, а второе ложно. Дизъюнкция по определению будет истинной.
Далее, в Вашем случае знак равенства в каких-то отдельных случаях возможен. Например, если y=z (а такое возможно), то d(x,z)=d(x,y)+d(y,z) в силу того, что y=z, а потому d(y,z)=0.
> количество вершин графа является мерой расстояния само по себе
Смысл этой фразы непонятен. Количество вершин в графе фиксировано и не зависит от точек. А значение d(x,y) зависит от x и y. В каком смысле тогда число вершин есть является мера расстояния?
У меня складывается впечатление, что Вам требуется нечто, что можно описать как граф с дополнительной структурой. Такая структура может быть, вообще говоря, любой. Например, на рёбрах могут быть расставлены направления ("стрелочки"). Или так: на множестве рёбер задаётся некая функция -- скажем, "стоимость проезда" по данному ребру. Такого рода конструкции часто привлекаются. При этом речь идёт не о смене прежней топологии, а о привлечении дополнительной структуры -- новой метрики, топологии, -- чего угодно. Старая структура при этом также остаётся, просто о ней обычно не вспоминают.
Я готов ответить на любые вопросы по этому поводу.
Re: структуры на графах
Date: 2008-04-20 12:19 am (UTC)http://en.wikipedia.org/wiki/Semimetric
и
http://en.wikipedia.org/wiki/Pseudometric_space
но только с отказом от аксиомы симметрии
Но для математиков, аксиома симметрии так дорога (смайл) что несимметричные расстояния не удосуживаются имени метрика, даже с префиксом "псевдо", "полу" и "недо"
Такие штуки называются directed distance и ими занимаются гораздо меньше чем метриками и метризуемостью, насколько я понял
Автор журнала задается вопросом, каковы будут геометрические свойства пространств, если волюнтаристически взять и использовать вместо метрики - directed distance на диграфах.
метрика графа
Date: 2008-04-20 12:23 am (UTC)Условие 2 при этом выполнено всегда.
Тут дело вот в чём. Если Вы вводите новую промежуточную вершину, разбивая ребро на две части, то меняется сам граф -- у него становится больше вершин. Поэтому не удивительно, что меняется и функция расстояния на нём. Раньше расстояние между точками было равно 1, а стало равно 2.
Как топологическое пространство граф, конечно, остался тем же. Но это ничему не противоречит, потому что топологическое пространство само по себе никакой метрикой не снабжено. На нём можно ввести метрику, которая определяет ту же топологию, и это можно сделать очень многими способами.
Re: структуры на графах
Date: 2008-04-20 12:34 am (UTC)Re: структуры на графах
Date: 2008-04-20 12:52 am (UTC)Шизофрения окрестности точки топ.пространства - это только у Вадима Мироновича в журнале может обсуждаться...
salesman traveller problem
Date: 2008-04-20 01:00 am (UTC)Тут даже имеет смысл ситуация, когда ребро снабжено отрицательным весом. Положительный означает, что мы платим, а тут может быть "доходное турне", оплачиваемое "спонсором". Типа, я проделал некий маршрут, по дороге кого-то "попиарил", мне за это башлей дали :)
Re: структуры на графах
Date: 2008-04-20 01:02 am (UTC)Re: salesman traveller problem
Date: 2008-04-20 01:03 am (UTC)язык описания
Date: 2008-04-20 01:10 am (UTC)Они могут быть какие угодно -- вплоть до появления "отрицательных расстояний", как я описал в примере чуть ниже. При этом можно с такой ситуацией либо примириться, а можно просто поменять язык описания, заменив расстояние на "расходы", и тогда "отрицательный расход" есть просто "доход" :)
Re: язык описания
Date: 2008-04-20 01:15 am (UTC)no subject
Date: 2008-04-20 03:41 am (UTC)Re: метрика графа
Date: 2008-04-20 08:30 am (UTC)про условие 2 уже понял.
no subject
Date: 2008-04-20 08:31 am (UTC)Re: структуры на графах
Date: 2008-04-20 08:32 am (UTC)спасибо!
вот
Date: 2008-04-20 05:53 pm (UTC)http://hgr.livejournal.com/1378786.html#cutid1