Metraipolis › archive › dc_135e8a069308

Tutte path — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Tutte_path
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T17:40:08.153Z
SHA-256 of the archived text
fc917e43363c9fe2e0f5fc9c8fbe85ef0ff414bf8f93e13eca8deb66a7397d35
Stable URL of this page
https://metraipolis.com/documento/dc_135e8a069308

How to cite

Tutte path — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Tutte_path (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_135e8a069308 (Metraipolis archive dc_135e8a069308, sha256 fc917e43363c9fe2e0f5fc9c8fbe85ef0ff414bf8f93e13eca8deb66a7397d35)
BibTeX
@misc{dc135e8a069308,
  title = {Tutte path — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Tutte_path},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_135e8a069308; sha256 fc917e43363c9fe2e0f5fc9c8fbe85ef0ff414bf8f93e13eca8deb66a7397d35},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Tutte_path. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In graph theory, a Tutte path is a path P {\displaystyle P} within a graph G {\displaystyle G} such that every connected component that remains after removing the vertices of P {\displaystyle P} from G {\displaystyle G} is connected back to P {\displaystyle P} at a limited number of vertices. The precise definition relies on the following terms: P {\displaystyle P} -bridge: For a given path P {\displaystyle P} in a graph G {\displaystyle G} , a P {\displaystyle P} -bridge is either a single edge not in P {\displaystyle P} that connects two vertices of P {\displaystyle P} , or it is a connected component of the graph remaining after deleting the vertices of P {\displaystyle P} , along with all the edges that connect this component to P {\displaystyle P} . Attachment point: The attachment points of a P {\displaystyle P} -bridge are the vertices of the path P {\displaystyle P} that are connected by an edge to a vertex within the P {\displaystyle P} -bridge. A Tutte path then is a path P {\displaystyle P} in G {\displaystyle G} such that every P {\displaystyle P} -bridge that remains after removing the vertices of P {\displaystyle P} from G {\displaystyle G} has at most three points of attachment to the path P {\displaystyle P} . Furthermore, if a P {\displaystyle P} -bridge contains edges from the outer face of the graph (in the context of planar graphs), it is restricted to having at most two attachment points.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Graph theory»).
Fonte: Wikipedia in inglese, voce «Tutte path» — https://en.wikipedia.org/wiki/Tutte_path
Wikidata Q135688778 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q135688778
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Tutte_path?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1354665512, consultata il 2026-10-15T16:35:27.852Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 561408ca5cbe83689ff26124a455bf325bf4d5d96a79f2690bc174a4c39a3ea4