Получить реберный список графа на лиспе - Lisp

Узнай цену своей работы

Формулировка задачи:

Помогите решить задачу, в вузе очень плохо объясняют почему-то именно этот предмет, а спрашивают жестко: "Граф задан с помощью списков. Построить его реберный граф". с комментами, если можно конечно, как работает прога.

Примечание : пусть задан граф G, тогда его

рёберный граф

L(G) —

это такой граф

, что две вершины графа L(G) смежны тогда и только тогда, когда их соответствующие рёбра имеют общую вершину («смежны») в G.

Пример работующей проги работающей программы сделайте пожалуйста с этим деревом: https://upload.wikimedia.org/wikiped...y_tree.svg.png Заранее спасибо.

Решение задачи: «Получить реберный список графа на лиспе»

textual
Листинг программы
  1. ;; Вспомогательная функция, проверяющая, имеют ли два
  2. ;; несовпадающих ребра общую вершину
  3.  
  4. (defun has-common-vertex (p1 p2)
  5.   (and (not (equal p1 p2)) (or (member (car p1) p2) (member (cadr p1) p2))))
  6.  
  7. ;; Построение реберного графа
  8.  
  9. (defun edge-graph (graph)
  10.   (let ((e-g nil)) ;; здесь будет результат
  11.     (dolist (e1 graph nil) ;; пробег по всем парам ребер
  12.       (dolist (e2 graph nil) ;; графа
  13.          (when (and (has-common-vertex e1 e2) ;; если пара имеет общую вершину
  14.                     (not (member (list e1 e2) e-g))  ;; и еще не присутствует в реберном графе
  15.                     (not (member (list e2 e1) e-g))) (push (list e1 e2) e-g)))) (renum e-g graph))) ;; добавим ее туда
  16.  
  17. ;; Перенумерация
  18.                    
  19. (defun renum (e-g graph)
  20.   (mapcar (lambda (r) (list (+ 1 (position (car r) graph))
  21.                             (+ 1 (position (cadr r) graph)))) e-g))
  22.  
  23. (edge-graph '((1 2) (1 3) (2 3) (3 4))) ;; граф с последней картинки
  24.  
  25. ==> ((3 4) (2 4) (2 3) (1 3) (1 2)) ;; реберный граф

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

5   голосов , оценка 4 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы