Многоагентные системы

УДК 004 
 ББК 16.2 
   Ч-88  
 
 
Рецензенты: 
д-р техн. наук, доц., проф.  Н.С. Галдин (СибАДИ, г. Омск); 
канд. техн. наук, доц. И.В. Лазута (СибАДИ, г. Омск) 
 
Работа утверждена редакционно-издательским советом СибАДИ в качестве 
учебно-методического пособия. 
 

Ч-88

Чуканов, Сергей Николаевич.
Многоагентные системы : учебно-методическое пособие / С.Н. Чуканов, 
Н.Н. Егорова. – Электрон. дан. – Омск : СибАДИ, 2022. – Режим доступа: 
http://bek.sibadi.org/MegaPro, для авторизованных пользователей. – Загл. 
с экрана.
 
Содержит теоретический материал и задания для самостоятельной работы  
студентов. 
Предназначено для обучающихся 1–4-го курсов всех форм обучения, изучающих дисциплины «Проектирование автоматизированных систем обработки информации и управления», «Теория систем и системный анализ», «Современные методы  
оптимизации», «Компьютерные технологии в науке и производстве».  
Имеет интерактивное оглавление в виде закладок. 
Подготовлено на кафедре «Цифровые технологии». 
 
 
 
Текстовое (символьное) издание (1,52 Мб) 
Системные требования: Intel, 3,4 GHz ; 150 МБ; Windows XP/Vista/7/10; 
1 ГБ свободного места на жестком диске; программа для чтения pdf-файлов:  
Adobe Acrobat Reader; Foxit Reader 
 
 
Редактор О.А. Соболева  

Техническая подготовка – А.А. Орловская  

 
 
Издание первое. Дата подписания к использованию 23.12.2022 
 
Издательско-полиграфический комплекс СибАДИ 
644080, г. Омск, пр. Мира, 5 
РИО ИПК СибАДИ 
644080, г. Омск, ул. 2-я Поселковая,1 
 
 

© ФГБОУ ВО «СибАДИ», 2022 

Согласно 436-ФЗ от 29.12.2010 «О защите 
детей от информации, причиняющей вред их 
здоровью и развитию» данная продукция 
маркировке не подлежит 

ВВЕДЕНИЕ 

 
Спроектированные распределенные мультиагентные сети, такие как 
распределенные роботы и мобильные сенсорные сети, поставили ряд проблем с точки зрения их теоретико-системного анализа и синтеза. Агенты в 
таких сетях должны работать согласованно друг с другом для достижения 
целей системного уровня, имея при этом доступ к ограниченным вычислительным ресурсам, а также возможность локальной связи.   
Примерами таких распределенных и сетевых систем являются: 
Boids - модель (искусственной жизни) Рейнольдса, модель формирование 
полета, сенсорные сети, наносистемы, социальные сети, энергетические 
сети, многоагентные системы. 
Важную роль в анализе и синтезе сетевых многоагентных систем играет геометрия взаимодействия. Если ребра в графах интерпретировать 
как возможность передачи информации между вершинами на соответствующем ребре, эти потоки могут быть как направленными, так и неориентированными.  
Однако направленность – это не единственный аспект ребер, который мы будем рассматривать. Мы также исследуем различные формы 
временной устойчивости, то есть ситуации, в которых грани могут исчезать и появляться снова. В частности, мы сгруппируем графы в три класса: 
Статические сети: в этих сетях края статичны, то есть набор границ 
не будет изменяться во времени. Это, например, ситуация, когда установлена статическая сеть связи, по которой проходит информация. 
Динамические сети, зависящие от состояния: здесь набор границ изменяется во времени, так как границы могут исчезать и снова появляться в 
зависимости от основного состояния сетевых агентов. Например, если 
вершины в графе соответствуют мобильным роботам, оснащенным датчиками дальности, ребра будут появляться, когда агенты попадают в сенсорный диапазон друг друга, и теряться, когда агенты выходят из сенсорного 
диапазона. 
Случайные сети: эти сети составляют особый класс динамических 
сетей в том смысле, что наличие определенного ребра задается вероятностным распределением, а не каким-то детерминированным геометрическим условием восприятия.  
Графы по своей сути являются комбинаторными объектами, обладающими преимуществами и ограничениями, присущими таким объектам.  

