This HTML5 document contains 226 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
dbthttp://dbpedia.org/resource/Template:
dbpedia-elhttp://el.dbpedia.org/resource/
dbpedia-nohttp://no.dbpedia.org/resource/
wikipedia-enhttp://en.wikipedia.org/wiki/
dbpedia-fihttp://fi.dbpedia.org/resource/
dbrhttp://dbpedia.org/resource/
dbpedia-hehttp://he.dbpedia.org/resource/
n26http://commons.wikimedia.org/wiki/Special:FilePath/
dbpedia-frhttp://fr.dbpedia.org/resource/
dctermshttp://purl.org/dc/terms/
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n31http://dbpedia.org/resource/File:
dbphttp://dbpedia.org/property/
xsdhhttp://www.w3.org/2001/XMLSchema#
dbpedia-ukhttp://uk.dbpedia.org/resource/
dbohttp://dbpedia.org/ontology/
dbpedia-srhttp://sr.dbpedia.org/resource/
dbpedia-vihttp://vi.dbpedia.org/resource/
dbpedia-pthttp://pt.dbpedia.org/resource/
dbpedia-huhttp://hu.dbpedia.org/resource/
dbpedia-jahttp://ja.dbpedia.org/resource/
dbchttp://dbpedia.org/resource/Category:
dbpedia-dehttp://de.dbpedia.org/resource/
dbpedia-plhttp://pl.dbpedia.org/resource/
yagohttp://dbpedia.org/class/yago/
dbpedia-ruhttp://ru.dbpedia.org/resource/
wikidatahttp://www.wikidata.org/entity/
yago-reshttp://yago-knowledge.org/resource/
n15https://global.dbpedia.org/id/
n16https://xlinux.nist.gov/dads/HTML/
dbpedia-ithttp://it.dbpedia.org/resource/
provhttp://www.w3.org/ns/prov#
foafhttp://xmlns.com/foaf/0.1/
dbpedia-zhhttp://zh.dbpedia.org/resource/
dbpedia-kohttp://ko.dbpedia.org/resource/
dbpedia-fahttp://fa.dbpedia.org/resource/
dbpedia-eshttp://es.dbpedia.org/resource/
freebasehttp://rdf.freebase.com/ns/
owlhttp://www.w3.org/2002/07/owl#

Statements

