next up previous
Next: Bibliography Up: НЕКОТОРЫЕ АЛГЕБРАИЧЕСКИЕ АСПЕКТЫ ТЕОРИИ Previous: 2 Содержание работы


3 Основные определения и обозначения

1 Граф и его подграфы

Пусть $\Gamma =\{V(\Gamma), E(\Gamma)\}$ -- конечный обыкновенный граф с множеством вершин $V(\Gamma)$ и множеством ребер $E(\Gamma)$.

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

Сокращяя обозначения, используем для множества вершин $V(\Delta)$ и для подграфа $\Delta$ один и тот же символ $\Delta$.

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

2 Регулярные графы

3 Расширения графов

4 Реберные графы

Известно, что наименьшее собственное значение треугольных и решетчатых графов равно $-2$.

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

Пусть $\Delta$ является $K_{m,n}$ графом. Перенумеруем вершины первой доли числами от $1$ до $m$, а вершины второй доли числами от $1$ до $n$. Множество всех вершин решетчатого $m\times n$-графа $\Gamma$, который является реберным графом графа $\Delta$, можно разложить в объединение $m$ максимальных непересекающихся клик $C_1,\dots , C_m$ по $n$ вершин каждая. Клика $C_i$ соответствует множеству ребер, исходящих из вершины с номером $i$ первой доли графа $\Delta$. Аналогично, множество всех вершин решетчатого графа можно разложить и в объединение $n$ максимальных непересекающихся клик $D_1,\dots , D_n$ по $m$ вершин каждая. Клика $D_j$ соответствует множеству ребер, исходящих из вершины с номером $j$ второй доли графа $\Delta$. Легко видеть, что $\vert C_i\cap D_j\vert=1$ для всех $i\in \{1,\dots m\}$, $j\in \{1,\dots n\}$, поскольку $C_i\cap D_j$ соответствует единственному ребру соединяющему вершину $i$ первой доли графа $\Delta$ с вершиной $j$ второй доли графа $\Delta$.

Таким образом, окрестность каждой вершины в решетчатом $m\times n$-графе является объединением двух изолированных клик на $m-1$ и $n-1$ вершинах соответственно, то есть она изоморфна $K_{m-1}+K_{n-1}$.

В любом решетчатом $m\times n$-графе $\Gamma$ все его подграфы из ${\cal M}(\Gamma)$ являются $2$-кокликами, а все его подграфы из ${\cal L}(\Gamma)$ являются $(m-2)$-кликами или $(n-2)$-кликами.

Треугольный граф $T(n)$ является локально решетчатым $(n-2)\times 2$ графом.

В любом треугольном графе $T(n)$ все его подграфы ${\cal M}(\Gamma)$ изоморфны $K_{2,2}$, то есть являются четырехугольниками, а все его подграфы из ${\cal L}(\Gamma)$ изоморфны $K_{n-3}+K_1$.

5 Граф Шлефли

Известно, что граф инцидентностей обобщенного четырехугольника является сильно регуляреным графом. Обобщенный четырехугольник $GQ(2,4)$ существует и притом только один (см. теорему 1.15.2 и пример (iii) на стр. 30 монографии [6]).

Заметим, что если $\Gamma$ граф Шлефли, то он является локально $G$-графом, где $G$ -- граф Клебша. Более того, поскольку в $GQ(2,4)$ через любую точку $p$ проходит 5 прямых, на каждой из которых по две точки, отличные от точки $p$, то любая антиокрестность в графе Шлефли изоморфна графу $K_{5\times 2}$. Таким образом любой подграф из ${\cal M}(\Gamma)$ изоморфен $K_{4\times 2}$.

В следующем пункте приводится другое определение графа Шлефли.

6 Граф системы корней

Подмножество векторов данной корневой решетки $L$ образуют систему корней $\Phi$ в $V={\bf R}\otimes L$, то есть $\Phi$ является конечным множеством ненулевых векторов, порождающих $V$, таких, что выполнены следующие три условия:


\begin{displaymath}{\rm если   } \lambda\in {\bf R} {\rm  и  } r,
\lambda r \in \Phi, {\rm  то  } \lambda =\pm 1;\end{displaymath}


\begin{displaymath}{\rm если  } r_1, r_2 \in \Phi, {\rm  то  }
r_2-2\frac{(r_1,r_2)}{(r_1,r_1)}\in \Phi;\end{displaymath}


\begin{displaymath}\frac{(r_1,r_2)}{(r_1,r_1)} {\rm  целое число для всех  }
r_1, r_2 \in \Phi.\end{displaymath}


Векторы системы корней $\Phi$ называются корневыми векторами или корнями. Систематическое изложение теории корневых систем можно найти в книге Бурбаки [5]. Нам понадобится определение системы корней $E_8$ и соответствующего ей графа.

Figure: Граф Петерсена
\begin{figure}\begin{center}
\begin{picture}(62.00,62.00)
\setlength{\unitlength...
...\emline{48.33}{1.00}{29}{41.00}{14.33}{30}
\end{picture}\end{center}\end{figure}

7 Обобщенно регулярные графы

Пусть $\Gamma$ некоторый граф и $\cal F$ некоторый класс графов.

8 Некоторые примеры дистанционно-регулярных графов

Следующие примеры дистанционно-регулярных графов играют важную роль в данной работе.

Пусть $V$ является $n$-мерным векторным пространством над конечным полем $F$.

Figure: Граф икосаэдра
\begin{figure}\begin{center}
\begin{picture}(81.49,81.49)
\setlength{\unitlength...
...emline{45.42}{9.42}{135}{41.08}{0.74}{136}
\end{picture}\end{center}\end{figure}

9 Редукция графа

10 Доминирование и неприводимость

11 Блоки и блок-графы

Вершина $v$ связного графа $\Gamma$ называется точкой сочленения, если если $\Gamma -v$ является несвязным графом.

Связный граф называется блоком, если он не имеет точек сочленения.

Блоком графа $\Gamma$ называется связный подграф $\Gamma$, который не имеет точек сочленения и максимален относительно свойства "не иметь точек сочленения". Если блок не является ребром, то это максимальный 2-связный подграф графа $\Gamma$.

Блок-граф -- это граф, в котором все блоки являются кликами.

Через ${\cal B}(\Gamma)$ обозначим множество всех блоков графа $\Gamma$, а через ${\cal C}(\Gamma)$ -- множество всех точек сочленения для $\Gamma$.

Граф $\Gamma$ называется кликово-сочлененным, если множество вершин из $B\cap {\cal C}(\Gamma)$ образуют клику для каждого блока $B$ из ${\cal B}(G)$.

Заметим, что любой блок-граф является кликово сочлененным графом.


next up previous
Next: Bibliography Up: НЕКОТОРЫЕ АЛГЕБРАИЧЕСКИЕ АСПЕКТЫ ТЕОРИИ Previous: 2 Содержание работы