Маршруты в графах и деревья.

Пусть G-граф (Графом) называется совокупность множеств вершин V и ребер Е между которыми установлено отношение инцедентности G = {V*E}}. Последовательность ребер в которых каждая пара соседних имеет общую вершину называется маршрутом. Зам: необязательно все ребра должны быть различными. Начало маршрута определяет начальную вершину, конец - конечную, а остальные - промежуточ­ные.Путем из Vi —> V_n называется такой маршрут, в котором каждое ребро не встречается более одного раза. Путь называется простым,, если он не проходит ни через одну из вершин графа более одного раза. Путь в котором совпадают его начальные и конечные вершины называется циклом. Простым циклом в графе называется цикл, не проходящий пи через одну из вершин графа более одного раза. Длиной пути называется число ребер этого пути. Длиной цикла называется число ребер данного цикла. Две вершины графа наз связными, если в графе сущ соединяющий их путь. Граф наз связным, если для каж пары различ вершин сущ соединяющий их путь. Несвяз, если сущ хотя бы одна пара вершин несвязан. Th: Связ граф представляет собой простой цикл, титтк степень каж его вершины=2. Путь наименьшей длины, соединяющий 2 вершины называется расстоянием. Свойства: d(u, v)> =0, d(u, u)=0, d(u, v)=d(v, u), d(u, v)+d(v, w)> =d(u, w). - диаметр графа. Выберем некоторую точку вершину V и обозначим . - центр графа, если она реализует минимум . - радиус Графа.

Эйлеровы графы. Эйлеровым путем в Q называется путь, содержащий нес ребра графа (не более 1 раза). Эйлеровым циклом в G называется цикл, содержащий все ребра графа. Граф, обладающий эйлеровым путем и эйлеровым циклом называется эйлеровым графом. Всякую замкнутую линию, если её можно начертить не отрывая карандаша от бумаги, проходя при этом каждый участок в точности один раз называют уникурсалъной. Рисунок графа, облада­ющий эйлеровым путем или циклом называется уникурсальной линией. Тh: Граф G является эйлеровым т. и т. т., к. он связный и каждая его вершина четна. Д-во: Пусть граф – Эйлеровый, следовательно он связный и содержит эйлеров цикл (путь), т.е. сколько раз конец карандаша приведт в вершину столько раз и выведет, причем по другому ребру. Сл-но,

Замкнутую фигуру в которой все вершины четны можно начертить одним росчерком, начиная обводить с любой точки или вершины.Тh: Если Gобладает эйлеровым путем с концами в вершинах а и b (причом а и b не совпадают), то граф связный и вершины а и b единственные нечетные вершины. Тh: Если G связный и вершины а и b нечетные вершины, то граф обладает эйлеровым путем с концами в этих вершинах.

Гамельтонов граф. Гамелътонов цикл (путь) - это цикл (путь), проходящий через каждую вершину в точности по одному разу, Гамельтонов путь или цикл всегда явл простым. Зам Гамельтонов путь или цикл может не содержать всех ребер. Граф, обладающий гамельтоновым путем или циклом называется гамельтоновым графом. Достаточные условия существования гамелътоновых циклов: 1) Всякий полный граф является гамельтоновым.(Для полного графа всегда найдется простой цикл, который содержит все вершины графа), 2) Если граф по мнению простого цикла содержит и другие ребра, то он также является гамель­тоновым.3) Если для любой пары вершин графа с п вершинами сумма их степеней не меньше п. то граф обладает гамельтоновым циклом.4) Граф с n вершинами имеет гамельтонов цикл, если для каждой его вершины степень больше или равна n/2.

Деревья. Лес. Деревом называется всякий связный граф, не имеющий цикла. Из определения следует, что дерево не содержит петель и кратных ребер и для каждой пары вершин существует единственный путь, соединяющий их. Принято считать, что граф состоящий из одной изолированной вершины также является деревом. Выбирается произвольная вершина, которая соединяется с соседними вершинами и т, д. Вершина степень которой равна 1 насыпается висячей вершиной.(pVi = 1, V - висячая вершина).Первоначально выбранная вершина называется корнем дерева.

Th: Дерево с п вершинами имеет n — 1 ребро. Док-во: для того, чтобы из дерева G, не явл изолир вершиной, получить 2 дерева с теми же вершинами, необходимо удалить ребро. Для того, чтобы из дерева G получить 3 дерева необходимо удалить 2 ребра. Из дерева с п вершинами можно получить п деревьев каждое из которых явл. изолированной вершиной для этого необходимо удалить n — 1 ребро, т.о. в дереве с п вершинами п — 1 ребро.

Пусть G-с вязный с множеством вершин V. Деревом покрытия G или покрывающим деревом наз. подграф с тем же мн-вом вершин, кот. является деревом.

Th: любой связный граф содержит в себе покрывающее дерево. Док-во: 1) Пусть G не содержит циклов => G дерево. 2) Пусть G - связный и содержит цикл. Удалим 1 ребро данного цикла => подграф G1 с тем же мн-вом вершин. Если g1 не содержит циклов, то он явл. деревом. Если g1 содержит цикл, то опять удаляем 1 ребро из цикла. Получаем подграф G2 с тем же мн-вом вершин. Опять процесс повторяем пока результирующий граф G_n не будет содержать ни одного цикла, G_n имеет тоже самое мн-во вершин, связность сохранена, т.о. G_n явл. деревом. Th доказана.

Зам: Связный G в общем случае может иметь много различных покрывающих деревьев. Всякое ребро в дер. явл. перегородкой, т.е. удаление ребра нарушает связность. Лесом наз. не связ. граф, представляющий объединение деревьев. Th: Лес, состоящий из k деревьев и имеющий п вершин содержит (n — k) ребер.Длина кратчайшего пути для 2-х вершин наз. расстоянием. Для каждой вершины считают наи­большее из расстояний до всех остальных вершин, max из этих чисел наз. диаметром, min - радиусом. Вершины для кот. max из расстояний совпадает с радиусом наз. корневой вершиной.

Th: Любое дерево имеет либо 1, либо 2 корневые вер-ны. Полным бинарным дер. наз. дер., у кот. только одна вер-на валентности 2, остальные 1 и 3. Вершина с валентностью 2 наз. корнем, вершина с валентностью 3 - вершиной решения, с валентностью 1- листья. Любое полное бинарное дер. имеет нечетное число вершин. В полном бинарном дер. листьев всегда ровно на 2 больше, чем вер-и решения. Цикломатическим числом G графа наз.число v(G)=v_c + v_r+ v _v, где v_c -число связных компонент данного графа (т.е. все связные подграфы); v_r -число ребер: v _v -число вершин. Цикломатическое число явл. не отрицательным чис­лом.

Дерево, у которго все вершины, кроме одной висячие называется звездой.