Транзитивное замыкание бинарного отношения

@bor_b · Регистрация: 29.10.2015

Студворк — интернет-сервис помощи студентам

Подскажите пожалуйста как на заданном графе R= ((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6) ) найти транзитивное замыкание бинарного отношения?

@helter · 30.10.2015, 00:21

Алгоритм нахождения транзитивных замыканий бинарных отношений — в студию!

@bor_b · 05.11.2015, 00:05 **[ТС]**

Может кто подскажет как реализовать эту логику
R= ((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6))
1. (1 3) (3 2) →(1 2)
2. (1 4) (4 5) → (1 5)
R*= ((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6))
3. (2 1) (1 3) → (2 3)
R** = ((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6))
4. (3 2) (2 1) → (3 1)
R*** = ((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6))
5. (4 1) (1 3) → (4 3)
6. (4 1) (1 4) → (4 4)
R**** = ((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6))
7. (4 5) (5 3) → (4 3)
8. (4 5) (5 6) → (4 6)
R***** = ((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6))
9. (5 3) (3 2) → (5 2)

@vlisp · 05.11.2015, 01:46

Lisp
1
(assoc (cadr (nth & r)) r)

@castorsky · 05.11.2015, 15:11

Сообщение от bor_b

Может кто подскажет как реализовать эту логику
R= ((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6))
1. (1 3) (3 2) →(1 2)
2. (1 4) (4 5) → (1 5)

и где тут логика? Элементов (1 2), (1 5) в R нет, значит нет замкнутости. Элемент (4 1) в R идет раньше чем (4 5), следовательно результатом должен быть он.

@helter · 06.11.2015, 00:47

Ну да, рёбра надо было добавлять к графу. А порядок пар неважен, это же множество.

На языке графов эту логику можно реализовать как-то так:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
(defun star (graph)
  (let ((new-arrows '()))
    (do-vertices (v1 graph)
      (do-successors (v2 v1 graph)
        (do-successors (v3 v2 graph)
          (unless (successorp v3 v1 graph)
            (push (make-arrow v1 v3) new-arrows)))))
    (if (null new-arrows)
        (values graph nil)
        (values (add-arrows new-arrows graph) new-arrows))))
 
(defun transitive-closure (graph)
  (let (new-arrows)
    (loop
      (setf (values graph new-arrows) (star graph))
      (unless new-arrows
        (return graph)))))

@bor_b · 17.11.2015, 20:29 **[ТС]**

Добавлено через 5 минут
Подскажите пожалуйста что делаю не так. Выдает ошибку когда ввожу (TRANSITIVE-CLOSURE '((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6) ))

@helter · 17.11.2015, 22:29

Сообщение от bor_b

Выдает ошибку когда ввожу (TRANSITIVE-CLOSURE '((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6) ))

Во-первых, в лиспе нет такой функции. Поэтому если вы запустите лисп и введёте туда это, что вы ожидаете кроме ошибки?

Во-вторых, ветеринаров здесь нет. Сообщаете об ошибке - должен быть минимальный неработающий пример, текст ошибки, бектрейс, можно указание реализации лиспа и операционной системы.

@bor_b · 17.11.2015, 22:47 **[ТС]**

Извините может я не правильно выражаюсь, я в этом деле человек новый.

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
[1]> 
STAR
[2]> 
TRANSITIVE-CLOSURE
[3]> (TRANSITIVE-CLOSURE '((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6)))
 
*** - EVAL: функция DO-VERTICES не определена
Имеются следующие варианты продолжения:
USE-VALUE      :R1      Input a value to be used instead of (FDEFINITION 'DO-VERTICES).
RETRY          :R2      Еще раз
STORE-VALUE    :R3      Input a new value for (FDEFINITION 'DO-VERTICES).
ABORT          :R4      Прервать главный цикл
Break 1 [4]>

@helter · 17.11.2015, 23:29

Сообщение от bor_b

Извините может я не правильно выражаюсь, я в этом деле человек новый.

В каком "этом"? У вас здравый смысл есть? "Доктор, у меня болит, сделайте мне хорошо."

Я так понимаю, вы взяли и забили в лисп то, что я написал. А не надо так делать. Не копипастьте код, который не понимаете, это чревато.

Разумеется, я не писал вам работающее решение. Я не из тех, кто пишет решения. Я написал, как сделать "на языке графов". Это язык, в котором не просвечивают детали реализации графов, а программа пишется в терминах теории графов. Чтобы вы увидели, как словесное описание алгоритма превратить в код. Я надеялся, что это будет прозрачная и понятная запись алгоритма.

Беда в том, что в лисп не встроен "язык графов". Если он вам нравится, его надо предварительно написать. Функции, макросы. Будете работать - могу помогать. Тут ещё один товарищ графами интересуется, можете объединить усилия.

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Access VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .

@bor_b 0 / 0 / 0 Регистрация: 29.10.2015 Сообщений: 4

	Транзитивное замыкание бинарного отношения 29.10.2015, 22:47. Показов 3776. Ответов 9 Метки нет (Все метки) Подскажите пожалуйста как на заданном графе R= ((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6) ) найти транзитивное замыкание бинарного отношения? 0

@helter 4528 / 3522 / 358 Регистрация: 12.03.2013 Сообщений: 6,038
	30.10.2015, 00:21
	Алгоритм нахождения транзитивных замыканий бинарных отношений — в студию! 0

@bor_b 0 / 0 / 0 Регистрация: 29.10.2015 Сообщений: 4
	05.11.2015, 00:05 [ТС]
	Может кто подскажет как реализовать эту логику R= ((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6)) 1. (1 3) (3 2) →(1 2) 2. (1 4) (4 5) → (1 5) R= ((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6)) 3. (2 1) (1 3) → (2 3) R* = ((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6)) 4. (3 2) (2 1) → (3 1) R* = ((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6)) 5. (4 1) (1 3) → (4 3) 6. (4 1) (1 4) → (4 4) R = ((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6)) 7. (4 5) (5 3) → (4 3) 8. (4 5) (5 6) → (4 6) R*** = ((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6)) 9. (5 3) (3 2) → (5 2) 0

@bor_b 0 / 0 / 0 Регистрация: 29.10.2015 Сообщений: 4
	17.11.2015, 20:29 [ТС]
	Добавлено через 5 минут Подскажите пожалуйста что делаю не так. Выдает ошибку когда ввожу (TRANSITIVE-CLOSURE '((1 3) (1 4) (2 1) (3 2) (4 1) (4 5) (5 3) (5 6) )) 0