planar graph oor Sweeds

planar graph

Vertalings in die woordeboek Engels - Sweeds

Planär graf

voorbeelde

Not every planar graph corresponds to a convex polyhedron in this way: the trees do not, for example.
Alla planära grafer motsvaras inte av en polyeder på detta sätt, exempelvis inte träd.

Planar graphs generalize to graphs drawable on a surface of a given genus.
En generalisering av planära grafer är grafer som kan ritas på en yta av ett givet genus.

It is NP-hard to test whether a given undirected planar graph can be realized as a matchstick graph.
Det är NP-svårt att avgöra huruvida en oriktad planär graf kan åstadkommas som en tändsticksgraf.

In this terminology, planar graphs have graph genus 0, since the plane (and the sphere) are surfaces of genus 0.
Med denna terminologi har planära grafer grafgenus 0, eftersom planet (och sfären) har genus 0.

In this sense, planar graphs are sparse graphs, in that they have only O(v) edges, asymptotically smaller than the maximum O(v2).
I den här meningen är planära grafer glesa grafer eftersom de bara har O(v) kanter och blir asymptotiskt mindre än det maximala O(v2).

Because the dual graph depends on a particular embedding, the dual graph of a planar graph is not unique, in the sense that the same planar graph can have non-isomorphic dual graphs.
Eftersom dualgrafen beror av inbäddningen så är inte dualgrafen till en planär graf unik på samma sätt som dualgrafen till en plan graf, utan en planär graf kan ha olika icke-isomera dualgrafer.

Such a drawing is called a plane graph or planar embedding of the graph.
En sådan avbildning kallas en plan graf eller planär inbäddning av grafen.

The Polish mathematician Kazimierz Kuratowski provided a characterization of planar graphs in terms of forbidden graphs, now known as Kuratowski's theorem: A finite graph is planar if and only if it does not contain a subgraph that is a subdivision of the complete graph K5 or the complete bipartite graph K3,3 (utility graph).
Den polske matematikern Kazimierz Kuratowski bidrog med en karakterisering av planära grafer byggd på två förbjudna grafer, vilket nu är känt som Kuratowskis sats: En ändlig graf är planär om och endast om den inte innehåller en delgraf som är en subdivision av K5 (den kompletta grafen över fem noder) eller K3,3 (den kompletta bipartita grafen över sex noder, så att tre av dem är förbundna med de andra tre).

A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.
En plan graf kan definieras som en planär graf med en avbildning av varje nod till en punkt i planet, och från varje kant till en plan kurva i planet, så att varje kurvas ändpunkter är de punkter som avbildas av kantens ändnoder och så att alla kurvor är disjunkta utom i ändpunkterna.

In practice, it is difficult to use Kuratowski's criterion to quickly decide whether a given graph is planar.
I praktiken är det svårt att använda Kuratowskis kriterium för att snabbt avgöra om en graf är planär.

Instead of considering subdivisions, Wagner's theorem deals with minors: A finite graph is planar if and only if it does not have K5 or K3,3 as a minor.
I stället för att betrakta subdivisioner behandlar Wagners sats minora av grafer: En ändlig graf är planär om och endast om den inte har K5 eller K3,3 som en minor.

Note that these theorems provide necessary conditions for planarity that are not sufficient conditions, and therefore can only be used to prove a graph is not planar, not that it is planar.
Märk att dessa satser ger nödvändiga, men inte tillräckliga, förutsättningar för planaritet och därför bara kan användas för att visa att en graf inte är planär.

However, there exist fast algorithms for this problem: for a graph with n vertices, it is possible to determine in time O(n) (linear time) whether the graph may be planar or not (see planarity testing).
Det finns dock snabba algoritmer för att lösa problemet: för en graf med n noder är det möjligt att avgöra i linjär tid O(n) huruvida en graf kan vara planär eller ej.

The minimum spanning tree of a planar graph.
Minimalt uppspännande träd till en planär graf.

A planar graph and its minimum spanning tree.
Minimalt uppspännande träd till en planär graf.

We provide both new exact algorithms for the case of general graphs as well as approximation algorithms for the case of planar graphs.
Vi visar nya exakta algoritmer i det fallet för generella grafer samt approximationsalgoritmer i fallet med planära grafer.

Main article: Planar graph A planar graph is a graph whose vertices and edges can be drawn in a plane such that no two of the edges intersect.
En graf kallas planär om det är möjligt att rita den i ett plan, till exempel på ena sidan av ett papper, utan att några kanter korsar varandra.