Необходимо определить степень связности орграфа

@nikberdes · Регистрация: 19.10.2012

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

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

@Catstail · 03.03.2013, 10:03

Если в лоб, то так:

- строим список всех пар вершин (их сисло = C_n²
- для каждой пары определяем число путей
- берем минимум из списка чисел путей

@nikberdes · 03.03.2013, 15:37 **[ТС]**

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

Если в лоб, то так:

- строим список всех пар вершин (их сисло = C_n²
- для каждой пары определяем число путей
- берем минимум из списка чисел путей

Название: ris80_1.jpg
Просмотров: 78

Размер: 1.9 Кб

(SETQ MAP '((1 (2 3 4))
(2 ( 1 3))
(3 ( 1 2))
(4 ( 1))))

((1 (2 3 4)) (2 (1 3)) (3 (1 2)) (4 (1)))

Как можно описать, ориентированный граф?

@Catstail · 03.03.2013, 15:57

Точно так же: Список списков. (V (список вершин, достижимых из V) ...

@nikberdes · 03.03.2013, 16:52 **[ТС]**

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

Точно так же: Список списков. (V (список вершин, достижимых из V) ...

Нашел, готовую функцию для определения числа соседних вершин:
(DEFUN NEIGHBOUR3 (LAMBDA (X GRAPH)
(COND ( (NULL (ASSOC X GRAPH)) NIL )
( T (CDR (ASSOC X GRAPH)) )
)
))
Но не могу правильно сделать ее вызов:
(NEIGHBOUR3 2 '(MAP))

@Catstail · 03.03.2013, 17:13

Подозрительная функция... А что значит "число соседних вершин"?

@nikberdes · 03.03.2013, 17:23 **[ТС]**

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

Подозрительная функция... А что значит "число соседних вершин"?

Например: в моем случаи, вершина 1 имеет 3 соседние вершины (2 3 4).

@Catstail · 03.03.2013, 17:54

Вот процедура поиска пути из вершины x в вершину y методом обхода в глубину:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(setq *graph* '((a (b c)) (b (a d)) (c (a d)) (d (b c e f)) (e (d f g)) (f (d e g)) (g (f e)))) 
 
==> ((a (b c)) (b (a d)) (c (a d)) (d (b c e f)) (e (d f g)) (f (d e g)) (g (f e)))
 
(defun dfs (x y graph &optional (s1 (list x)) (s2 (list x)))
   (if (eq x y) s2
       (let ((z (dolist (i (cadr (assoc x graph)) nil)
                    (if (not (member i s1)) (return i)))))
            (if (null z) (dfs (cadr s2) y graph s1 (cdr s2)) 
                       (dfs z y graph (cons z s1) (cons z s2))))))
 
==> dfs
 
(dfs 'a 'e *graph*)
 
==> (e d b a)
 
 
(dfs 'b 'g *graph*)
 
==> (g f e d c a b)

Может, пригодится.

@nikberdes · 03.03.2013, 18:02 **[ТС]**

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

Вот процедура поиска пути из вершины x в вершину y методом обхода в глубину:

Lisp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
(setq *graph* '((a (b c)) (b (a d)) (c (a d)) (d (b c e f)) (e (d f g)) (f (d e g)) (g (f e)))) 
 
==> ((a (b c)) (b (a d)) (c (a d)) (d (b c e f)) (e (d f g)) (f (d e g)) (g (f e)))
 
(defun dfs (x y graph &optional (s1 (list x)) (s2 (list x)))
   (if (eq x y) s2
       (let ((z (dolist (i (cadr (assoc x graph)) nil)
                    (if (not (member i s1)) (return i)))))
            (if (null z) (dfs (cadr s2) y graph s1 (cdr s2)) 
                       (dfs z y graph (cons z s1) (cons z s2))))))
 
==> dfs
 
(dfs 'a 'e *graph*)
 
==> (e d b a)
 
 
(dfs 'b 'g *graph*)
 
==> (g f e d c a b)

Может, пригодится.

Большое спасибо за помощь!

@Catstail · 03.03.2013, 18:03

Это не конец. Задача серьезнее.

@nikberdes · 03.03.2013, 18:55 **[ТС]**

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

Это не конец. Задача серьезнее.

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

Новые блоги и статьи Все статьи Все блоги /
Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .	[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .
делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .	Как дизайн сайта влияет на конверсию: 7 решений, которые реально повышают заявки Neotwalker 08.03.2026 Многие до сих пор воспринимают дизайн сайта как “красивую оболочку”. На практике всё иначе: дизайн напрямую влияет на то, оставит человек заявку или уйдёт через несколько секунд. Даже если у вас. . .

@nikberdes 0 / 0 / 0 Регистрация: 19.10.2012 Сообщений: 20

	Необходимо определить степень связности орграфа 02.03.2013, 20:04. Показов 2312. Ответов 10 Метки нет (Все метки) Под степенью связности графа понимается некоторое число R, такое, что между любыми двумя узлами графа имеются не менее R путей. Порекомендуйте, пожалуйста, как решить данную задачу. 0

@Catstail Супер-модератор 38192 / 21125 / 4309 Регистрация: 12.02.2012 Сообщений: 34,732 Записей в блоге: 14
	03.03.2013, 10:03
	Если в лоб, то так: - строим список всех пар вершин (их сисло = C_n² - для каждой пары определяем число путей - берем минимум из списка чисел путей 1

@Catstail Супер-модератор 38192 / 21125 / 4309 Регистрация: 12.02.2012 Сообщений: 34,732 Записей в блоге: 14
	03.03.2013, 15:57
	Точно так же: Список списков. (V (список вершин, достижимых из V) ... 1

@Catstail Супер-модератор 38192 / 21125 / 4309 Регистрация: 12.02.2012 Сообщений: 34,732 Записей в блоге: 14
	03.03.2013, 17:13
	Подозрительная функция... А что значит "число соседних вершин"? 0

@Catstail Супер-модератор 38192 / 21125 / 4309 Регистрация: 12.02.2012 Сообщений: 34,732 Записей в блоге: 14
	03.03.2013, 18:03
	Это не конец. Задача серьезнее. 0