Какому понятию теории графов соответствует

[_hum_]

Господа, подскажите, какому известному математическому понятию соответствует следующее

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

Спасибо.

[Narn]

Да вроде компонента сильной связности (strongly connected component).

[_hum_]

Narn в сообщении #1006412 писал(а):

Да вроде компонента сильной связности (strongly connected component).

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

[Narn]

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

[_hum_]

Вот нашел что-то из похожего

Convexity properties of graphs писал(а):

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)$.

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

[arseniiv]

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

_hum_ в сообщении #1007103 писал(а):

И всегда ли оно завязано прямо или косвенно на метрику?

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

_hum_ в сообщении #1007103 писал(а):

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

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

[_hum_]

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

arseniiv в сообщении #1007252 писал(а):

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

Да, орграф.

[arseniiv]

_hum_ в сообщении #1007273 писал(а):

так вы все-таки за то, что метрика обязательна?

Именно. Т. к. даже если её не было, в итоге получается всё равно что была. (Или я о каком-нибудь странном обобщении не знаю.)

_hum_ в сообщении #1007273 писал(а):

Но ведь тогда, получается, что выпуклость будет зависеть от того, какую метрику выбирать.

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

_hum_ в сообщении #1007273 писал(а):

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

А в каких теоремах участвует понятие? Там причину и стоит искать.

[_hum_]

arseniiv в сообщении #1007282 писал(а):

А в каких теоремах участвует понятие? Там причину и стоит искать.

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

[Geen]

Может тогда лучше в терминах порядка переформулировать вопрос?

[_hum_]

Geen в сообщении #1007387 писал(а):

Может тогда лучше в терминах порядка переформулировать вопрос?

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

[Geen]

_hum_ в сообщении #1007411 писал(а):

Geen в сообщении #1007387 писал(а):

Может тогда лучше в терминах порядка переформулировать вопрос?

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

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

[_hum_]

Geen в сообщении #1007415 писал(а):

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

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