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.


 

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

5864. Управление манипуляторами промышленного робота 448.5 KB
  Управление манипуляторами промышленного робота Если динамические уравнения движения манипулятора заданы, целью управления манипулятором является выполнение им движений в соответствии с заданным рабочим критерием. Проблема управления манипулятором в ...
5865. Роль цен, тарифов, льгот, субсидий, компенсаций в регулировании национального рынка 183 KB
  Происходящие изменения в экономике РФ обусловлены переходом на рыночные связи и отношения. Чтобы свести к минимуму предполагаемые потери при переходе к рынку, необходимо познать сущность и закономерности его развития. Все современные эконом...
5866. Технология разработки, перемещения и уплотнения грунта с элементами бетонирования 395.5 KB
  Определение объемов земляных работ по вариантам Для одиночных стаканных фундаментов возможны два вида земляных сооружений: - траншея по ряду фундаментов - котлован 3.1. Траншея по ряду фундаментов Отметка подошвы фундамента: м, где - абсолютная...
5867. История АМО ЗИЛ 42.5 KB
  Завод, основанный в 1916 г. как частное предприятие, через два года был национализирован, а спустя три четверти века, в 1992 г., вновь становится частным предприятием. В 1996 г. завод перешел практически в муниципальную собственность, сохранив форму...
5868. Место и роль монополии на рынке 103 KB
  Введение: формирование монополии Абсолютная (чистая) монополия - редкое для хозяйственной практики явление. Однако довольно часто приходится сталкиваться с монопольным влиянием, более реальными рыночными структурами монополистической конк...
5869. Взгляды Советских вождей на управление 97.5 KB
  За время существования СССР потерпело много реформ и преобразований. При разных правителях ситуация в СССР была совершенно разная т.к. у каждого из них были разные взгляды на жизнь и на управление страной. Скорее всего каждый из них руково...
5870. Воздействие ценовой дискриминации на экономическое благосостояние 237 KB
  Термин дискриминация образован от латинского discriminatio, что означает различие, различение. Под ценовой дискриминацией понимают практику установления разных цен на один и тот же товар при условии, что различия в ценах не связаны с затра...
5871. Организация защиты личного состава формирований ГО и РСЧС при проведении АСДНР 121 KB
  Организация защиты личного состава формирований ГО и РСЧС при проведении АСДНР Учебные цели: 1. Изучить основные мероприятия, осуществляемые руководителями (командирами) формированиям ГО и РСЧС по организации обеспечения защиты личного состава...
5872. Формальные методы спецификации программ 431.5 KB
  В предлагаемом учебном пособии рассматриваются два основных метода формального описания программных систем: метод алгебраических спецификаций и метод типизированных машин абстрактных состояний. Первый метод предназначен для описания статических аспе...