| dbo:abstract
|
- En teoria de grafs, el test de planaritat és un problema que consisteix en demostrar si un graf és pla, és a dir, si pot ser dibuixat a un pla sense que hi hagi interseccions entre les arestes. Es tracta d'un problema molt estudiat en ciències computacionals i per això té molts de possibles algorismes i optimitzacions, sovint relacionades amb la implementació de nous tipus d'estructures de dades. La majoria d'aquests mètodes operen en O(n) (temps lineal), on n és el nombre d'arestes o bé de vèrtexs del graf. En lloc d'un simple valor booleà (cert/fals), és preferible que el resultat de l'algorisme sigui una distribució planar del graf sempre que aquesta sigui possible, o bé una identificació dels obstacles de la planaritat, és a dir els subgrafs no planars. Tot i això, si un algorisme troba un subgraf no planar pot estar segur de que el resultat final no és planar i retornar-ho sense computacions addicionals. (ca)
- In graph theory, the planarity testing problem is the algorithmic problem of testing whether a given graph is a planar graph (that is, whether it can be drawn in the plane without edge intersections). This is a well-studied problem in computer science for which many practical algorithms have emerged, many taking advantage of novel data structures. Most of these methods operate in O(n) time (linear time), where n is the number of edges (or vertices) in the graph, which is asymptotically optimal. Rather than just being a single Boolean value, the output of a planarity testing algorithm may be a planar graph embedding, if the graph is planar, or an obstacle to planarity such as a Kuratowski subgraph if it is not. (en)
- En théorie des graphes, le problème du test de planarité est le problème algorithmique qui consiste à tester si un graphe donné est un graphe planaire (c'est-à-dire s'il peut être dessiné dans le plan sans intersection d'arêtes). Il s'agit d'un problème bien étudié en informatique pour lequel de nombreux algorithmes pratiques ont été donnés, souvent en décrivant de nouvelles structures de données. La plupart de ces méthodes fonctionnent en temps O(n) (temps linéaire), où n est le nombre d'arêtes (ou de sommets) du graphe, ce qui est asymptotiquement optimal. La sortie d'un algorithme de test de planarité, plutôt que d'être simplement une valeur booléenne (le graphe est-il planaire, oui ou non ?), peut être un plongement du graphe dans le plan si le graphe est planaire, ou la donnée d'un obstacle à la planarité tel qu'un sous-graphe de Kuratowski s'il ne l'est pas. (fr)
- Задача перевірки планарності — це алгоритмічна задача перевірки, чи є даний граф планарним (тобто, чи можна його намалювати на площині без перетину ребер). Задачу добре вивчено в інформатиці і придумано багато практичних алгоритмів, зокрема, з використанням сучасних структур даних. Більшість цих методів працюють за час O(n) (лінійний час), де n — число ребер (або вершин) графа, що є . Замість простого булівського значення, вихід алгоритмів перевірки планарності може дати вкладення графа, якщо граф планарний, або заваду планарності, таку як підграф Куратовського, якщо граф не планарний. (uk)
- Задача проверки планарности — это алгоритмическая задача проверки, является ли данный граф планарным (то есть, может ли он быть нарисован на плоскости без пересечения рёбер). Задача хорошо изучена в информатике и для неё было придумано много практических алгоритмов, многие из которых используют современные структуры данных. Большинство этих методов работают за время O(n) (линейное время), где n — число рёбер (или вершин) графа, что является . Вместо простого булевского значения, выход алгоритмов проверки планарности может дать вложение графа, если граф планарен, или преграду планарности, такую как подграф Куратовского, если граф не планарен. (ru)
|
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 13131 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- In graph theory, the planarity testing problem is the algorithmic problem of testing whether a given graph is a planar graph (that is, whether it can be drawn in the plane without edge intersections). This is a well-studied problem in computer science for which many practical algorithms have emerged, many taking advantage of novel data structures. Most of these methods operate in O(n) time (linear time), where n is the number of edges (or vertices) in the graph, which is asymptotically optimal. Rather than just being a single Boolean value, the output of a planarity testing algorithm may be a planar graph embedding, if the graph is planar, or an obstacle to planarity such as a Kuratowski subgraph if it is not. (en)
- Задача перевірки планарності — це алгоритмічна задача перевірки, чи є даний граф планарним (тобто, чи можна його намалювати на площині без перетину ребер). Задачу добре вивчено в інформатиці і придумано багато практичних алгоритмів, зокрема, з використанням сучасних структур даних. Більшість цих методів працюють за час O(n) (лінійний час), де n — число ребер (або вершин) графа, що є . Замість простого булівського значення, вихід алгоритмів перевірки планарності може дати вкладення графа, якщо граф планарний, або заваду планарності, таку як підграф Куратовського, якщо граф не планарний. (uk)
- Задача проверки планарности — это алгоритмическая задача проверки, является ли данный граф планарным (то есть, может ли он быть нарисован на плоскости без пересечения рёбер). Задача хорошо изучена в информатике и для неё было придумано много практических алгоритмов, многие из которых используют современные структуры данных. Большинство этих методов работают за время O(n) (линейное время), где n — число рёбер (или вершин) графа, что является . Вместо простого булевского значения, выход алгоритмов проверки планарности может дать вложение графа, если граф планарен, или преграду планарности, такую как подграф Куратовского, если граф не планарен. (ru)
- En teoria de grafs, el test de planaritat és un problema que consisteix en demostrar si un graf és pla, és a dir, si pot ser dibuixat a un pla sense que hi hagi interseccions entre les arestes. Es tracta d'un problema molt estudiat en ciències computacionals i per això té molts de possibles algorismes i optimitzacions, sovint relacionades amb la implementació de nous tipus d'estructures de dades. La majoria d'aquests mètodes operen en O(n) (temps lineal), on n és el nombre d'arestes o bé de vèrtexs del graf. En lloc d'un simple valor booleà (cert/fals), és preferible que el resultat de l'algorisme sigui una distribució planar del graf sempre que aquesta sigui possible, o bé una identificació dels obstacles de la planaritat, és a dir els subgrafs no planars. Tot i això, si un algorisme trob (ca)
- En théorie des graphes, le problème du test de planarité est le problème algorithmique qui consiste à tester si un graphe donné est un graphe planaire (c'est-à-dire s'il peut être dessiné dans le plan sans intersection d'arêtes). Il s'agit d'un problème bien étudié en informatique pour lequel de nombreux algorithmes pratiques ont été donnés, souvent en décrivant de nouvelles structures de données. La plupart de ces méthodes fonctionnent en temps O(n) (temps linéaire), où n est le nombre d'arêtes (ou de sommets) du graphe, ce qui est asymptotiquement optimal. La sortie d'un algorithme de test de planarité, plutôt que d'être simplement une valeur booléenne (le graphe est-il planaire, oui ou non ?), peut être un plongement du graphe dans le plan si le graphe est planaire, ou la donnée d'un ob (fr)
|
| rdfs:label
|
- Test de planaritat (ca)
- Test de planarité (fr)
- Planarity testing (en)
- Проверка планарности (ru)
- Перевірка планарності (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
