| dbo:abstract
|
- A számítástudományban egy irányított gráf topológiai rendezése a csúcsainak lineáris sorrendje, úgy, hogy minden irányított uv élnél, az u csúcstól a v csúcsig, u előtt v van a sorrendben. Például a gráf csúcsait reprezentálhatják a végrehajtandó feladatokat, és az élek képviselik azokat a korlátozásokat, amelyek szerint az egyik feladatot a másik előtt kell végrehajtani; ebben az alkalmazásban a topológiai rendezés csak egy érvényes sorrend a feladatokhoz. A topológiai rendezés akkor és csak akkor lehetséges, ha a gráfnak nincs köre, azaz ha ez egy irányított körmentes gráf (DAG). Legyen D=(V,A) irányított gráf. A gráf csúcsainak akkor és csak akkor van olyan sorrendje, amiben minden él előrefelé vezet, ha aciklikus (irányított körmentes gráf). Az ilyen sorrendet topologikus sorrendnek nevezik. (hu)
- A számítástudományban egy irányított gráf topológiai rendezése a csúcsainak lineáris sorrendje, úgy, hogy minden irányított uv élnél, az u csúcstól a v csúcsig, u előtt v van a sorrendben. Például a gráf csúcsait reprezentálhatják a végrehajtandó feladatokat, és az élek képviselik azokat a korlátozásokat, amelyek szerint az egyik feladatot a másik előtt kell végrehajtani; ebben az alkalmazásban a topológiai rendezés csak egy érvényes sorrend a feladatokhoz. A topológiai rendezés akkor és csak akkor lehetséges, ha a gráfnak nincs köre, azaz ha ez egy irányított körmentes gráf (DAG). Legyen D=(V,A) irányított gráf. A gráf csúcsainak akkor és csak akkor van olyan sorrendje, amiben minden él előrefelé vezet, ha aciklikus (irányított körmentes gráf). Az ilyen sorrendet topologikus sorrendnek nevezik. (hu)
|