1. ТЕОРИЯ ГРАФОВ 

Графы обеспечивают естественную абстракцию того, как информация распределяется между агентами в сети. В этой главе мы вводим элементы теории графов и предоставляем основные инструменты для рассуждений о таких абстракциях. В частности, мы дадим введение в основные определения и операции с графами. Мы также познакомимся с алгебраической теорией графов с особым акцентом на матричных объектах, 
связанных с графами, таких как матрицы смежности и лапласианы. 
Графические абстракции сетевых систем практически не содержат 
информации о том, что именно разделяют агенты, по какому протоколу 
происходит обмен или что впоследствии делается с полученной информацией. Вместо этого абстракция на основе графов содержит высокоуровневые описания топологии сети в терминах объектов, называемых вершинами и ребрами. В этой главе мы даем краткий обзор теории графов. Особое 
внимание будет уделено области алгебраической теории графов, которая 
предоставит инструменты, необходимые в последующих главах для связывания вместе динамических объектов (таких как многоагентные роботизированные системы) с комбинаторной характеристикой сетей (графов). 
 
1.1. Графы 
 
Конечный, неориентированный, простой граф – или граф для краткости – построен на конечном множестве, то есть на множестве, имеющем 
конечное число элементов. Мы называем это множество множеством 
вершин и обозначаем его  V ; тогда каждый элемент V  является вершиной 
графа. Когда множество вершин V  имеет n элементов, оно представляется 
как 
. 

Теперь рассмотрим множество 2-элементных подмножеств V, обозначенное [V]2. Этот набор состоит из элементов вида {vi, vj} таких, что 
. Конечный граф 
 формально определяется как пара  
, где [V]2
 – конечное множество вершин, а 
 – частное подмножество [V]2; мы называем 
 множеством ребер графа 
. Иногда мы называем вершины и ребра 
 как V(G), E(G), соответственно, и упрощаем 
