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.


 

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

23842. Житие протопопа Аввакума: жанровое своеобразие 21.5 KB
  Не будь Аввакума не было бы таких какими мы знаем Пушкина Толстого Гоголя Достоевского в один ряд с которыми Лихачев ставит Аввакума 1 этап Киевская Русь Феодосий Печерский. 2 этап Епифаний Премудрый плетение словес.3 этап борьба с каноном ЕрмолайЕразм Повесть о Петре и Февронье замена волшебной сказки.4 этап разрушение канона появление романа потом в произведениях многих авторов возникают отголоски жития вплоть до святых атеизма Как закалялась сталь Островского.
23843. Житие протопопа Аввакума: новаторство Аввакума 22.5 KB
  Житие протопопа Аввакума: новаторство АввакумаОн ощущает себя святым страдающим за веру пишет свое житие. Прожив полную лишений жизнь он говорит об этом случае в своем житие так глубоко в душу это ему запало.
23844. Эволюция жанра жития 24.5 KB
  Следующий этап эволюции наступает в тот момент когда на предыдущем этапе уже некуда развиваться достигнуто совершенство.1 этап.2 этап. Плетение словес Епифамия Премудрого совершенствовать уже было не и наступил следующий этап.
23845. Эволюция жанра хождения 23.5 KB
  Эволюция жанра хождения.Хождениями в древнерусской литературе назывались произведения в которых описывались путешествияпаломничества в Палестину Византию страны Востока. Хождения совершались как официальными представителями русской церкви так и по собственной инициативе или обету паломников их называли кАликами перехожими Хождение Игумена Даниила древнейшее произведение жанра хождения.Популярность Хождения игумена Даниила в древнерусской письменности была исключительно велика о чём свидетельствует тот факт что до нас...
23846. Зарождение Силлабической поэзии и русского театра 29 KB
  Зарождение Силлабической поэзии и русского театраЗарождение Силлабической поэзии в России связано с именами Симеона Полоцкого Сильвестра Медведева Кариона Истомина. Происхождение и образование Симеона Полоцкого наглядно показывают откуда и каким образом проникал в Россию стиль барокко. Наследие Симеона Полоцкого очень велико. Курянин по происхождению служивший подьячим в Приказе тайных дел а потом по настоятельному совету Симеона постригшийся в монахи [5] Сильвестр Медведев после смерти учителя унаследовал его место место придворного...
23847. Творчество Симеона Полоцкого 24 KB
  Творчество Симеона ПолоцкогоОн воспитывал государевых детей одного из них будущего царя Федора Алексеевича он научил сочинять силлабические вирши открыл латинскую школу неподалеку от Кремля в Заиконоспасском монастыре где обучались молодые подьячие Приказа тайных дел собственной канцелярии царя Алексея Михайловича. Симеон Полоцкий также занял или точнее учредил еще одну должность должность придворного поэта дотоле в России неизвестную. Любое событие в царской семье браки именины рождения детей давало Симеону Полоцкому повод...
23849. Предмет, об’єкт і задачі економічного аналізу 57 KB
  Поняття економічного аналізу та його роль в управлінні підприємством. Предмет і об’єкти економічного аналізу. Функції та принципи економічного аналізу. Система показників економічного аналізу. Історія розвитку економічного аналізу та його зв’язок з іншими дисциплінами...
23850. Теоретическая модель цифровой сети связи 83 KB
  Суть сети – соединение разного оборудования. Следовательно, одной из основных проблем является проблема совместимости. Поэтому, в настоящее время, все возможные пути развития сетей отражены в стандартах.