Презентация на тему Графы

рёбрами.
Вершины, прилегающие к одному и тому же ребру, называются

смежными.
Если ребра не имеют ориентации, граф называется неориентированным.

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

Неориентированный граф состоящий из четырех вершин и семи ребер, одно из которых является петлей.

Полный граф

то они называются дугами, и граф с такими ребрами

называется ориентированным графом или орграфом.

Вершины и рёбра графа называются также элементами графа, число вершин в графе V - порядком, число рёбер E - размером графа.

Вершина графа называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра

Ориентированный граф

графа, т.е. подграф содержит некоторые вершины исходного графа и

некоторые ребра (только те, оба конца которых входят в подграф).

Подграф, порожденный множеством вершин V это подграф, множество вершин которого - V, содержащий те и только те ребра, оба конца которых входят в V.

Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.

Виды подграфов: а – исходный граф; б – подграфы; в – остовные подграфы; г – порожденные подграфы

матрица А с n строками, соответствующими вершинам, и m

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

Матрица смежности. Это матрица n×n где n - число вершин, где bij = 1, если существует ребро, идущее из вершины х в вершину у, и bij = 0 в противном случае.

Матрицы инциндентности и смежности для следующего графа :

смежности определяется следующим образом:
aij = 1, если существует дуга

(хi, хj),
aij = 0, если нет дуги (хi, хj).

Каждый элемент матрицы инциндентности определяется следующим образом:
bij = 1, если хi является начальной вершиной дуги aj,
bij = –1, если хi является конечной вершиной дуги aj,
bij = 0, если хi не является концевой вершиной дуги aj или если aj является петлей.

Орграф и его матричное представление: а – орграф; б – матрица смежности; в – матрица инциденций

изоморфными, если существует соответствие между вершинами графа G и

вершинами графа H, сохраняющее отношение смежности.
Изоморфные графы отличаются только метками вершин.
Любой неориентированный граф превращается в орграф заменой каждого ребра двумя противоположно направленными ребрами. Два полученные таким образом орграфа, очевидно, изоморфны тогда и только тогда, если изоморфны исходные графы.

последовательность дуг, в которой конечная вершина всякой дуги, кроме

последней, является начальной вершиной следующей дуги.
Вершины x0, xn называются связанными данным путем (или просто связанными). Вершину x0 называют началом, xn - концом пути. Если x0 = xn, то путь называют замкнутым. Число n называется длиной пути.

Например, для графа на рисунке последовательности дуг
M1: a1, a6, a5, a9, a7 , где x1 – начало пути, x6 – конец пути.
M2: a1, a6, a5, a9, a10, a6, a4
являются путями. Пути могут быть различными.

можно пренебречь.
Цепь - маршрут, в котором все ребра

попарно различны.
Цикл - замкнутый маршрут, являющийся цепью.

Маршрут, в котором все вершины попарно различны, называют простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называются простым циклом.

Граф называется связным, если в нем для любых двух вершин имеется маршрут, соединяющий эти вершины.

A, C, A, D – маршрут, но не цепь;

A, C, E, B, C, D – цепь, но не простая цепь;

A, D, C, B, E, - простая цепь;

A, C, E, B, C, D, A – цикл, но не простой цикл;

A, C, D – простой цикл;

наименьшая длина пути, соединяющего эти вершины.
Расстояние от данной

вершины x до наиболее удаленной от нее вершины называется эксцентриситетом вершины x.
Вершину с наименьшим эксцентриситетом называют центральной, а вершину с наибольшим эксцентриситетом - периферийной. Множество всех центральных вершин называется центром графа. Сама величина наименьшего эксцентриситета называется радиусом графа, а величина наибольшего – диаметром.
Если расстояние между двумя вершинами равно диаметру графа, то кратчайший путь, соединяющий эти вершины, называется диаметральным путем, а подграф, образованный вершинами и ребрами этого пути, - диаметральной цепью.

Для графа, изображенного на рисунке, эксцентриситеты вершин приведены в следующей таблице:

