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.


 

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

64204. The Concept «GENTLEMAN» in the Novel of Charles Dickens «Great Expectations» 377.22 KB
  The aim of the diploma work is to establish Dickens’ understanding of the notion of GENTLEMAN within, by the discourse analysis, point out especial meaning and interpretation of the concept in the novel “Great Expectation”.
64205. Приостановление, прекращение и восстановление выплаты пенсии по действующему российскому законодательству 711.35 KB
  Однако по численности контингента и удельному весу расходуемых средств пенсии имеют преобладающее значение в общей системе материального обеспечения престарелых и нетрудоспособных граждан. За счет пенсии в денежной форме удовлетворяются самые разнообразные потребности человека в пище...
64206. Концентрация вредных веществ, мгновенно-опасная для жизни или здоровья 97 KB
  История вопроса Обсуждение того как использовать респираторы когда загрязнённость воздуха мгновенно-опасна для жизни или здоровья началось по крайней мере с начала 1940х. Неопасные случа это те когда загрязнённость воздуха не представляет мгновенной опасности для жизни или здоровья но создаёт сильный...
64207. СРЕДСТВА ИНДИВИДУАЛЬНОЙ ЗАЩИТЫ ОТ ВРЕДНЫХ ПРОИЗВОДСТВЕННЫХ ФАКТОРОВ 126 KB
  Типовой перечень ежегодно реализуемых работодателем мероприятий по улучшению условий и охраны труда и снижению уровней профессиональных рисков где значительное внимание уделено использованию СИЗ. Электронный каталог сертифицированных средств индивидуальной защиты...
64209. ПРОФЕССИОНАЛЬНАЯ ПОТЕРЯ СЛУХА – ПРОБЛЕМА ЗДОРОВЬЯ И БЕЗОПАСНОСТИ 97.5 KB
  Методы определения потерь слуха человека действовал 1980 по 1985 г. В итоге ранее абсолютным противопоказанием к продолжению работы в условиях шума являлось повышение порогов слуха на речевых частотах свыше 30 дБ а согласно данному документу...
64210. Развитие психической деятельности животных в онтогенезе 34 KB
  Для изучения этих процессов в зоопсихологии применяют биогенетический метод базирующийся на эволюционной теории развития видов. Изучение развития психики в онтогенезе предполагает рассмотрение следующих основных аспектов: Иными словами необходимо выяснить что получает особь в наследство от предыдущих поколений...
64211. Развитие психической деятельности в пренатальном периоде 30.5 KB
  Общим правилом эмбриогенеза является асинхронность развития органов систем и нервных центров которые регулируют их функции. Важно отметить что органы находящиеся на разных этапах развития всегда функционируют согласовано обеспечивая работоспособность всей системы организма.
64212. Сравнительный обзор развития двигательной активности зародышей 42 KB
  У морских козочек отряд бокоплавы до вылупления наблюдаются спонтанные и ритмичные движения головы и других частей эмбриона из которых впоследствии формируются специфические двигательные реакции этих рачков а к концу эмбриогенеза в день вылупления появляются двигательные ответы на тактильные раздражения.