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.


 

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

49135. Использование нейронных сетей для определения темперамента человека 564.5 KB
  При обучении на вход нейросети один за другим подаются исходные данные и сеть генерирует свои ответы. Цель: показать можно ли использовать нейронные сети и эффективно ли применение нейронных сетей при определении человеческого темперамента. Искусственный интеллект и нейросетевые технологии Нейронные сети и нейрокомпьютеры – это одно из направлений компьютерной индустрии в основе которого лежит идея создания искусственных интеллектуальных устройств по образу и подобию человеческого мозга. Искусственные нейронные сети подобно...
49136. Здійснення економічної діагностики підприємства 160.63 KB
  Ключовими елементами системи діагностики діяльності підприємства є: власники, керівники, тематичні фахівці підприємства, інвестори, кредитори підприємства, споживачі, постачальники, контрагенти, державні органи влади тощо. окремі сфери, напрями діяльності, підрозділи, працівники, елементи внутрішнього та зовнішнього середовищ, підприємство в цілому.
49137. Совершенстование маркетинговый деятельности гостиницы «Корстон» 230.51 KB
  Отечественные специалисты в большинстве своем пока не владеют специальной методикой проведения исследований, отвечающих международным стандартам и отечественным особенностям работ подобного рода. «Низкое качество исполнения маркетинговых исследований и расчетов, не учитывающих гостиничную специфику (чаще всего за основу берется типовая методика для промышленного предприятия)
49138. МИКРОПРОЦЕССОРНАЯ СИСТЕМА УПРАВЛЕНИЯ 755.5 KB
  Конечный датчик служит для сигнализации системе о том, что она максимально переместилась от нулевого положения или находится в нулевом положении. В качестве конечного датчика можно выбрать реле (такие как поляризованные, герметизированные и их виды: шариковые, плунжерные и т.д.) В данной системе требуется один конечный датчик (датчик нулевой позиции)
49139. Трехзвенный Г-образный фильтр верхних частот 667 KB
  Переходная харатеристика Техническое задание Электрическая принципиальная схема Задание: Расчет АЧХ ФЧХ и переходной характеристики трехзвенного Гобразного фильтра. Расчет Рис.
49140. Полосовой фильтр 24.46 MB
  Получить Амплетудно–Частотную, Фаза –Частотную характеристики, переходную характеристику и построить их графики Задание Расчет стационарных характеристик цепи Таблицы и графики АЧХ и ФЧХ...
49141. ИСПОЛЬЗОВАНИЕ АКУСТООПТИЧЕСКОГО ЭФФЕКТА ДЛЯ ИЗМЕРЕНИЯ ФИЗИЧЕСКИХ ВЕЛИЧИН 2.4 MB
  Широкий спектр применения акустооптических приборов возможен благодаря многогранности акустооптического эффекта с помощью которого можно эффективно манипулировать всеми параметрами оптической волны. Усиление слабых акустических волн а также их генерация под действием мощной оптической волны фото-акустические или опто-акустические явления. Под воздействием мощной волны ультразвука в жидкости может наблюдаться в свою очередь генерация оптической волны так называемая соно-люминесценция. Для плоской монохроматической акустической волны...
49143. Инфракрасная спектроскопия и метрологическое обеспечение 1.17 MB
  Содержание пояснительной записки курсовой работы проекта: Инфракрасная спектроскопия Икспектры поглощения органических соединений Инфракрасное излучение и колебания молекул Гармонические и ангармонические колебания Колебания многоатомных молекул Оборудование для инфракрасной спектроскопии Основные области инфракрасного спектра Инфракрасный спектр Характеристические частоты групп 4. Нефедов...