Пусть у нас есть ориентированный граф Р со следующими свойствами:
1) без петель
2) есть транзитивность (то есть если есть ребра A-->B; B-->C, то есть ребро A-->C для любых троек вершин, не обязательно различных).
Легко видеть, что эти два условия означают ацикличность

Пусть мы строим граф Р1, который получается из графа Р0 добавлением ребер по следующему правилу: ориентированное ребро X->Y будет добавлено, если Y.out включено в X.out, где X.out = {T | существует ребро X->T}. Y.out определяется аналогично.

Далее строится граф Р2, полученный аналогично из Р1, и так далее.

Требуется доказать следующие утверждения
1) В каждом таком Рi не будет циклов
2) Найдется такой i, что для графа Pi будут выполнены все нижеприведенные условия: а)граф без петель; б) есть транзитивность; в)для любых троек вершин A,B,C если не существует ребер A->B и B->C, то не существует ребра A->C

задан 16 Сен '17 0:50

10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×697
×153
×68

задан
16 Сен '17 0:50

показан
196 раз

обновлен
16 Сен '17 0:50

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru