Математическая энциклопедия - граф

множество Vвершин и набор Енеупорядоченных и упорядоченных пар вершин; обозначается Г. через . Неупорядоченная пара вершин наз. ребром, упорядоченная пара дугой. Г., содержащий только ребра, наз. неориентированным; Г., содержащий только дуги,ориентированным. Пара вершин может соединяться двумя или более ребрами (дугами одного направления), такие ребра (дуги) наз. кратными. Дуга (или ребро) может начинаться и кончаться в одной и той же вершине, такая дуга (ребро) наз. петлей. (Иногда под Г. понимают Г. без петель и кратных ребер; тогда Г., в к-ром допускаются кратные ребра, наз. мультиграфом, а Г., в к-ром допускаются кратные ребра и петли, наз. псевдографом.)

Вершины, соединенные ребром или дугой, наз. смежными. Ребра, имеющие общую вершину, также наз. смежными. Ребро (дуга) и любая из его двух вершин наз. инцидентными. Говорят, что ребро соединяет вершины и , а дуга начинается в вершине ин кончается в вершине v.

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

Существуют различные способы задания Г. Пусть вершины графа его ребра. Матрицей смежности, соответствующей графу G, наз. матрица у к-рой элемент равен числу ребер (дуг), соединяющих вершины и (идущих из в ), и , если соответствующие вершины не смежны. В матрице инцидентности графа Gэлемент , если вершина инцидентна ребру , и , если вершина и ребро не инцидентны. Г. можно задать посредством списков, напр., указанием пар вершин, соединенных ребрами (дугами), или заданием для каждой вершины множества смежных с ней вершин. Два графа и наз. изоморфными, если существует взаимно однозначное соответствие между множествами вершин V, W и множествами ребер сохраняющее отношение инцидентности (см. также Графов изоморфизм).

Подграфом графа наз. Г. с множеством вершин и множеством ребер (дуг) каждое из к-рых инцидентно только вершинам из . Подграфом порожденным подмножеством , наз. Г. с множеством вершин и набором ребер (дуг) , состоящим из всех ребер (дуг) графа G, к-рые соединяют вершины из .Остовный подграф содержит все вершины графа Gи нек-рый поднабор его ребер (дуг) Последовательность ребер наз. маршрутом, соединяющим вершины и . Маршрут замкнут, если . Маршрут наз. цепью, если все его ребра различны, и простой цепью, если все его вершины различны. Замкнутая (простая) цепь наз. (простым) циклом. Г. наз. связным, если любая пара его вершин соединена маршрутом. Максимальный связный подграф графа Gназ. компонентой связности. Несвязный Г. имеет по крайней мере две компоненты связности (см. также Графа связность).

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

наз. радиусом, а вершина , для к-рой

принимает наименьшее значение, наз. центром графа G. В Г. может быть много центров и ни одного.

Степенью вершины графа , обозначаемой di, наз. число ребер, инцидентных этой вершине. Если граф G (без петель) имеет пвершин и требер, то

Вершина наз. изолированной, если , и концевой, если . Г., у к-рого все вершины имеют одинаковые степени (равные k), наз. регулярным (степени k). В полном Г. нет петель и каждая пара вершин соединена в точности одним ребром. Для графа не имеющего петель и кратных ребер, дополнительным Г. к Gназ. граф , у к-рого и вершины смежны в только в том случае, когда они не смежны в G. Т., дополнительный к полному, состоит из изолированных вершин и наз. пустым. Многие характеристики для графа Gи его дополнения оказываются зависимыми. В ориентированном графе Gдля каждой вершины определяются полустепень исхода и полустепень захода как количества дуг, выходящих из этой вершины и входящих в нее соответственно. Полный ориентированный Г. наз. турниром.

Каждому графу G можно отнести ряд Г., являющихся производными от G. Так, реберным графом L (G) графа Gназ. Г., вершины к-рого соответствуют ребрам графа G и две вершины смежны в L(G) в том н только в том случае, когда соответствующие им ребра графа G смежны. В тотальном графе Т(G) графа G вершины соответствуют элементам графа G, т. е. вершинам и ребрам, и две вершины в Т(G).смежны тогда и только тогда, когда соответствующие элементы в G смежны или инцидентны. Многие свойства графа G переносятся на графы L(G).и T(G). Известно много обобщений понятия "Г."; одними из них являются понятия гиперграфа и сети.