|
|
|
Revision difference : distance (in a graph) |
| Version 7 |
Version 6 |
| The \emph{distance} $d(x,y)$ of two vertices $x$ and $y$ of a graph $G$ is the length of the shortest path (or, equivalently, walk) from $x$ to $y$. If there is no path from $x$ to $y$ (i.e. if they lie in different components of G), we set $d(x,y) := \infty.$ |
The \emph{distance} $d(x,y)$ of two vertices $x$ and $y$ of a graph $G$ is the length of the shortest path (or, equivalently, walk) from $x$ to $y$. If there is no path from $x$ to $y$ (i.e. if they lie in different components of G), we set $d(x,y) := \infty.$ |
|
|
| Two basic graph invariants involving distance are the \emph{diameter} $\diam G := \max_{(x,y)\in V(G)^2} d(x,y)$ (the maximum distance between two vertices of $G$) and the \emph{radius} $\rad G := \min_{x\in V(G)} \max_{y\in V(G)} d(x,y)$ (the maximum distance of a vertex from a \emph{central} vertex of $G$, i.e. a vertex such that the maximum distance to another vertex is minimal). |
Two basic graph invariants involving distance are the \emph{diameter} $\diam G := \max_{(x,y)\in V(G)^2} d(x,y)$ (the maximum distance between two vertices of $G$) and the \emph{radius} $\rad G := \min_{x\in V(G)} \max_{y\in V(G)} d(x,y)$ (the maximum distance of a vertex from a \emph{central} vertex of $G$, i.e. a vertex such that the maximum distance to another vertex is minimal). |
|
|
|
|
