ГРАФ

множество $V$ вершин и набор $E$ неупорядоченных и упорядоченных пар вершин; обозначается через $G(V, E)$. Неупорядоченная пара вершин называется ребром, упорядоченная пара - дугой. Г., содержащий только ребра, называется неориентированным; Г., содержащий только дуги,- ориентированным. Пара вершин может соединяться двумя или более ребрами (дугами одного направления), такие ребра (дуги) называются кратными. Дуга (или ребро) может начинаться и кончаться в одной и той же вершине, такая дуга (ребро) называется петлей. Вершины, соединенные ребром или дугой, называются смежными; ребра, имеющие общую вершину, - также смежными. Ребро (дуга) и любая из его двух вершин называются инцидентными. Говорят, что ребро $(u, v)$ соединяет вершины $u$ и $v$, а дуга $(u, v)$ начинается в вершине $u$ и кончается в вершине $v$. Каждый Г. можно представить в евклидовом пространстве множеством точек, соответствующих вершинам, к-рые соединены линиями, соответствующими ребрам (или дугам) Г.,- укладка Г. В 3-мерном пространстве любой Г. можно представить таким образом, что линии, соответствующие ребрам (дугам), не пересекаются во внутренних точках. Класс Г., называемых плоскими, допускает представление в 2-мерном пространстве. Существуют различные способы задания Г. Пусть $v_{1}, v_{2}$, $\ldots, v_{n}$ - вершины графа $G(V, E)$, а $e_{1}, e_{2}, \ldots, e_{m}$ - его ребра. Матрицей смежности, соответствующей графу $G$, называется матрица $A=\left\|a_{i j}\right\|, i=1, \ldots, n, j=1, \ldots, m$, у к-рой элемент $a_{i j}$ равен числу ребер (дуг), соединяющих вершины $v_{i}$ и $v_{j}$ (идущих из $v_{i}$ в $v_{j}$ ), и $a_{i j}=0$, если соответствующие вершины не смежны. В матрице инцидентности $B=\left\|b_{i j}\right\|$ графа $G$ элемент $b_{i j}=1$, если вершина $v_{i}$ инцидентна ребру $e_{j}$, и $b_{i j}=0$, если вершина $v_{i}$ и ребро $e_{j}$ не инцидентны. Г. можно задать посредством списков, напр. указанием пар вершин, соединенных ребрами (дугами), или заданием для каждой вершины множества смежных с ней вершин (степенью вершины $v$ называется число ребер, инцидентных $v)$. Последовательность ребер $\left(v_{0}, v_{1}\right),\left(v_{1}, v_{2}\right), \ldots,\left(v_{i-1}, v_{i}\right)$, $\left(v_{i}, v_{i+1}\right), \ldots,\left(v_{r-1}, v_{r}\right)$ называется маршрутом, соединяющим вершины $v_{0}$ и $v_{r}$. Маршрут замкнут, если $v_{0}=v_{r}$. Маршрут, содержащий все вершины или ребра Г. и обладающий определенными свойствами, называется обходом Г. В проблематике теории Г. можно выделить направления, носящие более комбинаторный или более геометрический характер. К первым относятся, напр., задачи о построении Г. с заданными свойствами, задачи о подсчете и перечислении Г. с фиксированными свойствами. Геометрический (топологический) характер носят, напр., задачи, связанные с обходами Г., и задачи, возникающие при укладке Г. на различных поверхностях. В. П. Козырев.

множество $V$ вершин и набор $E$ неупорядоченных и упорядоченных пар вершин; обозначается через $G(V, E)$. Неупорядоченная пара вершин называется ребром, упорядоченная пара - дугой. Г., содержащий только ребра, называется неориентированным; Г., содержащий только дуги,- ориентированным. Пара вершин может соединяться двумя или более ребрами (дугами одного направления), такие ребра (дуги) называются кратными. Дуга (или ребро) может начинаться и кончаться в одной и той же вершине, такая дуга (ребро) называется петлей. Вершины, соединенные ребром или дугой, называются смежными; ребра, имеющие общую вершину, - также смежными. Ребро (дуга) и любая из его двух вершин называются инцидентными. Говорят, что ребро $(u, v)$ соединяет вершины $u$ и $v$, а дуга $(u, v)$ начинается в вершине $u$ и кончается в вершине $v$. Каждый Г. можно представить в евклидовом пространстве множеством точек, соответствующих вершинам, к-рые соединены линиями, соответствующими ребрам (или дугам) Г.,- укладка Г. В 3-мерном пространстве любой Г. можно представить таким образом, что линии, соответствующие ребрам (дугам), не пересекаются во внутренних точках. Класс Г., называемых плоскими, допускает представление в 2-мерном пространстве. Существуют различные способы задания Г. Пусть $v_{1}, v_{2}$, $\ldots, v_{n}$ - вершины графа $G(V, E)$, а $e_{1}, e_{2}, \ldots, e_{m}$ - его ребра. Матрицей смежности, соответствующей графу $G$, называется матрица $A=\left\|a_{i j}\right\|, i=1, \ldots, n, j=1, \ldots, m$, у к-рой элемент $a_{i j}$ равен числу ребер (дуг), соединяющих вершины $v_{i}$ и $v_{j}$ (идущих из $v_{i}$ в $v_{j}$ ), и $a_{i j}=0$, если соответствующие вершины не смежны. В матрице инцидентности $B=\left\|b_{i j}\right\|$ графа $G$ элемент $b_{i j}=1$, если вершина $v_{i}$ инцидентна ребру $e_{j}$, и $b_{i j}=0$, если вершина $v_{i}$ и ребро $e_{j}$ не инцидентны. Г. можно задать посредством списков, напр. указанием пар вершин, соединенных ребрами (дугами), или заданием для каждой вершины множества смежных с ней вершин (степенью вершины $v$ называется число ребер, инцидентных $v)$. Последовательность ребер $\left(v_{0}, v_{1}\right),\left(v_{1}, v_{2}\right), \ldots,\left(v_{i-1}, v_{i}\right)$, $\left(v_{i}, v_{i+1}\right), \ldots,\left(v_{r-1}, v_{r}\right)$ называется маршрутом, соединяющим вершины $v_{0}$ и $v_{r}$. Маршрут замкнут, если $v_{0}=v_{r}$. Маршрут, содержащий все вершины или ребра Г. и обладающий определенными свойствами, называется обходом Г. В проблематике теории Г. можно выделить направления, носящие более комбинаторный или более геометрический характер. К первым относятся, напр., задачи о построении Г. с заданными свойствами, задачи о подсчете и перечислении Г. с фиксированными свойствами. Геометрический (топологический) характер носят, напр., задачи, связанные с обходами Г., и задачи, возникающие при укладке Г. на различных поверхностях. В. П. Козырев.