Форум программистов, компьютерный форум, киберфорум
Lisp
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.75/8: Рейтинг темы: голосов - 8, средняя оценка - 4.75
1 / 1 / 0
Регистрация: 02.11.2013
Сообщений: 7
1

Составить список степеней вершин графа, а также список вершин с одинаковою степенью

06.11.2013, 20:04. Просмотров 1522. Ответов 3
Метки нет (Все метки)

здравствуйте, помогите пожалуйста решить следующие задания:

1 Есть граф ((ab) (bc) (bd) (cd) (be) (ef) (fg) (fh) (gh) (fc) (fj) (fk) (ij)).Составить список степеней вершин графа , а также список вершин с одинаковою степенью.

2 Дерево описано ассоциированным списком вида: (a-b a-c b-e b-d c-f c-g e-h e-i d-j d-k g-l g-m ...). Построить список всех его листьев .

3 Дан список двухэлементных списков произвольной длины. Определить функционал, который меняет местами элементы в каждом втором из этих списков. Пример: ((1 2) (3 4) (5 6) (7 8) ...) ==> ((1 2) (4 3) (5 6) (8 7) ...).
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
06.11.2013, 20:04
Ответы с готовыми решениями:

Составить список вершин графа с указанием их степеней
Помогите пожалуйста с заданием: Есть неориентированный граф ((a b) (a c) (b f) (b e) (c d))....

Отобразить список вершин графа по матрице смежности
Здравствуйте! Предположим, у нас имеется матрица смежности для пяти вершин в виде вот такого...

Сумма степеней вершин графа G?
Доброго дня,участники форума. Подскажите, пожалуйста, верно ли моё решение данной задачи?...

Неориентированный граф задан списком вершин (abcdefgh) i списку рёбер (bg) (bc) (be) (gf) (fc) (ed). Найти список изолированных вершин
Неориентированный граф задан списком вершин (a b c d e f g h) i списку рёбер ((bg) (bc) (be) (gf)...

3
Модератор
Эксперт Python
27947 / 14909 / 2935
Регистрация: 12.02.2012
Сообщений: 24,431
Записей в блоге: 4
06.11.2013, 20:42 2
Список порядков вершин (HomeLisp):

Lisp
1
2
3
4
5
6
7
8
9
10
(defun degre-list (graph)
  (let ((vlist (setof (apply 'append graph))))
    (mapcar #'(lambda (x) 
            (list x (apply '+ (mapcar #'(lambda (y) (if (member x y) 1 0)) graph)))) vlist)))
 
==> degre-list
 
(degre-list '((a b) (b c) (b d) (c d) (b e) (e f) (f g) (f h) (g h) (f c) (f j) (f k) (i j)))
 
==> ((a 1) (d 2) (b 4) (e 2) (g 2) (h 2) (c 3) (f 6) (k 1) (i 1) (j 2))
Петли недопустимы

Добавлено через 11 минут
Вершины, сгруппированные по степеням:

Lisp
1
2
3
4
5
6
7
8
9
10
(defun elist (graph)
  (let* ((dlist (degre-list graph))
         (dl (setof (mapcar 'cadr dlist))))
    (mapcar #'(lambda (x) 
               (cons x (mapcar 'car (remove-if #'(lambda (y) (/= (cadr y) x)) dlist)))) dl)))
 
==> elist
(elist '((a b) (b c) (b d) (c d) (b e) (e f) (f g) (f h) (g h) (f c) (f j) (f k) (i j)))
 
==> ((4 b) (3 c) (6 f) (1 a k i) (2 d e g h j))
В каждом подсписке первый элемент - степень вершин, входящих в группу

Добавлено через 5 минут
Список листьев дерева:

Lisp
1
2
3
4
5
6
7
8
9
10
(defun list-tree (tree)
  (let ((blist (setof (mapcar 'car tree)))
        (elist (setof (mapcar 'cdr tree))))
    (remove-if #'(lambda (x) (member x blist)) elist)))
 
==> list-tree
 
(list-tree '((a . b) (a . c) (b . e) (b . d) (c . f) (c . g) (e . h) (e . i) (d . j) (d . k) (g . l) (g . m)))
 
==> (f h i j k L m)
Добавлено через 8 минут
Обмен элементов четных подсписков:

Lisp
1
2
3
4
5
6
7
8
9
(defun task (lst)
  (cond ((null lst) nil)
        (t (cons (car lst) (cons (list (cadr (cadr lst)) (car (cadr lst))) (task (cddr lst))))))) 
 
==> task
 
(task '((1 2) (3 4) (5 6) (7 8)))
 
==> ((1 2) (4 3) (5 6) (8 7))
2
1 / 1 / 0
Регистрация: 02.11.2013
Сообщений: 7
12.11.2013, 14:09  [ТС] 3
Цитата Сообщение от Catstail Посмотреть сообщение
Список листьев дерева:
Код Lisp

(defun list-tree (tree)
* (let ((blist (setof (mapcar 'car tree)))
* * * * (elist (setof (mapcar 'cdr tree))))
* * (remove-if #'(lambda (x) (member x blist)) elist)))
==> list-tree
(list-tree '((a . b) (a . c) (b . e) (b . d) (c . f) (c . g) (e . h) (e . i) (d . j) (d . k) (g . l) (g . m)))
==> (f h i j k L m)
не работает почему то
0
Модератор
Эксперт Python
27947 / 14909 / 2935
Регистрация: 12.02.2012
Сообщений: 24,431
Записей в блоге: 4
12.11.2013, 14:17 4
Добавь функцию setof:

Lisp
1
2
3
4
(defun setof (lst)
   (cond ((null lst) nil)
            ((member (car lst) (cdr lst)) (cons (car lst) (setof (remove (car lst) (cdr lst)))))
            (t (cons (car lst) (setof (cdr lst))))))
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
12.11.2013, 14:17

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Подсчитать количество вершин графа с четной степенью
Помогите решить задачу на неориентированный граф

Какой из кортежей может быть списком степеней вершин простого графа?
Какой из кортежей может быть списком степеней вершин простого графа. 1) (0,0,1,2,3), 2)...

Есть дерево (ab) (bc) (cd) (ce) (bf) (fg) (fh) (fi) (bj). Составить список висячих вершин
Есть дерево ((ab) (bc) (cd) (ce) (bf) (fg) (fh) (fi) (bj)). Составить список висячих вершин

Определить номера вершин графа, в которых пересекаются кратчайшие пути из вершин
Дано взвешенный граф в котором насчитывается N вершин и M ребер. Необходимо определитить номера...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.