наши 
обозначения 
для 
ребра 
{vi, 
vj}, 
иногда 
обозначая 
его 
как vi vj. 
Граф по своей сути является теоретико-множественным объектом; 
однако его удобно представить графически, что оправдывает его название. 
Графическое представление 
 состоит из «точек» (вершины 
 и «линий» 
между  vi  и vj , когда 
E
v
v
j
i
∈
. Это графическое представление приводит 

{
}
1,...,
n
V
v
v
=

,
1,2,..., ;
i j
n i
j
=
≠
G

(
)
,
V E
=
G
E

E
G

G

G
iv

ко многим определениям, идеям и наблюдениям относительно графов. 
Например, когда между вершинами vi и vj  существует ребро, мы называем 
их смежными. В этом случае ребро vivj называется инцидентным вершинам vi и vj.  
Аналогично окрестность 
 вершины vi будет пониматься как 
множество 
, то есть как множество всех вершин, смежных 
с 
. Если 
, то 
, поскольку множество ребер в (неориентированном) графе состоит из неупорядоченных пар вершин. Понятие 
смежности в графе можно использовать для «перемещения» по краям 
графа. Таким образом, путь длины 
 в 
 задается последовательностью 

различных вершин 
,  таких, что при 
 вершины vik  и 
vik+1 смежны. В этом случае 
 и 
 называются конечными вершинами 
пути; вершины 
 – внутренние вершины. Когда вершины пути различны, за исключением его конечных вершин, путь называется циклом. 
Граф без циклов называется лесом. 
Мы называем граф 
 связным, если для каждой пары вершин в 
 существует путь, имеющий их в качестве концевых вершин. Если 
это не так, граф называется несвязным.  
Мы называем связный граф имеющим одну компоненту связности – 
вкратце компонент. Таким образом, компонент – это подмножество графа, 
связанное с минимальным разбиением набора вершин, так что каждое 
разбиение является связным. Следовательно, несвязный граф имеет более 
одной компоненты. Лес с одной составляющей естественно называется 
деревом. 
Графическое представление графов позволяет рассматривать графы 
как логические конструкции без явного отождествления вершины с элементом множества вершин 
. Это достигается удалением «меток» на точках, представляющих вершины графа; в этом случае граф называется немаркированным. Когда вершинам в немаркированном графе возвращаются их идентичности, этот граф называется помеченным.  
Пример. Графы могут эффективно выражать комбинаторные отношения между конечными множествами. Пусть 
 и для 
 
рассмотрим 
-элементные подмножества 
 как вершины графа. Тогда 
пусть две вершины будут смежными, если соответствующие множества 
пересекаются в 
 элементах. Полученные графы для различных значений 
n, k, m  называются графами Джонсона 
.  

Два графа 
 и 
 называются изоморфными, если 
они имеют одинаковые множества вершин и ребер в том смысле, что су
( )
N i
V
⊆

{
}
|
j
i
j
v
V v v
E
∈
∈

iv
( )
jv
N i
∈
( )
iv
N j
∈

m
G

0,
,
m
i
i
v
v

0,1,...,
1
k
m
=
−

0iv
miv

1
1
,
,
m
i
i
v
v
−


G

( )
V G

V

[ ] {
}
1,...,
n
n
=
n
k
m
>
>

k
[ ]
n

m

(
)
, ,
J n k m

(
)
,
V E
=
G
(
)
,
V E
′
′
′
=
G

ществует биекция 
 такая, что что 
 тогда и только тогда, 
когда 
. Если это так, ���� и ����′  изоморфны, что обозначается 
как  ���� ≃ ����′. 
Наш первый стандартный граф – это полный граф с 
 вершинами 
Kn,. Это граф, в котором каждая вершина смежна с любой другой вершиной. Другие полезные графы включают в себя граф путей, граф циклов и 
звездный граф. Под графом путей понимается любой граф, изоморфный 
графу Рn = ({v1, …, vn}, Ep), где vivj ∈ Ep  тогда и только тогда, когда 
. Аналогично, 
-цикл 
 является графом с 
 тогда и только тогда, когда 
. Звездный граф 
задается как 
, где 
 тогда и только тогда, когда 
 или 
.  
Два других важных класса графов включают регулярные и двудольные графы. Каждая вершина 
-регулярного графа имеет степень 
; следовательно, граф циклов является 2-регулярным, а полный граф на  вершинах является  
-регулярным. Для двудольного графа 
 множество 
вершин представляет собой объединение двух непересекающихся множеств 
 таких, что из 
следует, что либо 
, либо 
. Если мощности множеств 
 равны 
 и 
 соответственно, то двудольный граф на множестве вершин 
 с 
 ребрами называется полным двудольным графом Km,n. 
Хотя графы чаще всего определяются как комбинаторные объекты, 
полезно выполнять теоретико-множественные операции с графами, такие 
как изучение их подмножеств и объединение или пересечение между ними. 
Рассмотрим граф  
  и подмножество вершин 
. Можно 
позволить подмножеству вершин «индуцировать подграф» относительно 
данного основного графа. Этот индуцированный подграф задается формулой  

. 
Другими словами, подграф 
 состоит из вершин в подмножестве 
 
графа 
 и ребер в 
, инцидентных вершинам в 
.  

Однако следует отметить, что необязательно позволять подграфам 
быть «индуцированными». Фактически любой граф 
 является 
подграфом  
, если 
. В этом случае мы иногда называем  
 «надграфом» 
. Если 
 для подграфа, он называется  
остовным подграфом. Остовное дерево для графа  
, таким образом,  

:V
V′
β
→
i
j
v v
E
∈

( ) (
)
i
j
v
v
E′
β
β
∈

n

1,
1,...,
1
j
i
i
n
= +
=
−
n
{
}
(
)
1,...,
,
n
n
C
C
v
v
E
=

i
j
C
v v
E
∈
1 mod
i
j
n
−
= ±

{
}
(
)
1,...,
,
n
n
star
S
v
v
E
=
i
j
star
v v
E
∈

1
i =
1
j =

k
k
n

(
)1
n −
G

1
2
,
V V
( )
uv
E
∈
G
(
)
(
)
1
2
u
V
v
V
∈
∧
∈

(
)
(
)
2
1
u
V
v
V
∈
∧
∈
1
2
,
V V
m
n

( )
1
2
V
V
V
=
∪
G
mn

(
)
,
V E
=
G
S
V
⊆

(
)
{
}
{
}
,
;
,
|
,
S
S
S
i
j
i
j
S E
E
v v
E v v
S
=
=
∈
∈
G

S
S

( )
V G
G
S

(
)
,
V E
′
′
′
=
G

(
)
,
V E
=
G
,
V
V E
E
′
′
⊆
⊆

G
′
G
V
V
′ =

G

является подграфом  
, который также является деревом. 
Теперь, когда мы можем индуцировать подграфы из наборов вершин 
графов, мы можем также выполнять ряд теоретико-множественных операций над подграфами. Например, для данных 
 пусть 
 и 
 – 
соответствующие индуцированные подграфы графа . Объединение и пересечения этих подграфов могут быть определены как подграфы, индуцированные 
 и 
 соответственно.  
Другими словами,  

 

Точно так же границы и замыкания подграфов могут быть определены 
как 
, 
где 

.  

Взвешенные графы. Если вместе с наборами ребер и вершин задана 
функция 
, которая связывает значение с каждым ребром, результирующий граф 
 является взвешенным графом. На таких графах можно рассматривать кратчайшие пути или геодезические между 
вершинами с помощью понятия длины пути, определяемого как сумма 
всех весов вдоль пути. В частности, если позволить 
 быть множе
ством всех путей, соединяющих 
, геодезическая (необязательно уни
кальная) между 
 будет минимизировать 
.  Точно так 

же диаметр взвешенного связного графа – это длина любой из его самых 
длинных геодезических. 
Ориентированные графы. Когда ребрам в графе заданы направления, результирующее соединение больше не считается неисправленным 
графом. Ориентированный граф, обозначаемый 
, на самом деле 
может быть получен двумя разными способами. Первый – просто отказаться от требования, чтобы множество ребер 
 содержало неупорядоченные пары вершин. Это означает, что если упорядоченная пара 
, то 
 называется хвостом (где начинается стрелка) ребра, а 
 – 
его головой. Другой способ, которым может быть построен ориентированный граф, состоит в том, чтобы связать ориентацию o с неупорядоченным множеством ребер 
. Такая ориентация назначает направление ребрам в том смысле, что 
, с 
. Говорят, что реб
ро 
 берет начало в 
 (хвосте) и оканчивается в 
 (голова), если 

, и наоборот, если 
. 

G

( )
,
S S
V
′ ⊆
G
S
G
S′
G

G

S
S′
∪
S
S′
∩

{
}
(
)

{
}
(
)

,
|
,

,
|
.

S
S
S
S
i
j
i
j

S
S
S
S
i
j
i
j

S
S
v v
E v v
S
S

S
S
v v
E v v
S
S

′
′
∪

′
′
∩

′
′
∪
=
=
∪
∈
∈
∪

′
′
∩
=
=
∩
∈
∈
∩

G
G
G

G
G
G

{
}
(
)
,
|
,
S
S
i
j
i
j
S
v v
E v v
S
∂
∂
=
= ∂
∈
∈∂
G
G

(
)
(
)
{
}
|
 s.t. 
i
i
j
i
j
S
v
E
v
S
v
S
v v
E
∂ =
∈
∉
∧
∈
∈

:
w E → R

(
)
, ,
V E w
=
G

(
)
,
i
j
v v
π

,
i
j
v v

,
i
j
v v

(
)
( )
,
min length

i
j
p
v v
p
∈π

(
)
,
V E
=
D

E

(
)
,
i
j
v v
E
∈
iv
jv

E

{
}
:
1,1
o E → −
(
)
(
)
,
,
i
j
j
i
o v v
o v v
= −

(
)
,
i
j
v v
iv
jv

(
)
,
1
i
j
o v v
=
(
)
,
1
i
j
o v v
= −

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

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

1.2. Графы и матрицы 
 
Графы – это конструкции для представления отношений между конечным числом объектов, допускающие простое графическое представление в терминах вершин и ребер. Графы также допускают представление в 
терминах матриц.  
Смежность и степень. Для неориентированного графа  
  степень 
данной вершины 
 – это кардинальность множества окрестностей 
, то есть она равна количеству вершин, смежных с вершиной  в  
.  

Последовательность степеней графа – это набор степеней его вершин, часто записываемых в порядке возрастания.  
Основываясь на понятиях степени и смежности, можно связать 
определенные матрицы с графами. Матрица степеней  
 – это диагональная матрица, содержащая степени вершин 
 на диагонали, то есть 

, где 
 – количество вершин. Матрица 

смежности 
 является симметричной матрицей размера  
n
n×
, кодирующей отношения смежности в графе 
, 

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

m

D
0,...,
m
i
i
v
v

0,1,...,
1
k
m
=
−
(
)
(
)
1
,
k
k
i
i
v
v
E
+ ∈
D

(
)
,
V E
=
D
(
)
,
V E
′
′
′
=
D

,
V
V E
E
′
′
⊆
⊆

G

( )
i
d v

( )
N i
iv
G

G

G

( )

( )
(
)

(
)

1

2

0
0
0
0

0
0
n

d v
d v

d v







∆
= 














G
n

( )
A G

G

( )
1
if 
,

0
otherwise.

i

ij

j
A
v v
E
∈





= 

G

(
)
o
D G
n m
×

Интерпретация здесь такова, что D(Go) фиксирует не только отношения смежности в графе, но и ориентацию, которой теперь обладает 
граф; матрица инцидентности связана с графом 
, который был ориентирован как G0. 
Эта матрица инцидентности имеет сумму столбцов, равную нулю, 
что является фактом, который справедлив для всех матриц инцидентности, поскольку каждое ребро должно иметь ровно один хвост и одну головку. Отметим, что матрица инцидентности для орграфа 
 может быть 
определена аналогично, пропустив предварительную ориентацию, которая 
необходима для графов. В этом случае мы обозначим матрицу инцидентности через 
. 

Линейные алгебраические свойства матрицы инцидентности графов 
и диаграмм позволяют понять их многие структурные аспекты. Мы развиваем эту связь с помощью понятия пространства циклов для слабосвязного орграфа 
, который определяется как нулевое пространство матрицы 
инцидентности, то есть множества векторов z  таких, что 
. 

Учитывая 
матрицу 
инцидентности 
, 
вектор 
пути 
со  
знаком – это вектор z, соответствующий пути в  
, такой, что -й индекс z  
принимает значение +1, если ребро  проходит положительно, -1, если оно 
пройдено отрицательно, и 0, если край не используется в пути. 
Следующие два наблюдения указывают на удобные средства выражения теоретических фактов графов с помощью линейной алгебры. 
Для данного пути с различными начальными и конечными вершинами, описанными вектором пути  z  со знаком в орграфе  
, вектор 
 таков, что его -й элемент принимает значение +1, если вершина  является начальной вершиной пути, -1, если конечная вершина пути, 
и 0 в противном случае. 
Для слабо связного орграфа 
 нулевое пространство 
 натянуто 
на все линейно независимые векторы путей со знаком, соответствующие 
циклам 
. 
Таким образом, естественно называть нулевое пространство  
 
пространством циклов орграфа. С другой стороны, ортогональное дополнение к пространству циклов называется разрезанным пространством  
, 
которое характеризуется пространством значений  
. 

 

(
) [
]

1
if  is tail of 
,
,
1
if  is head of 
,
0
otherwise.

i
j

o
ij
ij
i
j

v
e
D
d
d
v
e
−


=
= 


G

G

D

(
)
D D

D

(
)
0
D
z =
D

(
)
D D

D
i

i

D

( )
y
D
z
=
G
i

i

D
(
)
D D

D

(
)
D D

D

(
)
D D

Лапласиан графа. Еще одно матричное представление графа 
,  
которое играет важную роль – это лапласиан графа 
. Эта матрица 

может быть определена по-разному, что приведет к одному и тому же 
объекту. Наиболее прямое определение лапласиана графа, связанного с 
неориентированным графом 
, это 
, где 
 – матрица 

степеней графа 
, а 
 – это его матрица смежности. Из этого опреде
ления следует, что для всех графов сумма строк лапласиана равна нулю.  

В качестве альтернативы, учитывая (произвольную) ориентацию 
множества ребер 
, лапласиан графа группы 
 можно определить как 

, где 
 – соответствующая матрица инцидентно
сти для ориентированного графа 
.  
Это определение прямо показывает, что лапласиан графа на самом деле 
является симметричной и положительно полуопределенной матрицей. 
Примем соглашение об использовании 
 в качестве матрицы инцидентности графа, когда ориентация 
 произвольна. Независимо от этого факта иногда бывает полезно использовать одно из этих двух определений для лапласиана графа.  
В качестве примера можно сформировать лапласиан взвешенного 
графа, 
связанный 
с 
взвешенным 
графом 
, 
как 

, где 
 – диагональная матрица размера mxm , с 
, на диагонали. Обратите внимание, что для набора ребер 
была принята разметка, которая также необходима для определения матрицы инцидентности 
. 

Лапласиан ребер. Реберный лапласиан для произвольного ориенти
рованного графа  определяется как 
.  

Два ключевых линейных алгебраических свойства 
 следующие:  
1) множество ненулевых собственных значений 
 равно множеству ненулевых собственных значений 
