ГРАФ

— система объектов произвольной природы (вершин) и связок (ребер), соединяющих некоторые пары этих объектов. Ребра могут быть ориентированными или неориентированными, одна и та же пара вершин может соединяться любым количеством ребер, вершина может быть соединена сама с собой (рис. 1). Строгое определение Г. (по А. А. Зыкову) следующее: Г. задан, если даны мн-во (вершин), мн-во U (ребер) и инцидентор — трехместный предикат Р, причем означает высказывание: «ребро и соединяет вершину с вершиной у» и удовлетворяет двум условиям: а) Р определен на всех таких упорядоченных тройках элементов , для которых , т. е. каждое ребро соединяет какую-то пару (упорядоченную) вершин , но кроме нее может соединять еще только обратную пару

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

Другое определение Г. (по К. Бержу): Г. есть пара образованная мн-вом X (вершин) и семейством U (дуг), состоящим из упорядоченных пар вершин, причем одна и та же пара может фигурировать в U любое число раз. Все ребра (в том числе петли) есть дуги, т. е. «ориентированы», однако если в конкретном случае не важно, идет ли дуга из или из эту дугу рассматривают как «неориентированную» и рисуют без стрелки (либо с двумя противоположными стрелками); при таком представлении Г., в котором к дуг — «неориентированный», фактически представляет собой класс из 2 различных Г. В дальнейшем при изложении графов теории будем придерживаться определений и обозначений А. А. Зыкова.

Г. частью (по К. Бержу) — частичным подграфом) Г. , если и на подмн-вах X, U предикат Р совпадает с Р. Часть L есть подграф Г. L, если всякое ребро из U, соединяющее вершины мн-ва X, принадлежит U. Часть L есть суграф (по К. Бержу — частичный Г.) Г. L, если Два Г. изоморфны, если можно установить взаимно однозначное соответствие так, чтобы для соответствующих вершин и ребер высказывания были равносильны. Для каждого абстрактного (т. е. без указания конкретной природы вершин и ребер) Г. , в котором мн-ва X и U не более чем счетны, заведомо можно построить его топологическое представление — изоморфный Г. вершинами которого служат некоторые точки евклидова трехмерного пространства, а ребрами — соединяющие их простые жорда-новы дуги (с указанием или без указания направления), не имеющие друг с другом общих точек, отличных от вершин. Г. плоским, если он допускает такое топологическое представление, все вершины и дуги которого расположены в одной плоскости (или на одной сфере, а это равносильно, поскольку стереографическим проектированием всегда можно перевести плоское представление в сферическое и наоборот). Г. без дуг (т. е. «неориентированный»), без петель и кратных ребер наз. обыкновенным; его можно задавать парой (X, U), где U — некоторое мн-во (не семейство!) неупорядоченных пар различных вершин из X. Г. без звеньев («ориентированный»), без кратных петель и кратных дуг одного направления наз. Бержа графом (X, U), где U — некоторое мн-во упорядоченных пар вершин; такой Г. записывают также в виде (X, Г), где Г — отображение, которое каждому относит подмн-во тех вершин, в которые из идет дуга или петля. Напр., для Г. Бержа на рис. 2 имеем двудольным (или бихроматическим), если мн-во X его вершин можно разбить на два подмн-ва: так, чтобы никакое ребро не соединяло вершин одного и того же подмн-ва; в частности, двудольный обыкновенный Г. наз. графом Кёнига и при заданном разбиении мн-ва вершин его записывают в виде заданного типа наз. полным, если он содержит все возможные для этого типа ребра (при неизменном мн-ве вершин). Так, в полном обыкновенном Г. каждая пара различных вершин соединена ровно одним звеном; в полном Г. Бержа из каждой вершины в каждую другую идет одна дуга и при каждой вершине имеется одна петля; полный Г. Кёнига состоит из двух мн-в вершин и из всевозможных звеньев, соединяющих вершины одного мп-ва с вершинами другого (по одному звену для каждой такой пары вершин). На рис. 3 показаны полный обыкновенный пятивершинный Г. и полный Г. Кёнига с двумя трехвершинными мн-вами («три дома и три колодца»); оба они — неплоские. Г. без ребер пустым. С понятием Г. связана целая система конкретных проблем и методов преимущественно практических или вызванных теор. проблемами из др. областей математики. Лит.: Зыков А. А. Теория конечных графов, т. 1. Новосибирск, 1969 [библиогр. с. 515-542]; Ноnig D. Theorie der endlichen und unendlichen Graphen. Leipzig, 1936; Берн К. Теория графов и ее применения. Пер. с франц. М., 1962 [библиогр. с. 293-302]; Оре О. Теория графов. Пер. с англ. М., 1968 [библиогр. с. 325—338]; Berge С. Graphes et hypergraphes. Paris, 1971; Xapapи Ф. Теория графов. Пер. с англ. М., 1973 [библиогр. с. 269—286]. А. А. Зыков.