Центр этого графа составляют вершины 4,6, 7; периферийные вершины - 1,5 и 9; радиус его равен 3, а диаметр 5. Одна из диаметральных цепей порождается множеством вершин {1,3,6,7,8,9}.

ребра графа(путь, по определению, не может дважды проходить по

одному ребру).
Если эйлеров путь замкнут, то он является эйлеровым циклом.
Граф, содержащий эйлеров цикл, называется эйлеровым графом.

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

Эйлеров цикл : последовательность вершин 1,2,4,5,2,3,5,6,3,1

Эйлеров путь : последовательность вершин 2,4,5,2,1,3,5,6,3

или гамильтонов цикл.
Гамильтонов путь— путь, содержащий каждую вершину графа

ровно один раз.
Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом.

Условие Дирака
Пусть p — число вершин в данном графе; если степень каждой вершины не меньше p/2, чем , то граф называется графом Дирака. Граф Дирака — гамильтонов.

Граф с выделенным циклом Гамильтона

граф, в котором каждая пара вершин соединена одной и

только одной простой цепью, называется деревом.
.

а - неориентированное дерево
б - ориентированное дерево

Лесом называется несвязный граф, представляющий объединение деревьев

Лес, состоящий из четырех компонент, каждая из которых является деревом.

ребер, n- число вершин, p -число компонент связности.
Компонента связности—

некоторое множество вершин графа такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества.
Цикломатическим числом графа называют число n =m-n+p.
Цикломатическое число графа указывает то наименьшее число рёбер, которое нужно удалить из данного графа, чтобы получить дерево (для связного графа) или лес (для несвязного графа), т.е. добиться отсутствия у графа циклов.
Цикломатическое число всегда неотрицательно.

Несвязный граф с тремя компонентами связности

Цикломатическое число графа V=14-7+1=8

имеют номера от 1 до n, называют деревом с

пронумерованными вершинами.

Теорема Кэли о числе деревьев — на n вершинах, пронумерованных числами от 1 до n, существует ровно
n^(n-2) различных деревьев.

играющая роль своего рода "начала отсчета".
Дерево с выделенной

вершиной называют корневым деревом, а саму эту вершину - корнем. Из дерева с вершинами можно, таким образом, образовать различных корневых деревьев.

При графическом изображении корневого дерева обычно придерживаются какого-нибудь стандарта. Один из наиболее распространенных состоит в следующем. Возьмем на плоскости семейство параллельных прямых с равными расстояниями между соседними прямыми. Изобразим корень точкой на одной из этих прямых, смежные с корнем вершины - точками на соседней прямой, вершины, находящиеся на расстоянии 2 от корня, - на следующей, и т.д. Ребра изобразим отрезками прямых. Ясно, что вершины на каждой прямой можно разместить так, чтобы ребра не пересекались.

Пример корневого дерева

графа, таких, что из любой вершины графа можно попасть

в любую другую вершину, двигаясь по этим рёбрами, и в нём нет циклов, то есть из любой вершины нельзя попасть в саму себя, не пройдя какое-то ребро дважды.

Минимальное остовное дерево в связанном, взвешенном, неориентированном графе — это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.

Пример минимального остовного дерева в графе. Числа на ребрах обозначают вес ребер.

множество вершин которого можно разбить на две части таким

образом, что каждое ребро графа соединяет какую-то вершину из одной части с какой-то вершиной другой части, то есть не существует ребра, соединяющего две вершины из одной и той же части.
Для того, чтобы проверить граф на предмет двудольности, достаточно в каждой компоненте связности выбрать любую вершину и помечать оставшиеся вершины во время обхода графа поочерёдно как чётные и нечётные. Если при этом не возникнет конфликта, все чётные вершины образуют множество U, а все нечётные — V.

Двудольный граф

Проверка двудольности с помощью чётности расстояний

несмежных ребер (у них нет общих вершин).

Максимальное паросочетание —

это такое паросочетание, которое не содержится ни в каком другом паросочетании этого графа.
Наибольшее паросочетание — это такое паросочетание, которое содержит максимальное количество ребер.

Пример паросочетания