Каква е разликата между гора и простираща се гора в теорията на графиките?


Отговор 1:

„Гора“ е всяка колекция от дървета.

„Продължаваща гора“ е колекция от дървета, която включва („педя“ или „покритие“) всеки върх в графиката. Съществуват две конкурентни интерпретации:

  • „Пълна обхващаща гора“ или „максимална обхващаща гора“: всеки свързан компонент на графиката е покрит от обхващащо дърво. Тоест, има толкова много дървета, има свързани компоненти и не повече. Или всяка колекция от дървета, която покрива върховете, дори ако по-малка колекция от дървета би го направила. Може да има повече дървета, отколкото има свързани компоненти.

Например, помислете за тази графика:

Ето гората на графиката (зелени възли и ръбове), състояща се от две дървета, но пропускащи някои от върховете.

Ето една обхващаща се гора (всички върхове), която има едно дърво на свързан компонент, „пълна обхващаща гора“.

Ето една различна простираща се гора, която използва три дървета вместо да покрие всички върхове: