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.


 

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

79402. Проблема задатков, способностей, одаренности в психологии личности 24.98 KB
  В современной психологии Способности система свойств личности формирующаяся на основе задатков и определяющая успешность выполнения определенных видов деятельности а также овладение знаниями и навыками. По критерию происхождения различают природные и социальные способности. Природные способности обусловлены врожденными свойствами психических процессов.
79403. Проблема самосознания в психологии личности. Самосознание и жизненный путь личности в представлении Рубинштейна 38.03 KB
  Самосознание и жизненный путь личности в представлении Рубинштейна Изучение личности не заканчивается изучением ее психических свойств темперамента мотивов способностей характера. Завершающий этап изучение самосознания личности. Самосознание является необходимым условием существования личности.
79404. Я-концепция как результат социального развития личности 26.7 KB
  Концепция идентичности это понимание своего единого неразрывного целостного протяженного одновременно меняющегося и неизменного в течение всей жизни Я. Яконцепция это познанный аспект Я знание человека о себе как осознанное и артикулированное содержание Я на определенном этапе развития. Поскольку Яконцепция включает в себя как модальное реальное так и идеальное Я к которому добавляются социальные Я проявляющиеся в различных актах взаимодействия и отношениях с другими то следует говорить о структуре Яконцепции.
79405. Проблема характера в психологии личности. Черты личности. Черты характера 28.83 KB
  Черты характера К инструментальным проявлениям индивидуальности как субъекта деятельности относятся характер и способности. По Рубинштейну способ поведения является наиболее существенным и показательным выражением характера но характер определяет и сам способ поведения. Основные проблемы психологии характера К настоящему времени понятие характер признано дискуссионным.
79406. Понятие социализации как процесса формирования личности. Этапы, виды и механизмы социализации 28.33 KB
  Этапы виды и механизмы социализации Социальная роль как элемент структуры личности задаётся тем что попадая в определённую систему отношений с другими людьми в том или ином качестве человек сталкивается с определёнными требованиями которые неизбежно и неминуемо предъявляются тому кто попадает на это место с системой ожиданий что в определённой ситуации он будет вести себя соответствующим образом. Ролевая теория личности это подход к изучению личности согласно которому личность описывается посредством усвоенных и принятых ею или...
79407. Проблема индивидуальности в психологии личности. Специфика индивидуального бытия человека 28.25 KB
  Специфика индивидуального бытия человека В психологии существует несколько традиций понимания индивидуальности. Первая традиция связана с пониманием индивидуальности как единичности. Описание индивидуальности с этой точки зрения это определение линии потенциальных патологических изменений личности.
79408. Понятия и психологические образования индивидуальности 29.21 KB
  Психологические образования личности обеспечивающие человеку возможность совершать поступки позволяющие ему осуществить акт свободного самостоятельного и ответственного выбора отстаивать собственную позицию составляют особый уровень и особую структуру субъективности. С этой точки зрения субъектность человека способности и механизмы его душевной жизни входят в психологические образования личности в качестве их особых предпосылок. Характер также неотделим от личности поскольку реализует главные жизненные устремления человека.
79409. Мотивация развития индивидуальности 24.51 KB
  Преобладание формального чисто динамического описания движущих сил развития личности над содержательным их анализом и отсутствие адекватного подхода к изучению их общественно-исторической обусловленности постулирование положения о подчиненности активности субъекта некоторой конечной заранее предустановленной цели а тем самым и понимание человека как преимущественно адаптивного существа. На принципиально иных позициях строится подход к изучению движущих сил развития личности в советской психологии. Методологические...
79410. Жизненный путь личности 24.74 KB
  Сознание активность зрелось личности рассматриваются Рубинштейном как высшие личностные образования которые выполняют функции организации регуляции обеспечения целостности жизненного пути человека как субъекта деятельности. Рубинштейна выступает активность и творчество личности как организатора и преобразователя своей жизни. Ему принадлежит самое крупное лонгитюдное исследование личности и ее жизненного пути на основе которого была определена возрастная периодизация и онтогенез развития личности: детство юность выбор профессии...