Në teorinë e grafikëve, një pemë është një graf i padrejtuar në të cilin çdo dy kulme janë të lidhura saktësisht nga një shteg, ose në mënyrë ekuivalente një graf i lidhur aciklik i padrejtuar. … Një polipyll (ose pyll i drejtuar ose pyll i orientuar) është një graf jociklik i drejtuar, grafiku themelor i padrejtuar i të cilit është një pyll.
Çfarë janë pemët e drejtuara dhe të padrejtuara?
Një graf i padrejtuar pa cikle është një pyll dhe nëse është i lidhur quhet pemë. Një grafik i drejtuar është një pyll (ose pemë) nëse kur të gjitha skajet shndërrohen në skaje të padrejtuara, ai është pyll (ose pemë) i padrejtuar. Një pemë me rrënjë është një pemë me një kulm të caktuar si rrënjë.
Pse pemët janë të padrejtuara?
Teorema: Një graf i padrejtuar është një pemë nëse ka saktësisht një shteg të thjeshtë midis çdo çifti kulmeshVërtetim: Nëse kemi një graf T që është një pemë, atëherë ai duhet të jetë i lidhur pa cikle. Meqenëse T është i lidhur, duhet të ketë të paktën një shteg të thjeshtë ndërmjet çdo çifti kulmesh.
Ç'do të thotë pemë e drejtuar?
Një pemë e drejtuar është një graf i drejtuar aciklik Ajo ka një nyje me gradë 1, ndërsa të gjitha nyjet e tjera kanë shkallën 1 siç tregohet në fig: Nyja që ka shkallën e jashtme 0 është quhet një nyje e jashtme ose një nyje terminale ose një fletë. Nyjet që kanë shkallë më të madhe ose të barabartë me një quhen nyje të brendshme.
Si e dalloni nëse një graf i padrejtuar është një pemë?
Në rastin e grafikëve të padrejtuar, ne kryejmë tre hapa:
- Kryej një kontroll DFS nga çdo nyje për t'u siguruar që çdo nyje ka saktësisht një prind. Nëse jo, kthehu.
- Kontrollo që të gjitha nyjet janë vizituar. Nëse kontrolli DFS nuk ishte në gjendje të vizitonte të gjitha nyjet, atëherë kthehu.
- Përndryshe, grafiku është një pemë.