; 
2) ненулевые собственные значения 
 и 
 равны квадрату 
ненулевых особых значений 
. 
 Кроме того, рассмотрим граф 
 с 
 связными компонентами Gi  и 
ассоциированными 
матрицами 
инцидентности 
D(Gi), 
и 
пусть 
.  

 

G

( )
L G

G
( )
( )
( )
L
A
= ∆
−
G
G
G
( )
∆ G

G
( )
A G

( )
E G
G

( )
(
)
(
)
T
o
o
w
L
D
D
=
G
G
G
(
)
o
D G

G

( )
D G

G

(
)
, ,
V E w
=
G

( )
( )
( )
T
w
L
D
WD
=
G
G
G
W

( ),
1,...,
i
w e
i
m
=

( )
D G

G
( )
( )
( )
T
eL
D
D
=
G
G
G

( )
eL G
( )
eL G

( )
L G

( )
eL G
( )
L G

( )
D G

G
p

( )
(
)
(
)
1
p
D
D
D


= 


G
G
G

Тогда лапласиан ребер  имеет блочно-диагональную форму 

. 

Таким образом, лапласиан ребер можно рассматривать как «матрицу 
смежности ребер», в которой ребра, не имеющие общей вершины, считаются несмежными, и соответствующее значение в 
 становится равным нулю.  