Subject Item
dbr:Push–relabel_maximum_flow_algorithm
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:List_of_algorithms
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Top_sort
dbo:wikiPageWikiLink
dbr:Topological_sorting
dbo:wikiPageRedirects
dbr:Topological_sorting
Subject Item
dbr:Topological_Sort
dbo:wikiPageWikiLink
dbr:Topological_sorting
dbo:wikiPageRedirects
dbr:Topological_sorting
Subject Item
dbr:Topological_labelling
dbo:wikiPageWikiLink
dbr:Topological_sorting
dbo:wikiPageRedirects
dbr:Topological_sorting
Subject Item
dbr:Topological_ordering
dbo:wikiPageWikiLink
dbr:Topological_sorting
dbo:wikiPageRedirects
dbr:Topological_sorting
Subject Item
dbr:Topological_sort
dbo:wikiPageWikiLink
dbr:Topological_sorting
dbo:wikiPageRedirects
dbr:Topological_sorting
Subject Item
dbr:Toposort
dbo:wikiPageWikiLink
dbr:Topological_sorting
dbo:wikiPageRedirects
dbr:Topological_sorting
Subject Item
dbr:Topsort
dbo:wikiPageWikiLink
dbr:Topological_sorting
dbo:wikiPageRedirects
dbr:Topological_sorting
Subject Item
dbr:List_of_graph_theory_topics
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Cycle_(graph_theory)
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Dependency_graph
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Depth-first_search
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Weak_component
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:♯P-complete
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Alexander_Skopin
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Glossary_of_graph_theory
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Make_(software)
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Shortest_path_problem
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Feedback_arc_set
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Dependency_resolver
dbo:wikiPageWikiLink
dbr:Topological_sorting
dbo:wikiPageRedirects
dbr:Topological_sorting
Subject Item
dbr:Acyclic_orientation
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Certifying_algorithm
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Topological_sorting
rdf:type
yago:Communication100033020 yago:Procedure101023820 yago:YagoPermanentlyLocatedEntity yago:WikicatSortingAlgorithms yago:WikicatDirectedGraphs yago:Event100029378 yago:PsychologicalFeature100023100 yago:Act100030358 yago:Activity100407535 yago:WikicatGraphAlgorithms yago:Rule105846932 yago:Graph107000195 yago:Abstraction100002137 yago:SortingAlgorithm105847658 yago:VisualCommunication106873252 yago:Algorithm105847438 owl:Thing
rdfs:label
Топологічне сортування Топологическая сортировка Tri topologique 위상정렬 トポロジカルソート Topological sorting Ordenação topológica 拓撲排序 Topologische Sortierung Ordenamiento topológico Sortowanie topologiczne Τοπολογική ταξινόμηση Ordinamento topologico
rdfs:comment
In teoria dei grafi un ordinamento topologico (in inglese topological sort) è un ordinamento lineare di tutti i vertici di un grafo diretto. I nodi di un grafo si definiscono ordinati topologicamente se i nodi sono disposti in modo tale che ogni nodo viene prima di tutti i nodi collegati ai suoi archi uscenti.L'ordinamento topologico non è un ordinamento totale, poiché la soluzione può non essere unica. Nel caso peggiore infatti si possono avere ordinamenti topologici diversi che corrispondono a tutte le possibili permutazioni degli nodi. È possibile ordinare topologicamente un grafo se e solo se non contiene cicli (cioè solo se è un grafo aciclico diretto), e sono noti algoritmi per determinare un ordinamento topologico in tempo lineare. Sortowanie topologiczne skierowanego grafu acyklicznego – liniowe uporządkowanie wierzchołków, w którym jeśli istnieje krawędź skierowana prowadząca od wierzchołka do to znajdzie się przed wierzchołkiem Innymi słowy, każdy wierzchołek poprzedza wszystkie te wierzchołki, do których prowadzą wychodzące od niego krawędzie. Wierzchołki w każdym grafie acyklicznym skierowanym można posortować topologicznie na jeden lub więcej sposobów. トポロジカルソート（英: topological sort）は、グラフ理論において、有向非巡回グラフ（英: directed acyclic graph, DAG）の各ノードを順序付けして、どのノードもその出力辺の先のノードより前にくるように並べることである。有向非巡回グラフは必ずトポロジカルソートすることができる。 有向非巡回グラフのノードの集合に到達可能性関係 R (ノード x から y への(各辺の向きに逆行しない)経路が存在するとき、またそのときに限り xRy とする)を定めると、R は半順序関係となる。トポロジカルソートとは、この R を全順序になるように拡張したものとみなせる。 Topologische Sortierung bezeichnet in der Mathematik eine Reihenfolge von Dingen, bei der vorgegebene Abhängigkeiten erfüllt sind. Anstehende Tätigkeiten einer Person etwa unterliegen einer Halbordnung: es existieren Bedingungen wie „Tätigkeit A muss vor Tätigkeit B erledigt werden“. Eine Reihenfolge, welche alle Bedingungen erfüllt, nennt man topologische Sortierung der Menge anstehender Tätigkeiten. Im Gegensatz zur Sortierung einer Totalordnung ist die Reihenfolge nicht eindeutig, sondern es kann mehrere Möglichkeiten geben. Wenn gegenseitige Abhängigkeiten bestehen, ist eine topologische Sortierung unmöglich. Em teoria dos grafos, uma ordenação topológica de um digrafo acíclico (DAG) é uma ordem linear de seus nós em que cada nó vem antes de todos nós para os quais este tenha arestas de saída. Cada DAG tem uma ou mais ordenações topológicas. Mais formalmente, define-se a relação acessibilidade R sobre os nós do DAG tal que xRy se e somente se existe um caminho dirigido de x para y. Então, R é uma ordem parcial, e uma ordenação topológica é uma desta ordem parcial, isto é, uma ordem total compatível com a ordem parcial. 在计算机科学领域，有向图的拓扑排序或拓撲定序是对其顶点的一种线性排序，使得对于从顶点到顶点的每个有向边，在排序中都在之前。 例如，图形的顶点可以表示要执行的任务，并且边可以表示一个任务必须在另一个任务之前执行的约束；在这个应用中，拓扑排序只是一个有效的任务顺序。 当且仅当图中没有定向环时（即有向无环图），才有可能进行拓扑排序。 任何有向无环图至少有一个拓扑排序。已知有算法可以在线性时间内，构建任何有向无环图的拓扑排序。 在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，才能称为该图的一个拓扑排序（英語：Topological sorting）： 1. * 序列中包含每个顶点，且每个顶点只出现一次； 2. * 若A在序列中排在B的前面，则在图中不存在从B到A的路径。 In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. Precisely, a topological sort is a graph traversal in which each node v is visited only after all its dependencies are visited. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are know Топологічне сортування — впорядковування вершин безконтурного орієнтованого графу згідно з частковим порядком, визначеним ребрами цього графу на множині його вершин. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환 유향 그래프(directed acyclic graph)여야 한다. Τοπολογική ταξινόμηση ή αλλιώς τοπολογική διάταξη (αγγλικά: Topological sorting) ενός Κατευθυνόμενου Άκυκλου Γράφου (Directed Acyclic Graph ή DAG), ονομάζεται στη Θεωρία Γράφων η γραμμική διάταξη των κόμβων, έτσι ώστε κάθε πρόγονος ενός v προηγείται του v στη διάταξη. Κάθε Κατευθυνόμενος Άκυκλος Γράφος μπορεί να έχει μία ή περισσότερες τοπολογικές διατάξεις. En théorie des graphes, et plus spécialement en algorithmique des graphes, un tri topologique d'un graphe acyclique orienté (ou dag, de l'anglais directed acyclic graph) est un ordre total sur l'ensemble des sommets, dans lequel s précède t pour tout arc d'un sommet s à un sommet t. En d'autres termes, un tri topologique est une extension linéaire de l'ordre partiel sur les sommets déterminés par les arcs. Топологическая сортировка — упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин. Una ordenación topológica (topological sort, topological ordering, topsort o toposort en inglés) de un grafo acíclico dirigido G es una ordenación lineal de todos los nodos de G que satisface que si G contiene la arista dirigida uv entonces el nodo u aparece antes del nodo v. La condición que el grafo no contenga ciclos es importante, ya que no se puede obtener ordenación topológica de grafos que contengan ciclos. Para poder encontrar la ordenación topológica del grafo G deberemos aplicar una modificación del algoritmo de búsqueda en profundidad (DFS).
owl:differentFrom
dbr:Kuhn's_algorithm
foaf:depiction
n26:Parallel_Topological_Sorting.gif n26:Directed_acyclic_graph_2.svg
dcterms:subject
dbc:Articles_with_example_pseudocode dbc:Graph_algorithms dbc:Directed_acyclic_graphs dbc:Sorting_algorithms
dbo:wikiPageID
897064
dbo:wikiPageRevisionID
1123299686
dbo:wikiPageWikiLink
dbr:Comparison_sort dbr:Critical_path_method dbr:Logic_synthesis dbr:Indegree dbr:Instruction_scheduling dbc:Articles_with_example_pseudocode dbr:Connectivity_(graph_theory) dbr:Adjacency_matrix dbr:The_Art_of_Computer_Programming dbr:Prefix_sum dbr:Partial_order dbr:Tsort dbr:Longest_path_problem dbr:Layered_graph_drawing dbr:SPMD dbc:Graph_algorithms dbr:CRCW_PRAM dbr:Job_shop_scheduling dbr:Transitive_relation dbr:Directed_acyclic_graph dbr:Shortest_path_problem dbr:Weighted_graph dbr:Project_management dbr:Total_order dbr:Spreadsheet dbr:Tarjan's_strongly_connected_components_algorithm dbr:Transitive_reduction dbr:Min-plus_matrix_multiplication dbr:Linear_extension n31:Directed_acyclic_graph_2.svg dbr:Program_Evaluation_and_Review_Technique dbr:Feedback_arc_set dbr:Directed_path dbr:Hamiltonian_path dbr:Makefile dbr:Directed_cycle dbr:Dependency_graph dbr:Directed_graph dbr:NC_(complexity) dbr:Computer_science dbr:Distributed_memory dbr:Reachability dbr:Linear_time n31:Parallel_Topological_Sorting.gif dbr:Coffman–Graham_algorithm dbc:Directed_acyclic_graphs dbr:Serialization dbr:NP-hard dbr:Pre-topological_order dbr:Linker_(computing) dbc:Sorting_algorithms dbr:Depth-first_search dbr:Parallel_random-access_machine dbr:Vertex_(graph_theory) dbr:D._E._Knuth dbr:Lexicographic_order dbr:Algorithm
dbo:wikiPageExternalLink
n16:topologicalSort.html
owl:sameAs
dbpedia-fr:Tri_topologique dbpedia-ja:トポロジカルソート dbpedia-pl:Sortowanie_topologiczne dbpedia-it:Ordinamento_topologico n15:4v6KU freebase:m.03mt02 dbpedia-el:Τοπολογική_ταξινόμηση dbpedia-sr:Topološko_uređenje dbpedia-fa:مرتب‌سازی_توپولوژیکی dbpedia-es:Ordenamiento_topológico wikidata:Q753127 dbpedia-de:Topologische_Sortierung yago-res:Topological_sorting dbpedia-zh:拓撲排序 dbpedia-ru:Топологическая_сортировка dbpedia-vi:Sắp_xếp_tô_pô dbpedia-ko:위상정렬 dbpedia-fi:Topologinen_lajittelu dbpedia-uk:Топологічне_сортування dbpedia-no:Topologisk_sortering dbpedia-pt:Ordenação_topológica dbpedia-he:מיון_טופולוגי dbpedia-hu:Topologikus_sorrend
dbp:wikiPageUsesTemplate
dbt:= dbt:Short_description dbt:Redirect dbt:Mono dbt:Mset dbt:Reflist dbt:Sorting dbt:R dbt:Tmath dbt:Framebox dbt:Frame-footer dbt:Distinguish dbt:Mvar dbt:Harvp dbt:Math dbt:MathWorld
dbo:thumbnail
n26:Directed_acyclic_graph_2.svg?width=300
dbp:title
Topological Sort
dbp:urlname
TopologicalSort
dbp:mode
cs2
dbo:abstract
Topologische Sortierung bezeichnet in der Mathematik eine Reihenfolge von Dingen, bei der vorgegebene Abhängigkeiten erfüllt sind. Anstehende Tätigkeiten einer Person etwa unterliegen einer Halbordnung: es existieren Bedingungen wie „Tätigkeit A muss vor Tätigkeit B erledigt werden“. Eine Reihenfolge, welche alle Bedingungen erfüllt, nennt man topologische Sortierung der Menge anstehender Tätigkeiten. Im Gegensatz zur Sortierung einer Totalordnung ist die Reihenfolge nicht eindeutig, sondern es kann mehrere Möglichkeiten geben. Wenn gegenseitige Abhängigkeiten bestehen, ist eine topologische Sortierung unmöglich. Aus mengentheoretischer Sicht handelt es sich bei der topologischen Sortierung um eine lineare Erweiterung einer partiellen Ordnung. 1930 zeigte Edward Szpilrajn, dass aus dem Auswahlaxiom folgt, dass sich jede partielle Ordnung zu einer linearen Ordnung erweitern lässt. Die topologische Sortierung für endliche Mengen (hier wird das Auswahlaxiom nicht gebraucht) ist bei vielen Anwendungen der Informatik ein wichtiges Konzept. Bereits 1961 wurde von ein Algorithmus entwickelt, mit dem eine topologische Sortierung ganz allgemein erstellt werden kann. Zuvor waren allerdings schon Algorithmen für spezielle Anwendungen bekannt. Des Weiteren spielt die topologische Sortierung in der Graphentheorie bei der Untersuchung von gerichteten Graphen auf Zyklenfreiheit eine große Rolle. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 위상정렬을 가장 잘 설명해 줄 수 있는 예로 대학의 선수과목(prerequisite) 구조를 예로 들 수 있다. 만약 특정 수강과목에 선수과목이 있다면 그 선수 과목부터 수강해야 하므로, 특정 과목들을 수강해야 할 때 위상 정렬을 통해 올바른 수강 순서를 찾아낼 수 있다. 이와 같이 선후 관계가 정의된 상에서 선후 관계에 따라 정렬하기 위해 위상 정렬을 이용할 수 있다. 정렬의 순서는 유향 그래프의 구조에 따라 여러 개의 종류가 나올 수 있다. 위상 정렬이 성립하기 위해서는 반드시 그래프의 순환이 존재하지 않아야 한다. 즉, 그래프가 비순환 유향 그래프(directed acyclic graph)여야 한다. 일반적인 위상 정렬의 적용은 주로 업무의 일정을 일어나야 할 순서에 따라 배치하기 위하는 것으로, 이 알고리즘은 프로젝트 관리 기법을 평가 및 분석하기 위한 기법(PERT)에 적용하기 위한 목적을 위해 1960년대 초반부터 연구되었다 (Jarnagin 1960). 이 때, 해당 업무는 꼭짓점으로 표현되었고, 각 꼭짓점을 연결하는 변은 해당 업무 간의 선후 관계를 표현하였다. 가령, 옷을 다리기 위한 업무는 반드시 옷을 세탁기에 돌리는 업무 뒤에 배치되어야 한다. 이와 같이, 위상정렬은 각 업무를 수행하기 위한 순서를 제공하였다. Topological sorting(위상 정렬)은 컴퓨터 과학에서, 방향 그래프의 위상 정렬 또는 위상 배치는 정점의 선형 순서이다. 꼭짓점 u에서 꼭짓점 v로의 모든 방향 꼭짓점 uv는 v의 순서 전에 u가 오는 것이다. 예를 들어, 그래프의 꼭짓점은 아마 수행하는 일은 대표한다. 그리고 꼭짓점은 어떤 일이 다른 것보다 먼저 수행되어야 하는 허가되지 않은 것을 대표한다. 이러한 것에서, 위상 배열은 일의 유용한 순서에 불과하다. 정확히 위상 정렬은 모든 종속성을 방문한 후에만 각 노드 v를 방문하는 그래프 순환이다. 위상 배열은 가능하다. 정말 만약에 그래프 방향이 없는 순환이라면, 아마 그것은 방향 순환 그래프(DAG)일 것이다. 어떤 DAG는 최소 하나의 위상 배열을 가지고 있다. 그리고 알고리즘은 어떤 DAG 속 선형 시간의 위상 배열이 구성한다고 알려져 있다. 위상 정렬은 feedback arc set 와 같은 랭킹 문제를 해결하는데 많이 사용된다. 위상 정렬은 심지어 DAG의 요소가 연결되지 않을지라도 가능하다. Топологічне сортування — впорядковування вершин безконтурного орієнтованого графу згідно з частковим порядком, визначеним ребрами цього графу на множині його вершин. 在计算机科学领域，有向图的拓扑排序或拓撲定序是对其顶点的一种线性排序，使得对于从顶点到顶点的每个有向边，在排序中都在之前。 例如，图形的顶点可以表示要执行的任务，并且边可以表示一个任务必须在另一个任务之前执行的约束；在这个应用中，拓扑排序只是一个有效的任务顺序。 当且仅当图中没有定向环时（即有向无环图），才有可能进行拓扑排序。 任何有向无环图至少有一个拓扑排序。已知有算法可以在线性时间内，构建任何有向无环图的拓扑排序。 在图论中，由一个有向无环图的顶点组成的序列，当且仅当满足下列条件时，才能称为该图的一个拓扑排序（英語：Topological sorting）： 1. * 序列中包含每个顶点，且每个顶点只出现一次； 2. * 若A在序列中排在B的前面，则在图中不存在从B到A的路径。 トポロジカルソート（英: topological sort）は、グラフ理論において、有向非巡回グラフ（英: directed acyclic graph, DAG）の各ノードを順序付けして、どのノードもその出力辺の先のノードより前にくるように並べることである。有向非巡回グラフは必ずトポロジカルソートすることができる。 有向非巡回グラフのノードの集合に到達可能性関係 R (ノード x から y への(各辺の向きに逆行しない)経路が存在するとき、またそのときに限り xRy とする)を定めると、R は半順序関係となる。トポロジカルソートとは、この R を全順序になるように拡張したものとみなせる。 Топологическая сортировка — упорядочивание вершин бесконтурного ориентированного графа согласно частичному порядку, заданному ребрами орграфа на множестве его вершин. In teoria dei grafi un ordinamento topologico (in inglese topological sort) è un ordinamento lineare di tutti i vertici di un grafo diretto. I nodi di un grafo si definiscono ordinati topologicamente se i nodi sono disposti in modo tale che ogni nodo viene prima di tutti i nodi collegati ai suoi archi uscenti.L'ordinamento topologico non è un ordinamento totale, poiché la soluzione può non essere unica. Nel caso peggiore infatti si possono avere ordinamenti topologici diversi che corrispondono a tutte le possibili permutazioni degli nodi. È possibile ordinare topologicamente un grafo se e solo se non contiene cicli (cioè solo se è un grafo aciclico diretto), e sono noti algoritmi per determinare un ordinamento topologico in tempo lineare. Em teoria dos grafos, uma ordenação topológica de um digrafo acíclico (DAG) é uma ordem linear de seus nós em que cada nó vem antes de todos nós para os quais este tenha arestas de saída. Cada DAG tem uma ou mais ordenações topológicas. Mais formalmente, define-se a relação acessibilidade R sobre os nós do DAG tal que xRy se e somente se existe um caminho dirigido de x para y. Então, R é uma ordem parcial, e uma ordenação topológica é uma desta ordem parcial, isto é, uma ordem total compatível com a ordem parcial. Sortowanie topologiczne skierowanego grafu acyklicznego – liniowe uporządkowanie wierzchołków, w którym jeśli istnieje krawędź skierowana prowadząca od wierzchołka do to znajdzie się przed wierzchołkiem Innymi słowy, każdy wierzchołek poprzedza wszystkie te wierzchołki, do których prowadzą wychodzące od niego krawędzie. Wierzchołki w każdym grafie acyklicznym skierowanym można posortować topologicznie na jeden lub więcej sposobów. En théorie des graphes, et plus spécialement en algorithmique des graphes, un tri topologique d'un graphe acyclique orienté (ou dag, de l'anglais directed acyclic graph) est un ordre total sur l'ensemble des sommets, dans lequel s précède t pour tout arc d'un sommet s à un sommet t. En d'autres termes, un tri topologique est une extension linéaire de l'ordre partiel sur les sommets déterminés par les arcs. In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering. For instance, the vertices of the graph may represent tasks to be performed, and the edges may represent constraints that one task must be performed before another; in this application, a topological ordering is just a valid sequence for the tasks. Precisely, a topological sort is a graph traversal in which each node v is visited only after all its dependencies are visited. A topological ordering is possible if and only if the graph has no directed cycles, that is, if it is a directed acyclic graph (DAG). Any DAG has at least one topological ordering, and algorithms are known for constructing a topological ordering of any DAG in linear time. Topological sorting has many applications especially in ranking problems such as feedback arc set. Topological sorting is possible even when the DAG has disconnected components. Τοπολογική ταξινόμηση ή αλλιώς τοπολογική διάταξη (αγγλικά: Topological sorting) ενός Κατευθυνόμενου Άκυκλου Γράφου (Directed Acyclic Graph ή DAG), ονομάζεται στη Θεωρία Γράφων η γραμμική διάταξη των κόμβων, έτσι ώστε κάθε πρόγονος ενός v προηγείται του v στη διάταξη. Κάθε Κατευθυνόμενος Άκυκλος Γράφος μπορεί να έχει μία ή περισσότερες τοπολογικές διατάξεις. Πιο αυστηρά, μπορούμε να ορίσουμε την τοπολογική ταξινόμηση ενός Κατευθυνόμενου Άκυκλου Γράφου G(V, E), με V το σύνολο των κόμβων και E το σύνολο των ως μία γραμμική αλληλουχία των κόμβων V, έτσι ώστε αν (u, v) E, π(u) < π(v), όπου π(x) η θέση στην οποία βρίσκεται ο κόμβος x στη διάταξη. Una ordenación topológica (topological sort, topological ordering, topsort o toposort en inglés) de un grafo acíclico dirigido G es una ordenación lineal de todos los nodos de G que satisface que si G contiene la arista dirigida uv entonces el nodo u aparece antes del nodo v. La condición que el grafo no contenga ciclos es importante, ya que no se puede obtener ordenación topológica de grafos que contengan ciclos. Usualmente, para clarificar el concepto se suelen identificar los nodos con tareas a realizar en la que hay una precedencia a la hora de ejecutar dichas tareas. La ordenación topológica por tanto es una lista en orden lineal en que deben realizarse las tareas. Para poder encontrar la ordenación topológica del grafo G deberemos aplicar una modificación del algoritmo de búsqueda en profundidad (DFS).
prov:wasDerivedFrom
wikipedia-en:Topological_sorting?oldid=1123299686&ns=0
dbo:wikiPageLength
22902
foaf:isPrimaryTopicOf
wikipedia-en:Topological_sorting
Subject Item
dbr:Tree_traversal
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Tsort
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Data_lineage
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Linear_extension
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Package_manager
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:APT_(software)
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Parallel_algorithms_for_topological_sorting
dbo:wikiPageWikiLink
dbr:Topological_sorting
dbo:wikiPageRedirects
dbr:Topological_sorting
Subject Item
dbr:Partially_ordered_set
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Directed_graph
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Graph_theory
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:2-satisfiability
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Coffman–Graham_algorithm
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Tarjan's_strongly_connected_components_algorithm
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Directed_acyclic_graph
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:C3_linearization
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Algorithms_for_topological_sorting
dbo:wikiPageWikiLink
dbr:Topological_sorting
dbo:wikiPageRedirects
dbr:Topological_sorting
Subject Item
dbr:Reactive_programming
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Longest_path_problem
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:The_Art_of_Computer_Programming
dbo:wikiPageWikiLink
dbr:Topological_sorting
Subject Item
dbr:Kahn's_algorithm
dbo:wikiPageWikiLink
dbr:Topological_sorting
dbo:wikiPageRedirects
dbr:Topological_sorting
Subject Item
dbr:Dependency_resolution
dbo:wikiPageWikiLink
dbr:Topological_sorting
dbo:wikiPageRedirects
dbr:Topological_sorting
Subject Item
wikipedia-en:Topological_sorting
foaf:primaryTopic
dbr:Topological_sorting