конечные графы. Вершинами графа, элементы множества e называются ребрами графа а пара (V, e ), т е. множество вершин и ребер графа называется графом. Если две вершины графа соединены ребром, то такие вершины называются смежными
![]()
|
Теорема . Ориентированный граф имеет эйлеров цикл тогда и только тогда , когда он связный и степень входа каждой вершины равна ее степени выхода . ![]() ![]() ![]() ![]() ![]() a ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Среди приведенных ниже графов найдите те ,которые имеют эйлеров цикл . ![]() ![]() ![]() ![]() ![]() ![]() ![]() a ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() f ![]() ![]() ![]() ![]() ![]() I ![]() ![]() ![]() I 3 ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() I h d ![]() 5 ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() u 7 ![]() ![]() ![]() ![]() ![]() ![]() ![]() a ![]() ![]() ![]() ![]() ![]() f ![]() ![]() ef 2.Среди приведенных ниже графов найдите те , которые имеют собственный эйлеров цикл . 1 ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() •e•f • ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() •a •c 5 ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() a• •b •c e• •f 3.Какие из следующих ориентированных графов имеют эйлеровы циклы 1 ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() 6. Докажите , что если граф содержит цикл от вершины vк ней самой , то он содержит простой цикл от вершины vк ней самой . 7 . Докажите , что ориентированный граф является сильно связным , если в графе существует вершина v такая, что каждая другая вершина графа достижима из v и вершина v достижима из любой вершины графа. 8 . Ориентированный граф имеет эйлеров цикл тогда и только тогда , когда он сильно связный и степень входа каждой вершины равна ее степени выхода . Матрицы инцидентности и смежности . Определение .Пусть G –граф .B –матрица , строки которой обозначены вершинами графа, а столбцы обозначены ребрами графа . Будем считать , что вершины и ребра графа пронумерованы . B=( ![]() ![]() ![]() B называется матрицей инцидентности . ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() b ![]() ![]() ![]() ![]() ![]() Определение .Пусть G –ориентированный граф .B –матрица , строки которой обозначенывершинами графа и столбцы обозначены теми же вершинами в том же самом порядке . B=( ![]() ![]() ![]() B называется матрицей смежности графа G . ![]() ![]() ![]() ![]() ![]() •c a b c d ![]() Важным применением матрицы смежности является возможность находить пути фиксированной длины k . Определение . Для положительных целых чисел mи nматрицей m ![]() массивом m ![]() ![]() Определение .Булевой матрицей называется матрица , каждый элемент которой есть 0 или 1 . Определение булевых операций V и Ʌ на множестве {0,1}.
Пусть Aи Bбулевы матрицы размера m ![]() ![]() Тогда 1) U=AVBопределяется соотношением ![]() ![]() ![]() ![]() 2)I=AɅBопределяется соотношением ![]() ![]() ![]() D=AʘCопределяется соотношением ![]() ![]() ![]() ![]() ![]() V ![]() ![]() ![]() A= ![]() ![]() ![]() ![]() ![]() |