Tuesday, January 30, 2018

Subgraphs of connected graphs

Given a connected graph as well a subset of the vertices of the connected graph, we can form a subgraph of the connected graph containing only the vertices in that subset. This subgraph need not be connected itself, or even non empty as it could consist of disconnected points. The interesting property of the subgraph then is actually its metric rather then its adjacency relation. We can form a metric on the subgraph by determining the distance between each point in the parent graph based upon the shortest path metric.

No comments:

Post a Comment