С другой стороны, ребра, которые имеют общую вершину, считаются смежными, и знак соответствующей записи в 
 дает информацию о 
направлении обоих ребер относительно общей вершины. Наконец, каждое 
ребро всегда считается смежным самому себе. Число общих вершин между ребром и самим собой равно двум. Следовательно, все диагональные 
элементы краевого лапласиана 
 имеют значение 2. 

Лапласиан для орграфов. Определим понятия матриц смежности и 
степеней для ориентированных взвешенных графов. Пусть 
 обозначает 
нижележащий орграф; для матрицы смежности положим  

 

а для диагональной матрицы степеней 
 положим 
, 

где 
 – взвешенная внутренняя степень вершины , то есть 

 
. 

Отметим, что 
. Соответствующий (i n-степени) 
взвешенный лапласиан теперь определяется как 
.  Обратите внимание, что по построению для каждого орграфа 
 один имеет 
, то есть вектор всех единиц является собственным вектором, 
связанным с нулевым собственным значением 
.  
Наш выбор «внутренней степени» вместо «исходящей степени» для 
определения матриц смежности и Лапласа для орграфов в первую очередь 
мотивирован тем, как они будут использоваться в контексте сетевых систем. 
  
1.3. Алгебраическая и спектральная теория графов 
 
Алгебраическая теория графов связывает алгебраические объекты, 
такие как матрицы и многочлены, с графами, и тем самым делает доступным ряд алгебраических методов для их изучения. Примеры объектов, ко
G

( )
(
)
(
)

(
)
(
)

1
1
0

0

T

e

T
p
p

D
D

L

D
D





= 










G
G

G

G
G

( )
eL G

( )
eL G

( )
eL G

D

(
)
(
)
(
)
if 
,
,

0
otherwise,

ij
j
i

ij
w
v v
E
A

∈
=







D
D

(
)
∆ D
(
)
( ),
in
i
ii
d
v
i
∆
=
∀




D

( )
in
d
v
v

( )

(
)
(
)
{
}
,
j
i

in
i
ij
j v v
E
d
v
w

∈
=
∑
D

( )
( )
(
)
A
∆
= Diag
1
G
G

( )
( )
( )
L
A
= ∆
−
G
G
G

D

( )
(
)
1
L
∈ N
G

( )
L G