Flashcards

Untitled

Josh Kamps English 9 cards

Cards in this deck (9)

1A connected graph G with n vertices and n-1 edges is a:Tree
2A connected graph G is a tree iff ?every edge is a cut edge
3What does this imply? In a simple graph G, ∀u,v ∈ V(G) : ∃!(u,v)-path.That G is a tree
4What is clustering in a graph?It is the extent to which your neighbours are connected to each other.
i.e. How many of your neighbours are each others neighbours.
5What is centrality?The notion of some vertices being more important than others.
6What is the eccentricity of a vertex?The length of the maximal shortest path between u and v.
max{d(u,v) | v ∈ V(G)}
7What is the radius of a graph?The minimal eccentricity.
The smallest of all the maximal shortest paths.
min{ε(u) | u ∈ V(G)}
8What is the diameter of a graph?The maximal eccentricity.
The maximum shortest distance between any pair of nodes.
max{d(u,v) | u,v ∈ V(G)}
9What is _ d(u) ?The average length of the shortest paths from u to v.
The sum of all the shortest paths from u, divided by the number of vertices. (except u)