2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Какому известному мат. понятию соответствует?
Сообщение20.01.2015, 13:28 


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

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

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

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

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

 Профиль  
                  
 
 Re: Какому известному мат. понятию соответствует?
Сообщение20.01.2015, 20:06 
Заслуженный участник


27/04/09
28128
_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 


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

 Профиль  
                  
 
 Re: Какому известному мат. понятию соответствует?
Сообщение21.01.2015, 02:08 
Заслуженный участник


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

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

 Профиль  
                  
 
 Re: Какому известному мат. понятию соответствует?
Сообщение21.01.2015, 13:01 


23/12/07
1757
arseniiv в сообщении #965951 писал(а):
Как-то так?: из $a$ в $b$ в графе отношения (так говорят?) есть путь длиною больше 1…

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

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

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

 Профиль  
                  
 
 Re: Какому известному мат. понятию соответствует?
Сообщение21.01.2015, 20:30 
Заслуженный участник


27/04/09
28128
_hum_ в сообщении #966088 писал(а):
Путь длиной 1 тоже должен попадать.
Вы же сказали, что непосредственно элементы в отношение входить не должны. Это путь длины 1.

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

 Профиль  
                  
 
 Re: Какому известному мат. понятию соответствует?
Сообщение21.01.2015, 21:58 


23/12/07
1757
arseniiv в сообщении #966391 писал(а):
Вы же сказали, что непосредственно элементы в отношение входить не должны. Это путь длины 1.

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

 Профиль  
                  
 
 Re: Какому известному мат. понятию соответствует?
Сообщение21.01.2015, 22:19 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Какому известному мат. понятию соответствует?
Сообщение21.01.2015, 23:19 


23/12/07
1757
arseniiv в сообщении #966457 писал(а):
огда я запутался: что вы называете нетривиальным путём?

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

 Профиль  
                  
 
 Re: Какому известному мат. понятию соответствует?
Сообщение21.01.2015, 23:30 
Заслуженный участник


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

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


23/12/07
1757
arseniiv

(Оффтоп)

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


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


 Профиль  
                  
 
 Posted automatically
Сообщение21.01.2015, 23:53 
Админ форума
Аватара пользователя


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

 Профиль  
                  
 
 Re: Какому известному мат. понятию соответствует?
Сообщение22.01.2015, 01:59 
Заслуженный участник


27/04/09
28128

(2 _hum_.)

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 13 ] 

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group