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.


 

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

38874. МЕТОДИЧНІ ВКАЗІВКИ ЩОДО ВИКОНАННЯ дипломної роботи 200.5 KB
  Мета роботи – презентація студентом вміння виконувати наукове дослідження з теорії та вміння використовувати теоретичні знання для вирішення конкретних практичних завдань, а також виявлення ступеня підготовки випускника до самостійної практичної діяльності.
38875. Производство леворина. Ферментация с получением мицелиальной массы 295 KB
  Массовая доля основного вещества не менее 985; 2.Массовая доля влаги не более 05; 3.Массовая доля веществ нерастворимых в соляной кислоте не более 01 В состав питательной среды на ферментации 4.Массовая доля влаги не более 9; 5.
38876. Определение степени художественной адекватности и принципов художественного перевода произведений А.П. Чехова на белорусский язык 334 KB
  Толстой и другие плодотворно работали не только в сфере изящной словесности но и в области художественного перевода. Интерес к подобного рода переводам проявился в науке уже давно. В книге Искусство перевода классик украинской поэзии Максим Рыльский делится опытом перевода поэзии Пушкина Лермонтова Мицкевича размышляет о значении культурного взаимообмена между родственными народами о переводе как сотворчестве.
38877. Природа света и цвета 5.75 MB
  Согласно научному определению, «свет – это электромагнитное излучение» или энергия, которая распространяется в пространстве с одинаковой скоростью под действием природного или искусственного источника света (солнца, лампы накаливания и др.). Эта энергия рассматривается в физике как электромагнитные волны, которые отличаются по своей длине.
38878. ОСНОВНЫЕ НАПРАВЛЕНИЯ СОВЕРШЕНСТВОВАНИЯ ФОРМИРОВАНИЯ И ИСПОЛЬЗОВАНИЯ ТРУДОВЫХ РЕСУРСОВ В МУСХП «ЛУЧ» САФОНОВСКОГО РАЙОНА СМОЛЕНСКОЙ ОБЛАСТИ 1.35 MB
  Вопросы подлежащие разработке исследованию: рассмотреть теоретические основы формирования и использования трудовых ресурсов; дать характеристику организационнохозяйственной деятельности объекта исследования; проанализировать обеспеченность предприятия трудовыми ресурсами экономические и финансовые результаты деятельности предприятия; рассмотреть производительность труда работников предприятия и выявить пути её увеличения; разработать и обосновать резервы повышения эффективности использования трудовых ресурсов.2 Анализ производительности...
38880. Особенности экономического анализа бухгалтерской (финансовой) отчетности в государственных(муниципальных) учреждениях 868 KB
  Методы анализа бухгалтерской финансовой отчетности Анализ бухгалтерской отчетности предполагает установление и изучение взаимосвязей и взаимозависимостей между различными показателями финансовохозяйственной деятельности учреждения включенными в отчетность. Стандартные приемы методы анализа финансовой отчетности: анализ абсолютных показателей путем сравнения показателей учреждения с показателями конкурентов: горизонтальный сравнение интересующих позиций отчетности с данными предыдущих периодов; вертикальный ...
38882. Методические указания к разработке экономической части дипломного проектирования с элементами УИРС 229 KB
  Балансовая стоимость оптовая цена единицы техники руб. Кi=Цi IКтрКмКс руб. 4 где Кi капитальные вложения по базовому и проектируемому вариантам руб.: Цi цена оборудования по вариантам руб.