'

Теория графов: подграфы и деревья

Понравилась презентация – покажи это...





Слайд 0

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


Слайд 1

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


Слайд 2

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


Слайд 3

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


Слайд 4

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


×

HTML:





Ссылка: