УДК
Алгебраическая теория функций на графах
ФГБОУ ВПО «Кемеровский государственный университет»
*****@***ru
Цель: разобрать статью Н. Биггса, восстановить ряд доказательств, связанных с операторами Лапласа на графах. Отметить связь с электрическими цепями, обобщением проблемы Дирихле, группы Пикара, Якобиана, чип - файринг игры на графах. Результаты и методы теории Римановых поверхностей переносятся на теорию функций на графах.
Пусть G –конечный граф без петель, т. е. G содержит V вершин, E ребер и включает функцию i:E
V(2), где V(2) множество неупорядоченных пар вершин. Матрица инцидентности D - одна из форм представления графа, в которой указываются связи между инцидентными элементами графа (ребро и вершина). Столбцы матрицы соответствуют ребрам, строки — вершинам.
В работе изучаются:
Матрица инцидентности D и ее ранг.Ориентация графа G=(V, E, i), есть функция h: E
V, где h(e)
i(e), для всех ребер е, то есть i(e)={h(e),t(e)}. Тогда n=|V|, m=|E| и матрица D=(dve) для G выглядит как
dve=
де из вершины v выходит ребро e.
Через C0(G;R) и C1(G;R) обозначим векторные пространства вещественнозначных функций, определенных на V и E соответственно. Рассмотрим линейные операторы D: C1(G;R)
C0(G;R) и Dt: C0(G;R)
C1(G;R).
Для б
C0, формула для Dtб имеет вид: (Dtб)(e)=б(h(e))-б(t(e))
Путь на графе G есть последовательность альтернативных вершин и ребер v0,e1,v1,e2,v2,…,vr-1,er, vr, так же i(ej)={vj-1,vj}, 1≤j≤r. Отношения на V (v
w), если путь начинается с v и заканчивается w, есть отношение эквивалентности на V.
Для б
C0 условие Dtб=0 (Dtб)(e)=б(h(e))-б(t(e)) означает, что б принимает одинаковое значение, как на h(e) так и на t(e) ребра е. Если v и w находятся в некоторых компонентах G (определенных через отношение эквивалентности), тогда путь начинается с v и заканчивается w и так же б(v)=б(w). Другими словами, б будет постоянной на некоторой компоненте G. Если б=const на каждой компоненте, тогда она удовлетворяет условию Dtб=0.
Предложение 1.1: Ядро Dt есть пространство функций, которые являются константами на каждой компоненте G. В частности, если G связный граф, то ядро есть пространство скалярных функций u
C0, u(x)=1 
x
V.
Множество постоянных функций на некоторых компонентах есть векторное пространство размерности с. Равенство dim(Ker Dt)=c, дает, что ранг Dt есть n-c.
Предложение 1.2. Ранг D равен n-c;
Ортогональные разложения.Для f
C1 имеем (Df)(v)=
. Функция f из ядра D, если 
v
V, 
. Обозначим Ker D=Z и B будет ортогональным дополнением Z относительно скалярного произведения <x, y>=
на С1(G;R). Тогда существует прямая сумма C1(G;R)=Z
B=Ker D⨁ (Ker D)
.
Размерность Im D есть ранг D.
Предложение 2.1. Размерность Z равна m-n+c, и размерность B равна n-c.
Литература и источники
Biggs N. Algebraic potential theory on graphs. Bull. London Math. Soc.29 (1997) 641-682.Научный руководитель – д. ф.-м. н., профессор , ФГБОУ ВПО «Кемеровский государственный университет»
