| Property |
Value |
| 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. (hu)
- 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. (hu)
|
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 11891 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| prop-hu:author1Link
|
- Jaroslav Nešetřil (hu)
- Michael Garey (hu)
- Jaroslav Nešetřil (hu)
- Michael Garey (hu)
|
| prop-hu:author2Link
|
- David S. Johnson (hu)
- Patrice Ossona de Mendez (hu)
- David S. Johnson (hu)
- Patrice Ossona de Mendez (hu)
|
| prop-hu:contribution
|
- Chapter 6. Bounded height trees and tree-depth (hu)
- Chapter 6. Bounded height trees and tree-depth (hu)
|
| prop-hu:doi
| |
| prop-hu:first
|
- Jaroslav (hu)
- David S. (hu)
- Michael R. (hu)
- Patrice (hu)
- Jaroslav (hu)
- David S. (hu)
- Michael R. (hu)
- Patrice (hu)
|
| prop-hu:isbn
| |
| prop-hu:last
|
- Johnson (hu)
- Garey (hu)
- Nešetřil (hu)
- Ossona de Mendez (hu)
- Johnson (hu)
- Garey (hu)
- Nešetřil (hu)
- Ossona de Mendez (hu)
|
| prop-hu:location
|
- Heidelberg (hu)
- Heidelberg (hu)
|
| prop-hu:mr
| |
| prop-hu:page
| |
| prop-hu:pages
| |
| prop-hu:publisher
|
- Springer (hu)
- W. H. Freeman (hu)
- Springer (hu)
- W. H. Freeman (hu)
|
| prop-hu:ref
| |
| prop-hu:series
|
- Algorithms and Combinatorics (hu)
- Algorithms and Combinatorics (hu)
|
| prop-hu:title
|
- Computers and Intractability: A Guide to the Theory of NP-Completeness. (hu)
- Sparsity: Graphs, Structures, and Algorithms (hu)
- Computers and Intractability: A Guide to the Theory of NP-Completeness. (hu)
- Sparsity: Graphs, Structures, and Algorithms (hu)
|
| prop-hu:url
| |
| prop-hu:volume
| |
| prop-hu:wikiPageUsesTemplate
| |
| prop-hu:year
|
- 1979 (xsd:integer)
- 2012 (xsd:integer)
|
| dct:subject
| |
| rdfs:label
|
- Feszített út (hu)
- Feszített út (hu)
|
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageRedirects
of | |
| is foaf:primaryTopic
of | |
