Какому известному мат. понятию соответствует?

[_hum_]

Господа, помогите определить, какому известному мат. понятию соответствует следующее потребовавшееся мне для работы понятие.

Пусть имеется некоторое свойство $P$, которым могут обладать некоторые направленные графы. Для графа, обладающего таким свойством, введем следующее определение:

α-связью договоримся называть всякую связь из транзитивного замыкания этого графа, обладающую следующим свойством:
любое удаление из транзитивного замыкания этой связи и связей, обеспечивающих ее воспроизведение (через транзитивность), с необходимостью ведет к потере свойства $P$.

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


P.S. И еще, какой термин из теории отношений используется для указания, что элемент $a$ связан c элементом $b$ нетривиальным путем (в случае тривиального пути понятно - "$a$ находится в отношении с элементом $b$")?

[arseniiv]

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

P.S. И еще, какой термин из теории отношений используется для указания, что элемент $a$ связан c элементом $b$ нетривиальным путем (в случае тривиального пути понятно - "$a$ находится в отношении с элементом $b$")?

Правильно понимаю, что здесь нетривиальным — это значит, что не $a\mathrel Rb$, но $a\mathrel{R^*}b$? ($R^*$ тут пускай обозначает транзитивное замыкание $R$). Тогда вот так как раз и можно описать, хотя отдельного термина не знаю — но хотя бы это коротко (отношение «нетривиальных связей» в $R$ будет записываться $R^*\setminus R$).

-- Вт янв 20, 2015 22:13:27 --

Насколько помню, транзитивное замыкание отношения $\to$ нередко записывается $\stackrel{+}{\to}$, $R^+ = R \cup R\circ R \cup R\circ R\circ R \cup\ldots$, также есть $\stackrel{*}{\to}$, $R^* = \mathrm{id} \cup R^+$ и (не видел, но по аналогии) $\stackrel{?}{\to}$, $R^? = \mathrm{id} \cup R$ — рефлексивное замыкание. (Для симметричного замыкания ничего не помню.) Тогда ваше отношение можно записать как $R^+\circ R, R\circ R^+, R^2\circ R^*$ etc..

[_hum_]

arseniiv, мне нужен термин, а не обозначение :) потому как надо при разговоре как-то эту "косвенную" связь уметь называть.

[arseniiv]

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

мне нужен термин, а не обозначение :)

Знал бы — не таил. (Про α-связи тоже немного подумал, но ничего не пришло, да и терминов из теории графов мало знаю, чтобы пришло.) Если его нет, или знающие не появятся, можно пока попридумывать аналогию, обобщение…

Как-то так?: из $a$ в $b$ в графе отношения (так говорят?) есть путь длиною больше 1…

[_hum_]

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

Как-то так?: из $a$ в $b$ в графе отношения (так говорят?) есть путь длиною больше 1…

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

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

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

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

[arseniiv]

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

Путь длиной 1 тоже должен попадать.

Вы же сказали, что непосредственно элементы в отношение входить не должны. Это путь длины 1.

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

Вообще, в теории графов это вроде называется по-английски Reachability (достижимостью, связностью?).

Достижимостью, да.

[_hum_]

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

Вы же сказали, что непосредственно элементы в отношение входить не должны. Это путь длины 1.

не говорил такого :) я говорил, что для пути с шагом 1 - это понятно, как называть. а вот когда нетривиальный путь - нет.

[arseniiv]

Тогда я запутался: что вы называете нетривиальным путём?

[_hum_]

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

огда я запутался: что вы называете нетривиальным путём?

в данном контексте подразумевалась "может быть нетривиальным", а не "обязательно нетривиальный".

[arseniiv]

Так это ж просто транзитивное (и рефлексивное, если надо) замыкание! Да, какого-то общего слова, чтобы было «$a$ <слово> $b$», нету… В конце концов, можно прямо читать запись: «а <отношение>-плюс бэ», «а <отношение>-звёздочка бэ». С производными так делают. Запись и чтение описываются/рассказываются один раз, дальше всё прекрасно.

[_hum_]

arseniiv

(Оффтоп)

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

-- Чт янв 22, 2015 00:52:36 --

[Toucan]

Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Computer Science»

[arseniiv]

(2 _hum_.)

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

мне нужно это не для статьи, а для того, чтобы можно было ввести соответствующий термин в обывательскую терминологию

Понял-понял. Но вдруг и это пригодилось бы как-нибудь. В любом случае, пока предложить больше нечего.