конечные графы. Вершинами графа, элементы множества e называются ребрами графа а пара (V, e ), т е. множество вершин и ребер графа называется графом. Если две вершины графа соединены ребром, то такие вершины называются смежными
 Скачать 350.58 Kb.
|
|
Теорема . Пусть G –(ориентированный ) граф с вершинами  …, и матрицей смежности А . Путь длины kили k-путь из  в  для 1 существует тогда и только тогда , когда  =1.Теорема . Пусть G –(ориентированный ) граф с вершинами …, и матрицей смежности А . Из вершины в вершину имеется mпутей длины k , где 1 тогда и только тогда , когда  =m , где  =A обычное умножение матриц . = Теорема . Пусть G –(ориентированный ) граф с вершинами …, и матрицей смежности А . Пусть  =AV V V… V . Тогда  =1 тогда и только тогда , когда существует путь из в .Теорема . Пусть G –(ориентированный ) граф с вершинами …, и матрицей смежности А. Пусть  =IVAV V V… V где I единичная матрица . Тогда  =1 для всех Iи jтогда и только тогда , когда граф G(сильно ) связный .Найдите матрицы а) инцидентности , б) матрицы смежности следующих графов :   •       •      •            • 3. •  •         •  •  •   • • 4           . • • • 5. • •    • • • • • 6         •  • 7. •        • • •  •   • 8.Для заданной матрицы инцидентности найдите соответствующий граф .  9.Для заданной матрицы смежности найдите соответствующий граф . 1)  2) 10.Для заданных графов а) найдите матрицы смежности .б) Используя матрицу смежности , найдите все пути длины 2 .в) Используя матрицу смежности , найдите все пути длины 3 .       • • 2) d• •f   b• •e • • • a• •c 3     )e• 4) • c      • •d • •   •b •  •a •  • 11. Используя тот факт , что =AV V V… V , определите транзитивное замыкание отношения , представленного графом1   ) • • 2) •e      c• •d•b • • • •a    •b 4) •       a• •c  •  •d • • |