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.


 

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

18242. Изучение ассортимента и оценка качества безалкогольных газированных напитков, поступающих на реализацию в магазин «Дикси» 723.5 KB
  Провести анализ рынка безалкогольных газированных напитков России и Челябинска; дать подробную товароведную характеристику безалкогольных газированных напитков; дать характеристику организационно-хозяйственной деятельности магазину «Дикси» и его материально-технической базе; рассмотреть условия и сроки хранения безалкогольных газированных напитков в магазине...
18243. Технологическое производство консервы «Сайра натуральная» 635.5 KB
  Под технологическими процессами подразумевают искусственное воздействие на объект переработки с целью изменения или сохранения на длительное время структурно-механических, физико-химических, биологических, микробиологических или иных его свойств, формы, размеров, состояния и пр.
18244. Вивчення законів постійного струму на прикладі містка Уітстона і компенсаційної схеми 361 KB
  Лабораторна робота №4 Вивчення законів постійного струму на прикладі містка Уітстона і компенсаційної схеми Мета роботи: 1.Вивчити метод вимірювання опору за допомогою мостової схеми а також компенсаційний метод вимірювання електрорушійної сили далі ЕРС. ...
18245. ДОСЛІДЖЕННЯ ЗАЛЕЖНОСТІ РЕЛАКСАЦІЙНИХ КОЛИВАНЬ У НЕОНОВІЙ ЛАМПІ ВІД ОПОРУ ЕЛЕКТРИЧНОГО КОЛА 64.5 KB
  PAGE 3 ЛАБОРАТОРНА РОБОТА № 2 ДОСЛІДЖЕННЯ ЗАЛЕЖНОСТІ РЕЛАКСАЦІЙНИХ КОЛИВАНЬ У НЕОНОВІЙ ЛАМПІ ВІД ОПОРУ ЕЛЕКТРИЧНОГО КОЛА Мета роботи: а виміряти великий опір за допомогою електричного розряду у неоновій лампі; б дослідити залежність періоду рела
18246. ЭЛЕКТРИЧЕСКИЕ МАШИНЫ ПОСТОЯННОГО ТОКА 467 KB
  ЭЛЕКТРИЧЕСКИЕ МАШИНЫ ПОСТОЯННОГО ТОКА УСТРОЙСТВО ЭЛЕКТРИЧЕСКИХ МАШИН ПОСТОЯННОГО ТОКА. ОБРАТИМОСТЬ МАШИН. По назначению электрические машины постоянного тока делятся на генераторы и двигатели. Генераторы вырабатывают электрическую энергию поступающую в энергос...
18247. ОПРЕДЕЛЕНИЕ, ПОЛУЧЕНИЕ И ИЗОБРАЖЕНИЕ ПЕРЕМЕННОГО ТОКА 303.5 KB
  ОПРЕДЕЛЕНИЕ ПОЛУЧЕНИЕ И ИЗОБРАЖЕНИЕ ПЕРЕМЕННОГО ТОКА Переменным называют ток изменение которого по значению и направлению повторяется периодически через равные промежутки времени. Широкое применение переменного тока в различных областях техники объясняется ...
18248. ПОЛУПРОВОДНИКОВЫЕ ПРИБОРЫ ЭЛЕКТРОПРОВОДНОСТЬ ПОЛУПРОВОДНИКОВ. БЕСПРИМЕСНЫЕ И ПРИМЕСНЫЕ ПОЛУПРОВОДНИКИ 763.5 KB
  ПОЛУПРОВОДНИКОВЫЕ ПРИБОРЫ ЭЛЕКТРОПРОВОДНОСТЬ ПОЛУПРОВОДНИКОВ. БЕСПРИМЕСНЫЕ И ПРИМЕСНЫЕ ПОЛУПРОВОДНИКИ Полупроводники занимают по электропроводности промежуточное положение между металлами проводниками электрического тока и диэлектриками. Особенность электро
18249. РАСЧЕТ ЦЕПЕЙ 1.3 MB
  РАСЧЕТ ЦЕПЕЙ ВВЕДЕНИЕ Электротехника область науки и техники которая занимается изучением электрических и магнитных явлений и их использованием в практических целях. Научнотехнический прогресс невозможен без электрификации всех отраслей народного хозяйств...
18250. Словарь электротехника 102.5 KB
  Понятийнотерминологический словарь Абсолютная магнитная проницаемость среды величина являющаяся коэффициентом отражающим магнитные свойства среды. Автотрансформатором называют трансформатор у которого часть витков первичной обмотки используется в кач