This HTML5 document contains 61 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/
n17https://web.archive.org/web/20061125133622/http:/lita.sciences.univ-metz.fr/~kratsch/publications/
dbohttp://dbpedia.org/ontology/
n16http://orion.math.iastate.edu/lhogben/research/
foafhttp://xmlns.com/foaf/0.1/
n19http://axon.cs.byu.edu/papers/
dbpedia-huhttp://hu.dbpedia.org/resource/
n18http://portal.acm.org/
prop-huhttp://hu.dbpedia.org/property/
n6https://archive.org/details/computerintracta00mrga/page/
n11http://lita.sciences.univ-metz.fr/~kratsch/publications/
rdfshttp://www.w3.org/2000/01/rdf-schema#
n7http://www.nada.kth.se/~johanh/
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n15http://hu.dbpedia.org/resource/Sablon:
n21https://web.archive.org/web/20160303174028/http:/www.informatik.uni-rostock.de/~le/Research/
n20http://www.informatik.uni-rostock.de/~le/Research/
n5https://archive.org/details/
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n14http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Feszített_út
rdfs:label
Feszített út
dct:subject
n14:Gráfelméleti_objektumok
dbo:wikiPageID
1525432
dbo:wikiPageRevisionID
23912391
dbo:wikiPageExternalLink
n5:computerintracta00mrga n6:n206 n7:cliqueinap.ps n11:KMT_preprocWG.ps n16:BFHmrank.pdf n17:KMT_preprocWG.ps n18:citation.cfm%3Fid=982792.982920 n19:cyclecut.pdf n20:splitting.pdf n21:splitting.pdf
prop-hu:wikiPageUsesTemplate
n15:Harvtxt n15:Fordítás n15:Portál n15:Reflist n15:Cite_journal n15:Cite_book n15:Cite_conference n15:Refend n15:Refbegin
prop-hu:first
David S. Patrice Jaroslav Michael R.
prop-hu:isbn
978
prop-hu:last
Garey Ossona de Mendez Nešetřil Johnson
prop-hu:location
Heidelberg
prop-hu:page
196
prop-hu:pages
115
prop-hu:publisher
Springer W. H. Freeman
prop-hu:ref
harv
prop-hu:series
Algorithms and Combinatorics
prop-hu:title
Sparsity: Graphs, Structures, and Algorithms Computers and Intractability: A Guide to the Theory of NP-Completeness.
prop-hu:url
n5:computerintracta00mrga
prop-hu:year
1979 2012
prop-hu:doi
10
prop-hu:volume
28
prop-hu:mr
2920058
prop-hu:contribution
Chapter 6. Bounded height trees and tree-depth
prop-hu:author1Link
Jaroslav Nešetřil Michael Garey
prop-hu:author2Link
David S. Johnson Patrice Ossona de Mendez
dbo:abstract
A matematika, azon belül a gráfelmélet területén egy G irányítatlan gráfban egy feszített út (induced path) olyan út, mely G-nek feszített részgráfja. Tehát G-beli csúcsok sorozata, melynek egymást követő csúcsai G-ben éllel vannak összekötve, egymást nem követő csúcsai viszont nincsenek G-ben éllel összekötve. A feszített utat angol nyelvterületen néha kígyónak, snake-nek is nevezik, a hiperkockagráfban hosszú feszített utak keresésének problémáját ezért problémának hívják. Hasonlóan a feszített kör (induced cycle) olyan kör, ami G feszített részgráfja; a feszített köröket húrmentes körnek (chordless cycles) vagy (ha a kör legalább 4 hosszúságú) lyuknak (hole) nevezik. Egy antilyuk (antihole) a G komplementerében lévő lyuk, tehát az antilyuk a lyuk komplementere. Egy gráf leghosszabb feszített útjának hosszát néha detour-számnak (detour number, kb. „kerülőút-szám” vagy „kitérőút-szám”) is nevezik; ritka gráfokon a korlátos detour-szám a korlátos ekvivalens. Egy G gráf feszítettút-száma (induced path number) az a legkevesebb partíció, amibe G csúcsai szétoszthatók úgy, hogy mindegyik partícióban egy-egy feszített út legyen, a szorosan kapcsolódó útfedési szám (path cover number) pedig a G összes csúcsát tartalmazó feszített utak minimális száma. Egy gráf girthparamétere (derékbősége) a legrövidebb körének hossza, ez a kör viszont mindenképpen feszített kör, hiszen bármely rajta lévő húr segítségével egy rövidebb kört lehetne előállítani. Hasonló okból egy gráf páratlan, illetve páros bősége egyben a gráf legkisebb páratlan, illetve páros feszített köre.
prov:wasDerivedFrom
wikipedia-hu:Feszített_út?oldid=23912391&ns=0
dbo:wikiPageLength
11891
foaf:isPrimaryTopicOf
wikipedia-hu:Feszített_út
Subject Item
dbpedia-hu:Feszített_kör
dbo:wikiPageRedirects
dbpedia-hu:Feszített_út
Subject Item
dbpedia-hu:Feszítettút-szám
dbo:wikiPageRedirects
dbpedia-hu:Feszített_út
Subject Item
dbpedia-hu:Útfedési_szám
dbo:wikiPageRedirects
dbpedia-hu:Feszített_út
Subject Item
wikipedia-hu:Feszített_út
foaf:primaryTopic
dbpedia-hu:Feszített_út
Subject Item
dbpedia-hu:Detour-szám
dbo:wikiPageRedirects
dbpedia-hu:Feszített_út