Графы. Реализация графов на плоскости. Деревья

Определение: Графом G (в широком понимании) называется любая пара (V,E), где V = {v₁, v₂,... } - множество вершин графа, а E = {e₁, e₂,... } – множество неориентированных ребер, причем допускаются пары вида (v_i, v_i) и одинаковые пары. Если пары в V рассматриваются как неупорядоченные, то граф называется неориентированным, если как упорядоченные, то граф называется ориентированным (орграфом).

Элементы множества V называются вершинами графа, а пары из E - его ребрами; в орграфе они называются ориентированными ребрами или дугами.

Говорят, что ребро e = (u,v) в неориентированном графе соединяет вершины u и v, а в ориентированном графе дуга e = (u,v) идет из вершины u в вершину v.

Пара вида (v_i, v_i) называется петлей в вершине v_i(т.е. повторяются вершины в множестве). Если пара (v_i, v_j) встречается в E более одного раза, то говорят, что (v_i, v_j) - кратное ребро.

Определение: Говорят, что вершины v_i и v_j смежны в графе G = (V,E), если в E входит пара (v_i, v_j) или (v_j, v_i). Говорят, что ребро (дуга) (v_i, v_j) инцидентно вершинам v_i и v_j.

Определение: Смешанные графы - графы, в которых часть ребер ориентированы, а часть – нет.

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

Определение: Путем в графе (орграфе) G = (V,E) называется последовательность вершин и ребер (дуг) вида v₀, (v₀, v₁), v₁,..., v_n-1, (v_n-1, v_n), v_n, где все v_i ℮ E и все (v_i, v_i+1) ℮ E. Длина пути - это число ребер (дуг) в нем. Говорят, что этот путь идет из v₀ в v_n.

Определение: Маршрутом в графе называют последовательность вершин, любая пара последовательности вершин в которой смежна.

Определение: Путь называется циклом, если v_n = v₀ и ребра (дуги) не повторяются(т.е. начальная и конечная вершины совпадают). Путь называется простым циклом, если v_n = v₀ и больше нет повторений вершин.

Определение: Граф G = (V,E) называется связным, если для любых двух вершин v_i, v_j О V в G существует путь из v_i в v_j.

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

Определение: Граф G = (V,E) называется деревом, если он связный и не содержит циклов. Вершины степени 1 в дереве называют его листьями.

Пусть задан неориентированный граф G = (V,E). Пусть каждой вершине v_i из V сопоставлена точка a_i в некотором евклидовом пространстве, причем ai ≠ a_j при i ≠ j. Пусть каждому ребру e = (v_i, v_j) из E сопоставлена непрерывная кривая L, соединяющая точки a_i и a_j и не проходящая через другие точки a_k. Тогда если все кривые, сопоставленные ребрам графа, не имеют общих точек, кроме концевых, то это множество точек и кривых называется геометрической реализацией графа G.

Теорема. Каждый конечный граф G можно реализовать в трехмерном евклидовом пространстве (без пересечения ребер).

Определение: Граф называется планарным, если существует его планарная реализация, то есть геометрическая реализация на плоскости (без пересечения ребер).

Определение: Связный граф называется Эйлеровым, если в нем присутствует цикл, содержащий все ребра.

Теорема. (формула Эйлера.) Для любой планарной реализации связного планарного графа G = (V,E) с p вершинами, q ребрами и r гранями выполняется равенство: p-q+r = 2.

Критерий Эйлера: граф является Эйлеровым т. и т. т., когда он связный и все степени его вершин четны.