Теория графов: подграфы и деревья 11 класс Профиль Учитель информатики Тивякова Л.А., к учебнику автора Угриновича Н.Д. - презентация

1 Теория графов: подграфы и деревья 11 класс Профиль Учитель информатики Тивякова Л.А., к учебнику автора Угриновича Н.Д.

2 Подграфы и деревья Подграф графа G - граф, у которого все вершины и ребра принадлежат графу G. Остовной связный подграф – это подграф графа G, который содержит все его вершины и каждая его сторона достижима из любой другой.

3 Подграфы и деревья Дерево - это граф, в котором нет циклов (нельзя из некоторой вершины пройти по нескольким различным ребрам и вернуться в ту же вершину. Остовное связное дерево – это подграф, включающий все вершины исходного графа G, каждая вершина которого достижима из любой другой, и при этом не содержащий циклов.

4 Преобразование графа в остовное связное дерево минимального веса Дан граф G – связный, взвешенный неориентированный граф (R nm =R mn ). Тогда получаем матрицу из весов 10 ребер

5 Введем цикломатическое число γ - показывает, сколько ребер графа надо удалить, чтобы в нем не было циклов: γ = R-V+1 Для нашего случая получаем цикломатическое число γ = = 4 Задание: постройте остовные связные деревья графа G и просчитайте вес каждого графа Например, получили следующие деревья с весом 135, 130, 100, 135 соответственно.