Презентация по дискретной математике Элементы теории графов

Элементы теории графов ВВЕДЕНИЕ Теория графов – часть дискретной математики, геометрический подход к изучению объектов и связей Истоки: задача о Кенигсбергских мостах, о расстановке ферзей, о перевозке грузов и др. Однажды великому математику Леонарду Эйлеру был задан вопрос: можно ли обойти все семь мостов, стоявших тогда в городе Кёнигсберге (современный Калининград, Россия), побывав на каждом по одному разу? Перед вами план Кёнигсберга – можете попробовать! На карте старого Кёнигсберга был ещё один мост, появившийся чуть позже, и соединявший остров Ломзе с южной стороной. Своему появлению этот мост обязан самой задаче Эйлера-Канта. А произошло это вот как. Кайзер (император) Вильгельм славился своей прямотой, простотой мышления и солдатской «недалёкостью». Однажды, находясь на светском рауте, он чуть не стал жертвой шутки, которую с ним решили сыграть учёные умы, присутствующие на приёме. Они показали кайзеру карту Кёнигсберга, и попросили попробовать решить эту знаменитую задачу, которая по определению была нерешаемой. Ко всеобщему удивлению, кайзер попросил перо и лист бумаги, сказав, что решит задачу за полторы минуты. Ошеломлённый немецкий истеблишмент не мог поверить своим ушам, но бумагу и чернила быстро нашли. Кайзер положил листок на стол, взял перо, и написал: «приказываю построить восьмой мост на острове Ломзе». Так в Кёнигсберге и появился новый мост, который так и назвали — мост кайзера. Применение Анализ и проектирование сетей электроснабжения, водоснабжения, газоснабжения, телефонизации. Анализ и проектирование транспортных сетей, грузовых и пассажирских перевозок.Проектирование и возведение строительных объектов.Разработка новых технологий и изделийРазработка и эксплуатация компьютерных сетей. Маршрутизация данных в Интернете и т.д. Опр. Граф это множество вершин V={v1,v2,…vn} и множество неупорядоченных и упорядоченных пар вершин E={e1,e2,…em}. Граф обозначается так: G={V, E}.Неупорядоченная пара вершин называется ребром, а упорядоченная дугой.Граф содержащий только ребра называется неориентированным.Граф содержащий только дуги называется ориентированным или орграфом. Опр. Граф это множество вершин V={v1,v2,…vn} и множество неупорядоченных и упорядоченных пар вершин E={e1,e2,…em}. Граф обозначается так: G={V, E}.Неупорядоченная пара вершин называется ребром, а упорядоченная дугой.Граф содержащий только ребра называется неориентированным.Граф содержащий только дуги называется ориентированным или орграфом. Смешанный графСмешанный графНеориентированный графОриентированный графребродугавершинаМультиграфПсевдографКратные ребра и дугипетля Смежные вершиныСмежные ребра (дуги)v1v2v3v4e1e6e5e4e3e2Ребро e5 инцидентное вершинам v4 и v3. Вершина v1 инцидентна ребру e6.Ребро (u, v) соединяет вершины u и v. Дуга <u, v> начинается в вершине u и заканчивается в вершине vВершины v2 v3 и v4 соседи вершины v1 Опр. Степенью vi вершины графа G, обозначаемой di, называется число ее соседей, или число ребер смежных vi, или число инцидентных ей ребер.Для орграфа используется выражение «полустепень захода» и «полустепень исхода»Опр. Полустепенью захода vi вершины графа G, называется число заходящих в неё дуг. Полустепенью исхода vi вершины графа G, называется число исходящих из неё дуг.v3v6v1v2v4v5Для вершины v3 1 полустепень захода и 4 полустепени исхода Сумма полустепеней исходов (заходов) в орграфе G равно числу его ребер |Е|.Сумма степеней вершин неориентированного графа равна 2|Е|, где |Е| число ребер.Вершина vi графа G называется изолированной, если ее степень di=0. Если степень di=1, то вершина называется концевой.V2 (концевая)V1 (изолированная)v3v4v5 Опр. Граф G называется полным, если он не содержит петель и каждые две различные его вершины соединены ребром.Опр. Дополнением графа G называется граф с теми же вершинами что и граф G, и с теми ребрами, которые необходимо добавить к графу G, чтобы получить полный граф.Полный графНеполный граф GДополнение графа Gv1v2v3v4v1v2v3v4v1v2v3v4 Граф G={V,E} называется двудольным, если множество его вершин V можно разбить на два непересекающихся подмножества Vα Vβ, что каждое ребро (дуга) графа имеет один конец в Vα, а другой в Vβ .Vα ={a,b,c,d}, Vα ={e,f,g,h}, Vβ ={m,n,p,q,s} Vβ ={x,r,t} abcdefghmnpqsxrt Паросочетанием графа G={V,E} называется подмножество его ребер (дуг) E´ E, выбранное так, что никакие два ребра (дуги) из E´не являются смежными, т.е. не имеют общей вершиныE´={(a,e),(b,g),(c,f),(d,h)} E´={<n,t>,<p,u>,<r,q>}abcdefghmnpqrtu Граф G={V,E} называется взвешенным, если его ребрам (дугам) приписаны веса.Взвешенный граф часто называют сетьюabcde4562,32,583 abgjfedc261,51,21,16,52,52,50,82,03,10,85,521,2a исток сети (начальная вершина графа)J сток сети (конечная вершина графа)Примеры переходов(a,c) (c,d) (d,e)(a,d) (b,f) (f,j)(a,d) (d,c) (c,b) (b,g) (g,j) Маршрутом в неориентированном графе G={V,E} называется такая последовательность ребер e1, e2,. . . en, что каждые два соседних ребра ei-1, ei имеют общую инцидентную им вершину.Записывается последовательностью вершинa,c,f,ja,d,c,b,f,gd,c,f,eЕсли первая и последняя вершина совпадают то маршрут называется циклическим. Маршрут называется цепью, если каждое ребро графа (вершина) встречается в маршруте не более одного раза.Граф не содержащий циклов, называется ациклическим.Для орграфа аналогом маршрута является путь. Гамильтоновым циклом в графе G={V,E} называется цикл, проходящий через каждую вершину графа в точности по одному разу.Граф G={V,E}, содержащий гамильтоновый цикл, называется гамильтоновым графом. Один из гамильтоновых циклов 1,2,3,41234 Вершины ei, ek графа G={V,E} называются связанными, если существует маршрут или цепь с началом ei и концом ek.Граф или орграф G={V,E} называется связным, если все его вершины связан между собой, иначе называется несвязным.fedcbacabdefСвязный графНесвязный граф мост Связный ациклический граф называется деревом. Вершина дерева, степень которой равна 1 называется висячей вершиной.Всякое ребро в дереве является мостом.Все различные деревья с шестью вершинами Дерево, у которого одна вершина выделяется среди других , называется корневым деревом. Выделенная вершина - корень, а висячие вершины листья.Неориентированное корневое деревоОриентированное корневое дерево