Теория графов

№	понятия	определения, формулы
1	Конечный неориентированный граф	задается с помощью: множества вершин графа ; множества ребер графа U – множество неупорядоченных элементов из . Число вершин графа: . Число ребер:
2	Мультиграф	Если одну пару вершин соединяет несколько ребер, то граф называется мультиграфом.
3	Кратные ребра	Ребра, соединяющие одну и ту же пару вершин, называются кратными
4	Петля	Если начало и конец ребра находятся в одной точке, то такое ребро называется петлей
5	Псевдограф	Граф, содержащий хотя бы одну петлю, называется псевдографом
6	Простой или обыкновенный граф	Конечный неориентированный граф без петель и кратных ребер называется простым или обыкновенным графом
7	Плоский граф	Граф называется плоским (планарным), если на плоскости его можно изобразить так, что все пересечения его ребер являются вершинами графа
8	Ориентированный граф (орграф)	Если ребрам графа придать направление, то граф называется ориентированным. В этом случае ребра называются дугами
9	Инцидентность ребра и вершины	Пусть ребро соединяет вершины графа x и y, тогда ребро и вершина x называются инцидентными
10	Смежность вершин	Пусть ребро соединяет вершины графа x и y, тогда вершины x и y называются смежными
11	Степень вершины неориентированного графа	Число ребер, инцидентных вершине x, называют степенью этой вершины. Обозначают deg или
12	Изолированная вершина	Вершина, степень которой равна 0, называется изолированной
13	Висячая вершина	Вершина, степень которой равна 1, называется висячей
14	Полный граф	Неориентированный граф, в котором каждая пара вершин соединена ребром, называется полным
15	Полный -вершинный граф	Обозначается . Для каждой его вершины x имеем
16	Полустепень вершины орграфа	- число дуг, входящих в вершину x. - число дуг, исходящих из вершины x
17	Матрица смежности неориентированного графа или орграфа	, где - кратность ребра (дуги) для графа с петлями и кратными ребрами (дугами)
18	Матрица инцидентности неориентированного графа
19	Матрица инцидентности орграфа
20	Изоморфизм графов	Два графа и называются изоморфными, если между их вершинами можно установить взаимно-однозначное соответствие: любые две вершины графа смежны соответствующие вершины графа смежные
21	Маршрут	Конечная последовательность вершин и ребер неориентированного графа , в которой каждое ребро соединяет вершины и , называется маршрутом
22	Цепь	Маршрут, в котором все ребра различны, называется цепью
23	Цикл	Замкнутая цепь называется циклом
24	Простая цепь	Цепь называется простой, если все ее вершины различны
25	Простой цикл	Цикл, в котором все вершины различны, кроме первой и последней, называется простым
26	Цепь Гамильтона	Цепь Гамильтона - цепь, которая содержит все вершины данного графа и притом по одному разу
27	Цикл Гамильтона	Цикл Гамильтона - цикл, который содержит все вершины данного графа и притом по одному разу
28	Цепь Эйлера	Цепь Эйлера - цепь, которая содержит все ребра данного графа и притом по одному разу
29	Цикл Эйлера	Цикл Эйлера - цикл, который содержит все ребра данного графа и притом по одному разу
30	Подграф	Граф называется подграфом графа , если и
31	Основной подграф	Граф называется основным подграфом графа , если и
32	Связные вершины	Вершина a неориентированного графа называется связной с вершиной b, если существует маршрут, соединяющий эти вершины
33	Связный граф	Граф, любая пара вершин которого связна, называется связным
34	Связные компоненты графа	Пусть , ,…, - непересекающиеся связные подграфы графа : . Тогда эти подграфы называются связными компонентами графа . - число компонент связности графа. Для связного графа , для несвязного -
35	Цикломатическое число графа
36	Расстояние между двумя вершинами графа	Расстоянием между двумя вершинами x и y связного графа называется длина кратчайшей цепи, связывающей эти вершины. Обозначается
37	Диаметр графа
38	Эксцентриситет вершины x	Расстояние от x до самой отдаленной от x вершины называется эксцентриситетом вершины x
39	Радиус графа
40	Центральная вершина	Вершина, в которой достигается , называется центральной
41	Эйлеровы графы	Граф, содержащий цикл Эйлера, называется Эйлеровым графом
42	Критерий Эйлерового графа	Конечный граф является Эйлеровым графом - связный граф и все его вершины имеют четные степени
43	Дерево	Деревом называется связный граф без циклов
44	Лес	Граф , все компоненты связности которого – деревья, называется лесом
45	Транспортная сеть	Транспортная сеть – это орграф , в котором каждой дуге поставлено в соответствие неотрицательное число , которое называется пропускной способностью дуги; выделены две вершины s и t. При этом в графе нет дуг, которые заходят в вершину s, и нет дуг, которые выходят из вершины t. Эти две вершины называются источником и стоком соответственно
46		Обозначим - множество всех дуг, которые входят в вершину x, - множество всех дуг, которые выходят из вершины x. Для вершин s и t имеем:
47	Поток дуги транспортной сети	Функция называется потоком дуги , если ;
48	Величина потока транспортной сети	= Величина потока равна сумме потоков всех дуг, которые заходят в вершину t и равна сумме потоков всех дуг, которые выходят из вершины s