2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Какому понятию теории графов соответствует
Сообщение21.04.2015, 16:19 
Господа, подскажите, какому известному математическому понятию соответствует следующее

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

Спасибо.

 
 
 
 Re: Какому понятию теории графов соответствует
Сообщение21.04.2015, 16:47 
Да вроде компонента сильной связности (strongly connected component).

 
 
 
 Re: Какому понятию теории графов соответствует
Сообщение21.04.2015, 16:54 
Narn в сообщении #1006412 писал(а):
Да вроде компонента сильной связности (strongly connected component).

не, сильная связность - более сильное свойство (там нужна взаимная достижимость внутри множества).

 
 
 
 Re: Какому понятию теории графов соответствует
Сообщение21.04.2015, 17:35 
А, да, глупость сказал (вы же под "выпуклым" подмножеством понимаете только множество вершин, без ребер).

 
 
 
 Re: Какому понятию теории графов соответствует
Сообщение23.04.2015, 13:20 
Вот нашел что-то из похожего
Definitions
A set $S\subset V(G)$ of vertices is said to be convex if for all $u,v\in S$ the set $S$ contains all the vertices located on a shortest path between $u$ and $v$. Alternatively, a set $S$ is said to be convex if the distances satisfy $\forall u,v∈S, \forall w∈V∖S:d_G(u,w)+d_G(w,v)>d_G(u,v)$.

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

 
 
 
 Re: Какому понятию теории графов соответствует
Сообщение23.04.2015, 19:08 
Выпуклость в обычном понимании — это когда множество содержит все точки кратчайших кривых, соединяющих любые две его точки. В таких множествах нет дырок или «вмятин» и «вогнутостей» (откуда и название). Если взять, скажем, аффинное пространство, сечение выпуклого множества каким-то аффинным подпространством в нём тоже выпукло — в частности, с прямой пересечение будет отрезком/(полу)интервалом, и свечка, поставленная в любой точке внутри выпуклого множества, свет которой поглощается его границей, всегда осветит его целиком (и, вроде, в обратную сторону тоже работает — если из любой точки освещается, то выпукло). Есть какие-то полезные свойства, да я что-то все забыл.

_hum_ в сообщении #1007103 писал(а):
И всегда ли оно завязано прямо или косвенно на метрику?
Как-то же надо определять кратчайшие кривые. Началось всё, скорее всего, с выпуклости в аффинном пространстве — и там, в принципе, метрику можно не вводить, потому что отрезки и так там можем строить — но если мы связанное с ним линейное пространство вдруг надумаем сделать нормированным, метрика в обоих с кратчайшестью отрезков всегда согласится.

_hum_ в сообщении #1007103 писал(а):
Но здесь требуется только принадлежность кратчайшего пути, тогда как для моих нужд нужно чтобы все допустимые пути обладали обладали этим свойством.
Надеюсь, у вас орграф, потому что для неориентированного таким способом получится сразу вся компонента связности.

 
 
 
 Re: Какому понятию теории графов соответствует
Сообщение23.04.2015, 19:44 
arseniiv, так вы все-таки за то, что метрика обязательна? Но ведь тогда, получается, что выпуклость будет зависеть от того, какую метрику выбирать.
И все же я не увидел ответ на вопрос - почему так важно, чтобы кратчайший путь не выходил за пределы множества? В Евклидовой трехмерной - понятно - там тон задает прямолинейное распространение света, а в других областях - в той же теории графов, в дифференциальной геометрии - зачем им по кратчайшему?

arseniiv в сообщении #1007252 писал(а):
Надеюсь, у вас орграф, потому что для неориентированного таким способом получится сразу вся компонента связности.

Да, орграф.

 
 
 
 Re: Какому понятию теории графов соответствует
Сообщение23.04.2015, 19:57 
_hum_ в сообщении #1007273 писал(а):
так вы все-таки за то, что метрика обязательна?
Именно. Т. к. даже если её не было, в итоге получается всё равно что была. (Или я о каком-нибудь странном обобщении не знаю.)

_hum_ в сообщении #1007273 писал(а):
Но ведь тогда, получается, что выпуклость будет зависеть от того, какую метрику выбирать.
В общем случае. Для аффинного пространства уже получается не важно, если брать только метрики, согласованные с остальной структурой. Для каких-то важных случаев тоже вполне может статься.

_hum_ в сообщении #1007273 писал(а):
а в других областях - в той же теории графов, в дифференциальной геометрии - зачем им по кратчайшему?
А в каких теоремах участвует понятие? Там причину и стоит искать. :-)

 
 
 
 Re: Какому понятию теории графов соответствует
Сообщение24.04.2015, 00:05 
arseniiv в сообщении #1007282 писал(а):
А в каких теоремах участвует понятие? Там причину и стоит искать. :-)

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

 
 
 
 Re: Какому понятию теории графов соответствует
Сообщение24.04.2015, 00:26 
Аватара пользователя
Может тогда лучше в терминах порядка переформулировать вопрос?

 
 
 
 Re: Какому понятию теории графов соответствует
Сообщение24.04.2015, 01:18 
Geen в сообщении #1007387 писал(а):
Может тогда лучше в терминах порядка переформулировать вопрос?

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

 
 
 
 Re: Какому понятию теории графов соответствует
Сообщение24.04.2015, 01:24 
Аватара пользователя
_hum_ в сообщении #1007411 писал(а):
Geen в сообщении #1007387 писал(а):
Может тогда лучше в терминах порядка переформулировать вопрос?

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

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

 
 
 
 Re: Какому понятию теории графов соответствует
Сообщение24.04.2015, 01:40 
Geen в сообщении #1007415 писал(а):
Каждому порядку соответствует орграф. Но не каждый орграф задаёт порядок.
Поэтому, если исходная задача формулируется в терминах порядка, то может не стоит графы притягивать?

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

 
 
 [ Сообщений: 13 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group