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.


 

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

29982. Восприятие. Общая характеристика 88 KB
  Восприятие – это отражение в сознании человека предметов или явлений при их непосредственном воздействии на органы чувств. Маклаков Восприятие включает в себя ощущение и основывается на нём. Поэтому восприятие очень часто называют перцептивной системой человека. из гештальта пр восприятие мелодии 4.
29983. Основные подходы к изучению восприятия в зарубежной психологии 57 KB
  Основные подходы к изучению восприятия в зарубежной психологии. Помимо ощущений в процессе восприятия задействован предыдущий опыт процессы осмысления того что воспринимается т. Мир восприятия состоит из: 1ощущений которые возникают когда раздражается отдельный рецептор и 2 образов памяти которые представляют собой следы прежних ощущений Если 2 ощущения повторялись совместно много раз и если затем возникает ощущение или образ памяти то сразу же появляется образ памяти другого ощущения. И для того чтобы объяснить все виды...
29984. Внимание. Общая характеристика 61.5 KB
  Виды внимания. Добрынин О теории и воспитании внимания Свойства внимания. Концентрированность внимания – выделение сознанием объекта и направление на него внимания. Объем внимания можно увеличить если осмысленно связать и структурировать материал.
29985. Основные подходы к изучению памяти в зарубежной психологии 67 KB
  Основные подходы к изучению памяти в зарубежной психологии. Ассоциативная теория памяти: Ассоциация осн. Этот метод предоставляет возможности для изучения ассоциативных механизмов памяти. Метод разработан для изучения динамики изменения памяти и особенно забывания во времени.
29986. Основные факты и закономерности памяти 54.5 KB
  Основные факты и закономерности памяти Память запечатление сохранение последующее узнавание и воспроизведение следов прошлого опыта. Классические методы и основные результаты исследования памяти Первые экспериментальные методы изучения мнемических процессов были предложены Эббингаузом 19 век. Этот метод предоставляет возможности для изучения ассоциативных механизмов памяти. Метод разработан для изучения динамики изменения памяти и особенно забывания во времени.
29987. Память и деятельность 43.5 KB
  Подавляющее большинство наших систематических знаний возникает в результате специальной деятельности цель которой запомнить соответствующий материал чтобы сохранить в памяти. Исследование мнемической деятельности – одна из ЦЕНТРАЛЬНЫХ ПРОБЛЕМ В ПСИХОЛОГИИ. Произвольное запоминание – основа мнемической деятельности. Переход от одной сферы деятельности в которую включено намерение к другой – может привести за собой забывание этого намерения.
29988. РЕШЕНИЕ ТРАНСЦЕНДЕНТНЫХ УРАВНЕНИЙ 5.23 MB
  Эти значения x называются корнями уравнения 3. ak например для уравнения вида ax2 bx c = 0 его корни выражаются формулой: . В большинстве же случаев аналитическую запись корней уравнения найти очень сложно или в принципе невозможно такие уравнения называются трансцендентными и поэтому приходится решать уравнение численным способом. Отделение корней На данном этапе определяются те интервалы области изменения переменной x в каждом из которых расположен один и только один корень уравнения 3.
29989. Таинственное похищение Первого звонка. Сценарий праздника 1 сентября 179.11 KB
  Сценарий праздника 1 сентября Действующие лица Первый звонок Витя Петя Четверка Пятерка Двойка Единица Клякса Маша Флеш моб танец Первый ведущий. На сцену выходит Первый звонок. Первый звонок. Здравствуйте ребята вы меня я надеюсь узнали Да я ваш добрый знакомый Первый Школьный Звонок.
29990. СЦЕНАРІЙ СВЯТА ПЕРШОГО ДЗВОНИКА 130.46 KB
  Зріє жито молодеДружно з квітами до школиЗнову молодість іде Ведучий 2:Вересень немов учительДвері школи відчинивШколярів дзвінком врочистимДо навчання запросив Ведучий 1: Здрастуй школо здрастуй ріднаЗдрастуй любий класВ першовересень привітноТи стрічаєш нас Ведучий 2: Пахнуть фарбою класи просторіОй як хочеться вже до книжокМи від степу і синього моряВсі злетілись на перший урок Ведучий 1: Я не знаю хвилини врочистішеЩасливіших не бачив очей.Подивіться як урочистоМалюки зустрічають цей день Ведучий 1: На лінійку запрошуються...