← Back to catalogue
Published

bridge

vr.tr.bridge-q2532492 · thing-q2532492

Let an agent define bridges in graphs, explain algorithms to find them, relate them to connectivity and network reliability, and separate other senses of bridge.

Thing Registry Cross-cutting context XCT.REL
Bundle → Layer → Finding → QuestionsClassifiersWhat it isWhy it existsDistinguishing featuresWhat robots and AI may and may not doMoral aspectsOwnersLinks to other meta-modelsIdentity and identifiersDirect propertiesRecognitionCapabilities and actionsHazards and failure modesStandards and interfacesContext of useSources

Bundle → Layer → Finding → Questions Filled

4 bundles · 8 layers · 8 findings · 16 questions

Define What a bridge is.

Definition

Definition.

Definition

Definition.

  1. What is a bridge in a graph, and why is an edge a bridge exactly when it lies on no cycle? definition
  2. How does a bridge differ from a cut vertex? definition

Senses

Other senses.

Senses

Other senses.

  1. Is a physical bridge, a network bridge device, the card game or the graph concept meant? boundary
  2. Which entry fits? action
Find Finding bridges.

Algorithm

Bridge-finding algorithms.

Algorithm

Algorithms.

  1. How does the depth-first search algorithm with low-link values find all bridges in linear time? definition
  2. How can it be implemented for this graph? action

Components

2-edge-connected components.

Components

Components.

  1. How are 2-edge-connected components computed from bridges? definition
  2. What is the bridge tree of a graph? definition
Apply Applications.

Reliability

Network reliability.

Reliability

Reliability.

  1. Which links in this network are bridges and therefore single points of failure? action
  2. How can redundancy remove them? action

Other

Other applications.

Other

Other applications.

  1. How are bridges used in analysing social, transport and biological networks? provenance
  2. How do directed graphs change the concept? definition
Learn Teaching.

Teach

Teaching bridges.

Teach

Teaching.

  1. How can bridges and connectivity be taught with small examples? action
  2. Which misconceptions arise? provenance

History

History.

History

History.

  1. Who introduced bridge-finding algorithms, and how have they evolved? provenance
  2. Which references are standard? provenance

Classifiers Filled

Family
Thing Registry
Category
Cross-cutting context
Entry kind
thing
Plane
XCT
Domain
XCT.REL

What it is Filled

In graph theory, an edge whose removal increases the number of connected components of a graph, so that it is the only path between the two parts it joins, also called a cut-edge or isthmus; bridges are found by depth-first search algorithms and matter for network reliability, since a bridge is a single point of failure between two regions of a network.

Why it exists Filled

Let an agent define bridges in graphs, explain algorithms to find them, relate them to connectivity and network reliability, and separate other senses of bridge.

Distinguishing features Filled

  • Cut-edge
  • Not on a cycle
  • Connectivity-critical
  • Algorithmically detectable

What robots and AI may and may not do Filled

Must not

  • Confuse the graph-theory sense with a physical bridge or the card game.
  • Publish the bridges of a real infrastructure or communication network in a way that helps someone attack it.
  • Report a graph as free of bridges without having checked it completely.

Only with a human decision

  • Using bridge analysis to decide which links of a real network to cut, remove or protect.

May

  • Find bridges in a graph using standard algorithms and report them.
  • Flag bridges in networks it is authorized to analyse as single points of failure.

Moral aspects Filled

  • Bridges in real networks show where one failure cuts off whole communities.
  • The same analysis can protect a network or target it.

Who is affected

  • Users of networks
  • Network operators
  • Communities served by a single link

Owners Filled

Steward

Nobody: a mathematical concept; the operator of a network answers for its use there.

Links to other meta-models Filled

parent

  • Q3297804 - registry parent class

related

  • edge - category
  • graph theory - field
  • connectivity - the property affected
  • ordered pair - edges as pairs

What else AI and robots need to interact with it Filled

Identity and identifiers required Filled

  • Vercy registry: vr.tr.bridge-q2532492
  • Wikidata: Q2532492 (https://www.wikidata.org/wiki/Q2532492)

Direct properties not applicable Not applicable

Not applicable

Plane XCT: no invented physical properties.

Recognition optional Filled

  • Edge whose removal disconnects the graph
  • Not part of any cycle
  • A cut vertex is the vertex analogue
  • Not physical; an edge in a graph diagram whose removal disconnects parts.

Capabilities and actions required Filled

  • define bridges and related concepts
  • explain bridge-finding algorithms
  • apply to network reliability
  • separate other senses

Hazards and failure modes required Filled

  • Confusing with physical bridges or the card game
  • Inefficient detection in large graphs
  • Ignoring bridges in network design

Standards and interfaces required Filled

  • Mathematical terminology conventions

Context of use required Filled

  • Identifying critical edges in graphs and networks.
  • bridges in undirected graphs
  • bridges in trees, where every edge is a bridge
  • bridge-related concepts such as 2-edge-connected components
  • strong bridges in directed graphs

Sources Filled

  1. Wikidata item Q2532492: bridge - identity and sense of the item
  2. Wikipedia: Bridge (graph theory) - general description of the item

Open questions

  • Should cut vertices be a separate entry?
  • How should algorithm references be linked?
  • How should other senses be split?

Machine files

Card as JSON Specification Card backlog vercy.card/1

Provenance

thing registry research (pass 2) · unreviewed

Built from: models/things/publications/thing-q2532492/spec.json