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.


 

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

19013. Кинематика и динамика упругого столкновения частиц. Переход в Ц-систему. Импульсные диаграммы. Связь углов рассеяния в Л- и Ц-системах 1.06 MB
  Лекция 11. Кинематика и динамика упругого столкновения частиц. Переход в Цсистему. Импульсные диаграммы. Связь углов рассеяния в Л и Цсистемах Столкновение двух частиц называется упругим если оно не сопровождается изменением их внутреннего состояния в том числе не ...
19014. Дифференциальное сечение рассеяния частиц. Формула Резерфорда 2.55 MB
  Лекция 12. Дифференциальное сечение рассеяния частиц. Формула Резерфорда Для изучения характера взаимодействия частиц друг с другом обычно проводятся эксперименты по рассеянию целого пучка одинаковых частиц которые падают из бесконечности с одинаковой начальной с...
19015. Малые одномерные колебания (свободные и вынужденные). Вынужденные колебания под действием произвольной силы 2.55 MB
  Лекция 13. Малые одномерные колебания свободные и вынужденные. Вынужденные колебания под действием произвольной силы. Вынужденные колебания под действием гармонической силы. Резонанс. Затухающие колебания Распространенным движением в природе являются колебания те
19016. Малые колебания системы со многими степенями свободы. Собственные частоты и нормальные координаты 459.5 KB
  Лекция 14. Малые колебания системы со многими степенями свободы. Собственные частоты и нормальные координаты Рассмотрим случай малых колебаний системы частиц имеющей степеней свободы. Самый общий вид функции Лагранжа такой системы таков: 1 2 Устойч
19017. Уравнения Гамильтона (канонические уравнения). Функция Гамильтона. Скобки Пуассона и их свойства 750 KB
  Лекция 15. Уравнения Гамильтона канонические уравнения. Функция Гамильтона. Скобки Пуассона и их свойства Одна из форм уравнения движения это уравнения Лагранжа когда задается функция Лагранжа как функция независимых обобщенных координат и обобщенных скоростей
19018. Канонические преобразования. Производящие функции. Временная эволюция механической системы как каноническое преобразование 901 KB
  Лекция 15. Канонические преобразования. Производящие функции. Временная эволюция механической системы как каноническое преобразование Выбор обобщенных координат не ограничен никакими условиями ими могут быть любые величин однозначно определяющие положение сис
19019. Место квантовой механики в современной физической науке. Основные экспе-риментальные факты, лежащие в основе квантовой механики 318 KB
  Лекция 1. Место квантовой механики в современной физической науке. Основные экспериментальные факты лежащие в основе квантовой механики В современной науке квантовая механика занимает важнейшее место поскольку формирует основные идеи современного подхода к описа
19020. Принципы построения и постулаты квантовой механики. Операторы физических величин 285 KB
  Лекция 2 Принципы построения и постулаты квантовой механики. Операторы физических величин Как следует из опытов по дифракции микрочастиц в квантовой механике отсутствует понятие траектории т.е. состояние квантовой частицы не описывается заданием координаты и имп
19021. Операторы координаты и импульса: уравнения на собственные значения и собственные функции, разложения, координатное и импульсное представления волновой функции 444.5 KB
  Лекция 3 Операторы координаты и импульса: уравнения на собственные значения и собственные функции разложения координатное и импульсное представления волновой функции Найдем оператор координаты в представлении то есть найдем как действует этот оператор на про