длины n …

длины m , где a= и b= . В каждом пути должна существовать первая вершина , начиная с которой соответствующие вершины не совпадают , скажем и

в каждом пути должна существовать точка , начиная с которой вершины опять одни и те же . Скажем . Тогда … , поэтому граф G не является деревом .

Докажем импликацию : Любые две несовпадающие вершины графа G соединяет единственная простая цепь ⇒G- дерево .

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

являются путями из .значит из a= в b= существует не единственный путь .

Пусть G – связный граф. Эксцентриситетом вершины vназывается расстояние от вершины

V до самой дальней от v вершины . Центральной вершиной графа называется вершина , имеющая наименьший эксцентриситет . Множество центральных вершин графа называется центром графа .

Теорема . Центр дерева состоит из одной , или двух смежных вершин .

Доказательство . Пусть G –дерево . Самой дальней от любой его вершины будет некоторая висячая вершина . Если из дерева удалить все висячие вершины , то

Эксцентриситет каждой вершины в новом графе станет на единицу меньше , чем в

---

старом . Поэтому центральными вершинами в новом графе останутся те же вершины , что и в старом .Будем продолжать процесс удаления висячих вершин до тех пор , пока не

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

Определение . Наибольшее из расстояний между вершинами графа называется диаметром графа и обозначается d(G) .

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

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

Остовное дерево , имеющее минимальную суммарную длину ребер называется минимальным остовным деревом .

Теорема . У каждого связного графа существует подграф , который является остовным деревом .

Доказательство . Пусть G содержит цикл , если ребро { } входит в цикл то

Существуют два пути из . значит ребро { } можно из цикла удалить , а путь из вершины будет существовать . Пусть a иb – любые вершины в графе G .

Так как граф G связен , то существует путь из a вb . Если ребро { } удалено . то все равно существует путь из a вb .Удалим ребро { } из G и , если оставшийся граф все еще содержит цикл , удалим другое ребро , используя ту же процедуру . Процесс

продолжим до тех пор . пока все циклы не будут удалены . В результате получим связный граф без циклов , то есть дерево .

Заметим . что вообще говоря эта процедура не однозначна .

Пример :

---

• • • • • •

• • • • • • • • •

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

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

Теорема Эйлера . Связный граф является эйлеровым тогда и только тогда , когда степень каждой его вершины четна .

Доказательство . Пусть G имеет эйлеров цикл . Граф связен так как каждая вершина принадлежит циклу . Эйлеров цикл проходит через v, он вносит 2 в степень v . Поэтому степень v четная .

Докажем . что каждый связный граф , у которого степени вершин четные имеет эйлеров цикл . Доказательство индукцией по числу вершин . Пусть n . Предположим , что

Каждый связный граф , имеющий менее kвершин , все вершины которого имеют четную степень , содержит эйлеров цикл . Пусть G – связный граф , содержит kвершин , степени которых четные .Пусть – вершины графа G. Существует путь из . Поскольку

степень – четная существует неиспользованное ребро по которому можно продолжить путь .Так как граф конечный , то путь в конце концов должен вернуться в и эйлеров цикл можно считать построенным . Если эйлеров цикл для G , то доказательство закончено .Если нет , то пусть подграф графа G , полученный удалением всех ребер , принадлежащих . Поскольку содержит четное число ребер , инцидентных каждой вершине , каждая вершина подграфа имеет четную степень .Пусть e ребро графа ,

и

---

– компонента графа , содержащая e . Так как имеет менее , чем kвершин и у

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

. У и имеется общая вершина . Обозначим ее a .Теперь можно продолжить эйлеров цикл , начиная его в a . Пройти , вернуться в a , затем пройти и вернуться в

a . Продолжаем использовать этот процесс , расширяя наш эйлеров цикл , пока не получим эйлеров цикл для G .

Определение. Пусть G=G(V ,E) –граф . Путь, который включает каждое ребро графа G только один раз называется эйлеровым путем . В этом случае говорят , что граф имеет эйлеров путь . Эйлеров путь . не являющийся эйлеровым циклом будем называть собственным эйлеровым путем .

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

Определение. Ориентированный граф или орграф G , который обозначается G( V , E )

состоит из множества V вершин и множества Eупорядоченных пар элементов из V ., называемого множеством ориентированных ребер или просто ребер . элемент множества

E называется ориентированным ребром .Если (a, b) , то a называется начальной вершиной, а b называется конечной вершиной .

Ребро (a, b) называется дугой, соединяющей a иb .

Определение. Размеченный граф G=G (V, L,E) представляет собой множество вершин

V, множество меток L и множества , которое является подмножеством множества

V . Таким образом ребро eграфа G имеет вид (a,l,b) , где l–метка , а aи bвершины .

Определение.Ориентированный граф

---

( называется ориентированным подграфом ориентированного графа G( V , E ) , если .

Определение. Ориентированный путь из a вb задается последовательностью вершин

… , гдеa= , b= и ( , ) для 1 i –ориентированные ребра .

Длиной ориентированного пути называется количество ориентированных ребер , входящих в путь .

Определение. Если считать ребра ориентированного графаG неориентированными, то такой граф будем называть графом, соотнесенным с графом G .

Определение. Ориентированный графG( V , E ) называется связным , если его соотнесенный граф является связным .

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

a,b Vсуществует ориентированный путь из aв b .

Определение. Ориентированное дерево Tпредставляет собой свободный от петель

ориентированный граф, соотнесенный граф которого является деревом.

Если в ориентированном дереве существует ребро (a, b), то не существует ребра (b ,a),

так как в этом случае путь abaбыл бы циклом и путь из aв bбыл бы не единственным.

Таким образом , если (a, b) то (b ,a ) . Такое отношение называется

асиметричным .

Вершина в самой верхней части изображения дерева называется корнем дерева.

Если корень дерева определен , то дерево называется корневым деревом .Если ориентировать корневое дерево , то получится корневое ориентированное дерево ,

Порожденное корневым деревом .

Пусть корень дерева выбран. Уровень вершины vопределяется длиной единственного пути из корня в вершину v. Если рассматривается корневое ориентированное дерево

---

Смотрите также файлы

• Оушыны аты жні сыныбы Компьютер жне аіпсіздік блімі бойынша жиынты баалау.docx

• Ваша задача совместить два слова и придумать, что будетозначать новое слово.pdf

• Руководство по выполнению и защите выпускной квалификационной работы бакалавра для студентов специальности 5311000 Автоматизация и управление технологическими процессами и производствами.doc

• Из истории республики Алтай.docx

• К. У. Джамбурчина Пндік (циклдік) комиссия траасы.docx