Всё для Учёбы — студенческий файлообменник
1 монета
ppt

Студенческий документ № 000119 из ДГТУ (бывш. РИСХМ)

Матрицы графов и их свойства.

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

? Суммы элементов матрицы А по строкам равны степеням вершин графа G (?(1)=3, ?(2)=2, ?(3)=4, ?(4)=2, ?(5)=3.

Матрица смежности орграфа определяется аналогично: А=А(Д)=||aij||, где аij = 1, если дуга ?i?j принадлежит Д, и аij = 0 в противном случае. Итак, А(Д) не обязательно симметрична.

Матрицу смежности данного графа можно рассматривать как матрицу смежности симметрического орграфа.

Линейным подграфом орграфа Д называется подграф, в котором у каждой вершины полустепень исхода и полустепень захода равны 1. Таким образом, такой подграф содержит непересекающийся набор простых контуров.

Остовной подграф - подграф графа G, содержащий все его вершины.

Матрица инциденций.

Матрица инциденций определяет граф с точностью до изоморфизма.

Объединение G1 G2 - граф с множеством вершин V=V1 V2, а множество ребер Х=Х1 Х2.

Задача:

Найти число частей графа с m ребрами.

Найти число частей графа с данным числом ребер р.

Задача: Даны графы:

Показать полностью… https://vk.com/doc-128337234_438473741
734 Кб, 25 октября 2016 в 18:59 - Россия, Ростов-на-Дону, ДГТУ (бывш. РИСХМ), 2016 г., ppt
Рекомендуемые документы в приложении