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

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

Namespace Prefixes

PrefixIRI
wikipedia-huhttp://hu.wikipedia.org/wiki/
dcthttp://purl.org/dc/terms/
n24http://www.cs.yale.edu/homes/spielman/PAPERS/
n16http://resolver.sub.uni-goettingen.de/
n19http://www.math.cmu.edu/~af1p/Texfiles/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-huhttp://hu.dbpedia.org/resource/
n10http://portal.acm.org/
prop-huhttp://hu.dbpedia.org/property/
n15http://www.ics.uci.edu/~eppstein/pubs/
n7http://chalermsook.googlepages.com/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n22http://renyi.hu/~p_erdos/
n6http://www.kurims.kyoto-u.ac.jp/~kyodo/kokyuroku/contents/pdf/
n17http://users.uoa.gr/~sedthilk/papers/
n12http://digbib.ubka.uni-karlsruhe.de/eva/ira/2005/
n18http://www.cs.cmu.edu/~glmiller/Publications/Papers/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n11http://www.math.ucsd.edu/~fan/mypaps/fanpap/
n4http://hu.dbpedia.org/resource/Sablon:
n20http://www.cs.cornell.edu/~kash/papers/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n25http://www.renyi.hu/~p_erdos/
n14http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Síkgráf-elválasztási_tétel
rdfs:label
Síkgráf-elválasztási tétel
dct:subject
n14:Síkgráfok n14:Gráfelméleti_tételek
dbo:wikiPageID
1591937
dbo:wikiPageRevisionID
23701297
dbo:wikiPageExternalLink
n6:0427-11.pdf n7:mincut.ps n10:citation.cfm%3Fid=314625 n10:citation.cfm%3Fid=314613.314632 n11:117separatorthms.pdf n12:20 n11:116universal.pdf n15:EppMilTen-FI-95.ps.gz n16:purl%3FGDZPPN002153998 n17:planar.pdf n18:GrMiTe94.pdf n18:Mi87.pdf n19:sep.pdf n18:GaMi90.pdf n20:BBK03.pdf n22:1982-12.pdf n24:planarSep.pdf n25:1976-26.pdf
prop-hu:wikiPageUsesTemplate
n4:Citation n4:Refbegin n4:Halott_link n4:Reflist n4:Refend n4:Fordítás n4:Mvar n4:Math n4:Harvtxt
prop-hu:date
2021
prop-hu:url
n7:mincut.ps
dbo:abstract
A matematika, azon belül a gráfelmélet területén a síkgráf-elválasztási tétel, síkgráf-felbontási tétel, síkgráf-szeparációs tétel vagy Lipton–Tarjan-szeparátortétel (planar separator theorem) a síkbarajzolható gráfokra vonatkozó egyfajta izoperimetrikus egyenlőtlenség, ami kimondja, hogy bármely síkbarajzolható gráf kis számú csúcs eltávolításával kisebb darabokra szedhető szét. Pontosabban, egy n csúcsú gráfból O(√n) csúcsot eltávolítva (ahol O a nagy Ordó jelölésre utal) a gráfot olyan diszjunkt részgráfokra , melyek mindegyikében legfeljebb 2n/3 csúcs található. A szeparációs tételnek először egy gyengébb változatát sikerült bizonyítania -nak, melyben a szeparátor O(√n) helyett O(√n log n) csúcsból áll; az éles aszimptotikus korlátot elsőként igazolta. Azóta a szeparátortételt sokféleképpen sikerült bizonyítani, a tételben szereplő O(√n) tagot javították és a tételt kiterjesztették a nem síkbarajzolható gráfok egyes osztályaira is. A síkgráf-elválasztási tétel ismételt alkalmazása egy szeparátorhierarchiát hoz létre, ami a gráf vagy (branch-decomposition) formáját öltheti. Ezek a szeparátorhierarchiák felhasználhatók síkgráfokon futtatott hatékony „oszd meg és uralkodj”-algoritmusok létrehozására, és az ezeken a hierarchiákon végzett segítségével ezen gráfok általában optimalizációs problémáit megoldó vagy algoritmusok előállítására. A szeparátorhierarchiákat használják a (kb. „egymásba ágyazott boncolás”) módszerében is, ami a végeselemes módszerben fellépő ritka lineáris egyenletrendszerek megoldásának hatékony, Gauss-eliminációs variánsa. , Fomin, és Thilikos -elmélete a síkgráf-elválasztási tételt általánosítja és nagyban kiterjeszti az alkalmazási területét a síkbarajzolható gráfok rengeteg minimalizálási problémája mellett az egy-egy tiltott minort nem tartalmazó gráfokra.
prov:wasDerivedFrom
wikipedia-hu:Síkgráf-elválasztási_tétel?oldid=23701297&ns=0
dbo:wikiPageLength
70561
foaf:isPrimaryTopicOf
wikipedia-hu:Síkgráf-elválasztási_tétel
Subject Item
dbpedia-hu:Lipton–Tarjan-szeparátortétel
dbo:wikiPageRedirects
dbpedia-hu:Síkgráf-elválasztási_tétel
Subject Item
dbpedia-hu:Síkgráf-felbontási_tétel
dbo:wikiPageRedirects
dbpedia-hu:Síkgráf-elválasztási_tétel
Subject Item
dbpedia-hu:Síkgráf-szeparációs_tétel
dbo:wikiPageRedirects
dbpedia-hu:Síkgráf-elválasztási_tétel
Subject Item
wikipedia-hu:Síkgráf-elválasztási_tétel
foaf:primaryTopic
dbpedia-hu:Síkgráf-elválasztási_tétel