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.


 

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

85484. Модель современного школьного издания 495 KB
  Среди наиболее часто называемых проблем современной молодёжи, решению которых также могут способствовать школьные СМИ, нередко упоминается её низкий интерес к чтению и к осмысленной работе с информацией вообще.
85485. Совершенствование методического обеспечения принятия решений о привлечении и погашении заимствований в системе управления государственным (региональным) долгом субъекта РФ на этапе её реформирования 760 KB
  Критерий привлечения заемных средств для финансирования капитальных расходов бюджета субъекта РФ. Критерий принятия решений о досрочном погашении долговых обязательств субъекта РФ в условиях избытка платежеспособности бюджета. Методика расчета относительной стоимости капитальных расходов бюджета.
85487. Улучшение качества предлагаемых услуг и повышения эффективности использования капитала на ОАО «Приморье-64» 878.5 KB
  Главным определяющим признаком основных фондов выступает способ перенесения стоимости на продукт постепенно: в течение ряда производственных циклов частями: по мере износа. Износ основных фондов учитывается по установленным нормам амортизации сумма которой включается в себестоимость продукции.
85488. Внедрение CRM-системы для автоматизации отдела продаж на примере компании ООО «Актив Групп» 1.63 MB
  И сегодня большинство руководителей компаний начали понимать, что одна оптимизация производства уже не решает проблему выживания. Особенно это заметно в сфере услуг, где компании зависят не столько от качества самих продуктов или услуг, сколько от совершенства механизмов взаимодействия компании со своими клиентами.
85489. Разработка АРМ работника отдела сбыта на примере ЗАО «Луганский трубный завод» 985.5 KB
  Программа осуществляет обработку заказов для каждого из грузополучателей и выдачу результатов по остаткам спецификаций на печать. Программа работают совместно с ПО, осуществляющим выдачу результатов запросов на экран монитора и принтер.
85490. Анализ системы документооборота в ОАО «Сбербанк России» 1.94 MB
  В рамках автоматизации процесса обработки документа в организации начиная с момента его создания или получения и заканчивая моментом отправки корреспонденту или завершения исполнения и списания в дело должно быть обеспечено осуществление следующих функций: во-первых регистрация входящих в организацию документов...
85491. Розробка технологічного процесу механічної обробки деталей насоса – корпуса та вала 2.67 MB
  Деталь конструктивно подана як циліндричний вал з наявністю торцевих проточок шпонкового пазу евольвентних шліців а також внутрішньої різьбової поверхні. Відхилення від торцевого биття поверхні 2 відносно центральної осі становить не більше 003 мм.
85492. Информационные технологии в управлении персоналом на ОАО «Завод «НЕФТЕПРОММАШ» 2.61 MB
  В первой главе освещены теоретические основы управления персоналом организации. Представлена характеристика организации, определенны миссия и задачи организации. Показана организационная структура. Определены сущность и характеристики управления персоналом, рассмотрены требования...