Форум программистов, компьютерный форум, киберфорум
Lisp
Войти
Регистрация
Восстановить пароль
Карта форума Темы раздела Блоги Сообщество Поиск Заказать работу  
 
Рейтинг 4.85/13: Рейтинг темы: голосов - 13, средняя оценка - 4.85
0 / 0 / 0
Регистрация: 06.06.2015
Сообщений: 6
1

Нахождение центральной вершины орграфа

03.12.2015, 16:52. Показов 2653. Ответов 5

Author24 — интернет-сервис помощи студентам
Дан некоторый связный ориентированный граф. Необходимо найти в нём центральную вершину (наиболее равноудалённую ото всех остальных). Наиболее равноудалённая вершина может быть получена как вершина, среднее расстояние от которой до других вершин наиболее близко к среднему значению этой величины для всех вершин графа. Если таких вершин несколько, вывести их все.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
03.12.2015, 16:52
Ответы с готовыми решениями:

Нахождение вершины орграфа, достижимой от всех других вершин
Имеется невзвешенный орграф, требуется найти вершину достижимую от всех других вершин....

Для данной вершины орграфа вывести на экран все «выходящие» соседние вершины
Ребят, помогите пожалуйста сделать задачку на шарпе. Задание: Для данной вершины орграфа вывести на...

Вывести на экран вершины орграфа, смежные с данной
Вывести на экран те вершины орграфа, смежные с данной, т.е. вывести "входящие" и "выходящие"...

Вывести на экран вершины орграфа, смежные с данной
Уффф, к завтрашнему дню нужно сдать эти задачи, помогите пожалуйста кто чем сможет :sorry:...

5
Модератор
Эксперт функциональных языков программированияЭксперт Python
37291 / 20725 / 4272
Регистрация: 12.02.2012
Сообщений: 34,111
Записей в блоге: 14
03.12.2015, 17:05 2
Если в графе от вершины А до вершины Б имеется несколько путей, то под расстоянием А-Б понимается кратчайший путь?
0
0 / 0 / 0
Регистрация: 06.06.2015
Сообщений: 6
03.12.2015, 17:23  [ТС] 3
Цитата Сообщение от Catstail Посмотреть сообщение
Если в графе от вершины А до вершины Б имеется несколько путей, то под расстоянием А-Б понимается кратчайший путь?
Да.
0
Модератор
Эксперт функциональных языков программированияЭксперт Python
37291 / 20725 / 4272
Регистрация: 12.02.2012
Сообщений: 34,111
Записей в блоге: 14
03.12.2015, 17:33 4
Алгоритм Флойда...
0
0 / 0 / 0
Регистрация: 06.06.2015
Сообщений: 6
03.12.2015, 17:48  [ТС] 5
Цитата Сообщение от Catstail Посмотреть сообщение
Алгоритм Флойда...
1. Мне не совсем понятно, с чем именно сравнивать расстояния от А до всего остального. С медианой расстояний между всеми вершинами?
2. Всё же меня интересует реализация на LISP.
3. Или на Prolog это реализовать проще? Можно использовать любой из этих двух языков.
0
VH
430 / 258 / 23
Регистрация: 23.11.2010
Сообщений: 278
04.12.2015, 15:52 6
Лучший ответ Сообщение было отмечено agronom4ever как решение

Решение

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
(defun F (Net)
 ((lambda (enum counter)
   ((lambda (averages)
     ((lambda (mid)
       ((lambda (deviations)
         (EXTRACT_MIN (apply 'min deviations) deviations enum))
        (mapcar
        #'(lambda (dist)
          (abs (- dist mid)))
         averages)))
      (/ (apply '+ averages) counter)))
    (mapcar
    #'(lambda (node)
      (/
       (apply '+
        (mapcar
        #'(lambda (other)
          (DIJKSTRA Net node other))
         (remove node enum :test 'EQUAL)))
       (1- counter)))
     enum)))
  (mapcar 'car Net)
  (length Net)))
(defun EXTRACT_MIN (minimal deviations enum)
 (if deviations
  ((lambda (test result)
    (if test (cons (car enum) result) result))
   (equal (car deviations) minimal)
   (EXTRACT_MIN minimal (cdr deviations) (cdr enum)))))
(defun DIJKSTRA (Net Init Term
 &optional (Tmp nil) (Fix (list (cons Init 0))))
 ((lambda (fix_label fix_value)
   (if (equal fix_label Term) fix_value
    (apply 
     #'(lambda (newTmp newFix)
      (DIJKSTRA Net Init Term newTmp newFix))
     (TRANSFER_MIN
      (UPDATE_Tmp Tmp Fix (cdr (assoc fix_label Net)))
      Fix))))
  (caar Fix)
  (cdar Fix)))
(defun UPDATE_Tmp (Tmp Fix Links)
 (if Links
  ((lambda (link_label link_value)
    (UPDATE_Tmp
     (if (assoc link_label Fix :test 'EQUAL) Tmp
      ((lambda (link mark)
        (if link
         (subst
          (cons link_label (min mark (cdr link)))
          link
          Tmp
          :test 'EQUAL)
         (cons (cons link_label mark) Tmp)))
       (assoc link_label Tmp :test 'EQUAL)
       (+ link_value (cdar Fix))))
     Fix
     (cdr Links)))
   (caar Links)
   (cdar Links))
  Tmp))
(defun TRANSFER_MIN (Tmp Fix)
 (if Tmp
  (if (cdr Tmp)
   (apply
    #'(lambda (elem newTmp newFix)
     (if (< (cdr elem) (cdar newFix))
      (list
       (cons (car newFix) newTmp)
       (cons elem (cdr newFix)))
      (list
       (cons elem newTmp)
       newFix)))
    (cons (car Tmp) (TRANSFER_MIN (cdr Tmp) Fix)))
   (list
    (cdr Tmp)
    (cons (car Tmp) Fix)))
  (list Tmp Fix)))
Сеть связывается с формальным параметром Net и представлена списком списков связей узлов в следующем виде:
((узел (связанный_узел . длина_дуги)...)...)
Например, для сети
(setq Net
'((1 (2 . 4)(3 . 7))
(2 (1 . 4)(3 . 3)(6 . 1))
(3 (1 . 7)(2 . 3)(4 . 2)(5 . 5))
(4 (3 . 2)(5 . 1)(6 . 7))
(5 (3 . 5)(4 . 1)(6 . 3))
(6 (2 . 1)(4 . 7)(5 . 3))))
вызов (F Net) возвращает список «центральных» вершин из одной вершины (4).
4
04.12.2015, 15:52
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
04.12.2015, 15:52
Помогаю со студенческими работами здесь

Матрица инцидентности орграфа, когда две вершины взаимодостижимы через одно ребро
К примеру, матрица смежности: Как в этом случае заполнять матрицу инцидентности? Ведь вершина...

Найти все вершины орграфа, от которых существует путь заданной длины к выделенной вершине
Найти все вершины орграфа, от которых существует путь заданной длины к выделенной вершине.

Вывести для каждой вершины орграфа сначала полустепень захода, а потом полустепень исхода
Ориентированный граф задан списком ребер Есть программа, но она не работает, не могу понять, как...

Нахождение вершины
Даны числа x, y, x1, y1, x2, y2. Используя функцию принадлежности точки (x, y) прямоугольнику с...


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

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru