ГРАФ

- множество 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). Известно много обобщений понятия "Г."; одними из них являются понятия гиперграфа и сети.

С помощью различных операций можно строить Г. из более простых, переходить от одного Г. к более простому, разбивать Г. на более простые, в заданном классе Г. переходить от одного Г. к другому п т. д. Наиболее употребительными одноместными операциями являются: удаление ребра (вершины ребра сохраняются), добавление ребра между двумя вершинами Г., удаление вершины вместе с инцидентными ей ребрами (Г., полученный в результате удаления вершины из графа , часто обозначают ), добавление вершины (к-рую можно соединить ребрами с нек-рыми вершинами Г.), стягивание ребра - отождествление пары смежных вершин, т. е. удаление пары смежных вершин и добавление новой вершины, смежной с теми вершинами Г., к-рые были смежны хотя бы с одной из удаленных вершин; подразбиение ребра- удаление ребра и добавление новой вершины, к-рая соединяется ребром с каждой вершиной удаленного ребра. В ряде задач теории Г. используются двуместные операции над Г. Пусть _и -Г. такие, что и Объединением графов и наз. граф " с множеством вершин и множеством ребер Произведением графов наз. граф множеством вершин к-рого являются элементы декартова произведения причем две из этих вершин () и () смежны в том и только в том случае, если либо и вершина смежна с вершиной , либо и вершина смежна с вершиной Напр., любой Г. является объединением своих компонент связности; Г., известный как n-мерный единичный куб , может быть определен рекуррентно с помощью операции произведения:

где -граф, состоящий из пары вершин, соединенных одним ребром. Эти операции можно определить также для пересекающихся Г., в частности для подграфов одного Г. Сложением по модулю 2 графов наз. граф G с множеством вершин и множеством ребер .

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

Понятие "Г." используется в определении таких ма-тематич. понятии, как управляющая система, в нек-рых определениях алгоритма, грамматики и др. Изложение ряда математич. теорий становится более наглядным при использовании геометрич. представления Г., напр. теории марковских цепей. Понятие "Г." широко используется при создании п описании различных математич. моделей в экономике, биологии и т. д.

Лит.:[1] Берж К., Теория графов и ее применения пер. с франц., М., 1962; [2] Оре О., Теория графов, пер. с англ., M., 1968 [3] Зыков А. А..Теория конечных графов, [в. 1], Новосибирск., 1969; [4] Харари Ф., Теория графов, пер. с англ., М., 1973.