2014 dxdy logo

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

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




 
 Какому известному мат. понятию соответствует?
Сообщение20.01.2015, 13:28 
Господа, помогите определить, какому известному мат. понятию соответствует следующее потребовавшееся мне для работы понятие.

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

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

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

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

 
 
 
 Re: Какому известному мат. понятию соответствует?
Сообщение20.01.2015, 20:06 
_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..

 
 
 
 Re: Какому известному мат. понятию соответствует?
Сообщение21.01.2015, 01:17 
arseniiv, мне нужен термин, а не обозначение :) потому как надо при разговоре как-то эту "косвенную" связь уметь называть.

 
 
 
 Re: Какому известному мат. понятию соответствует?
Сообщение21.01.2015, 02:08 
_hum_ в сообщении #965936 писал(а):
мне нужен термин, а не обозначение :)
Знал бы — не таил. :-) (Про α-связи тоже немного подумал, но ничего не пришло, да и терминов из теории графов мало знаю, чтобы пришло.) Если его нет, или знающие не появятся, можно пока попридумывать аналогию, обобщение…

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

 
 
 
 Re: Какому известному мат. понятию соответствует?
Сообщение21.01.2015, 13:01 
arseniiv в сообщении #965951 писал(а):
Как-то так?: из $a$ в $b$ в графе отношения (так говорят?) есть путь длиною больше 1…

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

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

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

 
 
 
 Re: Какому известному мат. понятию соответствует?
Сообщение21.01.2015, 20:30 
_hum_ в сообщении #966088 писал(а):
Путь длиной 1 тоже должен попадать.
Вы же сказали, что непосредственно элементы в отношение входить не должны. Это путь длины 1.

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

 
 
 
 Re: Какому известному мат. понятию соответствует?
Сообщение21.01.2015, 21:58 
arseniiv в сообщении #966391 писал(а):
Вы же сказали, что непосредственно элементы в отношение входить не должны. Это путь длины 1.

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

 
 
 
 Re: Какому известному мат. понятию соответствует?
Сообщение21.01.2015, 22:19 
Тогда я запутался: что вы называете нетривиальным путём?

 
 
 
 Re: Какому известному мат. понятию соответствует?
Сообщение21.01.2015, 23:19 
arseniiv в сообщении #966457 писал(а):
огда я запутался: что вы называете нетривиальным путём?

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

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

 
 
 
 Re: Какому известному мат. понятию соответствует?
Сообщение21.01.2015, 23:52 
arseniiv

(Оффтоп)

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


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


 
 
 
 Posted automatically
Сообщение21.01.2015, 23:53 
Аватара пользователя
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Computer Science»

 
 
 
 Re: Какому известному мат. понятию соответствует?
Сообщение22.01.2015, 01:59 

(2 _hum_.)

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

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


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