конечные графы. Вершинами графа, элементы множества e называются ребрами графа а пара (V, e ), т е. множество вершин и ребер графа называется графом. Если две вершины графа соединены ребром, то такие вершины называются смежными

• Название: Вершинами графа, элементы множества e называются ребрами графа а пара (V, e ), т е. множество вершин и ребер графа называется графом. Если две вершины графа соединены ребром, то такие вершины называются смежными
• Анкор: конечные графы
• Дата: 21.05.2023
• Размер: 350.58 Kb.
• Имя файла: teoria_konechnykh_grafov.docx
• Тип: Документы; #1148256
• страница: 3 из 4

Теорема . Ориентированный граф имеет эйлеров цикл тогда и только тогда , когда он связный и степень входа каждой вершины равна ее степени выхода .

.bGимеет эйлеров цикл . не имеет эйлерова цикла .

a . . c . .

. d .

1. 
   Среди приведенных ниже графов найдите те ,которые имеют эйлеров цикл .
   

1. 
   . b 2) c
   

a . . c . d . e b d

f g h a f e

I j g j

I

3 )a 4) a

F b d e

e j g b c

I h

d c

5 ) b 6) a

a c b c d e

d f f g

e h i j k

u

7 ) b c 8) b

a d e a c

f gd

ef

2.Среди приведенных ниже графов найдите те , которые имеют собственный эйлеров цикл .

1 ) •с 2) •c

а• •в •d •fa• •b •d •e

•e•f

3. 
   • k 4) •a
   

g• •h •I •j b• •d •e

•f •d •c

•b

•a •c

5 ) •g 6) •c

d• •e •j a• •b •d

a• •b •c e• •f

3.Какие из следующих ориентированных графов имеют эйлеровы циклы

1 ) a• •b 2) a• •b 3) •b

•c a• •c

c• •s d• •e •d

•d •e

3. 
   •b 5) a• •b
   

•h

a• •g •I •cc• •d

•f •j e• •f

e• •d g• •h

6. Докажите , что если граф содержит цикл от вершины vк ней самой , то он содержит простой цикл от вершины vк ней самой .

7 . Докажите , что ориентированный граф является сильно связным , если в графе существует вершина v такая, что каждая другая вершина графа достижима из v и вершина v достижима из любой вершины графа.

8 . Ориентированный граф имеет эйлеров цикл тогда и только тогда , когда он сильно связный и степень входа каждой вершины равна ее степени выхода .

Матрицы инцидентности и смежности .

Определение .Пусть G –граф .B –матрица , строки которой обозначены вершинами графа, а столбцы обозначены ребрами графа . Будем считать , что вершины и ребра графа пронумерованы . B=( )

=

B

называется матрицей инцидентности .

•a



b • •c •d





Определение .Пусть G –ориентированный граф .B –матрица , строки которой обозначенывершинами графа и столбцы обозначены теми же вершинами в том же самом порядке . B=( )

=

B называется матрицей смежности графа G .

•b

a• •d

•c

a b c d



Важным применением матрицы смежности является возможность находить пути фиксированной длины k .

Определение . Для положительных целых чисел mи nматрицей m или

массивом m называется функция А={1,2,…,m} .

Определение .Булевой матрицей называется матрица , каждый элемент которой есть 0 или 1 .

Определение булевых операций V и Ʌ на множестве {0,1}.

V	0	1		Ʌ	0	1
0	0	1		0	0	0
1	1	1		1	0	1

Пусть Aи Bбулевы матрицы размера m , а С -булева матрица размера n .

Тогда 1) U=AVBопределяется соотношением = V , 1

2)I=AɅBопределяется соотношением = , 1

2. 
   D=AʘCопределяется соотношением = Ʌ V Ʌ V…
   

V Ʌ , 1

A= – матрица смежности ориентированного графа .

= ʘ =