67598

Теория графов

Лекция

Математика и математический анализ

Понятия смежности инцидентности степени опр Если x={vw} ребро то v и w концы ребра x. опр Если x=vw дуга орграфа то v начало w конец дуги. опр Если вершина v является концом ребра x неориентированного графа началом или концом дуги x орграфа то v и x называются инцидентными.

Русский

2014-09-12

107.5 KB

2 чел.

Лекция №7

Теория графов

Рассмотрим чертеж вида

Обозначения и определения

V – множество точек – вершины;

X – множество линий – ребра;

Графом называется совокупность множеств вершин и ребер.

v - номер вершины;

{v,w} – обозначение ребра;

{v,v} – петли;

Одинаковые пары - параллельные или кратные ребра;

Кратностью ребер называют количество одинаковых пар.

Пример:             кратность = 3.

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

Псевдограф без петель называется мультиграфом.

Мультиграф в котором ни одна пара не встречается более одного раза называется графом.

Если пары (v,w) являются упорядоченными, граф называется ориентированным (орграфом).

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

В неориентированном графе ребра обозначаются неупорядоченной парой - {v,w}.

В ориентированном графе дуги обозначаются упорядоченной парой - (v,w).

G, G0 - неориентированный граф, D, D0 – ориентированный.

Обозначают v,w  - вершины, x,y,z – дуги и ребра.

Пример

1) V={v1, v2, v3, v4},

X={x1=(v1,v2), x2=(v1,v2), x3=(v2,v2), x4=(v2,v3)}.

           

2) V={v1, v2, v3, v4, v5},

X={x1={v1,v2}, x2={v2,v3}, x3={v2,v4}, x4={v3,v4}}.

Понятия смежности, инцидентности, степени

опр || Если x={v,w} - ребро, то v и w - концы ребра x.

опр || Если x=(v,w) - дуга орграфа, то v - начало, w – конец дуги.

опр || Если вершина v является концом ребра x неориентированного графа (началом или концом дуги x орграфа), то v и x называются инцидентными.

опр || Вершины v, w называются смежными, если {v,w}X.

опр || Степенью вершины v графа G называется число (v) ребер графа G, инцидентных вершине v.

опр || Вершина графа, имеющая степень 0 называется изолированной, а степень 1 – висячей

замеч || В неориентированном псевдографе вклад каждой петли инцидентной вершине v в степень вершины v равен 2.

опр || Полустепенью исхода (захода) вершины v орграфа D называется число +(v) ((v)) дуг орграфа D, исходящих из v (заходящих в v).

Замечание || в случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в +(v), так и в (v).

Обозначение: n(G), n(D) количество вершин графа, m(G) - количество ребер, m(D) - количество дуг.

Утверждение. Для каждого псевдографа G выполняется равенство

.

Для каждого ориентированного псевдографа

Изоморфизм, гомеоморфизм.

опр || Графы G1=(V1,X1), G2=(V2,X2) называются изоморфными, если  биективное (взаимно однозначное) отображение : V1V2, сохраняющее смежность, т.е.

{v,w}X1  {(v), (w)}X2 .

опр || Орграфы D1=(V1,X1) и D2=(V2,X2) называются изоморфными, если  биективное отображение : V1V2, такое, что

(v,w)X1  ((v), (w))X2 .

Замечание || Изоморфные графы и орграфы отличаются лишь обозначением вершин.

Свойства изоморфных графов:

1) Если  изоморфны и : V1V2 биективное отображение, сохраняющее смежность то:

а) vV1 (v)=((v)),

б)  - количество вершин,

- количество дуг.

Аналогично, если  изоморфны и : V1V2 биективное отображение, сохраняющее смежность то выполняется

а) vV1 +(v)=+((v)), (v)=((v))

б)

Замечание ||

Для псевдографов и мультиграфов нужно сохранять кратность ребер или дуг

Примеры

         

Два графа изоморфны

  не изоморфный первым двум, так как нет ребра между крайними вершинами.

Утверждение. Изоморфизм графов (орграфов) является отношением эквивалентности на множестве графов (орграфов).

опр || Операцией подразбиения дуги (u,v) в орграфе D=(V,X) называется операция, которая состоит в удалении из X дуги (u,v), добавлении к V новой вершины w и добавлении к X\{(u,v)}, двух дуг (u,w) и (w,v).

Аналогично для ребер графа.

опр || Орграф D2 называется подразбиением орграфа D1 если D2 получается из D1 путем последовательного применения операции подразбиения дуг.

Пример.

            

опр || Орграфы  (графы ) называются гомеоморфными, если  их подразбиения, которые являются изоморфными.

Определение. Если степени всех вершин графа = k, то граф наз. регулярным степени k.  (см. рис. выше).

Граф, состоящий из 1 вершины, называется тривиальным.

Двудольным называется граф G(V,X), такой, что множество вершин V разбито на 2 подмножества V1 и V2 (V1V2=V, V1V2=), причем каждое ребро инцидентно вершине из V1 и V2.


 

