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.


 

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

1384. Лексико-семантичні одиниці на позначення ставлення людини до праці 175 KB
  Особливості лексико-семантичних одиниць на позначення якостей людини (ставлення до праці) (на матеріалі художньої літератури). Висвітлити теоретичні передумови та методологічні основи особливостей лексико-семантичних одиниць.
1385. Структуры и алгоритмы обработки данных 234.5 KB
  Формирование практических навыков организации и использования при решении задач динамических структур данных. Изучение наиболее распространенных алгоритмов решения задач с использованием сложных структур данных.
1386. Гидронасосные станции 143 KB
  Сигналы при взрывных работах. Требования, предъявляемые к монтажной камеры. Виды крепей по способу взаимодействия с кровлей. Меры безопасности при монтаже очистного комбайна. Гидросхема насосной станции СНП55-250-2.
1387. Характеристика СТО ООО Полиавтосервис 132.5 KB
  СТО ООО Полиавтосервис обслуживает легковые автомобили семейства ВАЗ. Краткие технические характеристики основных марок обслуживаемых автомобилей. Назначение объекта реконструкции зоны ТО и ТР.
1388. Учебник по дэйтрейдингу 1.62 MB
  Биржевая торговля — профессия, не похожая на другие, — требует уникального набора навыков и полнейшей самодисциплины. Независимо от того, каким личным или профессиональным опытом вы обладаете, когда вы впервые приступаете к торговле, вам приходится начинать с самого первого шага.
1389. Основы гидравлики 1.82 MB
  Общие сведения о жидкости. Жидкость как физическое тело. Растворимость газов в капельных жидкостях. Неньютоновские жидкости. Сила давления на криволинейную поверхность, погружённую в жидкость. Истечение жидкости из отверстий и насадков.
1390. Лингвистические аспекты теории перевода 1.89 MB
  Р. Якобсон О лингвистических аспектах перевода. М. А.К.Хэллидей Сопоставление языков. Основы теории закономерных соответствий. Грамматические трансформации и перевод некоторых синтаксических конструкций. К вопросу о типах межъязыковых лексических соответствий. П. Рикер Парадигма перевода.
1391. Стратегический менеджмент: целевое управление персоналом организаций 1.92 MB
  Механизм управления персоналом организаций в сфере материального производства на основе применения сверхдемократичной и одновременно сверхжесткой квалиметрической оценки персонала предприятия.
1392. Лекции по общей патологической анатомии 2.08 MB
  ВВЕДЕНИЕ В КУРС ПАТОЛОГИЧЕСКОЙ АНАТОМИИ. ЭТАПЫ РАЗВИТИЯ ПАТОЛОГИЧЕСКОЙ АНАТОМИИ. СОДЕРЖАНИЕ, ЗАДАЧИ, ОБЪЕКТЫ И МЕТОДЫ ИССЛЕДОВАНИЯ. ВОСПАЛЕНИЕ: ОПРЕДЕЛЕНИЕ, СУЩНОСТЬ, БИОЛОГИЧЕСКОЕ ЗНАЧЕНИЕ. МЕДИАТОРЫ ВОСПАЛЕНИЯ. МЕСТНОЕ И ОБЩЕЕ ПРОЯВЛЕНИЯ ВОСПАЛЕНИЯ. ОСТРОЕ ВОСПАЛЕНИЕ: ЭТИОЛОГИЯ, ПАТОГЕНЕЗ. МОРФОЛОГИЧЕСКОЕ ПРОЯВЛЕНИЕ ЭКССУДАТИВНОГО ВОСПАЛЕНИЯ. ИСХОДЫ ОСТРОГО ВОСПАЛЕНИЯ.