А также другие работы, которые могут Вас заинтересовать

20281. ЗАКЛЮЧИТЕЛЬНЫЙ ЭТАП ВТОРОЙ МИРОВОЙ ВОЙНЫ. РАЗГРОМ ФАШИСТСКОГО БЛОКА (1944—1945 гг.) 33.37 KB
  повлияли на ход войны Освобождение Красной Армией территории СССР и европейских стран и народов в 1944 1945 гг. народы СССР встретили с надеждой на полное изгнание врага с советской земли. Красная Армия полностью освободила территорию СССР и перенесла боевые действия на территорию оккупированных европейских стран где провела ряд успешных наступательных операций 1. В ходе наступления были освобождены Румыния с которой СССР подписал перемирие как с бывшей союзницей Германии и Болгария где произошло антифашистское восстание в...
20282. ОКТЯБРЬСКАЯ РЕВОЛЮЦИЯ И УСТАНОВЛЕНИЕ СОВЕТСКОЙ ВЛАСТИ В РОССИИ 39.52 KB
  Тогда СНК принял решение всячески затягивать переговоры рассчитывая на революцию в Германии. В ходе переговоров немцы предъявили ультиматум требуя передачи Германии территории в 150 тыс. ФЕДЕРАТИВНАЯ РЕСПУБЛИКА ГЕРМАНИИ Раскол Германии. война для Германии закончилась но трагедия германского народа продолжалась.
20283. Сущность и значение новой экономической политики 14.2 KB
  Крутой поворот в экономической политике был сделан на 10 съезде партии состоявшемся в марте 1921 г. съезда большевистской партии политика военного коммунизма заменялась новой экономической политикой нэпом и самой главной мерой которой стала замена продразверстки продналогом.
20284. Образование СССР 16.29 KB
  В ходе гражданской войны возник военнополитический союз советских республик который после войны был дополнен двухсторонними хозяйственными договорами. Однако со временем среди советских республик постепенно начало нарастать стремление к созданию федерации . Сталин предложил план автономизации это значит вхождения самостоятельных республик в состав РСФСР. Ленин который стоял за федеративное строительство это значит вхождение советских республик в Союз на равноправных и добровольных началах.
20285. Основные черты внутренней и внешней политики СССР в 30-е гг.20 в 51.58 KB
  Основные черты внутренней и внешней политики СССР в 30е гг. была принята Конституция СССР которая получила в истории название Конституции победившего социализма. Внешняя политика СССР и мероприятия по укреплению его обороноспособности. Одновременно она стала на путь всевозможных провокаций на границах с СССР и Монгольской Народной Республикой.
20286. ГОДЫ ПЕРЕСТРОЙКИ В СССР 25.09 KB
  ГОДЫ ПЕРЕСТРОЙКИ В СССР Вспомните. Андропов Юрий Владимирович 1914 1984 человек незаурядного ума председатель Комитета государственной безопасности СССР а ранее посол СССР в Венгрии во время Будапештской осени с 1982 г.РАСПАД СССР. Горбачева стала авария на Чернобыльской АЭС 26 апреля 1986 К Руководство КПСС некоторое время скрывало масштабы катастрофы и ее последствия что имело роковое значение для судьбы многих сотен тысяч людей и экологии большой территории СССР.
20287. Сценические эффекты в современном театре 97.5 KB
  ИЗВЕКОВ СВЕТ НА СЦЕНЕ ОЧЕРКИ ПО ИСТОРИИ ОСВЕЩЕНИЯ СЦЕНЫ 1. ИСТОКИ ТЕХНИКИ ОСВЕЩЕНИЯ СОВРЕМЕННОЙ СЦЕНЫ Взаимоотношения между техникой сцены и художественным построением спектакля были подробно рассмотрены в первой части нашей работы Сцена где уже говорилось о том что сценическое освещение являясь одним из технических средств при постановке спектакля одновременно выполняет функцию раскрытия идейного замысла спектакля. Исходным этапом в данном случае должно служить зарождение кулисной сценыкоробки которая во многом продолжает еще...
20288. Художественные искания в западной культуре второй половины XX века 75.5 KB
  Отвергнув возможность преобразования жизни с помощью искусства представители постмодернизма приняли бытие таким какое оно есть сделав искусство предельно открытым наполнили его фрагментами реального жизненного процесса.Хеппенинг Перерастая в искусство постмодернизма искусство действия приобретает более выраженные формы. ПопАрт В 50ые в США возникло новое крупнейшее направление в современном искусстве ПОПАРТ популярное искусство. Бодиарт Бодиарт это искусство тела авангардное направление возникшее в 60х годах.
20289. Жанры средневекового театра 676.5 KB
  Франция Мистерия основной театральный образ Средневековья. Мистерия самая поздняя но и самая полная форма выражения средневековой театральности. Если готический собор застывший образ мироздания то мистерия модель мироздания в действии. Мистерия вбирает в себя все жанры: литургическую драму бытовую драму фарс и соти миракль и моралите.